Paper 2022/759
SwiftEC: Shallue–van de Woestijne Indifferentiable Function To Elliptic Curves
Abstract
Hashing arbitrary values to points on an elliptic curve is a required step in many cryptographic constructions, and a number of techniques have been proposed to do so over the years. One of the first ones was due to Shallue and van de Woestijne (ANTSVII), and it had the interesting property of applying 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\colon \mathbb{F}_q\to E(\mathbb{F}_q)$ is the Shalluevan 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 has the drawback of being twice as expensive to compute than the straightforward, but not indifferentiable, $m\mapsto f\big(\mathfrak{h}_1(m)\big)$. Most other solutions so far have had the same issue: they are at least as costly as two base field exponentiations, whereas plain encoding maps like $f$ cost only one exponentiation. Recently, Koshelev (DCC 2022) provided the first construction of indifferentiable hashing at the cost of one exponentiation, but only for a very specific class of curves (some of those with $j$invariant $0$), and using techniques that are unlikely to apply more broadly. In this work, we revisit this longstanding open problem, and observe that the SW map actually fits in a oneparameter 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$, $F\colon m\mapsto f_{\mathfrak{h}_2(m)}\big(\mathfrak{h}_1(m)\big)$ is indifferentiable. Moreover, on a very large class of curves (essentially those that are either of odd order or of order divisible by 4), the oneparameter family admits a rational parametrization, which let us compute $F$ at almost the same cost as small $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 closetouniform random strings.
Note: v2:  Addressing special cases for curves with a=0  Corrected errors in the formulas of Algorithm 2
Metadata
 Available format(s)
 Category
 Publickey cryptography
 Publication info
 Preprint.
 Keywords
 Elliptic curve cryptography Hashing to curves Indifferentiability Elligator Algebraic geometry
 Contact author(s)

jorgechavezsaab @ gmail com
Francisco Rodriguez @ tii ae
mehdi tibouchi @ normalesup org  History
 20220621: revised
 20220614: received
 See all versions
 Short URL
 https://ia.cr/2022/759
 License

CC BY
BibTeX
@misc{cryptoeprint:2022/759, author = {Jorge ChávezSaab and Francisco Rodrı́guezHenrı́quez and Mehdi Tibouchi}, title = {SwiftEC: Shallue–van de Woestijne Indifferentiable Function To Elliptic Curves}, howpublished = {Cryptology ePrint Archive, Paper 2022/759}, year = {2022}, note = {\url{https://eprint.iacr.org/2022/759}}, url = {https://eprint.iacr.org/2022/759} }