Introduction to Post-Quantum Cryptography
You may not know this, but one of the main reasons we can securely communicate on the Internet is the presence of some well-designed cryptographic protocols. In February 1995, Netscape publicly released the Secure Sockets Layer (SSL) protocol. Since then, it has evolved a few times until it reaches its successor: the Transport Layer Security (TLS) protocol - widely used nowadays.
Although the protocols have evolved, they all keep the same basic structure. Digital signatures are used to authenticate the parties, and key exchange is used to establish a shared secret, which can then be used in symmetric cryptography - to provide confidentiality to their communication. Remember that, in symmetric cryptography, we use the same key for both encryption and decryption.
Ok, but how can a quantum computer change the cryptography’s paradigm?
The majority of the public-key cryptosystems is safe because it relies on some challenging mathematical problems. Let’s say you want to factor a large number or to compute a discrete logarithm in finite fields. These goals are tough to accomplish, and we can only do it in exponential time. Thus, the time and computational resources to complete these tasks are so exorbitant that no hacker will even bother breaking these cryptosystems.
In this context, quantum computers are indeed game-changers because - as we have seen on previous posts - qubits allow any quantum superposition of states 0 and 1. This critical trait makes it possible to solve those challenging problems much faster - polynomial time - and reveals how vulnerable our current public-key cryptosystems are. As Michele Mosca (co-founder of the Institute of Quantum Computing at the University of Waterloo and co-leader of the Open Quantum Safe project) stated in 2015, “I estimate a 1/7 chance of breaking RSA-2048 by 2026 and a 1/2 chance by 2031.”
However, if large-scale quantum computers don’t exist (yet), why and who should worry about quantum attacks?
The U.S. National Institute of Standards and Technology (NIST) launched, in 2016, its post-quantum (also known as quantum-resistant and quantum-safe) cryptography project. It is a long process that aims to choose a few selected quantum-resistant public-key cryptosystems. One of the major NIST’s guidelines in this competition is to adopt crypto-agility, i.e., the current security system has to evolve - incorporating a new encryption method - without having significant changes in its infrastructure.
Crypto-agility is a fundamental trait in the ongoing process of establishing a new cryptographic scheme. Once the algorithms’ vulnerabilities are exposed, we must be capable of evolving into a new model in a secure and fast way (which can be achieved by maintaining the main infrastructure of the system). For this reason, NIST expects all the candidates of this competition to meet the crypto-agility criteria.
On its third round, NIST’s program has chosen only fifteen candidates to the next stage, with two main focuses: public-key encryption and digital signatures. From all these algorithms, the most prominent ones belong to the “lattice-based cryptography” class. Initially proposed by Miklós Atjai in 1996, it became one of the leading research areas for new cryptosystems. Before we proceed to the main problems (LWE and ring-LWE) currently used for lattice-based cryptographic schemes, we have to understand what does a lattice-based system mean.
First off, lattice problems are useful for cryptography purposes because they are strongly believed to be difficult to solve even in the event of a large-scale quantum computer. We can imagine a lattice as being an infinite arrangement of equally spaced points. On a computer, we can represent a lattice by its basis: a set of vectors that can generate any point of the lattice, when combined.
There is a set of challenging lattice problems, such as finding a different basis for a given lattice or determining the closest point to the grid origin. Even though it looks simple at first glance, it is important to notice that - for cryptographic uses - we consider multi-dimensional lattices. Therefore, any easy or medium problem in a small configuration quickly becomes exceptionally arduous (even for large-scale quantum computers) for a lattice with thousands of dimensions because it involves a vast number of variables.
For these (and other) reasons, lattice-based cryptography is believed to be more efficient than the RSA scheme and to be able to keep security even in the worst-case scenarios. This approach is also the basis for one of the cryptography “holy grails,” formally known as Fully Homomorphic Encryption (FHE). In this new paradigm, calculations can be performed on a file without ever seeing sensitive data or exposing it to hackers, i.e., encrypted data can be efficiently computed while protecting data privacy.
One of the most famous lattice problems - the Gap Shortest Vector Problem (GapSVP) - inspired the creation of the Learning With Errors (LWE) problem by Oded Regev in 2005. As the LWE is a more abstract algebraic problem, it fits better the requirements for cryptographic schemes. This problem has inspired several researchers to study LWE’s properties a little further. Then, in 2010, Vadim Lyubashevsky, Chris Peikert, and Oded Regev created the ring-LWE - which is quite analogous to the LWE problem, using ring elements rather than vectors.
As we can see, post-quantum cryptography is a vibrant and dynamic research topic. Virtually every year, there are some significant advances in the algorithms or their implementations. Thus - as NIST and other organizations already know - if we want to keep our data secure, it is mandatory to have a close look and to stimulate the progress of this field.
References:
https://openquantumsafe.org/papers/SAC-SteMos16.pdf
https://openquantumsafe.org/papers/NISTPQC-CroPaqSte19.pdf
https://openquantumsafe.org/papers/PQCrypto-PaqSteTam20.pdf
https://www.cs.princeton.edu/~mzhandry/2018-Fall-COS597A/ln/LN10.pdf
https://eprint.iacr.org/2015/938.pdf
https://web.eecs.umich.edu/~cpeikert/pubs/slides-qcrypt.pdf