by Thijs Veugen (TNO and CWI), Thomas Attema (TNO), Maran van Heesch (TNO), and Léo Ducas (CWI)
In the post-quantum era, most of the currently used cryptography is no longer secure due to quantum attacks. Cryptographers are working on several new branches of cryptography that are expected to remain secure in the presence of a universal quantum computer. Lattice-based cryptography is currently the most promising of these branches. The new European PROMETHEUS project will develop the most secure design and implementations of lattice-based cryptographic systems. Exploitation of the project results will be stimulated by demonstrating and validating the techniques in industry-relevant environments.
Most current day cryptosystems are based on two computationally hard problems: factoring integers and computing the discrete logarithms in finite groups. Advances in solving these problems (classically) and increased classical computational power form a threat that is relatively easy to diminish by ‘simply’ increasing the key sizes. A more serious threat was revealed in 1994 already, when Shor [1] had proven that quantum algorithms are able to efficiently solve both these problems. While the requirement for a truly universal quantum computer to execute these attacks has long kept us secure, recent advances in quantum computing once again highlight our dependency on these computational problems. In short, the arrival of a quantum computer will leave commonly used cryptosystems such as RSA, DH and ECDH insecure.
To ensure secure communication in the presence of a universal quantum computer, for many years cryptographers have been working on constructing cryptographic schemes based on other computational problems since many years. Their efforts have led to the following six possible building blocks for cryptographic schemes: hash trees, error-correcting codes, lattices, multivariate equations, supersingular elliptic curve isogenies, and even quantum physics. These cryptographic building blocks fall within the realm of so-called “post-quantum cryptography”, the study of cryptographic algorithms that are secure against attacks by a quantum computer.
PROMETHEUS is a new, four-year European H2020 project (starting in January 2018) aiming to provide a secure design and implementation of new and quantum-safe cryptographic systems. The twelve project partners (ENS Lyon, ORANGE SA, CWI Amsterdam, IBM Research, RHU London, RU Bochem, Scytl Barcelona, Thales, TNO, UPC Barcelona, University Rennes, WIS Rehovot) will focus their efforts on lattice-based cryptography. A fundamental property of lattice-based cryptographic schemes is that their security can be reduced to well-studied computational problems, which is not necessarily the case for other post-quantum mechanisms.
An n-dimensional lattice L is a set of integer linear combinations of n independent vectors. The grid displayed in Figure 1 represents a lattice L. An example of a computationally hard lattice problem is the closest vector problem (CVP): given a lattice L and a random point y (not necessarily an element of the lattice), find the lattice element x closest to y. For higher dimensional lattices this problem soon becomes very hard to solve. In fact, no (quantum) algorithms have been found yet solving this problem efficiently.
Figure 1: Illustration of a two-dimensional lattice.
Research in using this and other hard lattice problems for cryptographic purposes began with the publication of the public key encryption scheme by Ajtai and Dwork in 1997 [2]. Improvements to this scheme and new schemes followed, trying to make use of additional structures in specific types of lattices. The first lattice-based cryptographic schemes for public-key encryption, signatures and key-exchange have been proposed, and are considered for standardization [L1]. A recently proposed key-exchange protocol [3] (partly developed at CWI) has successfully been implemented and tested by Google in the Chrome web browser [L2], and was awarded the Facebook Internet Defense prize [L3].
One particular challenge for the transfer from theory to practice lies in the choice of parameters for those schemes: while lattice problems become ‘hard’ with larger dimensions, predicting precisely how hard they are (e.g., it will take 100 years to solve with a cluster of 10,000 GPUs) remains difficult and uncertain. The issue becomes even more delicate when considering quantum algorithms, especially in the light of recent quantum algorithms specialised for “ideal lattices” [4]. This is the main issue for which CWI’s crypto group will provide its expertise.
The PROMETHEUS project recognises that modern day cryptography entails much more than protecting private information over insecure communication channels. With its digital signatures, commitment schemes, and homomorphic properties, lattice-based cryptography offers a wide variety of applications. To enhance the applicability and the adaptation of these techniques, four use-cases will be studied. By means of these use-cases PROMETHEUS aims to cover the entire range from theory to application.
The first use case will focus on constructing an anonymous credential system, which allows a user to prove to a service provider that he owns a certain attribute (e.g., driving licence), while minimising the information given to third parties, then protecting the user’s privacy. In the second use case technology will be developed that allows users to make secure, privacy-friendly contactless transactions, for a long-term use. In the third use case, a long-term secure e-voting system will be developed. Lastly, in the fourth use case, PROMETHEUS will develop quantum-safe homomorphic encryption techniques, and use them to develop a secure cyber threat-intelligence sharing mechanism.
All four use-cases aim for long-term security in the quantum era, requiring the cryptographic building blocks to be quantum safe. Many of these techniques already exist in a quantum vulnerable setting. Introducing long-term security by mitigating quantum threats is the core of our innovation. By covering the entire range from theory to application and building demonstrators, the exploitation of the project results will be stimulated.
Links:
[L1] https://kwz.me/hB2
[L2] https://kwz.me/hB3
[L3] https://kwz.me/hB5
References:
[1] P.W. Shor: “Algorithms for quantum computation: Discrete logarithms and factoring”, in Proc. of SFCS ‘94, 1994.
[2] M. Ajtai, C. Dwork: “A public-key cryptosystem with worst-case/average-case equivalence”, Proc. of the 29th annual ACM symposium on Theory of Computing. ACM, 1997.
[3] E. Alkim, L. Ducas, T. Pöppelmann, P. Schwabe: “Post-quantum Key Exchange-A New Hope”, USENIX Security Symposium, 2016.
[4] R. Cramer, L. Ducas, B. Wesolowski: ‘’Short Stickelberger Class Relations and application to Ideal-SVP’’, IACR, Eurocrypt 2017.
Please contact:
Thijs Veugen, TNO, The Netherlands
+31888667314,
