Reductions from Module Lattices to Free Module Lattices, and Application to Dequantizing Module-LLL
Publication Name
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Abstract
In this article, we give evidence that free modules (i.e., modules which admit a basis) are no weaker than arbitrary modules, when it comes to solving cryptographic algorithmic problems (and when the rank of the module is at least 2). More precisely, we show that for three algorithmic problems used in cryptography, namely the shortest vector problem, the Hermite shortest vector problem and a variant of the closest vector problem, there is a reduction from solving the problem in any module of rank n≥ 2 to solving the problem in any free module of the same rank n. As an application, we show that this can be used to dequantize the LLL algorithm for module lattices presented by Lee et al. (Asiacrypt 2019).
Open Access Status
This publication is not available as open access
Volume
14085 LNCS
First Page
836
Last Page
865
Funding Number
ANR-21-CE94-0003
Funding Sponsor
Intel Corporation