Grid-based methods are currently raising great expectations in the development of cryptography that is secure from quantum computers. Mathematicians associate grids with a number of difficult tasks involving the measurement of vector spaces. The difficulty of these problems increases exponentially with the complexity of the grid. For cryptographic applications, grids with hundreds of dimensions are used.
One of the first to make mathematical grids usable for cryptography was the Hungarian-American computer scientist Miklós Ajtai, who worked at the IBM research centre in Almaden. In the mid-1990s, he opened the door to a new field of cryptography. Shortly after the turn of the millennium, grid cryptography was still the work of a small group of researchers, reports the Italian-American computer scientist Daniele Micciancio in a YouTube lecture. In the meantime, one has to read more than 100 essays a year to keep track of this rapidly expanding field of research.
Vadim Lyubashevsky is one of the researchers who have excelled here. He worked with Micciancio at the University of California in San Diego as a doctoral student. Today, he conducts research at the IBM research laboratory in Rüschlikon on the Lake Zurich, Switzerland.
The IBM researcher has done much to transform the lattice theory, which has been developed over the past 25 years, into computer software that is relevant to practice. According to Lyubashevsky, a so-called Cryptographic Suite for Algebraic Lattices (Crystals) is already being used internally by IBM, but also by Google and Cisco for testing purposes. It has been shown that these programs work very efficiently, they are faster than conventional cryptographic methods. Only the memory requirements are slightly higher because the keys are longer.
IBM has not only developed software, but also hardware: the prototype of a tape drive can store encrypted data on 20-TByte tape cartridges in a way that cannot be converted into plain text even by quantum computers.
However, such products cannot be commercialised as long as there are no binding standards for post-quantum cryptography that ensure the interaction of hardware and software components from different manufacturers. The computer world is therefore waiting for the American National Institute of Standards (Nist) to complete a long-term evaluation of quantum-safe cryptographic procedures. An important milestone has just been reached in this process: at the end of July, the American authority announced the end of the second round of evaluation.
When the Nist began to deal with quantum-secure cryptography in 2015, 82 proposals were available for selection. After two evaluation rounds, 7 algorithms remained, including several proposals from IBM. According to the latest Nist evaluation report, the grid-based proposals are considered the most promising. After a third round, which is expected to take 12 to 18 months, binding standards should finally be in place by the end of 2021.