International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Reductions from module lattices to free module lattices, and application to dequantizing module-LLL

Authors:
Gabrielle De Micheli , University of California, San Diego
Daniele Micciancio , University of California, San Diego
Alice Pellet-Mary , CNRS and university of Bordeaux
Nam Tran , University of Wollongong and CSIRO Data61, Australia
Download:
DOI: 10.1007/978-3-031-38554-4_27 (login may be required)
Search ePrint
Search Google
Presentation: Slides
Conference: CRYPTO 2023
Abstract: In this article, we give evidences 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).
BibTeX
@inproceedings{crypto-2023-33175,
  title={Reductions from module lattices to free module lattices, and application to dequantizing module-LLL},
  publisher={Springer-Verlag},
  doi={10.1007/978-3-031-38554-4_27},
  author={Gabrielle De Micheli and Daniele Micciancio and Alice Pellet-Mary and Nam Tran},
  year=2023
}