Alice, Bob, and Eve: How quantum technology can secure against adversaries.

In this article, secure communications scenarios are described. The security risk that is taken when using RSA or ECC encryption is evaluated while the principles behind the alternative, quantum key distribution, is explained. 

In cryptography for communications, the names Alice, Bob and Eve are frequently used to describe an everyday scenario. The story goes as follows. Alice and Bob work far apart on a top-secret project, and, because of this, they need to exchange top-secret information using a communication medium. As the nature of things are, Eve has a large interest in intercepting the communications that Alice and Bob send to each other. To prevent Eve from reading their messages, Alice and Bob need to use techniques to ensure that they can send messages to each other while Eve has no way of discovering what the messages are.

At present, there are a handful of efficient ways for Alice and Bob to communicate securely using encryption. The main difficulty for them is not to encrypt their own messages, but rather to communicate the decryption algorithm securely. Think about it, while you can strongly encrypt a message using a secure algorithm, how do you tell Bob how you encrypted the message without Eve finding out? You can’t decide to also encrypt the decryption method, because how do you then communicate the decryption method for the decryption method?

The solution to this problem is known as public key cryptography. The solution is to use a mathematical method that allows you to generate a one-way encryption key. That means, if you use this key to encrypt a document, you cannot use the same key to decrypt the document. This kind of key is called a public key. There would then be another key that pairs with the public key which can decrypt anything that was encrypted with the public key. This key is known as the private key.

In the scenario where Alice and Bob want to communicate, Alice sends Bob a public key that he then uses to encrypt the key with which he will encrypt the documents he wants to send. Only the private key that Alice has can be used to find out how Bob intends to encrypt his documents. Eve cannot get Alice’s private key because the private key is never transmitted, and without the private key there is no way to decrypt Bob’s message. Not even Bob himself can decrypt his own message; only Alice can by using the private key.

For many years now, a good implementation of the public-key method has worked very well to ensure that communications stay secure. Unfortunately, that is all changing now. The advent of quantum computers (QCs) has placed Alice and Bob’s secure communications in peril. Ideally, the public key that Bob uses should not allow anyone else to discover the private key Alice has. We can state this as a mathematical condition that says that, if we pair the private key used for decryption with a public key for encryption, it should be very hard to discover what the private key is based on our knowledge of the public key. With QCs, it is no longer hard to do so.

To give a quantitative measure, with a classical computer the number of steps required to factor an RSA public key scales exponentially (factoring an RSA public key yields the corresponding private key that only Alice is supposed to have). With a quantum computer the number of steps to retrieve the private key scales better, with what is known a polynomial time (Shor, 1995). A comparison of the scaling is represented graphically in the image below.

The quantum speed-up is significant when compared to the classical case, and it becomes evident why RSA is at risk from quantum computation.  

If Eve is in possession of a QC, she would intercept the RSA or ECC public key that Alice sends to Bob, run an algorithm on the public key using her immensely powerful QC, and solve for Alice’s private key. Then, when Bob sends his encrypted documents to Alice, Eve would know exactly what the decryption key is, and she would discover all the information Bob sends to Eve. Therefore, we can see that a QC allows for destroying the single most critical part of secure communications: the means to securely communicate decryption keys. The only way that Alice and Bob can now securely communicate is to pre-arrange what decryption keys they will use when they meet each other so that they don’t have to communicate these keys at a later stage. The problem with this is that the decryption keys can’t be reused indefinitely - and more importantly - you need to meet in person with anyone whom you want to communicate with later. A better method would, therefore, be required to ensure that secure communications are still possible without such large limitations. That is where quantum key distribution (QKD) and quantum resistant cryptography comes in.

Due to the length of time that public key cryptography has been around for, the particular mathematical principles that it relies on have been extensively researched. This research has led to algorithms that are implementable and use the tremendous power of QCs to break the security of public key cryptography. RSA, ECC, DH, and all algorithms that derive their security from the same principles as these algorithms are at risk.

All is not lost, however, since quantum resistant algorithms that are currently in development would provide better security. Such algorithms, including AES symmetric keys, would be able to resist quantum computers by the fact that only a brute-force search on the decryption key would be possible. While it is not currently known whether such a brute-force search will be possible in practice, Grover’s algorithm theoretically speeds up brute-force search by a factor of N/2 (Bennett, Bernstein, Brassard, & Vazirani, 1997; Chen et al., 2016). Therefore, AES-128 will effectively have a key space of 128/2= 64 bits. We can see that AES-256 would have the same key strength as AES-128 in the presence of quantum computation, and AES is not considered to be at risk. Furthermore, it has been found that it is not possible to derive an equation that is faster than Grover’s algorithm for a purely brute-force search (Bennett et al., 1997).

Public key encryption methods have been found that provide similar security strengths to AES encryption against quantum computation. One of these methods is called Lattice Based Cryptography, which relies on the difficulty of finding the shortest vector between the lattice points in a lattice. Research into breaking this type of cryptography has been ongoing, and no quantum or classical attack has yet been found. While the security of such newer systems could yet prove to be absolute, at present this has not been established. Therefore, the only provably¹ secure communication method at present is QKD.

The remaining challenges that cryptography faces are that of authentication and verification. In effect, cryptography also needs to provide a way to add a signature to a document so that someone can verify the identity of the person who signed the document. At present signatures using the laws of quantum mechanics have been proposed, and initial implementations are promising. This would extend the concept of provably¹ secure QKD communications to provably¹ secure quantum digital signatures. An added advantage of the proposed quantum digital signatures schemes is that they offer non-repudiation. Non-repudiation means that if one person accepts the communication, they can prove that other receivers also accepted the message, and this is a requirement for the security of transactions (Jain, 2015). The principles of quantum digital signatures will be discussed in a future article.

QKD derives its security from the Heisenberg uncertainty principle. The Heisenberg uncertainty principle states that it is impossible to measure both the position and momentum of a quantum state exactly. If it is impossible to measure a state perfectly, then it is impossible to copy that state perfectly. QKD uses this principle to distribute symmetric encryption keys securely. In the most widely used method, referred to as the BB84 protocol, photons are transmitted with specific orientations, known as polarisations. To ensure that the communications cannot be intercepted, the photon orientation is changed periodically. The photon measurement equipment has to be set up according to the orientation of the photon, and an incorrect orientation would lead to an incorrect measurement. Attempting to read the photon polarisation would then result in a probability of setting the measurement equipment incorrectly.

An inaccurate measurement would not be a problem when Alice and Bob are communicating since they would discard the erroneous measurements that Bob made and only use the valid ones. The incorrect measurements can be determined by Bob communicating over a public line what orientation he used and Alice confirming the correct measurements. Communicating the measurement orientation does not allow Eve to deduce the data sent because the orientation of the photons can either be vertical or horizontal in one measurement or diagonal in the other. Stated otherwise, there are two measurement orientations that each have two possible photon orientations and Eve can only guess the photon orientation correct with 50% probability if she knows the measurement orientation. 

If Eve attempts to intercept the communications, she would measure the photons incorrectly some of the time as well. An incorrect measurement causes the photon to emerge with its orientation changed. So detection of a changed orientation constitutes a compromised communication channel. In this case, Bob would detect this when Alice tells him he should have a valid photon measurement, but he did not measure one. Alice and Bob would respond by not exchanging communications until the eavesdropper has been located and removed, or she fled.

While the BB84 protocol has been very successfully applied in practice, other means exist that may yield more reliable and faster QKD systems. Continuous variable QKD (CV-QKD) has been noted as one such a protocol. In contrast to the BB84 protocol that uses single photons to ensure that a quantum state is maintained, CV-QKD encodes data in the amplitude and phase of a coherent light signal. Coherent light means that multiple photons are exactly in phase with each other, and such a state can be seen as a form of entanglement (Streltsov, Singh, Dhar, Bera, & Adesso, 2015). Hence, the Heisenberg uncertainty principle can be applied to CV-QKD to say that the amplitude and phase of the photons cannot be reliably copied. The lack of ability for Eve to reliably copy the quantum state then leads to the ability to detect interception of communications. CV-QKD is expected to yield QKD data rate improvements in the next few years (Lance & Leiseboer, 2014).