Indifferentiable hashing from Elligator 2

Mike Hamburg

Paper 2020/1513

Indifferentiable hashing from Elligator 2

Mike Hamburg

Abstract

Bernstein et al. recently introduced a system ``Elligator'' for steganographic key distribution. At the heart of their construction are invertible maps between a finite field $F$ and an elliptic curve $E$ over $F$ . There are two such maps, called $ϕ$ in the ``Elligator 1'' system, and $ψ$ in the ``Elligator 2'' system. Here we show two ways to construct hash functions from $ψ$ which are indifferentiable from a random oracle. Because $ψ$ is relatively simple, our analyses are also simple. One of our constructions uses a novel ``wallpapering'' approach, whereas the other uses the hash-twice-and-add approach of Brier et al.

Note: I wrote this paper 2013, but I'm posting it in 2020 because it's relevant to the CFRG hash-to-curve discussion.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Preprint.
Keywords: Indifferentiability hashing to elliptic curves Elligator
Contact author(s): mike @ shiftleft org
History: 2020-12-02: received
Short URL: https://ia.cr/2020/1513
License: CC BY

BibTeX

@misc{cryptoeprint:2020/1513,
      author = {Mike Hamburg},
      title = {Indifferentiable hashing from Elligator 2},
      howpublished = {Cryptology {ePrint} Archive, Paper 2020/1513},
      year = {2020},
      url = {https://eprint.iacr.org/2020/1513}
}