The unique model of this story appeared in Quanta Magazine.
Laborious issues are often not a welcome sight. However cryptographers love them. That’s as a result of sure onerous math issues underpin the safety of contemporary encryption. Any intelligent trick for fixing them will doom most types of cryptography.
A number of years in the past, researchers discovered a radically new approach to encryption that lacks this potential weak spot. The strategy exploits the peculiar options of quantum physics. However not like earlier quantum encryption schemes, which solely work for just a few particular duties, the brand new strategy can accomplish a a lot wider vary of duties. And it might work even when all the issues on the coronary heart of strange “classical” cryptography grow to be simply solvable.
However this hanging discovery relied on unrealistic assumptions. The consequence was “extra of a proof of idea,” stated Fermi Ma, a cryptography researcher on the Simons Institute for the Principle of Computing in Berkeley, California. “It isn’t a press release about the actual world.”
Now, a new paper by two cryptographers has laid out a path to quantum cryptography with out these outlandish assumptions. “This paper is saying that if sure different conjectures are true, then quantum cryptography should exist,” Ma stated.
Fort within the Sky
You’ll be able to consider fashionable cryptography as a tower with three important components. The primary half is the bedrock deep beneath the tower, which is fabricated from onerous mathematical issues. The tower itself is the second half—there yow will discover particular cryptographic protocols that allow you to ship non-public messages, signal digital paperwork, solid secret ballots, and extra.
In between, securing these day-to-day purposes to mathematical bedrock, is a basis fabricated from constructing blocks referred to as one-way functions. They’re accountable for the asymmetry inherent in any encryption scheme. “It’s one-way as a result of you’ll be able to encrypt messages, however you’ll be able to’t decrypt them,” stated Mark Zhandry, a cryptographer at NTT Analysis.
Within the Nineteen Eighties, researchers proved that cryptography constructed atop one-way capabilities would guarantee safety for a lot of completely different duties. However a long time later, they nonetheless aren’t sure that the bedrock is powerful sufficient to assist it. The difficulty is that the bedrock is fabricated from particular onerous issues—technically referred to as NP issues—whose defining characteristic is that it’s simple to test whether or not any candidate answer is right. (For instance, breaking a quantity into its prime components is an NP downside: onerous to do for big numbers, however simple to test.)
Many of those issues appear intrinsically troublesome, however laptop scientists haven’t been able to prove it. If somebody discovers an ingenious algorithm for quickly fixing the toughest NP issues, the bedrock will crumble, and the entire tower will collapse.
Sadly, you’ll be able to’t merely transfer your tower elsewhere. The tower’s basis—one-way capabilities—can solely sit on a bedrock of NP issues.
To construct a tower on tougher issues, cryptographers would want a brand new basis that isn’t fabricated from one-way capabilities. That appeared unimaginable till only a few years in the past, when researchers realized that quantum physics might assist.
