QCrypt 2016

Last year I was fortunate enough to attend the QCrypt 2016 conference being held in Washington DC. It is my first time attending this conference and I will highlight some of the presentation that were of particular interest to me. It was also a great opportunity to meet with friends and colleagues after moving overseas from Europe to the United States.

The conference was hosted at this beautiful lecture hall at the Carnegie Institute for Science.

Quantum Key Distribution

A major topic a QCrypt this year was, of course, Quantum Key Distribution (QKD). This topic of research stems from the famous BB84 protocol, published in a 1984 paper by Bennett and Brassard¹. It proposes a protocol that uses quantum communication to distribute a secret key between two parties. There are many classical (i.e. non-quantum) protocols such as RSA which would make this unnecessary, were it not for the fact that the BB84 protocol is provably secure. This means even an adversary with unlimited (quantum) resources cannot figure out what the key is; the same cannot be said about RSA! As a side note, it is even possible for a finite quantum computer to break RSA².

Unfortunately for us theorists, practice and theory are are not the same. As evidenced by the many (poster) presentations implementing QKD is far from a done deal. E.g., see presentations on free-space QKD, or the very amusing laser damage creates backdoors in quantum cryptography, or field trials of high-speed QKD; as well industry exhibits and a lot of posters.

Device Independent Cryptography

Another topic that may also come as surprising –it certainly was for me– is device independent quantum cryptography. It is quite natural to assume that you have complete control of your device and that an adversary would just attack your communications; it is less so to remove this assumption. Let’s say you want to generate a secure random number, you could, for example, refer to /dev/urandom on Linux for a pseudo-random byte:

$ od -vAn -N1 -tu1 < /dev/urandom 
59
$ od -vAn -N1 -tu1 < /dev/urandom 
148

But how would you guarantee that a bit is actually secret, i.e. no one else knows any information about this bit. With randomness generation (tutorial) it is possible to certify that two black boxes capable of a protocol similar to QKD have indeed generated random bits.

This remarkable result is made possible by an inherently quantum property, the monogamy of entanglement: Perfect entanglement between two qubits implies that there is no third qubit that entangled with the first two. Given just

1. two black boxes that supposedly perform what is known as a Bell test (similar to QKD), and
2. monogamy of entanglement

we can certify randomness.

By performing a Bell test we can certify that the two black boxes indeed share (close to) perfect entanglement which precludes any third party from listening in (by monogamy). Now we just have to randomly mix in the Bell tests with measurement to get random bits and the black boxes won’t even know if they are being tested or actually generating randomness.

Zero-Knowledge Proofs

Sometimes, and especially in cryptography, we want to show that we know some secret recipe to cook a delicious dinner — or rather an algorithm for solving some problem. As part of her presentation Anne Broadbent gives an explanation a five-year old can understand.

An analogy that I’ve come across likens zero knowledge proofs to being able to distinguish Coca-Cola from Pepsi. Let’s assume that we think it’s really hard to distinguish between the two colas. Someone comes along and they claim to know how to distinguish the two and will prove it to us! We just have to choose a coke at random and keep it secret and give it to them (a single-blind trial). They will then tell you what it was.

Either they were lying and simply guess or they do actually know the difference. To see through any such deceiver, we repeat the experiment $n$ times. The probability that a deceiver guesses correctly in all $n$ experiments is $2^{-n}$. So you can very quickly figure out who is leading you by the nose and who is a connoisseur (of coke). Note that you have not figured out the secret recipe to distinguishing the two cokes which is the point of zero-knowledge.

Perhaps surprisingly, it is known that there exists a zero-knowledge proof for co-NP problems³. Under sufficient assumptions this can be extended to NP and even all of IP⁴.

Quantum Zero-Knowledge

Now for the quantum results. Previously it was proved that we can perform quantum rewinding, an operation that is important in classical zero-knowledge proofs. With this result Watrous was able to show that classical zero-knowledge protocols remain secure against quantum attackers⁵.

Now for the results presented at QCrypt 2016 (and QIP 2017 which I may get to some time), they extend the zero-knowledge result from classical NP to its quantum analogue, QMA. Showing that (again under sufficient assumptions) there are zero-knowledge proofs for all problems in QMA (Quantum Merlin Arthur).

If you wish to know more about Quantum zero-knowledge proofs and interactive provers, have a look at Vidick and Watrous’s survey “Quantum Proofs”⁶. I had the pleasure of reading through most if it in a reading group and it is a great way to get started. Admittedly, we did have some difficulty with the zero-knowledge chapter (the rest was great, promise!) so having some background on classical zero-knowledge first may help. It contains all you need to get started with QMA, Quantum Interaction Proofs (QIP), Quantum (Statistical) Zero-Knowledge (QSZK), and even Multi-Prover QIP (QMIP).

Conclusion

Many thanks to the organisers for making this great conference happen. Even though I cannot attend this year, I’m looking forward to QCrypt 2017. I’m hoping the presentation will again be recorded and made available afterwards.

QCrypt 2017 will be hosted at Cambridge, UK.