CryptoDB
Francisco Rodríguez-Henríquez
Publications
Year
Venue
Title
2024
CIC
Optimizations and Practicality of High-Security CSIDH
Abstract
<p> In this work, we assess the real-world practicality of CSIDH, an isogeny-based non-interactive key exchange. We provide the first thorough assessment of the practicality of CSIDH in higher parameter sizes for conservative estimates of quantum security, and with protection against physical attacks.</p><p> This requires a three-fold analysis of CSIDH. First, we describe two approaches to efficient high-security CSIDH implementations, based on SQALE and CTIDH. Second, we optimize such high-security implementations, on a high level by improving several subroutines, and on a low level by improving the finite field arithmetic. Third, we benchmark the performance of high-security CSIDH. As a stand-alone primitive, our implementations outperform previous results by a factor up to 2.53×.</p><p> As a real-world use case considering network protocols, we use CSIDH in TLS variants that allow early authentication through a NIKE. Although our instantiations of CSIDH have smaller communication requirements than post-quantum KEM and signature schemes, even our highly-optimized implementations result in too-large handshake latency (tens of seconds), showing that CSIDH is only practical in niche cases. </p>
2023
TCHES
Vectorized and Parallel Computation of Large Smooth-Degree Isogenies using Precedence-Constrained Scheduling
Abstract
Strategies and their evaluations play important roles in speeding up the computation of large smooth-degree isogenies. The concept of optimal strategies for such computation was introduced by De Feo et al., and virtually all implementations of isogeny-based protocols have adopted this approach, which is provably optimal for single-core platforms. In spite of its inherent sequential nature, several recent works have studied ways of speeding up this isogeny computation by exploiting the rich parallelism available in vectorized and multi-core platforms. One obstacle to taking full advantage of this parallelism, however, is that De Feo et al.’s strategies are not necessarily optimal in multi-core environments. To illustrate how the speed of vectorized and parallel isogeny computation can be improved at the strategylevel, we present two novel software implementations that utilize a state-of-the-art evaluation technique, called precedence-constrained scheduling (PCS), presented by Phalakarn et al., with our proposed strategies crafted for these environments. Our first implementation relies only on the parallelism provided by multi-core processors. The second implementation targets multi-core processors supporting the latest generation of the Intel’s Advanced Vector eXtensions (AVX) technology, commonly known as AVX-512IFMA instructions. To better handle the computational concurrency associated with PCS, we equip both implementations with extensive synchronization techniques. Our first implementation outperforms the implementation of Cervantes-Vázquez et al. by yielding up to 14.36% reduction in the execution time, when targeting platforms with two- to four-core processors. Our second implementation, equipped with four cores, achieves up to 34.05% reduction in the execution time compared to the single-core implementation of Cheng et al. of CHES 2022.
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)
- Fabio Campos (1)
- Daniel Cervantes-Vázquez (1)
- Jorge Chavez-Saab (2)
- Jesús-Javier Chi-Domínguez (1)
- Jérémie Detrey (1)
- Nicolas Estibals (1)
- Armando Faz-Hernández (1)
- Darrel Hankerson (1)
- M. Anwar Hasan (1)
- Julio López (4)
- Michael Meyer (1)
- Eiji Okamoto (1)
- Thomaz Oliveira (3)
- Kittiphon Phalakarn (1)
- Krijn Reijnders (1)
- Francisco Rodríguez-Henríquez (8)
- Peter Schwabe (1)
- Vorapong Suppakitpaisarn (1)
- Jonathan Taverne (1)
- Mehdi Tibouchi (1)
- Thom Wiggers (1)