Mildly Short Vectors in Cyclotomic Ideal Lattices in Quantum Polynomial Time

DOI10.1145/3431725zbMath1499.68122OpenAlexW3118425873MaRDI QIDQ5056439

Benjamin Wesolowski, Ronald Cramer, Léo Ducas

Publication date: 8 December 2022

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/3431725

zbMATH Keywords

cyclotomic fieldsideal latticesshortest vector problem

Mathematics Subject Classification ID

Cryptography (94A60) Number-theoretic algorithms; complexity (11Y16) Lattices and convex bodies (number-theoretic aspects) (11H06) Cyclotomic extensions (11R18) Quantum algorithms and complexity in the theory of computing (68Q12)

Related Items (6)

Some easy instances of ideal-SVP and implications on the partial Vandermonde knapsack problem ⋮ Log-\(\mathcal{S}\)-unit lattices using explicit Stickelberger generators to solve approx ideal-SVP ⋮ On module unique-SVP and NTRU ⋮ On the hardness of the NTRU problem ⋮ A short basis of the Stickelberger ideal of a cyclotomic field ⋮ The special case of cyclotomic fields in quantum algorithms for unit groups

This page was built for publication: Mildly Short Vectors in Cyclotomic Ideal Lattices in Quantum Polynomial Time