Paper 2021/1384

Log-S-unit lattices using Explicit Stickelberger Generators to solve Approx Ideal-SVP

Olivier Bernard, Andrea Lesavourey, Tuong-Huy Nguyen, and Adeline Roux-Langlois

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é in 2019. They performed experiments for prime conductors cyclotomic fields of degrees at most 70, reporting approximation factors reached in practice. The main obstacle for these experiments is the computation of a log-$\mathcal{S}$-unit lattice, which requires classical subexponential time. In this paper, our main contribution is to extend these experiments to 210 cyclotomic fields of any conductor $m$ and of degree up to $210$. Building upon new results from Bernard and Kučera on the Stickelberger ideal, we construct a maximal set of independent $\mathcal{S}$-units lifted from the maximal real subfield using explicit Stickelberger generators obtained via Jacobi sums. Hence, we obtain full-rank log-$\mathcal{S}$-unit sublattices fulfilling the role of approximating the full Tw-PHS lattice. Notably, our obtained approximation factors match those from Bernard and Roux-Langlois using the original log-$\mathcal{S}$-unit lattice in small dimensions. As a side result, we use the knowledge of these explicit Stickelberger elements to remove almost all quantum steps in the CDW algorithm, by Cramer, Ducas and Wesolowski in 2021, 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.