Paper 2019/1142

Lattice Reduction for Modules, or How to Reduce ModuleSVP to ModuleSVP

Tamalika Mukherjee and Noah Stephens-Davidowitz

Abstract

We show how to generalize lattice reduction algorithms to module lattices. Specifically, we reduce $\gamma$-approximate ModuleSVP over module lattices with rank $k \geq2$ to $\gamma'$-approximate ModuleSVP over module lattices with rank $2 \leq \beta \leq k$. To do so, we modify the celebrated slide-reduction algorithm of Gama and Nguyen to work with module filtrations, a high-dimensional generalization of the ($\Z$-)basis of a lattice. The particular value of $\gamma$ that we achieve depends on the underlying number field $K$, the order $R \subseteq \mathcal{O}_K$, and the embedding (as well as, of course, $k$, $\beta$, and $\gamma'$). However, for reasonable choices of these parameters, the resulting value of $\gamma$ is surprisingly close to the one achieved by ``plain'' lattice reduction algorithms, which require an arbitrary SVP oracle in the same dimension. In other words, we show that ModuleSVP oracles are nearly as useful as SVP oracles for solving higher-rank instances of approximate ModuleSVP. Our result generalizes the recent independent result of Lee, Pellet-Mary, Stehlé, and Wallet, which works in the important special case when $\beta = 2$ and $R = \mathcal{O}_K$ is the ring of integers of $K$ under the canonical embedding. Our reduction works for any $\beta$ dividing $k$, as well as arbitrary orders $R \subseteq \mathcal{O}_K$ and a larger class of embeddings. Indeed, at a high level our reduction can be thought of as a generalization of theirs in roughly the same way that block reduction generalizes LLL reduction.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
A minor revision of an IACR publication in CRYPTO 2020
Keywords
LatticesmodulesModuleSVPRing-LWE
Contact author(s)
noahsd @ gmail com
tmukherj @ purdue edu
History
2020-08-19: last of 3 revisions
2019-10-03: received
See all versions
Short URL
https://ia.cr/2019/1142
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2019/1142,
      author = {Tamalika Mukherjee and Noah Stephens-Davidowitz},
      title = {Lattice Reduction for Modules, or How to Reduce ModuleSVP to ModuleSVP},
      howpublished = {Cryptology ePrint Archive, Paper 2019/1142},
      year = {2019},
      note = {\url{https://eprint.iacr.org/2019/1142}},
      url = {https://eprint.iacr.org/2019/1142}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.