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 |\varDelta |$$
log|Δ| with
$$\varDelta $$
Δ 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 |\varDelta |)^{\alpha +1}/n))$$
exp(O~((log|Δ|)α+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 |\varDelta |)^{\max (2/3, 1-2\alpha )}))$$
exp(O~((log|Δ|)max(2/3,1-2α))) in the classical setting, and
$$\exp (\widetilde{O}((\log |\varDelta |)^{1-2\alpha }))$$
exp(O~((log|Δ|)1-2α)) 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 et 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.