Newsletters

PQC – security concerns about Learning with Errors (LWE)?

Share it

Table of Contents

Abstract

It is well known that the Learning with Errors problem, together with its variations, represents a key ingredient for prospective quantum-resistant cryptographic algorithms due to its efficiency properties and good implementation properties, as is shown by the fact that several proposals for the NIST competition on post quantum cryptography rely on flavors of the problem. In 2022 Koblitz et al. present a paper stating some concerns and skepticism about the security of some versions of the Learning with Errors problem as underlying problems for quantum-resistant schemes.

A brief introduction to LWE

The learning with errors (LWE) problem is parametrized by integers n, m and q together with a probability distribution D on Zq. The input in this problem is given by a pair (A, v) where A is a m × n matrix with entries in Zq is chosen uniformly and v is either:

  1. a chosen uniformly vector with m components in Zq or 
  2. A · s + e for uniformly chosen s with n components in Zq and e with m components in Zq. 

The goal of the problem is to distinguish some non-negligible probability between these two cases.

The SIVP problem and reductions

This SIVP problem asks for, given a basis of a lattice L and a factor c > 1, to find a linearly independent vectors set {y1, …, yn} such that max || yi || ≤ c · λn(L) where

A reduction from worst-case lattice problems such as SIVP to LWE was established by Regev, giving a strong indication that the LWE problem is hard. 

This reduction, however, is a quantum reduction, so the algorithm performing the reduction is a quantum algorithm. What this means is that the hardness of LWE (and hence the security of the cryptosystem) is established based on the worst-case quantum hardness of the SIVP. This means that LWE can be considered hard as long as there is no quantum algorithm solving SIVP. Hence, this result is weaker than a classical result.

Koblitz’s concerns

In a recent collaboration, Koblitz et al. perform a concrete and exhaustive analysis of the polynomial-time security reduction from the approximate SIVP to the Decision Learning With Errors (DLWE) problem in ideal lattices. The authors give a concrete analysis of this multi-step reduction and find that the tightness gap in the reduction is so great as to vitiate any meaningful security guarantee and find reasons to doubt the feasibility in the foreseeable future of the quantum part of the reduction. 

In addition, the authors find that the approximation factor in the SIVP problem is far larger than expected, a circumstance that causes the corresponding approximate-SIVP problem most likely not to be hard for proposed cryptosystem parameters.

Conclusions

Although the paper by Koblitz may sound concerning, it is important to keep in mind that the fact revolving around the quantum reduction of SIVP to LWE was known almost from the creation of the LWE problem. The paper by Koblitz only makes these concerns concrete, but in no case puts any further doubt on the security of the schemes based on the several flavors of LWE; nevertheless: it makes clear that there is no rigorous mathematical argument that supports the security of DLWE based cryptosystems.

The above conclusions do not mean that these schemes are insecure. In fact, the authors acknowledge that they were not able to find any attack on LWE, and cannot even assure the existence of such an attack. Therefore, one needs to tackle LWE-based cryptosystems as symmetric algorithms: they are secure until somebody cracks them.

References:

N. Koblitz, S. Samajder, P. Sarkar, and S. Singha, Concrete Analysis of Approximate Ideal-SIVP to Decision Ring-LWE Reduction, Cryptology ePrint Archive, Paper 2022/275, 2022.

More articles