International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

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

Authors:
Olivier Bernard , Univ Rennes, CNRS, IRISA, France and Thales, Gennevilliers, France
Andrea Lesavourey , Univ Rennes, CNRS, IRISA, France
Tuong-Huy Nguyen , Univ Rennes, CNRS, IRISA, France and DGA Maîtrise de l'Information, Bruz, France
Adeline Roux-Langlois , Univ Rennes, CNRS, IRISA, France
Download:
Search ePrint
Search Google
Presentation: Slides
Conference: ASIACRYPT 2022
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-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-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 hm+≤O(m).
BibTeX
@inproceedings{asiacrypt-2022-32512,
  title={Log-$\mathcal{S}$-unit lattices using Explicit Stickelberger Generators to solve Approx Ideal-SVP},
  publisher={Springer-Verlag},
  author={Olivier Bernard and Andrea Lesavourey and Tuong-Huy Nguyen and Adeline Roux-Langlois},
  year=2022
}