Quantum computers, which use odd subatomic features to crunch numbers in powerful new ways, do not yet work. However, if and when they begin to operate, they will be able to breach the cryptographic methods that currently safeguard internet conversations, financial transactions, medical information, and business secrets.
Today’s algorithms are generally based on the reality that ordinary computers struggle to factor very big integers. Generations of classical computers have struggled to determine the factors of the large integers employed by the RSA-2048 technique, which is frequently considered as a benchmark for advancement in the field. Experts, however, estimate that a quantum computer capable of cracking it in a day may arrive within the next decade or two. That’s already making cryptographers anxious. Sensitive data gathered illegally today could be kept on ice for years until a sufficiently effective codebreaker is developed.
New algorithms are consequently required. And, because transitioning to them will take years, the transition to post-quantum cryptography (PQC) should begin as soon as possible. The National Institute of Standards and Technology (NIST), America’s standards organization, has officially sounded the starting gun on this transformation. On August 13th, NIST announced the approval of three algorithms as official PQC standards. Two are based on lattice problems, which are mathematical puzzles that challenge both quantum and traditional computers. The third method, based on hash functions employed in data analysis, avoids putting too many eggs in one basket.
Lattice problems are a class of computational problems based on the mathematical concept of lattices, which are regular, grid-like structures in multidimensional space. These problems play a significant role in cryptography, particularly in designing post-quantum cryptographic systems, as they are believed to be difficult for both classical and quantum computers to solve.
A lattice in this context is a set of points in an n-dimensional space that are generated by taking integer linear combinations of a set of basis vectors. For example, in 2D, a lattice might look like a grid of regularly spaced points.
Lattice problems are hard to solve in high-dimensional spaces. These problems have been shown to be NP-hard, meaning no efficient algorithm is known to solve them in the worst case. Quantum computers, despite their power, have not been shown to offer any significant advantage in solving these problems efficiently.
Lattices operate in high-dimensional spaces (with hundreds or thousands of dimensions). Quantum computers struggle to efficiently solve problems in such high dimensions because the complexity grows exponentially with the dimension. The structure of lattices in these spaces makes it computationally infeasible for a quantum computer to find short vectors or approximate solutions.
Source: Economist
