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.
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