A team of cryptanalysts from Centrum Wiskunde & Informatica (CWI) has set a new code breaking record for an important computational problem: the lattice shortest vector problem (SVP). Lattice SVP is a foundation for the security of next generation public-key cryptography, designed to be secure against quantum computers. Their result is a new frontier in the computational state-of-the-art of cryptographic techniques, making use of high-performance graphics cards. This research is aimed to provide crucial insights into secure parameter choices for next generation cryptography. The team's paper 'Advanced Lattice Sieving on GPUs, with Tensor Cores' was accepted this month for the Eurocrypt 2021 conference, which takes place in October.
Internet and computer security are founded on cryptographic standards, enabling HTTPS security, electronic banking, signing documents, and software standards. Public-key cryptography (PKC) is fundamental for these applications. The most common PKC systems are built on specific mathematical computational problems, called the integer factoring problem and the discrete log problem. As long as you make these problems too difficult to solve, these cryptographic systems are safe. But although these systems meet the security requirements of today, in theory they can be broken using a large-scale general quantum computer in the future.
Shortest Vector Problem
In order to provide security against quantum computers, cryptologists design the next generation of public-key cryptography based on other mathematical problems studied for decades. One of these alternatives are lattices: a grid of points in a multidimensional space. The security of lattice-based cryptography depends on the hardness of certain lattice problems, the most central one being finding the shortest vector in the lattice of large dimension. The difficulty of this problem can be vastly increased by using more and more dimensions, making it increasingly difficult to solve – and therefore break – by both classical and quantum computers.
Challenge
Researchers of CWI’s Cryptology group have now solved the short vector problem for 180 dimensions in 52 days. The record was set as part of the Darmstadt Lattice Challenges, which was created to encourage cryptanalysis into lattice-based cryptography. The challenges consist of lattices of varying dimension and varying computational problems, including the most prominent: the shortest vector problem.
The team was composed of Leo Ducas, Marc Stevens and Wessel van Woerden, members of the CWI Cryptology group, headed by Prof. Ronald Cramer. The group investigates fundamental cryptographic questions from a broad scientific perspective, particularly from mathematics, computer science and physics.
Special machine
The team set the 52-day record using a special machine with 1.5 TB of RAM and four AI-capable graphics cards. The team has leveraged significant advances in cryptanalytic techniques as well as the exceptional computational power of the used graphic cards. Their NVIDIA RTX-2080 cards contain special high-performance tensor cores designed for AI and ray-tracing computations.
In comparison, the top-level record four years ago for a 150-dimensional lattice was achieved using several supercomputers taking more than a year. Since then, another approach called lattice sieving has taken the lead solving SVP up to dimension 155 in only weeks, where available resources limited immediate further progress. According to the researchers, with their new algorithmic improvements to sieving and using graphics cards, solving the 150-dimensional SVP takes only about one hour on their single machine and enables them to reach 180-dimensional SVP.
Why is this important and urgent
Lattice-based cryptography systems are considered a candidate for providing the first cryptographic standard to protect sensitive electronic data against the threat of quantum computers. To drive the development of the new standards, the US National Institute of Standards and Technology (NIST) is running a competition for new public-key cryptography standards secure against quantum computers. Among the seven schemes selected as finalists of the NIST competitions, five of them rely on lattices, including two designed in part at CWI.
Urgency
Even though sufficiently large quantum computers are unlikely to exist in the next decade or more, there is great urgency. It will take many years to actually deploy the upcoming standards. Meanwhile data protected by our current old cryptosystems can be eavesdropped and stored now to be broken later on.
Cryptographers crucially rely on large continuous cryptanalysis efforts, to expose weaknesses and deprecate weak standards. Another important goal is to validate the recommended key sizes and potentially increase them, similar to the RSA factoring efforts over the last decades in which CWI has also been involved.
This state-of-the-art cryptanalysis supports the proposed conservatively chosen key sizes to be secure. The computational cost grows exponentially, more doubling every four extra dimensions. Extrapolating suggests that breaking the NIST candidates — which would require solving SVP in dimensions greater than 400 — costs several billions of billions more computational effort. While this sounds astronomically infeasible, cryptographers usually keep sizable security margins in prediction of future progress on algorithms and hardware.
One question that might arise when the next record will be set. The CWI researchers estimate that they’ve essentially reached what is feasible with their algorithm on this high-end machine, even if they would let it run longer. Indeed, the required memory grows with each added dimension, and the SVP challenge of 180 dimensions already consumed the 1.5 Terabytes of RAM in their machine. Going further will require significantly more resources: clusters of several machines and/or hard drive storage. This raises further challenges to make effective use of such resources given the limitations they impose, in particular the vastly more limited bandwidth and worse latency compared to RAM.
The new SVP challenge record falls in a long line of similar cryptanalytic efforts — affecting real-world cryptographic practice — by cryptanalysts all over the world and at CWI.
The RSA Cryptosystem is the most widely used public-key cryptosystem and its security relies on the hardness of factoring. The RSA factoring challenges were introduced in 1991. The RSA factoring efforts since then have been the benchmark on which RSA key size recommendations are founded even today. CWI has been involved in the RSA factoring challenges since 1993 till 2012 with the retirement of Herman te Riele.
Cryptographic hash functions are another important cryptographic tool and a crucial part of all digital signatures. MD5 and SHA-1 have been industry’s de facto standards for many applications, including digital signatures. However, Chinese researchers lead by Prof. Xiaoyun Wang demonstrated in 2004 and 2005 that both MD5 and SHA-1 have significant weaknesses. CWI has been involved in efforts from 2008 till 2017 in studying the graveness of MD5’s and SHA-1’s weaknesses by significantly improving attacks in practice and demonstrating real world threats. Today’s secure hash standards are SHA-2 and a new hash standard SHA-3, published by NIST in 2012 following MD5’s and SHA-1’s weaknesses.
About CWI
Founded in 1946, Centrum Wiskunde & Informatica (CWI) is the national research institute for mathematics and computer science in the Netherlands. It is located at Amsterdam Science Park and is part of the Institutes Organisation of the Netherlands Organisation for Scientific Research (NWO). The institute is internationally focused and renowned. Over 150 researchers conduct pioneering research and share their acquired knowledge with society. Over 30 researchers are also employed as professors at universities. The institute has generated twenty-seven spin-off companies.
On 10 February Léo Ducas tweeted about the preprint: 'Is it possible to write a serious (...) paper mentioning crypto, quantum, *and* AI ? We answer this question positively in a joint work with @WesselWoerden @realhashbreaker, solving Darmstadt lattice challenge SVP-180 using AI-purpose hardware. https://eprint.iacr.org/2021/141.pdf'.
