Paper 2021/1384

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

Olivier Bernard, Univ Rennes, CNRS, IRISA, France, Thales, Gennevilliers, France
Andrea Lesavourey, Univ Rennes, CNRS, IRISA, France
Tuong-Huy Nguyen, Univ Rennes, CNRS, IRISA, France, DGA Maîtrise de l'Information, Bruz, France
Adeline Roux-Langlois, Univ Rennes, CNRS, IRISA, France
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.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
A major revision of an IACR publication in ASIACRYPT 2022
Keywords
Ideal lattices Approx-SVP Stickelberger ideal S-unit attacks Twisted-PHS algorithm
Contact author(s)
olivier bernard @ normalesup org
andrea lesavourey @ irisa fr
tuong-huy nguyen @ irisa fr
adeline roux-langlois @ irisa fr
History
2022-09-19: last of 3 revisions
2021-10-15: received
See all versions
Short URL
https://ia.cr/2021/1384
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/1384,
      author = {Olivier Bernard and Andrea Lesavourey and Tuong-Huy Nguyen and Adeline Roux-Langlois},
      title = {Log-$\mathcal{S}$-unit lattices using Explicit Stickelberger Generators to solve Approx Ideal-SVP},
      howpublished = {Cryptology ePrint Archive, Paper 2021/1384},
      year = {2021},
      note = {\url{https://eprint.iacr.org/2021/1384}},
      url = {https://eprint.iacr.org/2021/1384}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.