Cryptology ePrint Archive: Report 2010/382

Deterministic Encoding and Hashing to Odd Hyperelliptic Curves

Pierre-Alain Fouque and Mehdi Tibouchi

Abstract: 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.

Category / Keywords: public-key cryptography / Hyperelliptic Curve Cryptography, Deterministic Encoding, Hashing

Publication Info: Pairing 2010

Date: received 6 Jul 2010, last revised 11 Sep 2010

Contact author: mehdi tibouchi at normalesup org

Available format(s): PDF | BibTeX Citation

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

Version: 20100911:173506 (All versions of this report)

Short URL: ia.cr/2010/382

Discussion forum: Show discussion | Start new discussion