### 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 (ANTS-VII), 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 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 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 long-standing open problem, and observe that the SW map actually 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$, $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 one-parameter 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 close-to-uniform random strings.

Note: v2: - Addressing special cases for curves with a=0 - Corrected errors in the formulas of Algorithm 2

Available format(s)
Category
Public-key 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
2022-06-21: revised
See all versions
Short URL
https://ia.cr/2022/759

CC BY

BibTeX

@misc{cryptoeprint:2022/759,
author = {Jorge Chávez-Saab and Francisco Rodrı́guez-Henrı́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}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.