Mildly Short Vectors in Ideals of Cyclotomic Fields Without Quantum Computers

Abstract

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 2^no(1), which is a superpolynomial improvement over the BKZ algorithm.