Overstretched Parameters in Lattice-Based Cryptography

Abstract

Lattice-based cryptosystems such as Learning With Errors (LWE) and NTRU have gained popularity as one of the main methods for constructing cryptosystems secure against a quantum attacker. The process of instantiating these involves fixing multiple parameters based on cost estimates for performing lattice reduction attacks to find the secret key. Instantiations of NTRU using large moduli q, known as overstretched NTRU, are known to suffer from an attack that allows discovery of a dense sublattice of the q-ary NTRU lattice, breaking the cryptosystem at a significantly smaller cost than the traditional secret key recovery attack.

The question of whether ring-LWE, module-LWE and NTWE suffer from the dense sublattice attack remains unresolved. We apply the attack model developed by Ducas and van Woerden to these problems to produce asymptotic cost estimates for the dense sublattice attack. We find module-LWE and ring-LWE are not expected to suffer from this attack, while NTWE is. This is further corroborated by experiments performed on NTWE. Additionally, the analysis performed on NTRU by Ducas and van Woerden is extended to larger polynomial coefficients.

Taken together, we show that lattice-based cryptographic problems that have a corresponding problem on a q-ary lattice with a dense sublattice could be vulnerable to the dense sublattice attack and that the attack model can be used to predict such a vulnerability.