Bringing Balance to the Quantum Force

By Doug Hulette 

Quantum computing has plenty of skeptics, but assistant professor Mark Zhandry isn’t one of them. 

Zhandry, who joined the Department of Computer Science in 2016, is confident that the technology, driven by peculiarities of physics like superposition and entanglement, is the wave of future — in which quantum computers will solve complex problems exponentially faster than current computers. But he also sees a dark side to the massive increase in processing power, because quantum computers will be able to destroy electronic privacy and security as we know it. 

“Think about your log-in screens, biometric data, the chip in your credit card, all of which use cryptography to protect you and your information,” he says. “Someday, quantum computers will be able to break most of the cryptography used in practice today much faster than our current computers can.”

Zhandry is carving out a niche in cryptography, his primary research focus. He has been selected to receive the 2019 Best Paper award at Eurocrypt, one of the flagship conferences in the field. With five papers to appear in this conference, he also set the record for the largest number of papers ever accepted to the program, which is set for mid-May in Darmstadt, Germany.

 “Cryptography is the backbone of a secure digital world. Historically, the field has been synonymous with encryption: sending a secret message in the presence of an eavesdropper—someone who wants to learn your message,” he says. “Modern cryptography, however, has branched out to encompass pretty much any setting where you want to prevent a malicious party from doing something bad with digital information. 

“In the very long term, quantum computers will allow us to do all sorts of new things, but they also threaten to throw this whole system into disarray by voiding all the current safeguards. My work aims to mitigate this threat.”

Zhandry did postdoctoral work at MIT after earning his PhD from Stanford. As an undergrad at UC Berkeley, he majored in electrical engineering, computer science, and physics, with a minor in mathematics. In an email exchange, he shared some thoughts regarding his research:

Your Best Paper for Eurocrypt is titled, “Quantum Lightning Never Strikes the Same State Twice." Would you help me out here?  

Imagine that lightning strikes are so random that in nature, the old adage is true: lightning really never does strike the same place twice.  On the other hand, we can easily tamper with nature, say, by erecting a lightning rod on top of a tall building. Lightning would repeatedly strike the rod, proving the adage false. 

One can think of a lightning rod as a way of setting the initial conditions for a lightning bolt so that it always strikes the same place. My goal was to devise a secure digital version of natural lightning: an algorithm that never produces the same result twice even if you arbitrarily tamper with it. 

This hypothetical quantum lightning has numerous uses. For instance, it can make digital currencies whose resilience to counterfeiting is derived from physics; in contrast, existing mechanisms such as blockchains prevent counterfeiting by maintaining a public record of all transactions.   

My paper shows that if quantum computers can mount certain attacks on cryptography (which is bad), then those attacks can be turned around and converted into quantum lightning (which is good), thus balancing the negative and positive impacts of quantum computing. Later in the paper, I design a cryptographic algorithm, show how to mount an attack on it, and then leverage this connection to build quantum lightning.

You concentrate on theoretical rather than practical cryptography. Why the focus on theory?

Theory is at the heart of modern cryptography. Much of cryptography is derived from number theory, and thus relies on mathematical theory. Additionally, unlike much of computer science where you can test if you did things right by seeing if your program compiles and outputs the right result, things are much harder in cryptography.  It isn’t enough to design a system that’s secure against only the attacks that you thought of. Instead, you must design a system that is secure against all attacks. Because it’s impossible to enumerate all possible attacks, the only way to demonstrate security is through a mathematical proof that shows beyond doubt that your algorithm is secure.

Finally, the process of standardizing cryptographic algorithms to be used in practice takes many years. This is particularly relevant for quantum computing, as the standardization process is happening now, even though we don’t have quantum computers yet.  

As to why I work on theory, I have always been fascinated by fundamental questions: what computers can and cannot do in principle.  I am also a big fan of mathematics, which I find very elegant. But I enjoy seeing the applications of math to the real world, so cryptography was a natural fit for me.

When are we going to have to deal with the pluses and minuses of quantum computing?

No one has a full-fledged quantum computer yet, but there has been significant progress in recent years.  There are many differing opinions on when we can expect to see a real quantum computer, ranging from several years to a few decades away; I punt this question to the physicists.  But we must be prepared for the arrival of quantum computers now, so that we are not caught unawares when the day inevitably and/or unexpectedly arrives.

How did you become interested in cryptography as your main field of interest?

I actually had a really hard time narrowing down what I wanted to study. As an undergrad, it took me until my senior year to even settle on computer science as my main field going forward. Then, during my first year of grad school, I worked on four different projects ranging from graphics to complexity theory, trying to find the right fit. I guess I owe my ultimate choice to my advisor, Professor Dan Boneh, who gave me a project to work on that was a great match for my interests and got me excited about cryptography. The rest is history.