A new vulnerability threatens three finalists of the NIST Post-Quantum Cryptography contest
At the beginning of April 2022, the Center of Encryption and Information Security (an information security unit within the Israeli Defence Force) published a report on the security of Learning with Errors (LWE) and Learning with Rounding (LWR) based algorithms. The report is of particular interest because three of the six shortlisted finalists in NIST’s post-quantum cryptography standardization project are LWE/LWR based.
The report shows that the application of some improvements to a specific attack type (known as a dual lattice attack) significantly reduces the security of the shortlisted algorithms – to the point that they fall below NIST’s required security threshold. The claim is, of course, under scrutiny by the community.
Abstract
“Many of the leading post-quantum key exchange and signature schemes rely on the conjectured hardness of the Learning with Errors (LWE) and Learning with Rounding (LWR) problems and their algebraic variants, including 3 of the 6 finalists in NIST’s PQC process. The best-known cryptanalysis techniques against these problems are primal and dual lattice attacks, where dual attacks are generally considered less practical.
In this report, we present several algorithmic improvements to the dual lattice attack, which allow it to exceed the efficiency of primal attacks. In the improved attack, we enumerate over more coordinates of the secret and use an improved distinguisher based on FFT. In addition, we incorporate improvements to the estimates of the cost of performing a lattice sieve in the RAM model, reducing the gate-count of random product code decoding and performing less inner product calculations.
Combining these improvements considerably reduces the security levels of Kyber, Saber and Dilithium, the LWE/LWR based finalists, bringing them below the thresholds defined by NIST.”
A copy of the full report is available to download here.
Transitioning to quantum-safe security
Having the cybersecurity unit of a defence agency publish this type of report is a bit unusual. You might think the exposure of a specific weakness might be beyond their usual purview. One interpretation may be that they see the risk of standardizing a potentially vulnerable algorithm as too high. After all, if the good guys can find the vulnerability, you can bet the bad guys will too. This involvement in the NIST process shouldn’t be seen as a bad thing. The fact that stakeholders from around the world are independently testing the shortlisted algorithms demonstrates how seriously everyone is taking it.
This is the first time that military cryptographers include QKD as a possible solution. Could this precede a change of mind for the NSA (in the USA) and the NCSC (in the UK), who have both been rather vocal against the use of quantum technologies to counter the quantum threat?
The conclusion is obvious: both QKD and PQC are needed for long-term security in the quantum era.
