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.