Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

Request Permissions   Purchase Content 
 

 

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
MathSciNet review: 2983033
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?)

  • 1. Joonsang Baek and Yuliang Zheng, Identity-based threshold decryption, Public key cryptography—PKC 2004, Lecture Notes in Comput. Sci., vol. 2947, Springer, Berlin, 2004, pp. 262–276. MR 2095652, 10.1007/978-3-540-24632-9_19
  • 2. Paulo S. L. M. Barreto and Michael Naehrig, Pairing-friendly elliptic curves of prime order, Selected areas in cryptography, Lecture Notes in Comput. Sci., vol. 3897, Springer, Berlin, 2006, pp. 319–331. MR 2241646, 10.1007/11693383_22
  • 3. Alexandra Boldyreva, Threshold signatures, multisignatures and blind signatures based on the gap-Diffie-Hellman-group signature scheme, Public key cryptography—PKC 2003, Lecture Notes in Comput. Sci., vol. 2567, Springer, Berlin, 2002, pp. 31–46. MR 2171915, 10.1007/3-540-36288-6_3
  • 4. Enrico Bombieri, On exponential sums in finite fields, Les Tendances Géom. en Algèbre et Théorie des Nombres, Éditions du Centre National de la Recherche Scientifique, Paris, 1966, pp. 37–41 (English, with French summary). MR 0204413
  • 5. Dan Boneh and Matt Franklin, Identity-based encryption from the Weil pairing, Advances in cryptology—CRYPTO 2001 (Santa Barbara, CA), Lecture Notes in Comput. Sci., vol. 2139, Springer, Berlin, 2001, pp. 213–229. MR 1931424, 10.1007/3-540-44647-8_13
  • 6. Dan Boneh, Craig Gentry, Ben Lynn, and Hovav Shacham, Aggregate and verifiably encrypted signatures from bilinear maps, Advances in cryptology—EUROCRYPT 2003, Lecture Notes in Comput. Sci., vol. 2656, Springer, Berlin, 2003, pp. 416–432. MR 2090433, 10.1007/3-540-39200-9_26
  • 7. Dan Boneh, Ben Lynn, and Hovav Shacham, Short signatures from the Weil pairing, Advances in cryptology—ASIACRYPT 2001 (Gold Coast), Lecture Notes in Comput. Sci., vol. 2248, Springer, Berlin, 2001, pp. 514–532. MR 1934861, 10.1007/3-540-45682-1_30
  • 8. C. Boyd, P. Montague and K.Q. Nguyen.
    Elliptic Curve Based Password Authenticated Key Exchange Protocols.
    In ACISP 2001, volume 2119 of Lecture Notes in Computer Science, pages 487-501. Springer, 2001.
  • 9. Xavier Boyen, Multipurpose identity-based signcryption: a Swiss Army knife for identity-based cryptography, Advances in cryptology—CRYPTO 2003, Lecture Notes in Comput. Sci., vol. 2729, Springer, Berlin, 2003, pp. 383–399. MR 2093205, 10.1007/978-3-540-45146-4_23
  • 10. E. Brier, J.-S. Coron, T. Icart, D. Madore, H. Randriam, and M. Tibouchi.
    Efficient indifferentiable hashing into ordinary elliptic curves.
    In T. Rabin, editor, CRYPTO, volume 6223 of Lecture Notes in Computer Science, pages 237-254. Springer, 2010.
  • 11. Jae Choon Cha and Jung Hee Cheon, An identity-based signature from gap Diffie-Hellman groups, Public key cryptography—PKC 2003, Lecture Notes in Comput. Sci., vol. 2567, Springer, Berlin, 2002, pp. 18–30. MR 2171914, 10.1007/3-540-36288-6_2
  • 12. H. Chabanne and M. Tibouchi.
    Securing e-passports with elliptic curves.
    IEEE Security & Privacy, 9(2):75-78, 2011.
  • 13. J.-M. Couveignes and J.-G. Kammerer.
    The geometry of flex tangents to a cubic curve and its parameterizations.
    Cryptology ePrint Archive, Report 2011/033, 2011.
    http://eprint.iacr.org/.
  • 14. Michael Drmota and Robert F. Tichy, Sequences, discrepancies and applications, Lecture Notes in Mathematics, vol. 1651, Springer-Verlag, Berlin, 1997. MR 1470456
  • 15. R. R. Farashahi.
    Hashing into Hessian curves.
    In A. Nitaj and D. Pointcheval, editors, AFRICACRYPT, volume 6737 of Lecture Notes in Computer Science, pages 278-289. Springer, 2011.
  • 16. Reza R. Farashahi, Igor E. Shparlinski, and José Felipe Voloch, On hashing into elliptic curves, J. Math. Cryptol. 3 (2009), no. 4, 353–360. MR 2608601, 10.1515/JMC.2009.022
  • 17. P.-A. Fouque and M. Tibouchi.
    Deterministic encoding and hashing to odd hyperelliptic curves.
    In M. Joye, A. Miyaji and A. Otsuka, editors, Pairing 2010, volume 6487 of Lecture Notes in Computer Science, pages 265-277. Springer, 2010.
  • 18. P.-A. Fouque and M. Tibouchi.
    Estimating the size of the image of deterministic hash functions to elliptic curves.
    In M. Abdalla and P. Baretto, editors, LATINCRYPT, volume 6212 of Lecture Notes in Computer Science, pages 81-91. Springer, 2010.
  • 19. Craig Gentry and Alice Silverberg, Hierarchical ID-based cryptography, Advances in cryptology—ASIACRYPT 2002, Lecture Notes in Comput. Sci., vol. 2501, Springer, Berlin, 2002, pp. 548–566. MR 2087407, 10.1007/3-540-36178-2_34
  • 20. Jeremy Horwitz and Ben Lynn, Toward hierarchical identity-based encryption, Advances in cryptology—EUROCRYPT 2002 (Amsterdam), Lecture Notes in Comput. Sci., vol. 2332, Springer, Berlin, 2002, pp. 466–481. MR 1975549, 10.1007/3-540-46035-7_31
  • 21. Thomas Icart, How to hash into elliptic curves, Advances in cryptology—CRYPTO 2009, Lecture Notes in Comput. Sci., vol. 5677, Springer, Berlin, 2009, pp. 303–316. MR 2556964, 10.1007/978-3-642-03356-8_18
  • 22. Henryk Iwaniec and Emmanuel Kowalski, Analytic number theory, American Mathematical Society Colloquium Publications, vol. 53, American Mathematical Society, Providence, RI, 2004. MR 2061214
  • 23. J.-G. Kammerer, R. Lercier, and G. Renault.
    Encoding points on hyperelliptic curves over finite fields in deterministic polynomial time.
    In M. Joye, A. Miyaji and A. Otsuka, editors, Pairing 2010, volume 6487 of Lecture Notes in Computer Science, pages 278-297. Springer, 2010.
  • 24. David R. Kohel and Igor E. Shparlinski, On exponential sums and group generators for elliptic curves over finite fields, Algorithmic number theory (Leiden, 2000) Lecture Notes in Comput. Sci., vol. 1838, Springer, Berlin, 2000, pp. 395–404. MR 1850620, 10.1007/10722028_24
  • 25. Benoît Libert and Jean-Jacques Quisquater, Efficient signcryption with key privacy from gap Diffie-Hellman groups, Public key cryptography—PKC 2004, Lecture Notes in Comput. Sci., vol. 2947, Springer, Berlin, 2004, pp. 187–200. MR 2095647, 10.1007/978-3-540-24632-9_14
  • 26. Rudolf Lidl and Harald Niederreiter, Finite fields, 2nd ed., Encyclopedia of Mathematics and its Applications, vol. 20, Cambridge University Press, Cambridge, 1997. With a foreword by P. M. Cohn. MR 1429394
  • 27. Ueli Maurer, Renato Renner, and Clemens Holenstein, Indifferentiability, impossibility results on reductions, and applications to the random oracle methodology, Theory of cryptography, Lecture Notes in Comput. Sci., vol. 2951, Springer, Berlin, 2004, pp. 21–39. MR 2146712, 10.1007/978-3-540-24638-1_2
  • 28. T. Ristenpart, H. Shacham, and T. Shrimpton.
    Careful with composition: Limitations of the indifferentiability framework.
    In K. G. Paterson, editor, EUROCRYPT, volume 6632 of Lecture Notes in Computer Science, pages 487-506. Springer, 2011.
  • 29. Michael Rosen, Number theory in function fields, Graduate Texts in Mathematics, vol. 210, Springer-Verlag, New York, 2002. MR 1876657
  • 30. Andrew Shallue and Christiaan E. van de Woestijne, Construction of rational points on elliptic curves over finite fields, Algorithmic number theory, Lecture Notes in Comput. Sci., vol. 4076, Springer, Berlin, 2006, pp. 510–524. MR 2282946, 10.1007/11792086_36
  • 31. M. Skałba, Points on elliptic curves over finite fields, Acta Arith. 117 (2005), no. 3, 293–301. MR 2139009, 10.4064/aa117-3-7
  • 32. Maciej Ulas, Rational points on certain hyperelliptic curves over finite fields, Bull. Pol. Acad. Sci. Math. 55 (2007), no. 2, 97–104. MR 2318631, 10.4064/ba55-2-1
  • 33. André Weil, Basic number theory, Classics in Mathematics, Springer-Verlag, Berlin, 1995. Reprint of the second (1973) edition. MR 1344916
  • 34. Fangguo Zhang and Kwangjo Kim, ID-based blind signature and ring signature from pairings, Advances in cryptology—ASIACRYPT 2002, Lecture Notes in Comput. Sci., vol. 2501, Springer, Berlin, 2002, pp. 533–547. MR 2087406, 10.1007/3-540-36178-2_33

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: https://doi.org/10.1090/S0025-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