Imagine tapping the card that bought you a cup of coffee this morning, giving a hacker on the other side of the world access to your bank account and allowing himself to purchase whatever he wants. Now imagine that this wasn't a one-off glitch, but that it happened all the time. Imagine that the lock protecting your electronic data suddenly stops working.
This is not a science fiction scenario. It could become a reality once sufficiently powerful quantum computers come online. These devices will use the strange properties of the quantum world to unlock secrets that would take a normal computer a lifetime or more to decipher.
We don't know when this will happen. But many people and organizations are already concerned about so-called “harvest now, decrypt later” attacks, in which cybercriminals or other attackers steal encrypted data now and keep it for days when it can be decrypted by quantum computers.
As the advent of quantum computers approaches, cryptographers are trying to devise new mathematical schemes to protect data from virtual attacks. The math involved is very complex, but the survival of the digital world depends on it.
‘Quantum proof’ encryption
Deciphering current online security comes down to the mathematical problem of multiplying two numbers to produce a third number. You can think of this third number as the key that unlocks secret information. As this number grows, the time it takes for a typical computer to solve a problem becomes longer than our lifetime.
But future quantum computers should be able to crack these codes much faster. Therefore, the race is on to find new encryption algorithms that can combat quantum attacks.
The National Institute of Standards and Technology has been calling for proposed “quantum proof” encryption algorithms for years, but few have so far stood up to scrutiny. (One of the proposed algorithms, called Supersingular Isogeny Key Encapsulation, was dramatically broken in 2022 with the help of Australian mathematical software called Magma, developed at the University of Sydney.)
This year's race is heating up even more. Last February, Apple updated its security system for its iMessage platform to protect data that may be collected for the post-quantum future.
Two weeks ago, Chinese scientists announced that they had installed a new “cryptographic shield” to protect the Origin Wukong quantum computer from quantum attacks.
Around the same time, cryptographer Yilei Chen announced that he had found a way for quantum computers to attack an important class of algorithms based on lattice mathematics that had been considered the most difficult to crack. Grid-based methods are not only part of Apple's new iMessage security, but they are also two of the three frontrunners for standard post-quantum encryption algorithms.
What is a grid-based algorithm?
A lattice is an array of dots in a repeating structure, like the edges of bathroom tiles or the atoms of a diamond crystal. Tiles are two-dimensional and atoms in diamonds are three-dimensional, but mathematically we can create lattices of many more dimensions.
Most grid-based cryptography is based on a seemingly simple question: If you hide a secret point in such a grid, how long will it take someone else to start from a different point and find the secret location? This game of hide and seek can support a variety of ways to make your data safer.
A variation of the lattice problem called “learning through errors” is considered too difficult to crack even for quantum computers. It is believed that as the size of the grid increases, the time it takes to solve it will increase exponentially, even with a quantum computer.
Lattice problems, such as the problem of finding arguments for large numbers on which much of current cryptography relies, are closely related to a deep open problem in mathematics called the “hidden subgroup problem.”
Yilei Chen's approach suggested that quantum computers could solve lattice-based problems faster under certain conditions. Experts rushed to check his results and quickly discovered the error. After the error was discovered, Chen published an updated version of his paper explaining the flaw.
Despite these findings, Chen's paper caused many cryptographers to lose confidence in the security of lattice-based methods. Some are still evaluating whether Chen's ideas can be extended to new routes for attacking these methods.
Needs more math
Chen's paper took the small community of cryptographers equipped to understand it by storm. But it has received little attention in the wider world. Probably because so few people understand this kind of work or its implications.
Last year, when the Australian government released its national quantum strategy to make the country a “leader in the global quantum industry” where “quantum technologies are essential to a prosperous, fair and inclusive Australia”, there was a key omission. Don't mention math at all.
Australia is home to many leading experts in quantum computing and quantum information science. However, making the most of quantum computers and defending them requires deep mathematical training to produce new knowledge and research.
This article is republished from: conversation Under Creative Commons License. read original article.
Image source: ZENG YILI / Unsplash