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 relative 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 optimal 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 (however, 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.
Category / Keywords: public-key cryptography / Elliptic Curve Cryptography, Injective Encoding, Algebraic Curves Publication Info: ACISP 2013 Date: received 10 Jun 2013 Contact author: mehdi tibouchi at normalesup org Available format(s): PDF | BibTeX Citation Version: 20130612:145055 (All versions of this report) Short URL: ia.cr/2013/373 Discussion forum: Show discussion | Start new discussion