International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Approx-SVP in Ideal Lattices with Pre-processing

Authors:
Alice Pellet-Mary
Guillaume Hanrot
Damien Stehlé
Download:
DOI: 10.1007/978-3-030-17656-3_24 (login may be required)
Search ePrint
Search Google
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
}