Paper 2019/215
Approx-SVP in Ideal Lattices with Pre-processing
Alice Pellet-Mary, Guillaume Hanrot, and Damien Stehlé
Abstract
We describe an algorithm to solve the approximate Shortest Vector Problem for lattices corresponding to ideals of the ring of integers of an arbitrary number field $K$. This algorithm has a pre-processing phase, whose run-time is exponential in $\log |\Delta|$ with $\Delta$ the discriminant of $K$. Importantly, this pre-processing phase depends only on $K$. The pre-processing phase outputs an advice, whose bit-size is no more than the run-time of the query phase. Given this advice, the query phase of the algorithm takes as input any ideal $I$ of the ring of integers, and outputs an element of $I$ which is at most $\exp(\widetilde O((\log |\Delta|)^{\alpha+1}/n))$ times longer than a shortest non-zero element of $I$ (with respect to the Euclidean norm of its canonical embedding). This query phase runs in time and space $\exp(\widetilde O( (\log |\Delta|)^{\max(2/3, 1-2\alpha)}))$ in the classical setting, and $\exp(\widetilde O((\log |\Delta|)^{1-2\alpha}))$ in the quantum setting. The parameter $\alpha$ can be chosen arbitrarily in $[0,1/2]$. Both correctness and cost analyses rely on heuristic assumptions, whose validity is consistent with experiments. The algorithm builds upon the algorithms from Cramer al. [EUROCRYPT 2016] and Cramer et al. [EUROCRYPT 2017]. It relies on the framework from Buchmann [Séminaire de théorie des nombres 1990], which allows to merge them and to extend their applicability from prime-power cyclotomic fields to all number fields. The cost improvements are obtained by allowing precomputations that depend on the field only.
Metadata
- Available format(s)
-
PDF
- Category
- Foundations
- Publication info
- Published by the IACR in EUROCRYPT 2019
- Contact author(s)
-
alice pellet___mary @ ens-lyon fr
guillaume hanrot @ ens-lyon fr
damien stehle @ ens-lyon fr - History
- 2019-02-27: received
- Short URL
- https://ia.cr/2019/215
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2019/215, author = {Alice Pellet-Mary and Guillaume Hanrot and Damien Stehlé}, title = {Approx-{SVP} in Ideal Lattices with Pre-processing}, howpublished = {Cryptology {ePrint} Archive, Paper 2019/215}, year = {2019}, url = {https://eprint.iacr.org/2019/215} }