Gran parte de la comunicación en Internet se protege mediante algoritmos basados en criptografía de clave pública (PKC), un sistema que permite a las partes verificar identidades y cifrar mensajes utilizando bases de datos públicas de claves y firmas .Actualmente,la PKC es vulnerable a algoritmos que requieren una computadora cuántica para ejecutarse.
On April 10th, a researcher from Tsinghua University submitted a research preprint—that is, a public but not yet peer reviewed paper—to the Cryptology ePrint Archive. This submission kicked off an important effort to validate the article’s main claim, which was that its author, Yilei Chen, had found a method for efficiently solving certain lattice problems. The effort ended on April 19th, when two researchers independently found mistakes in the preprint that Chen could not fix.
If the work had been validated through peer-review, however, it would have marked significant progress towards breaking the cryptographic methods that underpin the latest National Institute of Standards and Technology (NIST) program to standardize new cryptographic algorithms and replace older, more vulnerable ones.
A lattice problem is a computational problem concerning mathematical objects called lattices. Roughly speaking, a lattice is a collection of points which can be used to define a structure. These structures in turn allow us—mathematicians, cryptographers, computer scientists—to express any point in the lattice as a combination of a few special points within the lattice; these points are called a lattice basis.
In cryptography, lattices can be used to describe and define security guarantees. A cryptographic algorithm is called lattice based if the difficulty of breaking it implies the ability to solve a lattice problem. The lattice problems chosen for cryptography are thought to be very hard for computers to solve, which is good. That means that algorithms using a lattice-based security system have a high degree of security.
A cryptographic algorithm is called lattice based if the difficulty of breaking it implies the ability to solve a lattice problem.
Chen’s findings in his research preprint would have provided a way for quantum computers to efficiently and effectively solve lattice problems. On one hand, had they been correct, we know by comparing guarantees to the preprint that Chen’s algorithm would not have directly broken any of NIST’s final candidates for standardization. But, on the other hand, they would have paved the way for research that potentially could break cryptographic standards.
While Chen’s algorithm was wrong, the possibility it raised highlighted just how high the stakes in this competition—between securing communications and developing attacks— are, currently. They are quite high. Much of internet communication is secured using algorithms based on public key cryptography (PKC), a system that allows parties to verify identities and encrypt messages using public databases of keys and signatures.
Currently, modern PKC is vulnerable to algorithms that require a quantum computer to run. While there are presently no capable quantum computers to run such an algorithm, a steady stream of advances in quantum computing technology is undeniably increasing the urgency to standardize and implement post-quantum algorithms, or algorithms which are resistant to both present-day computing and on-the-horizon quantum computing. Current efforts to standardize lattice-based and other post-quantum methods, like NIST’s program, are part of the race to protect the world’s communication systems from a quantum attack called Shor’s algorithm before the first capable quantum computers are built.
Only time will tell if the lattice problems, which underlie the most mature post-quantum algorithms, can also be easily solved by a quantum computer. However, there are questions we can answer today that would decrease the uncertainty around post-quantum migration.
For example, are efforts to break cryptographic systems rare? The answer is certainly no, for both lattice-based cryptography and cryptography in general. The Tsinghua University preprint is not the first attempt to break lattice-based cryptography, and it will not be the last.
How, then, can we measure research progress towards breaking cryptographic algorithms? This question is interesting because most announcements of security vulnerabilities do not represent debilitating, theoretical breaks of cryptographic systems. In 2022, a team from the Royal Institute of Technology announced a vulnerability of NIST’s forerunner lattice algorithm, called CRYSTALS-Kyber, which allowed a machine learning–based attack to probabilistically crack encrypted messages. Because the analysis did not reveal a theoretical vulnerability, cryptographers quickly found a way to strengthen CRYSTALS-Kyber against the 2022 attack.
One way of measuring progress towards true breaks in lattice-based cryptography would be to collaborate closely with the cryptographic research community, identify key problems and research questions which represent theoretical weaknesses in cryptosystems, and track developments in those problems and questions. The ongoing NIST standardization program is the best-in-class example of how to go about doing this. And Chen’s preprint, although flawed, raises new points to track. How viable, for example, are the methods of Chen’s algorithm? Can they be fixed?
Once a fundamental break is found and able to cause damage, stakeholders would resist adopting other lattice-based algorithms.
But still, the central question lingers: Could lattice-based cryptography recover from a fundamental break? Regardless of whether new, secure lattice-based algorithms could be constructed, a theoretical flaw in CRYSTALS-Kyber would quickly evaporate the confidence that has been slowly building among stakeholders of lattice-based cryptography. Once a fundamental break is found and able to cause damage, stakeholders would resist adopting other lattice-based algorithms.
Which leads to a final question worth pondering: What could we do with post-quantum cryptography now, to prepare for the future?
Chen’s algorithm is a quantum algorithm, meaning that, if it had been proven correct, in the worst-case scenario, there would still be time to gather alternative cryptographic algorithms and move away from our existing, vulnerable standards. In general, a mathematical attack on a cryptographic method can only target a narrow scope of algorithms, leaving mathematically unrelated algorithms unaffected. We should take care, now, to discover and refine new methods, beyond lattice-based cryptography, to prepare for a future where cryptographic paradigms are occasionally broken.
Fuente: https://www.rand.org
