Original version With this history appeared in Quanta Magazine.
Say you want to send a private message, cast a secret vote, or securely sign a document. If you do any of these tasks on a computer, you rely on encryption to protect your data. That encryption must withstand attacks by codebreakers with their own computers, so up-to-date encryption methods rely on assumptions about what mathematical problems are demanding for computers to solve.
But as cryptographers built the mathematical foundations for this approach to information security in the 1980s, several researchers discovered that computational difficulty was not the only way to protect secrets. Quantum theory, originally developed to understand atomic physics, turned out to have deep connections with information and cryptography. Researchers have found ways to base the security of several 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 end of the millennium, quantum cryptography researchers thought that was the end of the story. But in the past few years, the deposit has undergone another seismic shift.
“There has been some realignment of what we think is possible with quantum cryptography,” he said Henry Yuenquantum information theorist at Columbia University.
In a series of recent papers, scientists have shown that most cryptographic tasks can still be performed securely even in hypothetical worlds in which virtually all computations are effortless. All that matters is the difficulty of the special computational problem involving quantum theory itself.
“The assumptions you need may be much, much, much weaker,” he said Stop momquantum cryptographer at the Simons Institute for the Theory of Computing in Berkeley, California. “This gives us a new perspective on computational hardness itself.”
This message will self-destruct
The story begins in the slow 1960s, when physics student Stephen Wiesner began to wonder about the destructive nature of measurements in quantum theory. Measure any system obeying the laws of quantum physics and you will change the quantum state that mathematically describes its configuration. This disruption of quantum measurement has been a stumbling block for most physicists. Wiesner, who took an unconventional, information-centric view of quantum theory, wondered whether it could be useful. Perhaps this could serve as a form of built-in tamper-proof protection for sensitive data.
However, Wiesner’s ideas were too ahead of their time and he left academia after graduating. Fortunately, he discussed his ideas with his friend and fellow physicist Charles Bennett, who had been trying unsuccessfully for a decade to interest others in the topic. Finally, in 1979, Bennett met computer scientist Gilles Brassard while swimming off the coast of Puerto Rico during a conference. Together they wrote, among others: groundbreaking article describing a fresh approach to an critical cryptographic task. Their protocol was based on the disruption of quantum measurement and required no assumptions about the difficulty of any computational problems.