Welcome to the resource topic for 2019/215
Title:
Approx-SVP in Ideal Lattices with Pre-processing
Authors: Alice Pellet-Mary, Guillaume Hanrot, 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.
ePrint: https://eprint.iacr.org/2019/215
Talk: https://www.youtube.com/watch?v=Plh9ygNT-E4
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .