We often read or hear that Quantum Computing will strongly impact certain activities such as financial transactions or e-commerce because no cryptography could resist it.
In May 2018, during a meeting of The Churchill Club in San Francisco, Arvind Krishna, director of IBM Research, announced that: “Anyone wishing to protect its data for the next 10 years must switch to post-quantum cryptography”. It was a loud and clear message: in 10 years, Quantum Computing would be able to break all the current cryptography.
Cryptography combines mathematical algorithms and processes to protect the confidentiality, integrity and authentication of data that we call messages. Just like the secret messages you probably sent to your friends during your high-school years using ink made of lemon juice.
Some experts even speak of post-quantum cryptography to emphasize that there would be one cryptography before and one cryptography after the advent of Quantum Computing.
Urban legend or true paradigm shift? Let’s try to elaborate a bit further.
First of all, there should be no confusion between quantum cryptography and post-quantum cryptography. Quantum cryptography uses quantum phenomena. Post-quantum cryptography, by misuse of language, refers to non-quantum cryptographic algorithms that cannot be solved much faster by a quantum computer than by a conventional computer.
Cryptography
Let begin with a little reminder about (classical) cryptography.
There are 3 main families of cryptographic algorithms and applications:
- Hashing functions : They can generate a kind of signature, a virtual hallmark or seal to guarantee and challenge the integrity of a file, for example. When you download a large file on a Dropbox-type service, you can use this technology to verify that the downloaded file is right. Certificates and electronic signatures also exploit these features. For example: MD5, SHA-1, SHA-2.
- Symmetric encryption: The oldest technique of cryptographers, often called ‘by secret key’. In essence, symmetric cryptography has existed since Humanity needs to protect private or sensible information. As a drawback, one must first find a way to secretly distribute the (secret) key to those who want to exchange securely information. Then, the sender can encrypt with the secret key and the receiver can decipher with this same key. This technology is very efficient in terms of computing power and memory requirements. By cons, it requires the exchange of the secret key with all the potential disadvantages: loss, theft, misuse for compromise, etc. For example: DES, 3DES, AES.
- Asymmetric encryption: This technique, from the 70s, often called ‘by public key’, avoids the exchange of the secret key made necessary with symmetric encryption. On the other hand, it consumes computing time and memory because it uses the factorization of integers or logarithmic calculations. It has revolutionized and still revolutionizes our lives every day: e-commerce, crypto-currencies, blockchain, PGP, etc. For example: RSA, elliptic curves.
In general, a cryptosystem uses several types of cryptography. For example asymmetric encryption can be used to secretly exchange the private keys of the symmetric encryption, which will then actually encrypt the data.
Asymmetric cryptography is based on the factorization of large integers into prime numbers. Prime numbers are mathematical objects that have very particular properties. These are integers that are only divisible by 1 and by themselves. They are therefore all odd, except 2 which is the only even prime number. Any integer can be broken down into prime numbers. This process is named factorization.
For example:
- 12 = 2 x 2 x 3 ; which can be written: 22x 3
- 457 = 457 (457 is a prime number)
- 458 = 2 x 229
- 459 = 33x 17
If we consider two prime numbers of large size (for example of 250 digits each) and multiply them, it becomes almost impossible to achieve the reverse calculation (a factorization in prime numbers), even for an extremely powerful computer. This particularity of non-reversibility of computation is at the base of symmetric cryptography.
In 1994, Peter Shor, then professor at MIT, developed a quantum algorithm able to factorize integers faster than with a conventional computer. The quantum computation time to factorize became polynomial with the number of digits and no longer exponential. This discovery convinced some researchers it would be possible to break – theoretically at least – many asymmetric cryptographies, known as public keys cryptographies.
However, at the technical implementation level, this discovery needs that quantum computer may store and process very large integers which is far from being true at the moment.
In 1996, Grover proposed a new quantum algorithm that could efficiently search for items in an unordered list or unstructured database. This algorithm makes it possible to speed up the search for a certain type of encryption key (symmetric encryption). Indeed, the time needed to break the cryptography by brute force (trying all combinations), is only 2n/2 iterations instead of 2n in classical computing.
Since then, the concept of post-quantum cryptography has been introduced by the National Institute of Standards and Technology (NIST) to designate any algorithm that can withstand Shor’s Algorithm.
This new class of algorithms now exists in two categories: the most interesting algorithms are considered unbreakable by mathematical proof (formal proof), the others are considered sufficiently resistant in terms of the number of qubits and decryption time which are required to break them.
For example, it has been mathematically proven that the Lattice algorithm class is resistant to quantum computers. No algorithm known to date can break this type of cryptography.
In the case of symmetric cryptography, in the current state of knowledge, it is possible to keep using the current algorithms if the size of the encryption keys is increased. For example, for the widely used AES algorithm, doubling the key size from 256 bits to 512 bits may be acceptable.
Still in the current state of knowledge, hash functions are not impacted by Quantum Computing (although there have recently been many flaws detected and exploitable by classical computing).
By the way, ‘state of knowledge’ is a fuzzy term because nobody knows what governmental agencies actually know…
Consider that we want to evaluate the resistance of a message with encryption, which means encrypted using a cryptographic algorithm. We must immediately take into account the creation date of the encrypted message. There are three cases:
- The message was encrypted a long time ago (about ten years ago). There is a good chance that the algorithm used has already been weakened or broken. It is also possible that the current computing power – classical computing – can decipher it by brute force. The brute force process can decipher by trying all the possible combinations, which can take a few minutes to a few years. Remember for example the breaking of the passwords of the first generation of Wi-Fi networks which exploited a weakness of the algorithm allowing the attacks by brute force.
- The message is encrypted today. The choice of the cryptographic algorithm and the size of the key should be done according to the requested level of confidentiality and integrity but also the availability of local encryption/decryption tools. Most current algorithms, if properly implemented, help ensure a high level of security for many years to come. However, in twenty years, when quantum computers have evolved, message will most likely be breakable.
- The message will be created and encrypted in the more or less close future. It seems clear that post-quantum cryptography will become the de facto standard. As any technological innovation, demanding and costly, it is likely that it will be limited initially for applications requiring a high, persistent and guaranteed level of security.
The advent of a quantum computer with sufficient capacity for threatening classical cryptography is still distant. In the meantime, we can think that research on post-quantum cryptography will be well advanced, and that the change in cryptographic paradigm can be widely anticipated.
Quantum Key Distribution
Quantum Key Distribution (QKD) is one of the main and most promising applications of Quantum Physics, thanks to qubits entanglement. Please keep in mind that the reading (measurement) of the state of one of the entangled qubits irremediably leads to the loss (collapse) of information on the other qubit. Theoretically this property should allow to detect any attempt to read a quantum encryption key by a third party. Here is the famous BB84 Protocol born in 1984.
This protocol is often misunderstood.
We have seen that the main problem of symmetric cryptography was the distribution of the private key to only those authorized to encrypt and decrypt messages. If the key is stolen or intercepted by a third party, the latter can decrypt the messages but can also encrypt fakes, without the knowledge of authorized persons. For example, during the Second World War, the Germans ignored for a long time that the Allies broke their Enigma system and could read their secret messages.
In classical cryptography, we can use public-key asymmetric cryptography to securely exchange the private and secret keys of symmetric cryptography that will be used to encrypt messages. However, for some extremely private communications, you’d better not use asymmetric cryptography for private key distribution.
BB84 Protocol was proposed in 1984 by Charles H. Bennett, IBM T.J. Watson Research Center, and Gilles Brassard, Montréal University.
A photon can be polarized along two axes (or bases): H: Horizontal (0) or V: Vertical (Pi/2) and A: Antidiagonal (Pi/4) or D: Diagonal (3pi/4). The fictitious graphical angles are in parentheses for your better understanding.
Consider arbitrarily that the polarizations V and D represent the information bit ‘1’, and respectively H and A, the information bit ‘0’.
The sender will send to the receiver a series of photons polarized randomly along the rectilinear and diagonal axes (H, V, A or D). This transmission is done via a quantum communication link, usually by optical fiber.
In Cryptography, we like to personalize the roles of the sender and receiver. It is common to name Alice the sender of a message and Bob the recipient. We also introduce the (wicked) Eve who will try to intercept the messages between Alice and Bob (love affair?).
The recipient will receive this sequence (with some photons lost due to defects in the transmission and/or the detector) and will measure their polarization along an axis (rectilinear or diagonal) randomly chosen for each photon.
Once all the measurements have been done, the recipient will use an unsecured communication channel such as the Internet to inform the sender of the measurement axis he has used for each photon.
The sender compares this information with his own polarization choices and informs the recipient of which results are correct.
The sender and the receiver compare their results and reject all the results the recipient was wrong (the recipient did not measure with the correct axis) or if the photon was lost.
To spy Alice and Bob, Eve must intercept the photons sent by Alice, then, for each photon, measure its polarization along one of the axes, rectilinear or diagonal. But especially, knowing that the measurement may change the photon state, she must forward a new polarized photon for each intercepted photon.
Unfortunately for Eve, she does not know the axis chosen by Alice for each photon. Since she can measure the intercepted photon only on one axis and it is impossible to copy a photon (Heisenberg’s uncertainty principle), it means that chances are she is wrong by sending back the photon with the wrong polarization. As Bob has also a chance over 2 not to select the right axe, Eve will be wrong once in four.
To summarize:
- If the communication has not been eavesdropped by Eve or a third party, the probability of a correct measurement is 3/4 (that is, 1/2 * (1 + 1/2)).
- If, on the other hand, Eve has intercepted the message, the probability is 5/8 (that is, 1/2 * (3/4 + 1/2)).
The sender and the recipient may understand that they have been eavesdropped if the result does not match the right probability. If they have been eavesdropped, they just have to repeat the process.
If the transmission has been secure, part of the information transmitted by the quantum channel may become the secret private key.
In 1989, the two researchers validated their theory by achieving QKD practically over a distance of 32 cm.
The advanced reader may have perhaps noted that this protocol is only valid if Eve does not pretend to be Bob to Alice. So Alice and Bob should authenticate each other first!
In 1991, Ekert published a secret key distribution protocol based on the Bell’s theorem.
In March 2019, Singaporean company SK Telecom announced its first Quantum Security Gateway, intended to be installed in communicating (and possibly autonomous) cars to protect all vehicle systems and all communications. This security would be provided by a quantum random number generator and quantum distribution of encryption keys. As a reminder, in 2018, SK Telecom took a majority stake in the Swiss start-up ID Quantique (IDQ), which for several years had been protecting sensitive networks such as those between two banking datacenters.
The first quantum cryptography systems appeared at the beginning of the 2000s. Some systems were broken or weakened but as usual in this domain, they were eventually defects of hardware or wrong software implementations. Quantum principles have never been questioned. Some protocols were also biased by design.
The researchers have then developed cryptographic protocols independent of the hardware. In early 2019, Chinese scientists successfully attacked these new protocols. A complicated story of laser resonance, but the same researchers found the countermeasure. A Cat and Mouse game…
Copyright ADVIXO 2019 / F. Franchin
