Estimating the size of the image of deterministic hash functions to elliptic curves

Abstract. Let E be a non-supersingular elliptic curve over a finite field Fq. At CRYPTO 2009, Icart introduced a deterministic function Fq → 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