Paper 2024/844
Finding Dense Submodules with Algebraic Lattice Reduction
Abstract
We prove an algebraic analogue of Pataki-Tural lemma (Pataki-Tural, arXiv:0804.4014, 2008) -- the main tool in analysing the so-called overstretched regime of NTRU. Our result generalizes this lemma from Euclidean lattices to modules over any number field enabling us to look at NTRU as rank-2 module over cyclotomic number fields with a rank-1 dense submodule generated by the NTRU secret key. For Euclidean lattices, this overstretched regime occurs for large moduli $q$ and enables to detect a dense sublattice in NTRU lattices leading to faster NTRU key recovery. We formulate an algebraic version of this event, the so-called Dense Submodule Discovery (DSD) event, and heuristically predict under which conditions this event happens. For that, we formulate an algebraic version of the Geometric Series Assumption -- an heuristic tool that describes the behaviour of algebraic lattice reduction algorithms. We verify this assumption by implementing an algebraic LLL -- an analog of classical LLL lattice reduction that operates on the module level. Our experiments verify the introduced heuristic, enabling us to predict the algebraic DSD event.
Note: This is a full version of the eponymous AfricaCrypt 2024 submission.
Metadata
- Available format(s)
-
PDF
- Category
- Attacks and cryptanalysis
- Publication info
- Preprint.
- Keywords
- NTRUCryptoanalysisLLL algorithmModule Lattices
- Contact author(s)
-
alexander karenin @ tii ae
elena kirshanova @ tii ae - History
- 2024-05-31: approved
- 2024-05-29: received
- See all versions
- Short URL
- https://ia.cr/2024/844
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2024/844,
author = {Alexander Karenin and Elena Kirshanova},
title = {Finding Dense Submodules with Algebraic Lattice Reduction},
howpublished = {Cryptology {ePrint} Archive, Paper 2024/844},
year = {2024},
url = {https://eprint.iacr.org/2024/844}
}
