Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS

   
Mobile Device Pairing
Green Open Access
Mathematics of Computation
Mathematics of Computation
ISSN 1088-6842(online) ISSN 0025-5718(print)

 

Indifferentiable deterministic hashing to elliptic and hyperelliptic curves


Authors: Reza R. Farashahi, Pierre-Alain Fouque, Igor E. Shparlinski, Mehdi Tibouchi and J. Felipe Voloch
Journal: Math. Comp. 82 (2013), 491-512
MSC (2010): Primary 11T23, 11T71, 14G50
Published electronically: April 24, 2012
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 essentially 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 any of the known deterministic encodings 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.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 11T23, 11T71, 14G50

Retrieve articles in all journals with MSC (2010): 11T23, 11T71, 14G50


Additional Information

Reza R. Farashahi
Affiliation: Macquarie University, Department of Computing, North Ryde, Sydney, NSW 2109, Australia— and — Isfahan University of Technology, Department of Mathematical Sciences, P.O. Box 85145 Isfahan, Iran
Email: reza.farashahi@mq.edu.au

Pierre-Alain Fouque
Affiliation: École normale supérieure, Département d’informatique, Équipe de cryptographie, 45 rue d’Ulm, f-75230 Paris Cedex 05, France
Email: pierre-alain.fouque@ens.fr

Igor E. Shparlinski
Affiliation: Macquarie University, Department of Computing, North Ryde, Sydney, NSW 2109, Australia
Email: igor.shparlinski@mq.edu.au

Mehdi Tibouchi
Affiliation: École normale supérieure, Département d’informatique, Équipe de cryptographie, 45 rue d’Ulm, f-75230 Paris Cedex 05, France
Address at time of publication: NTT Information Sharing Platform Labs, 3-9-11 Midori-cho, Musashino-shi Tokyo, 180-8585, Japan
Email: tibouchi.mehdi@lab.ntt.co.jp

J. Felipe Voloch
Affiliation: University of Texas, Department of Mathematics, Austin, Texas 78712
Email: voloch@math.utexas.edu

DOI: http://dx.doi.org/10.1090/S0025-5718-2012-02606-8
PII: S 0025-5718(2012)02606-8
Keywords: Elliptic curve cryptography, hashing, random oracle model, exponential sums, pseudorandomness
Received by editor(s): February 4, 2011
Received by editor(s) in revised form: August 8, 2011
Published electronically: April 24, 2012
Article copyright: © Copyright 2012 American Mathematical Society