Welcome to the resource topic for 2022/759
Title:
SwiftEC: Shallue–van de Woestijne Indifferentiable Function To Elliptic Curves
Authors: Jorge Chávez-Saab, Francisco Rodrı́guez-Henrı́quez, and Mehdi Tibouchi
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.
ePrint: https://eprint.iacr.org/2022/759
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .