Cryptography on a Quantum Computer

Quantum computing research is developing really fast, and we witnessed incredible advancements toward the realization of a practical quantum computer in the last few years. Since 1994, it is a well-known fact that a scalable QC would threaten the security of most cryptographic protocols in use nowadays. This knowledge, in turn, has led to the development of a new branch of cryptography dubbed “quantum-resistant”, or “quantum-safe”, or “post-quantum” (there is sometimes ambiguity in these definitions, but a common meaning is “cryptography that you can use today, but which is supposedly resistant against some form of quantum attacks”).

This blog post, however, is not about quantum-resistant cryptography. We are going to discuss quantum cryptography instead; cryptography that you can run on a future quantum computer, to protect quantum data. Not to be confused with quantum key distribution (QKD), which is a specific subfield of it, quantum cryptography is the manipulation of data at a quantum level in order to achieve tasks such as encryption, digital signatures, and fully homomorphic encryption. Some of these classical tasks have a natural analog in the quantum realm; some others are impossible classically but possible quantumly, or vice versa.

In this blog post, we are going to have a look at the quantum analog of one of the most basic cryptographic functionalities: encryption.

Scenario

Quantum computing is usually considered a threat in the world of IT security. However, this is only true as long as just adversarial actors have access to such technology. If we look at the evolution of classical computing, we know that such a scenario can only be transient, caused by the initially prohibitive cost of the technology, and that mass adoption follows soon. And, with mass adoption, networks arise. So, if we look at a future scenario where quantum computers are ubiquitous and connected through dedicated networks (a “quantum internet”), we have to consider how to secure such a new communication and computing infrastructure.

Quantum mechanics exhibits particular phenomena which make IT security for quantum hardware a completely new challenge. For example, quantum data cannot be copied; this would make it impossible, e.g., to perform a log audit of traffic. On the other hand, quantum data can be entangled; this allows for decentralized joint computing through quantum teleportation, which might very well be considered a sort of “parallel computing on steroids”. In any case, by “quantum data” we mean a logical representation of quantum information, usually represented through a mathematical formalism describing the state of a physical system. All the power of quantum computing comes from the fact that performing computation on this kind of information allows for certain operations which are impossible classically, and that in some cases lead to speedups. So, if we look at a future where data is stored in quantum databanks and transmitted through, for example, optic fibre quantum data networks, if we want to protect such data from theft or manipulation we have to design new cryptographic algorithms that act natively on this kind of information, and which therefore can only be run on a quantum computer proper.

To put it differently: we cannot use existing tools such as AES, or the post-quantum cryptography algorithms standardized by NIST in order to secure quantum data. We have to come up with entirely new ideas.

Quantum Encryption: the Basics

In the following, we will use the term “classical” for “non-quantum”. The most basic security task in classical cryptography is symmetric-key encryption. For example, if we want to protect one single bit of plaintext information, there are only two possible operations that we can perform to hide its value in a reversible way:

Either the identity, i.e., we leave the bit unchanged; or
The Boolean NOT operation, i.e., we flip the value of the bit.

Given this observation, we can devise a very basic form of symmetric-key encryption: we use a secret bit as a key, and according to the value of the secret bit we flip (secret bit = 1) or not (secret bit = 0) the value of the plaintext, obtaining a new ciphertext bit. And, given the ciphertext and the secret bit, we can recover the plaintext by performing the operation in reverse. This very simple system is the well-known one-time pad cryptosystem (OTP) and it can be extended to plaintexts of many bits by using larger secret keys: one bit of secret key for every bit of plaintext. In simple terms, the OTP is a bitwise XOR of plaintext and key, that we write as $x \oplus k$ . It is a very insecure system but it is sufficient for an introductory example.

Now, as a first step what we want to do is to find a quantum analog of the OTP to encrypt quantum data. The difference with the classical case is that, given a single qubit, there are now four possible elementary reversible operations, not two:

We can leave the qubit unchanged, as in the classical case; we represent this operation as the unitary evolution $I$ (“identity”);
Also, as in the classical case, we can flip the basis elements, swapping the $\left| 0 \right\rangle$ and the $\left| 1 \right\rangle$ components (sort of a “quantum NOT”); we denote this unitary evolution with the symbol $X$ ;
However, quantumly we can do more: we can apply a Fourier phase shift, which turns a state of the form $\left| 0 \right\rangle + \left| 1 \right\rangle$ into $\left| 0 \right\rangle - \left| 1 \right\rangle$ , i.e., it changes the relative phase of the two components of the canonical basis; we denote this unitary evolution with the symbol $Z$ ;
Finally, we can apply both a 0/1 flip and a phase flip, i.e., the operations $X$ and $Z$ at the same time; we denote this unitary evolution with the symbol $Y$ ;

These four operations $I, X, Y, Z$ are called Pauli operators. Since they are 4, we will need two bits of classical secret key to label one of them (one can also consider using a quantum secret key, but for technical reasons having a classical key is always considered desirable, because it simplifies key management and transmission). So, the first important thing we have to remember is that, unlike in the classical case, one needs two bits of key in order to encrypt one single qubit. Pauli operators are also elementary gates, and any unitary operation on 1 qubit can be approximated by a linear combination of Pauli operators.

Pauli operators can also be applied to states of many qubits, by applying one of the 4 operations qubit-wise: for example, applying the 3-tensor Pauli $X \otimes I \otimes X$ to the state $\left| 000 \right\rangle$ produces the state $\left| 101 \right\rangle$ . In general, the set of all possible unitary evolutions that can be realized by only using weighted sequences of Pauli operators is called the Pauli group. Operations of the Pauli group have the property that modifications of one single qubit in the (quantum) plaintext only affect one single qubit in the (quantum) ciphertext.

The system we just described is indeed called “quantum one-time pad” (QOTP), and it works by encrypting an $n$ -qubit quantum state into another $n$ -qubit quantum state using $2n$ bits of classical secret key.

Analogously to the classical case, this is the simplest form of quantum encryption, and it is only one-time quantum secure (QIND). However, it is an interesting building block for constructing more advanced secret-key quantum encryption schemes (SKQE).

Symmetric-Key Quantum Encryption

The QOTP is a very simple system, but (like its classical counterpart) it is only secure if the same key is never used twice, which is an unacceptable limitation in most practical scenarios. If we want to encrypt a quantum state with a symmetric-key system which remains secure even if we reuse the same secret key many times, we need to take inspiration from classical cryptography.

A simple way to transform the insecure OTP scheme into a practical scheme is through the use of pseudorandom functions, or PRF in short. A PRF is a classical algorithm that takes as input a value and a secret key, and outputs another value, not necessarily in a reversible way, but such that the output is indistinguishable from true randomness without knowledge of the secret key used. For example, a very simple construction of a PRF with secret key $k$ , input value $x$ , output $y$ can be done using a hash function $h$ such as SHA3 in the following way: $y = h(k \| x)$ , where $\|$ denotes concatenation.

A PRF $f$ cannot be used directly to encrypt data (because it is not necessarily reversible), but can be used to strengthen the OTP by “randomizing” it for every fresh encryption. More precisely, whenever one wants to encrypt a plaintext $x$ with a key $k$ , do the following:

Generate a fresh random value $r$ ;
Compute $y = x \oplus f(k,r)$
Output ciphertext $(y,r)$

Using the same key $k$ and the same PRF $f$ , one can decrypt the ciphertext as $x = y \oplus f(k,r)$ . This simple system allows to transform a one-time secure (IND) encryption scheme such as OTP into an encryption scheme many-time secure against chosen-plaintext attacks (IND-CPA).

The cool thing is that the same trick also works for quantum encryption schemes: if we want to strengthen the QOTP, all we need is a (classical, but post-quantum secure) PRF $f$ with output of $2n$ bits, and we can encrypt an $n$ -qubit quantum state $\left| \varphi \right\rangle$ in a secure way by doing the following:

Generate a fresh random value $r$
Compute $z = f(k,r)$
Encrypt $\left| \varphi \right\rangle$ using the QOTP with key $z$ , obtaining a new quantum state $\left| \psi \right\rangle$
Encode the randomness $r$ into a quantum state $\left| r \right\rangle$
Output the joint quantum state $\left| \psi \right\rangle \otimes \left| r \right\rangle$ as ciphertext.

During decryption, first $r$ is recovered by measuring the state $\left| r \right\rangle$ , and then the QOTP is undone by using the PRF and the secret key. The resulting SKQE scheme is many-time secure against quantum plaintext attacks (QIND-CPA).

Public-Key Quantum Encryption

The next step is to perform public-key encryption on quantum states. Concretely: given the (classical) public key $\mathsf{pk}$ of a recipient user, we would like to encrypt a quantum state $\left| \varphi \right\rangle$ into a different quantum state in such a way that only the recipient (with the appropriate secret key $\mathsf{sk}$ ) can undo the encryption. These systems are called public-key quantum encryption schemes (PKQE), and cannot be realized by unitary transformations alone. Instead, the inspiration comes once again from classical cryptography: in many real-world applications such as PGP, public-key encryption schemes such as RSA are never used directly to encrypt a message. Instead, they are used to encrypt a fresh ephemeral symmetric key, which is in turn used to encrypt the plaintext proper, for reasons of efficiency.

In the quantum case we can use the same trick, all we need as a building block is a (classical, but post-quantum) public-key encryption scheme such as one of those being evaluated by NIST. If we denote such post-quantum scheme as $(\mathsf{Enc}_\mathsf{pk}, \mathsf{Dec}_\mathsf{sk})$ for a public-secret key pair $(\mathsf{pk,sk})$ , we can then perform public-key encryption of an $n$ -qubit quantum state $\left| \varphi \right\rangle$ as follows:

Generate a fresh $2n$ -bit random key $k$ ;
Compute $z = \mathsf{Enc}_\mathsf{pk}(k)$
Encrypt $\left| \varphi \right\rangle$ using the QOTP with key $k$ , obtaining a new quantum state $\left| \psi \right\rangle$
Encode the value $z$ into a quantum state $\left| z \right\rangle$
Output the joint quantum state $\left| \psi \right\rangle \otimes \left| z \right\rangle$ as ciphertext.

The receiver, using the appropriate secret key $\mathsf{sk}$ , can hence recover the quantum plaintext by first measuring and decrypting $z$ through $\mathsf{Dec}_\mathsf{sk}$ , and then using the recovered ephemeral decryption key $k$ to undo the QOTP. The resulting scheme is QIND-CPA secure as long as the classical public-key encryption scheme used is post-quantum IND-CPA.

Quantum Authentication

The last step in strengthening both symmetric- and public-key quantum encryption is to add quantum authentication as an additional level of security. Unlike the previous scenarios, this problem is really tricky and has been solved only very recently.

Authentication means checking that an encryption was performed correctly, by the intended sender, and it has a lot of applications. For example, a famous attack against SSL and TLS relies on the fact that the encryption scheme used was not authenticating ciphertexts and was therefore malleable. That is: given a valid (correctly generated) ciphertext, an adversary was able to modify it into a different (but still valid) one, even without the knowledge of the secret key and of the underlying plaintext. If we want an encryption scheme to be resistant against these kind of attacks, then the security notion of IND-CPA that we discussed previously is not enough, and we need to achieve properties such as “indistinguishability under chosen-ciphertext attack” (IND-CCA), “integrity of ciphertexts” (INT-CTXT), or “authenticated encryption (AE).

Achieving these notions classically is possible, and many encryption schemes nowadays do that. However, in the quantum realm, it is not so easy.

Fundamentally, the issue lies in the fact that in quantum mechanics there is no such thing as deciding if two quantum states are “the same”, because quantum states form a continuum, cannot be copied, and measurements are probabilistic. The way to address this issue is to realize that for our purpose what we really want quantumly is that the adversary is not able to replay a ciphertext, not that he cannot create a duplicate one! Classically, the two concepts “equal to” and “replayed from” are equivalent, but quantumly they are not because of the no-cloning theorem! So, the way to go forward is to imagine a real-VS-ideal approach, where we require that no efficient adversary can distinguish any difference between A) a scenario where he can play with many copies of a ciphertext; and B) a scenario where he is allowed to replay previous ciphertexts.

Things are a bit more complicated than that, but the above intuition is ultimately at the core of strong quantum encryption such as adaptive quantum IND-CCA (QIND-CCA2), quantum authenticated encryption (QAE), and unforgeable quantum encryption (QUF). The techniques for realizing such schemes basically boil down to 1) append a publicly known “authentication tag state” to the plaintext: and 2) encrypt the resulting joint state with a randomized quantum algorithm (depending on the encryption key) such that modifications on single qubits of the ciphertexts “propagate” to many different qubits on the plaintext (that is, using operations more involved than the QOTP called “2-designs”). Then, to recover the plaintext, first undo the encryption using a decryption key, and then check that the tag state has not been touched.

Conclusions

The problem of encrypting quantum data is a fascinating one, and fundamental problems in this field have been solved recently. Quantum key distribution exists nowadays already, but it solves an entirely different problem, and it is of no use in protecting quantum data. Also, because of the nature of quantum mechanics, certain tasks that we assume natural in the classical world are impossible, or carry over with big limitations or differences. As long as we are talking about “simple” cryptographic tasks such as symmetric-key encryption and public-key encryption, quantum analogue exist and can be realized efficiently once quantum computers become available. This knowledge will be precious once we’ll need to protect quantum networks and quantum data storage.