In this paper, we present a new, simpler technique based on bounds of character sums to prove the indifferentiability of similar hash function constructions based on essentially any deterministic encoding to elliptic curves or curves of higher genus, such as the algorithms by Shallue, van de Woestijne and Ulas, or the Icart-like encodings recently presented by Kammerer, Lercier and Renault. In particular, we get the first constructions of well-behaved hash functions to Jacobians of hyperelliptic curves.
Our technique also provides more precise estimates on the statistical behavior of those deterministic encodings and the hash function constructions based on them. Additionally, we can derive pseudorandomness results for partial bit patterns of such encodings.
Category / Keywords: public-key cryptography / Elliptic Curve Cryptography, Hashing, Random Oracle Model, Exponential Sums, Pseudorandomness Date: received 21 Oct 2010 Contact author: mehdi tibouchi at normalesup org Available formats: PDF | BibTeX Citation Version: 20101025:150950 (All versions of this report) Discussion forum: Show discussion | Start new discussion