Abstract
Without cryptography, anyone could eavesdrop your Internet conversations or gain access to your bank accounts. To prevent all this, your web browser and your mobile phone routinely perform mathematical calculations on extremely large numbers that form the basis of the security of the cryptography used daily. If the latter has perfectly been established for 50 years, Planck, de Broglie and Einstein have highlighted a phenomenon that could change the situation within 10 years: quantum physics. Indeed, the existence of a quantum computer, based on the quantum superposition and entanglement principles, would break a large part of the current standards in cryptography. Mathematical solutions have existed for a long time to counter this threat, proposing a new kind of mechanisms known as post-quantum cryptography. But it is essential to increase research to obtain concrete cryptographic tools that can be deployed in our products and services by 2030: this was the primary objective of PROMETHEUS.
Started in 2018, this H2020 project studied the entire chain of post-quantum cryptography: the mathematical bases, the encryption and signature primitives used every day, and the applications protecting our lives as individuals. PROMETHEUS has published more than a hundred articles, initiated 3 of the 4 future cryptography standards, provided about fifteen public libraries to help the industry better prepare for the quantum transition, and validated in a significant environment 4 secure prototypes in a quantum world.
PROMETHEUS has been rewarded by the French Ministry of Research by the Etoile de l’Europe Award for its work on the transition to a quantum-safe era.
Key takeaways
Quantum computers are not for now, but the existence of such machine is certainly the biggest threat cryptography has ever faced since its existence. We need to be prepared as they could take off quickly, hence the importance to design alternatives to historical cryptography used every day. This has been our main motivation all along the PROMETHEUS project.
Thanks to our results on research, standardisation, implementation and use case prototyping, we have given to the ICT community a large number of improvements related to lattice-based cryptography, from foundations to advanced protocols. We have thoroughly assessed the exact maturity level of such post-quantum cryptographic family. We have also largely shared our conclusions (publications, libraries, use cases’ prototypes) to academy, to industry, but also to European authorities, so as to prepare all of them to a safe real-life transition to quantum-resistant cryptography. In particular, three among the four future NIST standards on post-quantum cryptography have been designed by members of the PROMETHEUS consortium. We have also provided the first quantum-safe systems for four relevant use cases: e-voting, privacy-preserving payment, privacy-preserving authentication, and cyber threat intelligence.
For all this work, PROMETHEUS has recently been rewarded by the French Ministry of High Education, Research and Innovation by the Special Prize of the Etoile de l’Europe Awards.
Introduction
For decades, cryptography has protected citizens in their digital life, securing their sensitive communication, such as web browsing, online and contactless payments, or home services. The greatest success of this field is probably that cryptographic algorithms are ubiquitous today and yet go unnoticed by their users. Indeed, cryptographic standards used in these contexts have been perfectly mastered since the 1970s. Current standards are mainly based on the difficulty of solving mathematical problems (such as the factorization of big numbers) that we know how to perfectly configure to guarantee the security of our services against classical computers.
Unfortunately, this state of affairs is about to change since those mathematical foundations cannot withstand quantum computing. As a matter of fact, a quantum computer would destroy the security of a large part of the cryptography used today, as being able to factorize a very large number in a very short time by using the Shor algorithm. While this threat was far enough away at a time where the advent of quantum computers seemed elusive, the situation has dramatically changed in the last few years. Research in this field is advancing rapidly and it is now widely accepted that this threat could materialize soon, impacting all citizens and companies worldwide. In cryptography, it is hence essential to follow this evolution, and to find alternatives.
We have known for several decades mathematical problems compatible with cryptographic requirements and able to resist quantum computers. But their transformation into real cryptographic systems deployable on a large scale remained to be accomplished.
The objective of the H2020 PROMETHEUS project was to fill this gap between theory and practice, to offer the academic, industrial and state communities a better mastery of these new systems, in order to be ready, by 2030, for a transition to the quantum era. For this purpose, PROMETHEUS has focused on lattice-based cryptography.
Lattice-based cryptography
Informally speaking, Euclidean lattices are grids of points, regularly arranged in spaces, typically a space with many more than 3 dimensions. In practice, they are represented by a basis, i.e., a set of linearly independent vectors such that the lattice is made of all integer linear combinations of those vectors. Lattices have a long mathematical history, and they are relevant in cryptography as they give rise to computational problems of geometric nature. The simplest one is the Shortest Vector Problem: given a lattice (represented by a basis), find its shortest non-zero vector (or a good approximation of it). While very easy in dimension 2, this problem becomes exponentially hard as the dimension increases.
Intuitively, public-key cryptography based on lattices relies on the following principle: one generates a lattice together with a good basis and keeps it as his secret key. He/she nevertheless reveals a bad basis of that same lattice as the public-key. Only him who knows the good basis (the secret key) is able to solve the short vector problem (or one related problem such as the Learning With Errors, of the Short Integer Solution), and solving this problem is made by design of the cryptosystem to correspond to the decryption operation (or the signature operation).
Lattice-based cryptography is one of the quantum-resistant alternatives to traditional cryptography (based on RSA and Elliptic Curve Cryptography). Indeed, other proposals are based on some different mathematic tools such as multivariate polynomials, codes, isogenies or hash functions. But, to date, the most promising solutions are arguably those using lattices. As evidence, several systems based on the other problems have recently been broken, the most impressive being based on isogenies or multivariate polynomials. This does not mean that this is the end of those families but that the maturity is not yet enough for now.
Indeed, lattices are the only solutions whose security can be reduced to well-studied computational problems such as Learning With Errors or Short Integer Solution, while permitting to design efficient cryptographic protocols in the public-key setting. Hence our choice to focus on such family within PROMETHEUS.
Identity card of the H2020 PROMETHEUS project
Based on an initial idea by ENS de Lyon (as coordinator) and Orange (as technical leader) to focus and deeply improve the maturity of lattice-based cryptography, one of the possible family of post-quantum cryptography, the main objectives of the project have next been designed by a consortium composed of academic research centres (ENS de Lyon, Centrum Wiskunde & Informatica, Interdisciplinary Center Herzliya, Royal Holloway University of London, Ruhr Universität Bochum, Universitat Politècnica de Catalunya, Université de Rennes 1 and Weizmann Institute of Science), one independent research organization (TNO), one SME (Scytl) and two industrial companies (Orange and Thales). More precisely, the three main objectives of PROMETHEUS were to:
- build a complete study of the foundations of lattice-based cryptography;
- provide innovative lattice-based cryptographic primitives; and
- protect the privacy of individuals in a post-quantum era.
After four years of work, PROMETHEUS has given a very precise vision of how services will have to evolve to be ready in 2030, enabling all citizens and businesses to continue their digital activities safely in a quantum world. This resulted in several major contributions, on different aspects of cryptographic research and innovation.
Scientific output
Based on a very strong core in fundamental research, PROMETHEUS has generated a large number of scientific productions with several major results in the field of lattice-based cryptography, and a very significant number of publications: 118 listed to date, all in peer-reviewed international journals/conferences. Compared to other H2020 projects in the cryptographic field, it is 1.5 to 5 times more! Additionally, among our scientific publications, more than a half are published in the 3 most renowned world conferences in cryptography: Eurocrypt, Crypto, Asiacrypt.
Foundations of lattice-based cryptography: we have provided an in-depth study of the underlying lattices mathematical problems, leading to the concrete security of such kind of cryptography. The set of hard problems is today much larger than at the beginning of the project, and we additionally better know their real hardness by concrete estimations. We have also worked on the basis of security proofs inb the quantum setting, working on quantum random oracle model proof technique, of the quantum seuciry of some generic transforms (so-called Fiat-Shamir, Chosen Ciphertext Attack). This has permitted us to formally show how cryptographic schemes (ours but also the ones of other researchers in cryptography) should be designed such as to resist an attacker with quantum capabilities. We have eventually published papers and provided the first proofs of concept on the way to securely implement a lattice-based cryptographic scheme, giving a set of countermeasures against so-called side-channel attacks.
Lattice-based cryptographic primitives: we have designed and implemented a set of building blocks related to digital signatures with additional features, to new encryption schemes, and to zero-knowledge proofs of knowledge that are used to prove that some mathematical statements used in a cryptographic protocol are true. Those primitives have been essential for our work on standardisation and for the design of our use cases’ prototypes (see below). In particular, we have fully redesigned the concept of a secure blind signature scheme in the lattice setting, one building block standardised at ISO/IEC and particularly relevant to protect the privacy of individuals. The robustness of the system we have designed has been shown thanks to proofs that the security of the scheme can mathematically be reduced to the difficulty of solving a lattice hard problem (see above).
Lattice-based cryptographic protocols: last but not least, we have designed cryptographic protocols related to real-life use cases. More precisely, we have created the first secure quantum-safe digital cash system that protects the privacy of individuals. We have shown that all previous constructions were not really proven secure, and we have proposed both a generic design and a concrete construction that are fully proven secure. We have also studied and proposed several frameworks for lattice-based e-voting. Our work has also led to the first implementation of lattice-based anonymous credentials, a primitive used to minimise the quantity of sensitive data an individual gives to interact with a service provider.
Creation of values
Standardisation: one of the most fundamental results we achieved in PROMETHEUS is related to standardisation. Shortly before the submission of the project, the National Institute of Standards and Technology (NIST) in the US, launched a competition to define the future standards of post-quantum cryptography. After 4 years of competition and 69 initial submissions, the NIST finally announced in June 2022 the 4 winners, future standards in cryptography to be used in our everyday life. Among these systems, 3 of them have been initiated by PROMETHEUS partners:
- CRYSTALS-KYBER for public-key encryption and key-establishment algorithms,
- CRYSTALS-DILITHIUM and Falcon for digital signatures.
This main result was possible through the work of the project, with publications supporting our proposals or demonstrating weaknesses in some others, but also with implementations that we have published to show the relevance of the consortium’s solutions.
Open-source libraries: another important output of the project is the publication of several open-source libraries related to post-quantum cryptography. At first, we provided the scientific community several software and hardware implementations of lattice-based cryptographic primitives (digital signatures and encryption mechanisms). Another important aspect of our research has been the creation and maintenance of a set of libraries (LWE-estimator, Leaky-LWE-estimator and NTRUFatigue-estimator) dedicated to the estimation of the best parameters to be used in lattice-based cryptography, considering the best-known attacks and the impact on the efficiency. Such set of open-source tools is of prime importance to help:
- the academic community to design lattice-based cryptographic schemes;
- the industry to choose concrete parameters according to their own requirements and the state-of-the-art on cryptanalysis;
- everybody to better understand attacks on lattice-based cryptography.
Societal output
Use cases: to show the relevance of our research work, PROMETHEUS has eventually illustrated the maturity of lattice-based cryptography with respect to real life requirements by providing four demonstrators in a relevant environment (known as a Technology Readiness Level 5). Such set of use cases has been selected to demonstrate how to protect the daily life of individuals in a quantum era.
Quantum-safe e-voting system – At first, we provided the first quantum-safe e-voting prototype. Increasingly used at the institutional level or in companies and associations, e-voting is particularly sensitive to the threat of quantum computers. Indeed, one of the risks associated to the latter concerns the problem of “store now and decrypt later”: a malicious person stores the digital votes of an election today and awaits the arrival of quantum computers in order to annihilate the security of the cryptographic system used and thus know the vote of each voter. The work PROMETHEUS has carried out on this subject makes it possible to deploy solutions that prevent this attack more quickly.
Quantum-safe privacy-preserving payment system – The second use case focused on consumers concerned about protecting how they pay for their goods or services in their digital lives. By using a quantum-safe digital cash system, the cryptographic core of which was invented by the project, our prototype prevents anyone from tracing customers’ purchases (except in case of fraud), even using a quantum computer. Such a system has been discussed with the French CNIL and the European Data Protection Board (EDPB) to help them build their requirements on a future privacy-preserving digital European payment system.
Quantum-safe privacy-preserving authentication system – The third prototype practically shows how the anonymous credential systems we have designed could be used in a real-life product. With such system, an individual can minimize the amount of personal information (age, place of residence, job, etc.) he/she reveals when he/she wishes to access some on-line services or validate some administrative procedures. Such a system could be the basis for the future privacy-preserving digital European identity card.
Long-term data protecting cyber threat intelligence system – Additionally, we have prototyped a long-term data protection Cyber Threat Intelligence system, in which several companies can securely share their sensitive data in order to better detect some cyberattacks together.
Security agencies: we had scientific exchanges with security and privacy national agencies (ANSSI and CNIL in France) about the transition towards quantum-resistant cryptography and the work of PROMETHEUS on basic and advanced cryptographic primitives. More specifically, we discussed with the French ANSSI about their position on post-quantum primitives and their strategy about transition to quantum-safe systems from now to 2030. We also presented our work on advanced protocols, the difficulties we have encountered and the solutions we have provided. We also had two dedicated meetings with the French privacy agency (CNIL): one about real-life exploitation of e-cash, and the other about the current maturity of post-quantum privacy- preserving cryptography.
Conclusion
PROMETHEUS has done an essential work to improve the maturity of post-quantum cryptography, and more specifically that based on Euclidean lattices. This might lead one to believe that the bulk of work has been done but unfortunately there is still a long way to go before concrete exploitation of these results. This is because there is a significant gap between the design of these protocols and their concrete implementations. Hence, it remains to address the technical challenges arising from the integration of cryptographic mechanisms, which so far have only been the concern of theoretical studies, to real-life products. This is the work that awaits us for the next few years.
