Welcome to the resource topic for 2019/1142
Title:
Lattice Reduction for Modules, or How to Reduce ModuleSVP to ModuleSVP
Authors: Tamalika Mukherjee, 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.
ePrint: https://eprint.iacr.org/2019/1142
Talk: https://www.youtube.com/watch?v=dEsTYS75RMc
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .