Quantum Cryptography and Foundations

Prior to Mahadev’s 2018 breakthroughs, research in quantum cryptography was dominated by advances in quantum key distribution—that we already explained. Today, the field has blossomed into a diverse and rich sub-discipline with increasingly intricate underlying mathematics.

We briefly describe some of the interesting achievements in this direction but this is not meant to be a representative list. The goal is to give the reader some idea of the kinds of problems the community has focussed on in recent years. We explain some of our contributions and current research efforts subsequently.

Recent Advances

Verification

Quantum computers are sophisticated complex machines that are designed to isolate certain quantum systems, from any external interaction, to serve as quantum bits (qubits) and allow the user to apply quantum circuits on these qubits. Due to the nature of quantum physics (specifically the fact that measurements irreversibly disturb the state of the system), that of the engineering sophistication required to construct such a device, and the difficulty of

establishing that a device is truly doing something that cannot be reproduced by a classical (as opposed to quantum) computer, leads to a major problem—how does one ensure that a quantum computer functions as promised?

Given the importance of this question, various approaches have been taken to address it. One such approach treats the quantum computer as a “black-box” that one can only interact with by sending and receiving classical messages (i.e. bit strings). Evidently, such a treatment is extremely practical because it allows a client to use our existing network infrastructure to communicate with a quantum computer on the “cloud”. This approach—which we broadly term classical control of quantum devices—became feasible after the breakthrough work of Mahadev 2018. She was the first to solve the quantum verification problem, to wit: establishing that (under widely held cryptographic assumptions), a classical client can verify the answer to any “quantum problem” by (classically) interacting with an untrusted quantum computer. All prior approaches either required one to assume that the client has some limited quantum capabilities or placed some kind of restriction on the remote quantum device—such as it must consist of two non-communicating parts.

Proof of Quantumness

Since Mahadev’s work, the field of quantum cryptography (based on computational assumptions) has witnessed rapid advances in many directions. One important line of works is motivated by the observation that we do not expect powerful quantum computers to suddenly become available. On the contrary, early iterations of quantum devices are noisy and are therefore limited in the size and complexity of the circuit they can apply. Thus, a major research effort has been put into developing cryptographic protocols—called proofs of quantumness (PoQ)—that allow a classical client to ensure that an untrusted device is indeed quantum, by having it perform quantum circuits that are much simpler than performing generic verification. We emphasise that a PoQ is not a heuristic statement

but offers a rigorous guarantee that no classical device can spoof (as long as widely held cryptographic assumptions hold).

Certified Deletion

Another striking application of quantum physics to cryptography was initiated by the work of Broadbent and Islam in 2019 that led to a sequence of increasingly capable functionalities. Very basically, it is a sophisticated version of the no-cloning theorem. The key observation is that classical information cannot be deleted because it can always be copied. Could it be that somehow a message, encoded into a quantum system, can be certifiably deleted?

It may help to consider a more concrete scenario. Suppose A has written a will and she encrypts it using a secret key, and gives the encrypted will to her lawyer. Later, she has a change of heart and writes another will, encrypts it using another secret key, and gives the second encrypted will to her lawyer—together with the instruction that he destroys the first will. (The idea being that when she dies, the secret keys will get revealed so she wants to make sure that the last will is executed.) Now, classically, there is no way around this problem if one desires security against unbounded adversaries. Quantumly, it turns out, one can produce an encryption scheme that has the property that the recipient can produce a “deletion certification” which guarantees that the message inside the encryption has been destroyed.

There are many other fascinating topics that we are not mentioning here—multi-party computation, homomorphic computation, proofs of knowledge, zero knowledge proofs, pseudo-randomness related topics (such as pseudo-entanglement, pseudo-random unitaries), cryptography using primitives weaker than one-way-functions and many more.

Our contributions and ongoing efforts

Coin flipping

In classical cryptography (as opposed to quantum cryptography) obtaining information theoretic security is impossible for all but very specific problems. In quantum cryptography, the situation turns out to be more interesting. Aside from key distribution, many primitives in the broader area of two-party secure computation—where two parties don’t trust each other and yet wish to perform some joint computation without revealing their inputs—can be realised to varying degrees of security. Specifically, we have made various contributions to the (strong) coin flipping problem: two remote mistrustful parties, wish to agree at an unbiased shared random bit. When the two parties have opposite preferences, this problem is easier to solve and the primitive, accordingly, is called “weak coin flipping”. This problem has an interesting history. Very briefly, classically, this problem cannot be solved with information theoretic security. In the quantum setting, it was initially conjectured that (strong) coin flipping is possible with information theoretic security. Later, errors were found in the initial proposals and Kitaev established that a malicious party can always bias the output by $$\frac{1}{\sqrt{2}}$$. Then Mochon, in 2007, in his breakthrough work, showed that weak coin flipping is possible with arbitrarily small bias, i.e. nearly perfect security. However, his proof went through a non-constructive step. Consequently, explicit descriptions of these protocols remained elusive. We resolved this question in a sequence of works [1,2,3]. In an interesting twist to the story, in 2019, Miller showed that round-efficient weak coin flipping is impossible—the number of messages the two parties exchange must grow exponentially as one approaches perfect security. Owing to this, we asked if some variant of the weak coin-flipping problem does allow for better efficiency. In an upcoming work [4], we consider cheat-penalised weak coin flipping. The idea here is that the parties can detect the other party cheating and can penalise the cheating party by some amount $$\Lambda$$. For $$\Lambda=0$$, everything reduces to regular weak coin flipping. We show that for small cheating penalties, even $\Lambda=0.01$$, one can already obtain protocols with bias at most $$10^{-10}$$, using only 24 qubits—nothing even remotely close is known in the non-penalised version.

Device Independence

Given how sensitive quantum devices are to the environment, it is difficult to ascertain it is functioning as designed. The situation gets even more delicate when these devices are intended for cryptographic purposes: How can one be certain that the manufacturers haven’t tweaked it to compromise security? Device independence is one answer to this level of extreme paranoia—which is a good thing as far as cryptographic security is concerned. The basic idea here is to minimise the assumptions one needs to make about the device and yet be able to deduce the inner workings of the device. A bit more concretely, consider a device with two parts such that the two parts can be isolated so as to prevent communication across them. By observing the input output behaviour of such a device, one can distinguish a quantum device from a classical device. This is the famous theorem by Bell. It turns out that when one observes a specific kind of behaviour, one can also guarantee what the inner workings of the device must be—even if it is produced by a malicious adversary.

In one of our early works, we showed how one can derive a similar statement using the phenomenon of quantum contextuality [5]. In fact, this work was done in collaboration with an experimentalist group who demonstrated this procedure using trapped ions. The difficulty there was that the underlying assumption had to do with assuming that certain measurements are commuting. This is less satisfactory than the setting Bell considered where one can more easily validate the underlying assumption, i.e. the different parts of the device are isolated and cannot communicate. To remedy this, we defined the notion of an operational test of contextuality and show how to realise it under standard cryptographic assumptions [6]. This was motivated by the, now celebrated, KLVY compiler (due to Kalai, Lombard, Vaikuntanathan and Yang) that shows how one can replace the spatial separation assumption in Bell-like settings with cryptographic assumptions, while preserving many properties of the original setting. We also explored applications of these ideas to improve device independent weak coin flipping protocols [7]. We are currently working on proving some continuity conjectures we had to make in the security proof of this work.

Adversarial-self testing

Self-testing may be viewed as the setting where two parties trust each other (and their classical computations), but not their quantum devices. It is natural to ask: is trust between the parties necessary to perform a self-test? We know that, for example, it is impossible to self-test an EPR pair because doing so would immediately yield perfect coin flipping—which is ruled out by Kitaev impossibility for strong coin flipping. We showed that self-testing in this fully adversarial setting, is impossible generically [8]. When we say impossible, we mean in the information theoretic setting. One can therefore ask, can fully adversarial self-testing (FAST) be realised under computational assumptions? We show that, indeed, this is possible assuming classical secure two-party computations can be performed. We also find that the situation gets more subtle beyond the bipartite case. Finally, we study the shared-entanglement setting and show that there is strong evidence to suggest that the shared-entanglement model is stronger than the plain model for secure two-party computation.

Expertise