Hashing arbitrary values to points on an elliptic curve is a required step in many cryptographic constructions. One of the first techniques was due to Shallue and van de Woestijne (ANTS-VII), and applied to essentially all elliptic curves over finite fields. It did not, however, have the desirable property of being indifferentiable from a random oracle when composed with a random oracle to the base field. Various approaches have since been considered to overcome this limitation, starting with the foundational work of Brier et al. (CRYPTO 2011). For example, if \(f:{\mathbb {F}}_{q}\rightarrow E({\mathbb {F}}_{q})\) is the Shallue–van de Woestijne (SW) map and \(\mathfrak {h}_1,\mathfrak {h}_2\) are two independent random oracles to \({\mathbb {F}}_{q}\) , we now know that \(m\mapsto f\big (\mathfrak {h}_1(m)\big )+f\big (\mathfrak {h}_2(m)\big )\) is indifferentiable from a random oracle. Unfortunately, this approach, as well as most other solutions studied so far, has the drawback of requiring two field exponentiations, whereas the original (but nonindifferentiable) encoding requires only one. We revisit this long-standing open problem and observe that the SW map fits in a one-parameter family \((f_u)_{u\in {\mathbb {F}}_{q}}\) of encodings, such that for independent random oracles \(\mathfrak {h}_1, \mathfrak {h}_2\) to \({\mathbb {F}}_{q}\) , \(m\mapsto f_{\mathfrak {h}_2(m)}\big (\mathfrak {h}_1(m)\big )\) is indifferentiable. Moreover, on a very large class of curves, the one-parameter family admits a rational parametrization, which lets us compute the mapping at almost the same cost as f and finally achieve indifferentiable hashing to most curves with a single exponentiation. Our new approach also yields an improved variant of the Elligator Squared technique of Tibouchi (FC 2014) that represents points of arbitrary elliptic curves as close-to-uniform random strings.
