Injective Encodings to Elliptic Curves

Abstract : For a number of elliptic curve-based cryptographic protocols, it is useful and sometimes necessary to be able to encode a message (a bit string) as a point on an elliptic curve in such a way that the message can be efficiently and uniquely recovered from the point. This is for exam-ple the case if one wants to instantiate CPA-secure ElGamal encryption directly in the group of points of an elliptic curve. More practically rele-vant settings include Lindell's UC commitment scheme (EUROCRYPT 2011) or structure-preserving primitives. It turns out that constructing such an encoding function is not easy in general, especially if one wishes to encode points whose length is large rel-ative to the size of the curve. There is a probabilistic, "folklore" method for doing so, but it only provably works for messages of length less than half the size of the curve. In this paper, we investigate several approaches to injective encoding to elliptic curves, and in particular, we propose a new, essentially opti-mal geometric construction for a large class of curves, including Edwards curves; the resulting algorithm is also quite efficient, requiring only one exponentiation in the base field and simple arithmetic operations (how-ever, the curves for which the map can be constructed have a point of order two, which may be a limiting factor for possible applications). The new approach is based on the existence of a covering curve of genus 2 for which a bijective encoding is known.
Type de document :
Communication dans un congrès
Information Security and Privacy - 18th Australasian Conference, Jul 2013, Brisbane, Australia. Springer, LNCS 7959, pp.16, 2013, ACISP 2013. 〈10.1007/978-3-642-39059-3_14〉
Liste complète des métadonnées

Littérature citée [17 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01094294
Contributeur : Pierre-Alain Fouque <>
Soumis le : vendredi 12 décembre 2014 - 09:17:15
Dernière modification le : mercredi 29 novembre 2017 - 15:27:01
Document(s) archivé(s) le : vendredi 13 mars 2015 - 10:20:39

Fichier

FJT13.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Pierre-Alain Fouque, Antoine Joux, Mehdi Tibouchi. Injective Encodings to Elliptic Curves. Information Security and Privacy - 18th Australasian Conference, Jul 2013, Brisbane, Australia. Springer, LNCS 7959, pp.16, 2013, ACISP 2013. 〈10.1007/978-3-642-39059-3_14〉. 〈hal-01094294〉

Partager

Métriques

Consultations de la notice

39

Téléchargements de fichiers

95