Paper 2019/215 Original: eprint.iacr.org/2019/215 ↗

Approx-SVP in Ideal Lattices with Pre-processing

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.