The original version of this story appeared in Quanta Magazine.
Say you want to send a private message, cast a secret vote, or sign a document securely. If you do any of these tasks on a computer, you’re relying on encryption to keep your data safe. That encryption needs to withstand attacks from code breakers with their own computers, so modern encryption methods rely on assumptions about what mathematical problems are hard for computers to solve.
But as cryptographers laid the mathematical foundations for this approach to information security in the 1980s, a few researchers discovered that computational hardness wasn’t 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 a few specific cryptographic tasks directly on the laws of physics. But these tasks were strange outliers—for all others, there seemed to be no alternative to the classical computational approach.
By the end 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’s been this rearrangement of what we believe is possible with quantum cryptography,” said Henry Yuen, a quantum information theorist at Columbia University.
In a string of recent papers, researchers have shown that most cryptographic tasks could still be accomplished securely even in hypothetical worlds where practically all computation is easy. All that matters is the difficulty of a special computational problem about quantum theory itself.
“The assumptions you need can be way, way, way weaker,” said Fermi Ma, a 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 started thinking about the destructive nature of measurement in quantum theory. Measure any system governed by the rules of quantum physics, and you’ll alter the quantum state that mathematically describes its configuration. This quantum measurement disturbance was a hindrance for most physicists. Wiesner, who took an unorthodox information-centric view of quantum theory, wondered whether it could be made useful. Perhaps it could serve as a form of built-in tamper protection for sensitive data.
But Wiesner’s ideas were too far ahead of their time, and he left academia after graduate school. Fortunately, he’d discussed his ideas with his friend and fellow physicist Charles Bennett, who unsuccessfully tried to interest others in the subject for a decade. Finally, in 1979, Bennett met the computer scientist Gilles Brassard while swimming off the coast of Puerto Rico during a conference. Together, they wrote a groundbreaking paper describing a new approach to an important cryptographic task. Their protocol was based on quantum measurement disturbance, and needed no assumptions about the difficulty of any computational problems.
Discussion about this post