Paper 2021/1384

Log-$\mathcal{S}$-unit lattices using Explicit Stickelberger Generators to solve Approx Ideal-SVP

Abstract

In 2020, Bernard and Roux-Langlois introduced the Twisted-PHS algorithm to solve Approx-SVP for ideal lattices on any number field, based on the PHS algorithm by Pellet-Mary, Hanrot and Stehlé. They performed experiments for prime conductors cyclotomic fields of degrees at most 70, one of the main bottlenecks being the computation of a log-$\mathcal{S}$-unit lattice which requires subexponential time. Our main contribution is to extend these experiments to cyclotomic fields of degree up to $210$ for most conductors $m$. Building upon new results from Bernard and Kučera on the Stickelberger ideal, we use explicit generators to construct full-rank log-$\mathcal{S}$-unit sublattices fulfilling the role of approximating the full Twisted-PHS lattice. In our best approximate regime, our results show that the Twisted-PHS algorithm outperforms, over our experimental range, the CDW algorithm by Cramer, Ducas and Wesolowski, and sometimes beats its asymptotic volumetric lower bound. Additionally, we use these explicit Stickelberger generators to remove almost all quantum steps in the CDW algorithm, under the mild restriction that the plus part of the class number verifies $h^+_{m}\leq O(\sqrt{m})$.

Note: Update (29/11/2021): We improved the drift strategy used to guarantee that the output is indeed in the challenge ideal, obtaining much better and narrower estimated approximation factors than previously reported in the 15/10/2021 version, as shown by new Fig.1.1, 5.3 et 5.4. We also further extended the range of experiments to include cyclotomic fields of degree up to 210. Update (19/09/2022): We included the results of the comparison with the CDW algorithm and clarifications with respect to other related works. Update (14/02/2022): Adding references to the published version (DOI:10.1007/978-3-031-22969-5_23).