## CryptoDB

### Paper: Lattice Reduction for Modules, or How to Reduce ModuleSVP to ModuleSVP

Authors: Tamalika Mukherjee , Purdue University Noah Stephens-Davidowitz , Simons Institute DOI: https://doi.org/10.1007/978-3-030-56880-1_8 (login may be required) Search ePrint Search Google CRYPTO 2020 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$ and $\beta$). However, for reasonable choices of these parameters, the approximation factor that we achieve 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 approximate ModuleSVP in higher dimensions. Our result generalizes the recent independent result of Lee, Pellet-Mary, Stehl\'e, 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. 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.
##### BibTeX
@inproceedings{crypto-2020-30526,
title={Lattice Reduction for Modules, or How to Reduce ModuleSVP to ModuleSVP},
publisher={Springer-Verlag},
doi={https://doi.org/10.1007/978-3-030-56880-1_8},
author={Tamalika Mukherjee and Noah Stephens-Davidowitz},
year=2020
}