Paper 2010/037

Estimating the Size of the Image of Deterministic Hash Functions to Elliptic Curves

Pierre-Alain Fouque and Mehdi Tibouchi


Let E be a non-supersingular elliptic curve over a finite field F_q. At CRYPTO 2009, Icart introduced a deterministic function F_q->E(F_q) which can be computed efficiently, and allowed him and Coron to define well-behaved hash functions with values in E(F_q). Some properties of this function rely on a conjecture which was left as an open problem in Icart's paper. We prove this conjecture as well as analogues for other hash functions. See also Farahashi, Shparlinski and Voloch, _On Hashing into Elliptic Curves_, for independent results of a similar form.

Note: Fixed an error in Prop. 4

Available format(s)
Public-key cryptography
Publication info
Published elsewhere. Latincrypt 2010
Elliptic CurvesFunction FieldsHash Functions
Contact author(s)
mehdi tibouchi @ ens fr
2010-08-04: last of 3 revisions
2010-01-26: received
See all versions
Short URL
Creative Commons Attribution


      author = {Pierre-Alain Fouque and Mehdi Tibouchi},
      title = {Estimating the Size of the Image of Deterministic Hash Functions to Elliptic Curves},
      howpublished = {Cryptology ePrint Archive, Paper 2010/037},
      year = {2010},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.