CryptoDB
Approx-SVP in Ideal Lattices with Pre-processing
| Authors: | |
|---|---|
| Download: |
|
| 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 |\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. |
Video from EUROCRYPT 2019
BibTeX
@article{eurocrypt-2019-29376,
title={Approx-SVP in Ideal Lattices with Pre-processing},
booktitle={Advances in Cryptology – EUROCRYPT 2019},
series={Advances in Cryptology – EUROCRYPT 2019},
publisher={Springer},
volume={11477},
pages={685-716},
doi={10.1007/978-3-030-17656-3_24},
author={Alice Pellet-Mary and Guillaume Hanrot and Damien Stehlé},
year=2019
}