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^{1}. It proposes a protocol that uses quantum communication to distribute a secret key between two parties. There are many classical (i.e. nonquantum) 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^{2}.
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 freespace QKD, or the very amusing laser damage creates backdoors in quantum cryptography, or field trials of highspeed 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 pseudorandom 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
 two black boxes that supposedly perform what is known as a Bell test (similar to QKD), and
 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.
ZeroKnowledge 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 fiveyear old can understand.
An analogy that I’ve come across likens zero knowledge proofs to being able to distinguish CocaCola 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 singleblind 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 zeroknowledge.
Perhaps surprisingly, it is known that there exists a zeroknowledge proof for coNP problems^{3}. Under sufficient assumptions this can be extended to NP and even all of IP^{4}.
Quantum ZeroKnowledge
Now for the quantum results. Previously it was proved that we can perform quantum rewinding, an operation that is important in classical zeroknowledge proofs. With this result Watrous was able to show that classical zeroknowledge protocols remain secure against quantum attackers^{5}.
Now for the results presented at QCrypt 2016 (and QIP 2017 which I may get to some time), they extend the zeroknowledge result from classical NP to its quantum analogue, QMA. Showing that (again under sufficient assumptions) there are zeroknowledge proofs for all problems in QMA (Quantum Merlin Arthur).
If you wish to know more about Quantum zeroknowledge proofs and interactive provers, have a look at Vidick and Watrous’s survey “Quantum Proofs”^{6}. 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 zeroknowledge chapter (the rest was great, promise!) so having some background on classical zeroknowledge first may help. It contains all you need to get started with QMA, Quantum Interaction Proofs (QIP), Quantum (Statistical) ZeroKnowledge (QSZK), and even MultiProver 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.

C. H. Bennett and G. Brassard. “Quantum cryptography: Public key distribution and coin tossing”. In Proceedings of IEEE International Conference on Computers, Systems and Signal Processing, volume 175, page 8. New York, 1984. ↩

See Shor’s Algorithm ↩

Goldreich, Oded, Silvio Micali, and Avi Wigderson. “Proofs that yield nothing but their validity or all languages in NP have zeroknowledge proof systems.” Journal of the ACM (JACM) 38, no. 3 (1991): 690728. doi:10.1145/116825.116852 ↩

BenOr, M. et al., Everything Provable is Provable in ZeroKnowledge. Lecture Notes in Computer Science, pp.37–56. doi:10.1007/0387347992_4 ↩

Watrous, J., 2009. ZeroKnowledge against Quantum Attacks. SIAM Journal on Computing, 39(1), pp.25–58. doi:10.1137/060670997 ↩

Vidick, T. & Watrous, J., 2016. Quantum Proofs. Foundations and Trends® in Theoretical Computer Science, 11(12), pp.1–215. doi:10.1561/0400000068 ↩