International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Daniel J. Bernstein

Publications

Year
Venue
Title
2021
TCHES
CTIDH: faster constant-time CSIDH 📺
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 📺
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
TCHES
Fast constant-time gcd computation and modular inversion 📺
Daniel J. Bernstein Bo-Yin Yang
This paper introduces streamlined constant-time variants of Euclid’s algorithm, both for polynomial inputs and for integer inputs. As concrete applications, this paper saves time in (1) modular inversion for Curve25519, which was previously believed to be handled much more efficiently by Fermat’s method, and (2) key generation for the ntruhrss701 and sntrup4591761 lattice-based cryptosystems.
2019
EUROCRYPT
Quantum Circuits for the CSIDH: Optimizing Quantum Evaluation of Isogenies 📺
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.
2019
ASIACRYPT
Decisional Second-Preimage Resistance: When Does SPR Imply PRE?
Daniel J. Bernstein Andreas Hülsing
There is a well-known gap between second-preimage resistance and preimage resistance for length-preserving hash functions. This paper introduces a simple concept that fills this gap. One consequence of this concept is that tight reductions can remove interactivity for multi-target length-preserving preimage problems, such as the problems that appear in analyzing hash-based signature systems. Previous reduction techniques applied to only a negligible fraction of all length-preserving hash functions, presumably excluding all off-the-shelf hash functions.
2017
EUROCRYPT
2017
CHES
Gimli : A Cross-Platform Permutation
This paper presents Gimli, a 384-bit permutation designed to achieve high security with high performance across a broad range of platforms, including 64-bit Intel/AMD server CPUs, 64-bit and 32-bit ARM smartphone CPUs, 32-bit ARM microcontrollers, 8-bit AVR microcontrollers, FPGAs, ASICs without side-channel protection, and ASICs with side-channel protection.
2017
CHES
Sliding Right into Disaster: Left-to-Right Sliding Windows Leak
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.
2016
EUROCRYPT
2016
PKC
The first 10 years of Curve25519
Daniel J. Bernstein
2015
EUROCRYPT
2014
ASIACRYPT
2014
CHES
2013
CHES
2013
ASIACRYPT
2013
ASIACRYPT
2013
FSE
Failures of secret-key cryptography
Daniel J. Bernstein
2012
CHES
NEON Crypto
Daniel J. Bernstein Peter Schwabe
2011
PKC
2011
CRYPTO
2011
CHES
2009
EUROCRYPT
2009
CRYPTO
Batch Binary Edwards
Daniel J. Bernstein
2008
EUROCRYPT
2008
CHES
2007
ASIACRYPT
2007
FSE
2006
PKC
2005
EUROCRYPT
2005
FSE
1999
JOFC

Program Committees

CHES 2019
FSE 2019
CHES 2018
Asiacrypt 2018
CHES 2017
CHES 2016
FSE 2015
Asiacrypt 2015
CHES 2015
FSE 2014
Asiacrypt 2014
CHES 2014
CHES 2013
CHES 2012
Eurocrypt 2011
CHES 2011
CHES 2010
FSE 2010
CHES 2009
Asiacrypt 2009
FSE 2009
Asiacrypt 2008
CHES 2008