Efficient Indifferentiable Hashing into Ordinary Elliptic Curves

Eric Brier; Jean-Sebastien Coron; Thomas Icart; David Madore; Hugues Randriam; Mehdi Tibouchi

Paper 2009/340

Efficient Indifferentiable Hashing into Ordinary Elliptic Curves

Eric Brier, Jean-Sebastien Coron, Thomas Icart, David Madore, Hugues Randriam, and Mehdi Tibouchi

Abstract

We provide the first construction of a hash function into ordinary elliptic curves that is indifferentiable from a random oracle, based on Icart's deterministic encoding from Crypto 2009. While almost as efficient as Icart's encoding, this 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. We also describe a more general (but less efficient) construction that works for a large class of encodings into elliptic curves, for example the Shallue-Woestijne-Ulas (SWU) algorithm. Finally we describe the first deterministic encoding algorithm into elliptic curves in characteristic 3.

Note: Added: - proof of indifferentiability for f(h1(m))+f(h2(m)) - hash algorithms in characteristic 3

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Published elsewhere. An extended abstract will appear at CRYPTO 2010. This is the full version.
Keywords: Random Oracle Model Elliptic Curve Cryptography
Contact author(s): jscoron @ gmail com
History: 2014-06-03: last of 3 revisions; 2009-07-13: received; See all versions
Short URL: https://ia.cr/2009/340
License: CC BY

BibTeX

@misc{cryptoeprint:2009/340,
      author = {Eric Brier and Jean-Sebastien Coron and Thomas Icart and David Madore and Hugues Randriam and Mehdi Tibouchi},
      title = {Efficient Indifferentiable Hashing into Ordinary Elliptic Curves},
      howpublished = {Cryptology {ePrint} Archive, Paper 2009/340},
      year = {2009},
      url = {https://eprint.iacr.org/2009/340}
}