International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Cryptographic Smooth Neighbors

Authors:
Giacomo Bruno , IKARUS Security Software
Maria Corte-Real Santos , University College London
Craig Costello , Microsoft Research
Jonathan Komada Eriksen , NTNU
Michael Meyer , University of Regensburg
Michael Naehrig , Microsoft Research
Bruno Sterner , University of Surrey
Download:
Search ePrint
Search Google
Presentation: Slides
Conference: ASIACRYPT 2023
Abstract: We revisit the problem of finding two consecutive B-smooth integers by giving an optimised implementation of the Conrey-Holm\-strom-McLaughlin ``smooth neighbors'' algorithm. While this algorithm is not guaranteed to return the complete set of B-smooth neighbors, in practice it returns a very close approximation to the complete set but does so in a tiny fraction of the time of its exhaustive counterparts. We exploit this algorithm to find record-sized solutions to the pure twin smooth problem, and subsequently to produce instances of cryptographic parameters whose corresponding isogeny degrees are significantly smoother than prior works. Our methods seem well-suited to finding parameters for the SQISign signature scheme, especially for instantiations looking to minimize the cost of signature generation. We give a number of examples, among which are the first parameter sets geared towards efficient SQISign instantiations at NIST's security levels III and V.
BibTeX
@inproceedings{asiacrypt-2023-33453,
  title={Cryptographic Smooth Neighbors},
  publisher={Springer-Verlag},
  author={Giacomo Bruno and Maria Corte-Real Santos and Craig Costello and Jonathan Komada Eriksen and Michael Meyer and Michael Naehrig and Bruno Sterner},
  year=2023
}