CryptoDB
Tanja Lange
Publications
Year
Venue
Title
2021
TCHES
CTIDH: faster constant-time CSIDH
📺
Abstract
This paper introduces a new key space for CSIDH and a new algorithm for constant-time evaluation of the CSIDH group action. The key space is not useful with previous algorithms, and the algorithm is not useful with previous key spaces, but combining the new key space with the new algorithm produces speed records for constant-time CSIDH. For example, for CSIDH-512 with a 256-bit key space, the best previous constant-time results used 789000 multiplications and more than 200 million Skylake cycles; this paper uses 438006 multiplications and 125.53 million cycles.
2020
TCHES
Concrete quantum cryptanalysis of binary elliptic curves
📺
Abstract
This paper analyzes and optimizes quantum circuits for computing discrete logarithms on binary elliptic curves, including reversible circuits for fixed-base-point scalar multiplication and the full stack of relevant subroutines. The main optimization target is the size of the quantum computer, i.e., the number of logical qubits required, as this appears to be the main obstacle to implementing Shor’s polynomial-time discrete-logarithm algorithm. The secondary optimization target is the number of logical Toffoli gates. For an elliptic curve over a field of 2n elements, this paper reduces the number of qubits to 7n + ⌊log2(n)⌋ + 9. At the same time this paper reduces the number of Toffoli gates to 48n3 + 8nlog2(3)+1 + 352n2 log2(n) + 512n2 + O(nlog2(3)) with double-and-add scalar multiplication, and a logarithmic factor smaller with fixed-window scalar multiplication. The number of CNOT gates is also O(n3). Exact gate counts are given for various sizes of elliptic curves currently used for cryptography.
2019
EUROCRYPT
Quantum Circuits for the CSIDH: Optimizing Quantum Evaluation of Isogenies
📺
Abstract
Choosing safe post-quantum parameters for the new CSIDH isogeny-based key-exchange system requires concrete analysis of the cost of quantum attacks. The two main contributions to attack cost are the number of queries in hidden-shift algorithms and the cost of each query. This paper analyzes algorithms for each query, introducing several new speedups while showing that some previous claims were too optimistic for the attacker. This paper includes a full computer-verified simulation of its main algorithm down to the bit-operation level.
2018
PKC
Rounded Gaussians
Abstract
This paper suggests to use rounded Gaussians in place of discrete Gaussians in rejection-sampling-based lattice signature schemes like BLISS or Lyubashevsky’s signature scheme. We show that this distribution can efficiently be sampled from while additionally making it easy to sample in constant time, systematically avoiding recent timing-based side-channel attacks on lattice-based signatures.We show the effectiveness of the new sampler by applying it to BLISS, prove analogues of the security proofs for BLISS, and present an implementation that runs in constant time. Our implementation needs no precomputed tables and is twice as fast as the variable-time CDT sampler posted by the BLISS authors with precomputed tables.
2018
ASIACRYPT
CSIDH: An Efficient Post-Quantum Commutative Group Action
Abstract
We propose an efficient commutative group action suitable for non-interactive key exchange in a post-quantum setting. Our construction follows the layout of the Couveignes–Rostovtsev–Stolbunov cryptosystem, but we apply it to supersingular elliptic curves defined over a large prime field $$\mathbb F_p$$, rather than to ordinary elliptic curves. The Diffie–Hellman scheme resulting from the group action allows for public-key validation at very little cost, runs reasonably fast in practice, and has public keys of only 64 bytes at a conjectured AES-128 security level, matching NIST’s post-quantum security category I.
2017
CHES
Sliding Right into Disaster: Left-to-Right Sliding Windows Leak
Abstract
It is well known that constant-time implementations of modular exponentiation cannot use sliding windows. However, software libraries such as Libgcrypt, used by GnuPG, continue to use sliding windows. It is widely believed that, even if the complete pattern of squarings and multiplications is observed through a side-channel attack, the number of exponent bits leaked is not sufficient to carry out a full key-recovery attack against RSA. Specifically, 4-bit sliding windows leak only 40% of the bits, and 5-bit sliding windows leak only 33% of the bits.In this paper we demonstrate a complete break of RSA-1024 as implemented in Libgcrypt. Our attack makes essential use of the fact that Libgcrypt uses the left-to-right method for computing the sliding-window expansion. We show for the first time that the direction of the encoding matters: the pattern of squarings and multiplications in left-to-right sliding windows leaks significantly more information about the exponent than right-to-left. We show how to extend the Heninger-Shacham algorithm for partial key reconstruction to make use of this information and obtain a very efficient full key recovery for RSA-1024. For RSA-2048 our attack is efficient for 13% of keys.
2008
JOFC
2005
CRYPTO
2003
EUROCRYPT
Program Committees
- PKC 2022
- CHES 2019
- PKC 2016
- PKC 2014
- Asiacrypt 2013
- Crypto 2010
- Asiacrypt 2008
- Crypto 2007
- Asiacrypt 2006
- Asiacrypt 2005
- CHES 2004
Coauthors
- Michel Abdalla (2)
- Gustavo Banegas (2)
- Jens Bauch (1)
- Mihir Bellare (2)
- Daniel J. Bernstein (16)
- Joachim Breitner (1)
- Leon Groot Bruinderink (2)
- Fabio Campos (1)
- Wouter Castryck (1)
- Dario Catalano (2)
- Yun-An Chang (1)
- Tien-Ren Chen (1)
- Chen-Mou Cheng (2)
- Li-Ping Chou (1)
- Tung Chou (1)
- Chitchanok Chuengsatiansup (2)
- Mathieu Ciet (1)
- Craig Costello (1)
- Niels Duif (1)
- Reza Rezaeian Farashahi (1)
- Daniel Genkin (1)
- Nadia Heninger (2)
- Daira Hopwood (1)
- Andreas Hülsing (3)
- Eike Kiltz (2)
- Tadayoshi Kohno (2)
- John Malone-Lee (2)
- Chloe Martindale (2)
- Michael Meyer (1)
- Michael Naehrig (1)
- Gregory Neven (2)
- Ruben Niederhagen (1)
- Pascal Paillier (2)
- Lorenz Panny (2)
- Louiza Papachristodoulou (1)
- Christiane Peters (1)
- Jean-Jacques Quisquater (1)
- Joost Renes (1)
- Michael Schneider (1)
- Peter Schwabe (4)
- Haixia Shi (2)
- Francesco Sica (1)
- Kit Smeets (1)
- Benjamin Smith (1)
- Nicko van Someren (1)
- Jana Sotáková (1)
- Henry de Valence (1)
- Iggy van Hoof (1)
- Christine van Vredendaal (1)
- Christine van Vredendaal (1)
- Zooko Wilcox-O'Hearn (1)
- Bo-Yin Yang (2)
- Yuval Yarom (2)