Cryptology ePrint Archive: Report 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 $\mathbb{F}$ and an elliptic curve $\mathcal{E}$ over $\mathbb{F}$. There are two such maps, called $\phi$ in the ``Elligator 1'' system, and $\psi$ in the ``Elligator 2'' system.

Here we show two ways to construct hash functions from $\psi$ which are indifferentiable from a random oracle. Because $\psi$ 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.

Category / Keywords: public-key cryptography / Indifferentiability, hashing to elliptic curves, Elligator

Date: received 2 Dec 2020, last revised 2 Dec 2020

Contact author: mike at shiftleft org

Available format(s): PDF | BibTeX Citation

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

Version: 20201202:150737 (All versions of this report)

Short URL: ia.cr/2020/1513