Secure cryptography in a post-quantum world

Communication is undoubtedly an essential part of human society, with the task of secure communication being motivated by the need to protect end users’ private data. More than ever, we are provided with an abundance of options for digital communication: emailing, messaging, image/audio clips, and video, among many others. Today’s society often blindly trusts that those means of communication are secure enough for data to be privately transmitted. How safe are we really, though, and for how long?

For centuries, transmitting confidential messages meant coming up with different schemes of encryption and decryption, and keeping those schemes secret. Over the years, new methods were discovered in which parties could send information perfectly securely, even if the scheme was known, as long as the parties had previously shared a secret key. It has become clear that the critical aspect of secure communication is, in fact, the security of those keys used for encryption/decryption, rather than the method itself. This has given rise to the problem of distribution of keys between distant users, a fundamental challenge in cryptography. Mathematical problems with computationally complex algorithmic solutions have been proposed  –  from discrete logarithms, and integer factorization, through to public key cryptography (PKC), to provide ways of key distribution as well as authentication. At present, PKC is used to secure most of the private data transmitted over the Internet.

One of the most promising modern applications of quantum physics is quantum computation. Quantum computers work in a fundamentally different way to traditional computers, by using quantum bits or qubits (represented by a two-level quantum system, such as the polarization of photons, or spin of electrons) instead of regular classical bits. Qubits display unique features of quantum mechanics, in particular superposition, interference, and entanglement, allowing for possibilities that are not feasible with classical bits. Quantum computers, which exhibit and exploit these unique features of quantum systems, can speed up computing capabilities exponentially, enabling computations otherwise impossible using classical computers. The various applications range from problems of optimization and searching unsorted data, to machine learning, simulations, and quantum chemistry, among others.

The relevance of quantum technologies in cryptography became apparent with Shor’s algorithm for quantum computers, based on efficiently finding prime factors of arbitrary integers. Interestingly, they are changing the landscape of information security in more than one way. On one hand, quantum computers are, in theory, able to break cryptography used every day to protect data, which is based on public key cryptography. Without being aware of it, we use these protocols all the time in our daily lives, from texting friends on the phone, to making purchases with cards at the supermarket. On the other hand, quantum protocols have been developed that can be used to perform these tasks, without being susceptible to attacks by any computer. To be able to break these protocols, you would have to break the very laws of physics! These quantum cryptography protocols use photons, which are the “quanta” of light, to encode information by manipulating different degrees of freedom, such as polarization or phase, and accurately measuring their state. Thus, quantum systems allow us to realize communication protocols that have superior security when compared to their classical counterparts.

Figure 1: The impact of quantum computing attacks

Despite the ongoing efforts and investments in the development of quantum computers, the timeline for the availability of a large-scale, fault-tolerant quantum computer is uncertain. This is because these computers are yet to overcome the challenges associated with increasing the available number of qubits, i.e., increasing their computational power. IBM recently unveiled their 127-qubit processor called Eagle[1]. Nevertheless, it is also important to understand that the migration from quantum-vulnerable to quantum-resistant protocols requires time and effort that are, again, difficult to estimate at this point. With the upcoming “quantum threat” of cryptographically relevant quantum computers (CRQC)[2], there is a dire necessity for secure communication schemes that are resilient to quantum attacks. Therefore, it is wise to start looking into quantum-secure protocols that have superior security when compared to their classical counterparts.

Quantum key distribution (QKD) was the first quantum protocol to receive mainstream attention due to two main features. Firstly, it achieves the task of key distribution, a problem at the heart of achieving secure encryption; second, it does so while being “unconditionally secure,” as opposed to classical protocols that rely on the difficulty of specific computational problems. During QKD, two parties (traditionally called Alice and Bob) share a collection of quantum systems and then make measurements on them, such that they can establish a secret key between themselves on which a third party has no information. In fact, the laws of physics guarantee that any attempt to try to eavesdrop on the quantum channel to distribute keys can be detected by Alice and Bob through communication over an authenticated channel.

Beyond the key distribution problem for secure communication between two parties, another important scenario to consider is that of multiple parties interested in performing joint computations. These computations may use private inputs from individual parties and should be privacy-preserving in the sense that a user’s private inputs are not revealed to any other party during the computation. The famous Millionaires’ problem is an example of such a computation, where two millionaires want to determine who is richer while keeping their individual wealth private (Figure 2). This task, known as secure multiparty computation (SMC), is of extreme importance when involving scenarios with multiple parties that do not necessarily trust each other (as opposed to QKD, in which the two parties trust each other and try to keep their shared key secret from external eavesdroppers). This guarantee of keeping users’ private data secret is further enforced by strict data protection laws. Volumes of data like the approximately 64 zettabytes generated in 2020[3] and the 181 zettabytes expected by 2025 are a great source of power. Having access to an SMC service and performing arbitrary computations will provide ways to profit from valuable data from multiple sources, such as through privacy preserving data mining (PPDM) (Figure 3).

Figure 2: The Millionaires’ problem, first proposed by Andrew Yao in 1982, as an example of secure computation, as well as its solution

At Capgemini Engineering, Portugal, we are looking into ways of performing the task of SMC with quantum technologies and exploring how the use of quantum resources can provide security against attacks that impact PKC. Interestingly, the techniques used in QKD have been found to be useful for other tasks beyond key distribution. In our Quantum Lab, we prepare and measure quantum systems in very similar ways to QKD – by encoding information in the polarization states of photons and performing measurements. This means that all the technology and infrastructure being developed so far to support QKD can be very easily adapted to implement our SMC scheme.

Figure 3: Companies can, for instance, provide digital services to users in exchange for their information, which can be analyzed in a secure way through privacy-preserving computations.

Finally, considering that we are moving towards a society with an increasing application of IoT, there are many concerns about how private information will be handled when nearly every device is connected and potentially collecting information about us. The security aspect of our private data is clearly crucial to us as individuals as well as to businesses and governments and having reliable protocols for secure communication and computation will be one of the most fundamental challenges ahead.

---

[1] IBM – https://research.ibm.com/blog/127-qubit-quantum-processor-eagle

[2] NSA FAQs – https://media.defense.gov/2021/Aug/04/2002821837/-1/-1/1/Quantum_FAQs_20210804.PDF

[3] Statista – https://www.statista.com/statistics/871513/worldwide-data-created/