CryptoDB
Francisco Rodríguez-Henríquez
Publications
Year
Venue
Title
2022
ASIACRYPT
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: F_q→E(F_q) is the Shallue--van de
Woestijne (SW) map and H, H' are *two* independent random oracles,
we now know that m↦f(H(m))+f(H'(m)) 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↦f(H(m)).
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∈F_q}
of encodings, such that for independent random oracles H, H',
F: m↦f_{H'(m)}(H(m)) 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 lets 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.
2019
JOFC
Koblitz Curves over Quadratic Fields
Abstract
In this work, we retake an old idea that Koblitz presented in his landmark paper (Koblitz, in: Proceedings of CRYPTO 1991. LNCS, vol 576, Springer, Berlin, pp 279–287, 1991 ), where he suggested the possibility of defining anomalous elliptic curves over the base field $${\mathbb {F}}_4$$ F 4 . We present a careful implementation of the base and quadratic field arithmetic required for computing the scalar multiplication operation in such curves. We also introduce two ordinary Koblitz-like elliptic curves defined over $${\mathbb {F}}_4$$ F 4 that are equipped with efficient endomorphisms. To the best of our knowledge, these endomorphisms have not been reported before. In order to achieve a fast reduction procedure, we adopted a redundant trinomial strategy that embeds elements of the field $${\mathbb {F}}_{4^{m}},$$ F 4 m , with m a prime number, into a ring of higher order defined by an almost irreducible trinomial. We also suggest a number of techniques that allow us to take full advantage of the native vector instructions of high-end microprocessors. Our software library achieves the fastest timings reported for the computation of the timing-protected scalar multiplication on Koblitz curves, and competitive timings with respect to the speed records established recently in the computation of the scalar multiplication over binary and prime fields.
2009
CHES
Program Committees
- CHES 2022
- CHES 2021
- Asiacrypt 2021
- CHES 2020
- CHES 2019
- CHES 2009
Coauthors
- Diego F. Aranha (2)
- Jean-Luc Beuchat (1)
- Daniel Cervantes-Vázquez (1)
- Jorge Chavez-Saab (1)
- Jérémie Detrey (1)
- Nicolas Estibals (1)
- Armando Faz-Hernández (1)
- Darrel Hankerson (1)
- Julio López (4)
- Eiji Okamoto (1)
- Thomaz Oliveira (3)
- Jonathan Taverne (1)
- Mehdi Tibouchi (1)