Cryptology ePrint Archive: Report 2021/1384

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

Olivier Bernard and Andrea Lesavourey and 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 192 cyclotomic fields of any conductor $m$ and of degree up to $190$. Building upon new results from Bernard and Kucera 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})$.

Category / Keywords: public-key cryptography / Ideal lattices, Approx-SVP, Stickelberger, S-units, Twisted-PHS

Date: received 13 Oct 2021, last revised 15 Oct 2021

Contact author: olivier bernard at irisa fr, andrea lesavourey at irisa fr, tuong-huy nguyen at irisa fr, adeline roux-langlois at irisa fr

Available format(s): PDF | BibTeX Citation

Version: 20211015:184743 (All versions of this report)

Short URL: ia.cr/2021/1384