Mildly Short Vectors in Ideals of Cyclotomic Fields Without Quantum Computers


Ideal lattices
Cyclotomic fields
Approximate short vector problem
Mildly short vectors
Ideal class group
S-unit group

How to Cite

Biasse, J.-F., Erukulangara, M. R., Fieker, C., Hofmann, T., & Youmans, W. (2022). Mildly Short Vectors in Ideals of Cyclotomic Fields Without Quantum Computers. Mathematical Cryptology, 2(1), 84–107. Retrieved from


We present an algorithm for finding mildly short vectors in ideal lattices of cyclotomic fields, i.e. solutions to γ-SVP for γ∈2Õ(√n) where n is the degree of the field. Our algorithm is an adaptation of a method due to Cramer, Ducas and Wesolowski which is designed to use quantum computers. Our method, which only uses classical computers, leverages recursive methods using subfield computations based on norm relations introduced by Biasse, Fieker, Hofmann and Page. Our method applies to non-cyclic cyclotomic fields. In certain fields, the search for mildly short vectors efficiently reduces to subfield computations in fields of significantly smaller degree. In particular, we are able to identify infinite families of number fields where mildly short vectors can be found in time 2no(1), which is a superpolynomial improvement over the BKZ algorithm.

Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.

Copyright (c) 2022 Jean-François Biasse, Muhammed Rashad Erukulangara, Claus Fieker, Tommy Hofmann, William Youmans