The original version of this story appeared in Quanta Magazine.
Let’s say you want to send a private message, cast a secret ballot, or securely sign a document. If you do any of these tasks on a computer, you’re relying on encryption to keep your data safe. That encryption must resist attacks from codebreakers with their own computers, so modern encryption methods rely on assumptions about which math problems are hard for computers to solve.
But as cryptographers laid the mathematical foundations for this approach to information security in the 1980s, some researchers discovered that computational hardness was not the only way to safeguard secrets. Quantum theory, originally developed to understand the physics of atoms, turned out to have deep connections to information and cryptography. Researchers found ways to base the security of some specific cryptographic tasks directly on the laws of physics. But these tasks were strange outliers: for all the others, there seemed to be no alternative to the classical computational approach.
At the turn of the millennium, quantum cryptography researchers thought that was the end of the story. But in just the past few years, the field has undergone another seismic shift.
“There has been a reorganization of what we believe is possible with quantum cryptography,” he said. Henry Yuenquantum information theorist at Columbia University.
In a series of recent papers, researchers have shown that most cryptographic tasks could still be performed securely even in hypothetical worlds where virtually all computations are easy. All that matters is the difficulty of a particular computational problem over quantum theory itself.
“The assumptions you need can be much, much, much weaker,” he said. Fermi Maa quantum cryptographer at the Simons Institute for the Theory of Computing in Berkeley, California. “This is giving us new insights into computational hardness itself.”
This message will self-destruct
The story begins in the late 1960s, when a physics graduate student named Stephen Wiesner began thinking about the destructive nature of measurement in quantum theory. If you measure any system governed by the rules of quantum physics, you will disrupt the quantum state that mathematically describes its configuration. This disruption of quantum measurement was a stumbling block for most physicists. Wiesner, who held an unorthodox, information-centric view of quantum theory, wondered if it might prove useful. Perhaps it could serve as a form of built-in protection against tampering with sensitive data.
But Wiesner’s ideas were too ahead of their time, and he left academia after graduating. Fortunately, he had discussed his ideas with his friend and fellow physicist Charles Bennett, who tried, unsuccessfully, to interest others in the subject for a decade. Finally, in 1979, Bennett met computer scientist Gilles Brassard while he was swimming off the coast of Puerto Rico during a conference. Together they wrote a groundbreaking document Describing a new approach to an important cryptographic task. His protocol was based on quantum measurement of perturbations and required no assumptions about the difficulty of any computational problem.