This article is divided into three parts, and is intended to retrace the main elements of cryptography and the changes that the "quantum" world has introduced up to the Quantum Key Distribution and the European Quantum-Secure Net project carried out by Italtel , Cefriel, Polytechnic of Milan, CNR, Polytechnic University of Madrid and Telefonica.
The first part, starting from the current state of cryptography, comes to define the contours of the so-called “quantum threat”. The second part tells the contours of quantum and post-quantum cryptography, leading to the introduction of Quantum Key Distribution (QKD). The third part tells about the Quantum-Secure Net project.
1. The current state of cryptography
Public key cryptography is vital to online security and is used in a variety of everyday systems, from banking to the mobile applications we use every day. When two or more parties want to communicate, in the current state of technology, public key cryptography ensures that information is confidential and accurate and that the correct parties are communicating. Most of the time encryption works behind the scenes and you don't realize it's used, let alone the type of encryption that's currently in use. When you visit an HTTPS website (in the following image detail of the certificate of an HTTPS site), using Safari or Google Chrome, clicking on the Certificate icon and then Details, and scrolling down to "Public Key Info" to see which algorithms are securing the connection to this site, you will probably see RSA or ECC algorithms.
At the base of every public key scheme there is a "complex" mathematical problem, that is of complex (but not impossible) resolution or, with a high "numerical complexity". If a person or computer can effectively solve this problem, they can bypass the cryptographic system. Not all complex math problems are suitable for use in cryptography; the key feature is that the problem must be difficult to solve in one direction, but easy in the opposite direction. For example, it is easy to multiply two large prime numbers, but it is very difficult to factor a large number into the prime numbers that constitute it (particularly as the size and number of primes that factor the chosen number increase).
Public key cryptography currently in use relies on problems involving prime number factorization (RSA), discrete logarithms (Diffie-Hellman), and elliptic curves (ECC). While these seem like different problems, in reality they are all cases of a general problem called the Abelian hidden subgroup problem. This problem is difficult to solve, especially with classical algorithms that have a so-called (sub) exponential complexity. It would take years to crack the current public key cryptography with even the most powerful of computers, assuming the system is implemented correctly.
2. How encryption systems are attacked
In general, an attacker of a pure cryptographic system has two basic methods at his disposal: using brute force to decrypt a message, trying all possible keys, or solving the mathematical problem that underlies it.
Brute force attacks typically take a long time and are directly dependent on the length of the cryptographic keys used (e.g., how many primes were used). In this case, nothing prevents the attacker from being successful, except time.
The solution of the mathematical problem is vice versa a problem of robustness of the encryption algorithm. A mathematical problem can be defined as difficult to solve in an unconditional or practical sense. For example, a math problem that is difficult to solve today may not be solved tomorrow, as the attacker's computing power increases. In cryptography, the term unconditional computational security refers to those problems that cannot be solved whatever the computing power of the attacker. While "practical" (practical computational security) are indicated those that are intractable with the computing resources currently available, but which could become tractable in the future.
3. The quantum threat
Researchers have known for decades that by the time it becomes possible to build a large-scale quantum computer, it could perform computations at a rate that threatens the cryptographic systems we rely on for security today.
Current public key cryptography has been enough for decades, but the recent development of quantum computers poses a real threat. Quantum computers are based on quantum physics rather than classical physics. In classical computer science, the basic unit of information is a bit, where the value 0 or 1 can represent two distinct voltage levels. In quantum computing, this unit is replaced by a qubit, where the value, a combination of 0 and 1, can represent an electron spin or a photon polarization. Quantum computers take advantage of the quantum phenomenon which allows them to solve certain problems much more efficiently.
In particular, the Shor algorithm and the related quantum algorithms, without going into details, have shown how it is possible to decrypt the keys used in asymmetric encryption with times that grow little as the length of the cryptographic keys increases (in other words, it allows to solve the problem of the hidden abelian subgroup in polynomial rather than exponential time, with respect to the length of the key). Therefore all the encryption algorithms that have the practical computational security attribute (eg RSA, ECC, AES) are violable in a time practically independent of the length of the keys (the attacker is able to calculate the encryption keys using a and once "normal").
Assuming that a sufficiently powerful quantum computer is developed, this algorithm lays the theoretical foundations necessary to corrupt the current public key cryptography, regardless of the size of the keys used.
While there is currently no suitable quantum computer, there are many reasons why organizations are already looking into secure quantum cryptography, including the following.
- It is difficult to estimate when quantum computing will reach such applicability as to corrupt current cryptographic systems. It is a new form of science and technology, with companies, governments and universities trying different approaches, and estimates range from ten to thirty years. However, the new quantum cryptography needs to be studied, implemented and tested before anyone develops a quantum computer.
- The transition of cryptographic systems can take many years. This is often overlooked, but the transition of any technology, especially in a large organization, is a difficult process and can take a decade to scale. Even a simple update of an algorithm or key can take a long time. It may require new infrastructure, developer training, redesign of old applications and new cryptographic standards, deployment of the new solution across the network. This applies to the whole structure on which a large part of the Internet is based today.
- In addition to the encrypted data in transit, the data storage must be secured. Companies are already storing encrypted data in compliance with legislative regulations (e.g., GDPR). While the quantum world today represents a relatively remote risk, and some data may not be as relevant in ten or thirty years, most data will still be sensitive. Data such as personal or health information (personal identifiable information / personal healthcare information PII / PHI) or government information, needs long-term encryption.
- Quantum security algorithms are safer against both quantum and classical attacks and, in some cases, are also more efficient and flexible.
So, what are the safe quantum algorithms to replace the current ones, and how can the growing need for security be met? The answers fall into two possible categories: quantum cryptography and post-quantum cryptography.
Enrico Frumento (1), Nadia Fabrizio (1), Paolo Maria Comi (2)
(1) CEFRIEL Polytechnic of Milan, Viale Sarca 226 - 20126 Milan
(2) Italtel, Via Reiss Romoli - loc. Castelletto - 20019 Settimo Milanese (Mi)
Works Cited
[1]
R. Jozsa, “Quantum factoring, discrete logarithms, and the hidden subgroup problem,” Computing in Science & Engineering, vol. 3, no. 2, pp. 34-43, 17 12 2001.
[2]
“Difficulty understanding the quantum algorithm for the abelian hidden subgroup problem,” [Online]. Available: https://qastack.it/cstheory/19129/difficulty-in-understanding-the-quantu....
[3]
Wikipedia, “Shor's algorithm,” [Online]. Available: https://en.wikipedia.org/wiki/Shor%27s_algorithm.
Images: GCN / web
The Quantum-Secure Net project (part 2/3): European product of Quantum Key Distribution
The Quantum-Secure Net project (part 3/3): European product of QUANTUM KEY DISTRIBUTION
