The original version of this story appeared in Quanta Magazine.
Imagine the need to send a private message, cast a secret vote, or sign a document securely. In all these scenarios, encryption plays a vital role in keeping your data safe when done on a computer. The encryption methods in use today rely on assumptions about mathematical problems that are hard for computers to solve, to withstand attacks from code breakers.
However, back in the 1980s, as cryptographers were establishing the mathematical foundations for information security through encryption, some researchers discovered that computational hardness wasn’t the only way to safeguard secrets. Surprisingly, quantum theory, which was initially developed to understand the physics of atoms, had deep connections to information and cryptography. This led researchers to find ways to base the security of specific cryptographic tasks directly on the laws of physics. Although these tasks were unusual outliers, there seemed to be no alternative to the classical computational approach for others.
As the millennium approached, quantum cryptography researchers believed that this was the limit of what was possible. However, in recent years, the field has experienced a significant shift.
“There’s been this rearrangement of what we believe is possible with quantum cryptography,” remarked Columbia University’s quantum information theorist Henry Yuen.
Recent research papers have demonstrated that most cryptographic tasks could still be achieved securely, even in hypothetical worlds where nearly all computation is easy. What matters most is the complexity of a specific computational problem related to quantum theory itself.
“The assumptions you need can be way, way, way weaker,” explained Fermi Ma, a quantum cryptographer at the Simons Institute for the Theory of Computing in Berkeley, California. “This is providing us with new insights into computational difficulty.”
This Message Will Self-Destruct
The story traces back to the late 1960s when physics graduate student Stephen Wiesner contemplated the disruptive impact of measurement in quantum theory. Any measurement of a system governed by quantum physics alters its mathematical quantum state, a phenomenon that hindered most physicists. Wiesner, however, considered whether this quantum measurement disturbance could be leveraged for built-in data protection for sensitive information.
Although Wiesner’s ideas were ahead of their time, and he eventually left academia after graduate school, he had shared his thoughts with fellow physicist Charles Bennett. Bennett, in turn, attempted to generate interest in the subject without success until the pair finally published a groundbreaking paper in 1979. During a conference in Puerto Rico, Bennett connected with computer scientist Gilles Brassard, and they outlined a new approach to an essential cryptographic task based on quantum measurement disturbance, without relying on the complexity of computational problems.