Deterministic Encoding and Hashing to Odd Hyperelliptic Curves

Pierre-Alain Fouque (1, 2, 3) , Mehdi Tibouchi (3)

1 LIENS - Laboratoire d'informatique de l'école normale supérieure
2 CASCADE - Construction and Analysis of Systems for Confidentiality and Authenticity of Data and Entities
3 ENS-PSL - École normale supérieure - Paris

In this paper we propose a very simple and efficient encoding function from Fq to points of a hyperelliptic curve over Fq of the form H : y2 = 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 Fq -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 (Fq ) 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.

Domaines: Cryptographie et sécurité [cs.CR]

Pierre-Alain Fouque, Mehdi Tibouchi. Deterministic Encoding and Hashing to Odd Hyperelliptic Curves. Pairing-Based Cryptography - Pairing 2010 - 4th International Conference, 2010, Yamanaka Hot Spring, Japan. pp.265-277, ⟨10.1007/978-3-642-17455-1_17⟩. ⟨inria-00556678⟩