### Indifferentiable Deterministic Hashing to Elliptic and Hyperelliptic Curves

Reza R. Farashahi, Pierre-Alain Fouque, Igor E. Shparlinski, Mehdi Tibouchi, and J. Felipe Voloch

##### Abstract

At Crypto 2010, Brier et al. proposed the first construction of a hash function into ordinary elliptic curves that was indifferentiable from a random oracle, based on Icart's deterministic encoding from Crypto 2009. Such a hash function can be plugged into any cryptosystem that requires hashing into elliptic curves, while not compromising proofs of security in the random oracle model. However, the proof relied on relatively involved tools from algebraic geometry, and only applied to Icart's deterministic encoding from Crypto 2009. 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.

Available format(s)
Category
Public-key cryptography
Publication info
Published elsewhere. Unknown where it was published
Keywords
Elliptic Curve CryptographyHashingRandom Oracle ModelExponential SumsPseudorandomness
Contact author(s)
mehdi tibouchi @ normalesup org
History
Short URL
https://ia.cr/2010/539

CC BY

BibTeX

@misc{cryptoeprint:2010/539,
author = {Reza R.  Farashahi and Pierre-Alain Fouque and Igor E.  Shparlinski and Mehdi Tibouchi and J.  Felipe Voloch},
title = {Indifferentiable Deterministic Hashing to Elliptic and Hyperelliptic Curves},
howpublished = {Cryptology ePrint Archive, Paper 2010/539},
year = {2010},
note = {\url{https://eprint.iacr.org/2010/539}},
url = {https://eprint.iacr.org/2010/539}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.