Paper 2010/382

Deterministic Encoding and Hashing to Odd Hyperelliptic Curves

Pierre-Alain Fouque and Mehdi Tibouchi


In this paper we propose a very simple and efficient encoding function from F_q to points of a hyperelliptic curve over F_q of the form H: y^2=f(x) where f is an odd polynomial. Hyperelliptic curves of this type have been frequently considered in the literature to obtain Jacobians of good order and pairing-friendly curves. Our new encoding is nearly a bijection to the set of F_q-rational points on H. This makes it easy to construct well-behaved hash functions to the Jacobian J of H, as well as injective maps to J(F_q) which can be used to encode scalars for such applications as ElGamal encryption. The new encoding is already interesting in the genus 1 case, where it provides a well-behaved encoding to Joux's supersingular elliptic curves.

Note: (Fixed a typo in the definition of an "odd" hyperelliptic curve).

Available format(s)
Public-key cryptography
Publication info
Published elsewhere. Pairing 2010
Hyperelliptic Curve CryptographyDeterministic EncodingHashing
Contact author(s)
mehdi tibouchi @ normalesup org
2010-09-11: last of 4 revisions
2010-07-07: received
See all versions
Short URL
Creative Commons Attribution


      author = {Pierre-Alain Fouque and Mehdi Tibouchi},
      title = {Deterministic Encoding and Hashing to Odd Hyperelliptic Curves},
      howpublished = {Cryptology ePrint Archive, Paper 2010/382},
      year = {2010},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.