Estimating the Size of the Image of Deterministic Hash Functions to Elliptic 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

Let E be a non-supersingular elliptic curve over a finite field Fq . At CRYPTO 2009, Icart introduced a deterministic function from Fq to E(Fq ) which can be computed efficiently, and allowed him and Coron to define well-behaved hash functions with values in E(Fq ). Some properties of this function rely on a conjecture which was left as an open problem in Icart?s paper. We prove this conjecture below as well as analogues for other hash functions.

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

Pierre-Alain Fouque, Mehdi Tibouchi. Estimating the Size of the Image of Deterministic Hash Functions to Elliptic Curves. Progress in Cryptology - LATINCRYPT 2010, First International Conference on Cryptology and Information Security in Latin America, 2010, Puebla, Mexico. pp.81-91, ⟨10.1007/978-3-642-14712-8⟩. ⟨inria-00556676⟩