PKC 2021
Lattices and Factoring
In this talk, I would like to re-popularize two dual ideas that relate Lattices and Factoring. Such a connection may appear surprising at first, but is only one logarithm away: after all, factoring is nothing more than a multiplicative knapsack problem, i.e. a subset product problem, where the weights are given by the set of small enough primes.
The first of the two ideas, we owe to Schnorr (1991) and to Adleman (1995). It consists in finding close or short vectors in a carefully crafted lattice, in the hope that they will provide so-called factoring relations. While this idea does not appear to lead to faster factoring algorithms, it remains fascinating and has in fact lead to other major results. Indeed, the Schnorr-Adleman lattice plays a key role in the proof by Ajtai (1998) of the NP-hardness of the shortest vector problem.
The second idea, due to Chor and Rivest (1988) shows a reverse connection: constructing the lattice this time using discrete logarithms, they instead solve the bounded distance decoding (BDD) problem through easy factoring instances. Revisiting their idea, Pierrot and I (2018) showed that this was a quite close to an optimal construction for solving BDD in polynomial time. It was in fact the best known such construction until some recent work by Peikert and Mook (2020).
I wish to conclude with an invitation to explore the cryptographic potential of other lattices than the random q-ary lattices ---the lattices underlying the Learning with Error problem (LWE) and the Short Integer Solution problem (SIS). While SIS and LWE have shown to be very convenient for constructing the most advanced schemes and protocols, I believe that more general lattices have a yet untapped potential for cryptography.
Léo Ducas obtained his PhD at ENS Paris, on the topic of Lattice-based Cryptography. After a post-doc at UCSD, he joined the Cryptology Group of the Centrum Wiskunde & Informatica (CWI, Amsterdam) in 2015, where he is now tenured.
Léo does research on cryptology, with a special taste for lattices, algorithms, and cryptanalysis. He enjoys all aspects of this topic, from algebraic number theory, down to fast implementation. Léo has also contributed to quantum cryptanalysis of lattice-based schemes, showing that not all lattice problems are equally resistant to quantum computing. He is a co-designer of several candidate schemes to the NIST post-quantum standardisation process, two of which (Kyber & Dilithium) are now at the final round.
Léo is a proponent of openness in science, especially regarding software source code; he systematically makes his research artefacts open source, and contributes regularly to the lattice reduction library FPLLL.
How provably secure are (EC)DSA signatures?
Today, digital signatures are an omnipresent cryptographic primitive. They are extensively used for message and entity authentication and find widespread application in real-world protocols. Without much doubt, the specific schemes deployed most often are the RSA-based PKCS#1 v1.5, and the discrete logarithm-based DSA and ECDSA. For instance, current versions of TLS - the standard technology for securing internet connections - exclusively employ signatures of these types to authenticate servers. Furthermore, most cryptocurrencies like Bitcoin and Ethereum use ECDSA for signing transactions.
The popularity of (EC)DSA signatures stands in stark contrast to the absence of rigorous security analyses. In this talk we will survey known provable security results about DSA and ECDSA. We will also discuss limitations of current provable security approaches
Eike Kiltz is a professor at the Center of Computer Science at Ruhr-Universität Bochum. He was a postdoc at UC San Diego from 2004 to 2005 with Mihir Bellare and a researcher at CWI Amsterdam from 2005 to 2010 in the group of Ronald Cramer. His research areas are cryptography and security, specifically practice-oriented provable security as a way to obtain practical, high-assurance cryptography. Kiltz has had many fundamental contributions to the design and analysis of cryptosystems. He has published more than 100 peer-reviewed papers at conferences and journals. In 2010 he received the Sofja Kovalevskaja Award for developing quantum-resistant cryptography. In 2013 he received an ERC Consolidator Grant for building fast cryptography on small devices. Currently he is the spokesperson for the DFG cluster of excellence "Cyber Security in the Age of Large-Scale Adversaries".