In first article we have introduced what are the main problems of modern cryptography, or rather, what are the mathematical limitations that are exposed by the world of quantum computing. The problem is complex and in recent years research has attempted to solve the dilemma by defining cryptographic methods that offer some kind of quantum strength.
This second part explores precisely these aspects, introducing the topic of quantum and post-quantum cryptography and in particular the technology of Quantum Key Distribution (QKD) which represents a particular technology in this context, able to offer the so-called perfect secrecy.
Quantum cryptography works on quantum computers and is "safe" against both classical and quantum attacks, in the sense of attacks conducted using quantum computers. This form of encryption is secure based on the laws of quantum physics. This means that quantum computers are both the problem (ie they can be used to "break" cryptography) and the solution (ie they can be used to "do" cryptography). However, there are some problematic aspects of using quantum cryptography when compared to "classical" public key cryptography. Quantum cryptography requires both parties to have access to a quantum computer and can be very expensive, impractical and therefore inefficient at the moment.
Quantum cryptography is already in development and use, however, given the current costs, it is unlikely to replace all current cryptographic use cases, especially in the near future.
Post-quantum cryptography is a form of classical cryptography (i.e. it does not require quantum computers) that is based on quantum strength mathematical foundations and works on current computers. In essence, post-quantum cryptography is a system that is based on non-quantum computers, just like the current public key cryptography, but on different mathematical principles, not easily solved even by a quantum computer. It is important to note the distinction because the term "post-quantum" is often used, meaning "quantum" and vice versa. The difference is that quantum cryptography uses a quantum computer, and post-quantum cryptography doesn't. However, although the researchers have developed ciphers that are resistant to Shor's algorithm, post-quantum cryptography is not as robust as quantum cryptography (it does not have the attribute of unconditional computational security): it is not possible to prove that the developed algorithms are not attackable in polynomial time. This means that there is still no formal proof of the real security of these methods, similar to what happens for the current public key cryptography.
Given the complexity of quantum cryptography, it is however of great interest to study other solutions, not based on quantum technologies, which increase the degree of security compared to the current public key cryptography. This makes it necessary to have attack-resistant cryptographic systems, conducted by quantum computers, that can run on non-quantum computers (ie, the worst case where the attacker has a quantum computer at his disposal is the attacker no).
Quantum computing and applications to symmetric cryptography
It is essential to underline that, what has been said so far, speaking of attacks on asymmetric forms of public and private key cryptography, does not apply to symmetric cryptography (which makes use of the same key shared between the communicating parties). Shannon in 1949 demonstrated that with symmetric cryptography the conditions exist to achieve perfect security (perfect secrecy) or unconditional.
First of all a brief summary. Public key cryptography, or asymmetric cryptography, guarantees confidentiality. Suppose one party (Alice) wants to send another party (Bob) a secret message. Alice encrypts her message with Bob's public key, creating an incomprehensible ciphertext, which she sends to Bob. Bob decrypts the ciphertext to find out the original message. Note that the communication is one-way or "asymmetric"; Alice cannot decrypt Bob's messages as she does not have the private key. Public key encryption is asymmetric and is generally slower than symmetric encryption schemes such as AES. For this reason, public key encryption is mainly used to establish a secret key shared between the parties. That is, the secret message sent by Alice to Bob is a secret key, and this secret key is then used to efficiently encrypt and decrypt the data using symmetric encryption.
Alice and Bob need a secure method to share their symmetric key, this step is called Key Establishment Mechanism (KEM). Asymmetric key encryption is then used in the initialization phase of the communication channel, to allow Alice and Bob to share a symmetric key without interference (this scheme, initially proposed by Diffie-Hellman, then became the basis of the communication protocol SSL).
What is Quantum Key Distribution?
As mentioned in the previous paragraph, the conditions exist to make symmetric encryption an unconditionally secure encryption method, always assuming that an attacker does not know the key. The problem is therefore that of distributing the keys without being intercepted. This problem leads to the birth of the Quantum Key Distribution (QKD), which is a system based on a "quantum channel" (optical fibers or strings "Free space" satellite) to distribute symmetric keys in a non-interceptable way. As already mentioned at the beginning of the article, QKD is a technology related to quantum computing due to the fact that it uses the same mathematical "terminology": it can be said that in this case we speak of "quantum" without the "computing" attribute .
QKD in particular uses the quantum properties of photons (i.e., poor interaction with matter and the ability to maintain their quantum state in a suitable medium, such as an optical fiber, for a few microseconds, in the form of phase or angular momentum) to exchange a symmetric cryptographic key, which can be used to encrypt messages which are then exchanged through a "traditional" channel. The security of QKD is based on fundamental laws of nature, which are insensitive to increasing computing power, new attack algorithms or quantum computers.
The safety of QKD is based on a fundamental feature of quantum mechanics: due to the Heisenberg uncertainty principle, following which one cannot measure a physical quantity without interfering with it, the act of measuring the state of a quantum of light destroys it. With this type of systems, security derives precisely from the fact that any malicious actor who tries to intercept an exchange of information will inevitably leave detectable traces in the form of errors in the transmitted key. At this point the two parties Alice and Bob can decide to use a new symmetric key or stop the transmission.
The QKD formally also has a second advantage, it being possible to demonstrate that it is a safe system from the point of view of information theory (information-theoretically secure). Its security derives exclusively from information theory, that is, it is not based on the alleged difficulty of the mathematical problems used, and is therefore secure even when the opponent has unlimited computing power.
Another important operational feature of QKD, when used sequentially to produce successive encryption keys, is the called property "forward-secrecy" of the keys: the keys subsequently exchanged on a QKD link, are independent of each other. Therefore, the potential compromise of one of them cannot lead to the compromise of the others. This is a particularly valuable feature for both high-security networks and long-term data storage (everlasting security).
A QKD implementation typically includes the following components:
Figure - Alice and Bob are connected through a QKD Link (made up of the pair of Ethernet and fiber optic connections) and exchange symmetric cryptographic keys, to then establish a symmetrically encrypted secure connection. Eve is listening on the QKD link and trying to intercept the encrypted key or stream
A fiber optic transmission channel to send qubits of information (qubits) between the transmitter (Alice) and the receiver (Bob).
A traditional and public but authenticated communication link between the two parties to carry out the key-post-exchange phases
A key exchange protocol that leverages quantum properties to ensure security, detecting wiretaps or errors, and calculating the amount of information that has been intercepted or lost.
Enrico Wheat*, Nadia Fabrizio*, Paolo Maria Comi+
* CEFRIEL Polytechnic of Milan, Viale Sarca 226 - 20126 Milan
+ Italtel, Via Reiss Romoli - loc. Castelletto - 20019 Settimo Milanese (Mi)
To learn more:
CSO Insiders, “What is quantum cryptography? It's no silver bullet, but could improve security, ”12 3 2019. [Online]. Available: https://www.csoonline.com/article/3235970/what-is-quantum-cryptography-i....
T. Laarhoven, M. Mosca and J. vd Pol, “Solving the Shortest Vector Problem in Lattices Faster Using Quantum Search,” Post-Quantum Cryptography, pp. 83-101, 2013.
O. Regev, “Quantum Computation and Lattice Problems,” SIAM Journal on Computing, vol. 33, no. 3, pp. 738-760, 2004.
Research Institute, “A Guide to Post-Quantum Cryptography,” 16 5 2019. [Online]. Available: https://medium.com/hackernoon/a-guide-to-post-quantum-cryptography-d785a....
C. Shannon, “Communication Theory of Secrecy Systems,” Bell System Technical Journal, vol. 28, no. 4, pp. 656-715, 1949.
W. Diffie and M. Hellman, “New directions in cryptography,” IEEE Transactions on Information Theory, vol. 22, pp. 644-654, 1976.
Akamai, “Enterprise Security - SSL / TLS Primer Part 1 - Data Encryption,” 2016. [Online]. Available: https://blogs.akamai.com/2016/03/enterprise-security---ssltls-primer-par....
R. Alléaume, C. Branciard, J. Bouda, T. Debuisschert, M. Dianati, N. Gisin, M. Godfrey, P. Grangier, T. Länger, N. Lütkenhaus, C. Monyk, P. Painchault, M. Peev, A. Poppe, T. Pornin, J. Rarity, R. Renner, G. Ribordy, M. Riguidel, L. Salvail, A. Shields, H. Weinfurter and A. Zeilinger, “Using quantum key distribution for cryptographic purposes : A survey, ”Theoretical Computer Science, vol. 560, pp. 62-81, 2014.
W. Diffie, P. v. Oorschot and M. Wiener, “Authentication and Authenticated Key Exchanges,” in Designs, Codes and Cryptography 2, Kluwer Academic, 1992, pp. 107-125.
CSA Cloud Security Alliance, “What is Quantum Key Distribution ?,” in Quantum-Safe Security Working Group.