Post-Quantum Cryptography: Everything You Need to Know About the Internet’s Future Safety
This article was written by Jelizaveta Vakarjuk, a Junior Researcher at Digit's co-organizer, Cybernetica
The rise of post-quantum cryptography
You may have heard that the future security of the Internet is in danger because of the developments in quantum technologies. Let us dive into this topic and examine what danger an attacker with quantum computing power poses to modern systems.
Pre-quantum cryptography
Cryptography invisibly surrounds almost all our actions in the digital world — accessing a website, authenticating to a website, digitally signing documents, approving bank transactions, exchanging messages with our friends, etc. There are two big families of cryptographic algorithms: symmetric cryptography and asymmetric cryptography. Asymmetric (or public key cryptography) allows a secure connection to be created (1 step in the picture), while symmetric cryptography enables data transfer (2nd step in the picture).
The main public-key cryptographic algorithms that underlie the security of the Internet are key establishment (KEM) and digital signature schemes. Key establishment allows parties, who want to securely communicate (for example, your browser and the server hosting website you want to access) to agree on a secret key that can be used to encrypt messages exchanged during communication. The digital signature scheme, as the name suggests, allows the creation of digital signatures that are used for authenticity and data integrity properties. The most commonly used algorithms include RSA, DH, (EC)DSA, EdDSA, etc. All of those are vulnerable to the quantum attack presented by Peter Shor. Therefore, it is essential to plan and implement protection against quantum computer attacks on our digital infrastructure.
Quantum adversary?
Quantum computers are built on the principles of quantum mechanics and therefore have properties that cannot be achieved by classical computers. Quantum algorithms, which are sets of instructions for quantum computers, are developed specifically to exploit those properties. The security of many cryptographic schemes relies on complex mathematical problems. The most common mathematical problems used in modern public key cryptography are integer factorisation and discrete logarithm problems. In 1994, Peter Shor published an algorithm that was able to solve both problems. A quantum adversary is an attacker who has access to a large enough quantum computer that is used to attack systems.
There are quantum algorithms that influence the security of symmetric primitives (hash functions, block ciphers) as well. An important distinction is that symmetric primitives are not completely broken by those algorithms, increasing key length will be enough to maintain security.
Quantum cryptography vs post-quantum cryptography
A very common confusion point is between quantum cryptography and post-quantum cryptography, so let us start with it.
Quantum cryptography builds on top of laws of quantum physics that have specific properties not available to classical computers. Therefore, quantum cryptography works only with quantum devices and cannot be realised solely on classical computers.
The most common example of quantum cryptography is quantum key distribution (or QKD). This technology utilises a special quantum channel through which qubits (quantum bits of information) travel to their destination. QKD allows communicating parties to establish a secret key that can be later used to exchange encrypted messages. QKD requires specific and costly infrastructure to be set up, which makes the adoption of the technology more resource-consuming.
Due to the properties of quantum mechanics, information sent over the quantum channel cannot be copied. This is a compelling property of the system, guaranteeing that attacks, where the adversary listens in on the communication (eavesdropping), can be detected. On the other hand, sensitivity to such attacks has the downside of being more vulnerable to denial-of-service attacks, where the adversary aims to stop the system from functioning. Additionally, there is a caveat in making QKD work for longer distances (over 200 km): one needs to set up multiple trusted nodes on the path.
Post-quantum cryptography works on classical computers and does not require any specific equipment. Underlying hard mathematical problems are what set it apart from pre-quantum cryptography.
Factorisation and discrete logarithm problems are the basis of pre-quantum cryptographic algorithms and are vulnerable to quantum attacks. There are no known quantum attacks for mathematical problems that are the basis of post-quantum cryptographic algorithms, such as learning with errors and short integer solution.
Post-quantum cryptography offers functionality for a wider range of applications — key establishment, authentication, encryption, etc. Since post-quantum cryptography algorithms work on classical computers, those can be implemented and tested more easily. Furthermore, the standards for post-quantum cryptography are already being developed and published, making it possible to build interoperable solutions.
However, integrating post-quantum cryptography into our current infrastructure requires a careful approach. It is essential to take into account the limitations of different systems (e.g., computational power, storage, backward compatibility) and maintain interoperability of the systems. Additionally, for more cryptographically complicated systems, like i-voting, and Smart-ID authentication and signing, switching to post-quantum algorithms is more challenging since having KEM and a regular digital signature scheme is not enough. New post-quantum algorithms should be developed to fit into the existing infrastructure. The necessity of developing a migration strategy and implementing post-quantum cryptography is an urgent priority.
Is the number of qubits enough?
Qubit (quantum bit) is a basic unit of quantum information, like bits for classical computers. The number of qubits is frequently used to measure the progress of quantum technology, and thus we are nearing the period during which we need to switch to post-quantum cryptography. This is not the only property that should be considered.
Imagine, you are trying to prepare the most delicious cake for the Worldwide Cake Competition. Just having the most powerful oven that bakes perfectly is not enough. You should also:
- select proper ingredients for your cake – those that are seasonal, fresh, and taste the best (selecting what to build qubits from);
- figure out the best recipe – start with a basic recipe and add your magic ingredients (there are known quantum algorithms that can be further optimised);
- do the tasting and quality assurance – once the cake is ready, you need to make sure that it is properly baked, the cream is perfectly whipped and the decorations are in place. Of course, some errors could happen in the process, but this is the place where those should be fixed (developing an error-correction strategy);
- figure out and maintain optimal temperature – the baking process itself can be complicated, and the right temperature can be crucial to receiving the expected result (selecting the architecture, and how to connect qubits with each other).
Post-quantum cryptography standardisation and migration
Standardisation of post-quantum cryptography was initiated by the US National Institute of Standards and Technology (NIST) in 2016. The primary goal of the project was to standardise post-quantum key establishment mechanisms and digital signature schemes. Currently, there are standard drafts for the schemes that were chosen through the careful selection process.
The table below shows soon-to-be standardised post-quantum alternatives to the commonly used pre-quantum cryptographic algorithms, which are not secure against quantum computer attacks.
Post-quantum
| Pre-quantum
| Category
|
Crystals-Kyber
| DH, (EC)DH
| Key establishment
|
Crystals-Dilithium, Falcon, Sphincs+
| RSA, (EC)DSA, Schnorr, EdDSA
| Digital signatures
|
Moreover, there are additional standardisation rounds for key establishment and digital signature schemes to add more variety to the selected schemes.
The goal of the post-quantum migration process is to plan and execute the switch of systems from traditional cryptographic algorithms to those secure against quantum computer attacks. Since different systems have different purposes, requirements, use-cases, and constraints, the migration process is unique for each of the systems.
Hybrid mode
You may have encountered the term “hybrid mode” when reading about the migration process. Since post-quantum algorithms are not considered mature enough to be used as standalone solutions, it is considered a better option to use post-quantum and pre-quantum cryptography simultaneously.
The idea behind this is that if one of the schemes appears to be broken or vulnerable to some attacks, the other scheme will be enough to guarantee security for the user’s information. An intuitive example would be locking your bicycle with two different locks, then it would not be enough for the robber to break just one lock, both locks should be broken for a successful robbery.
We hope you will gain a valuable, in-depth overview of the implementation of PQC technologies at the Digit Conference 2024, presented by Cybernetica’s Security Engineer, Petr Muzikant.