Note that this is a rough draft, written in 2013. I posted it in December 2020 because it's relevant to a CFRG discussion.
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 𝔽 and an elliptic curve E over 𝔽. 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.