Paper 2022/1439

Cryptographic Smooth Neighbors

Giacomo Bruno, IKARUS Security Software
Maria Corte-Real Santos, University College London
Craig Costello, Microsoft Research
Jonathan Komada Eriksen, Norwegian University of Science and Technology
Michael Meyer, University of Regensburg
Michael Naehrig, Microsoft Research
Bruno Sterner, University of Surrey
Abstract

We revisit the problem of finding two consecutive $B$-smooth integers by giving an optimised implementation of the Conrey-Holmstrom-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. Though these solutions are still not large enough to be cryptographic parameters themselves, we feed them as input into known methods of searching for twins to yield cryptographic parameters that are much smoother than those given in prior works. Our methods seem especially well-suited to finding parameters for the SQISign signature scheme, particularly those that are geared towards high-security levels.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
A minor revision of an IACR publication in ASIACRYPT 2023
Keywords
Post-quantum cryptographyisogeny-based cryptographytwin smooth integerssmooth neighborsPell equationSQISign.
Contact author(s)
giako13 @ gmail com
maria santos 20 @ ucl ac uk
craigco @ microsoft com
jonathan k eriksen @ ntnu no
michael @ random-oracles org
mnaehrig @ microsoft com
b sterner @ surrey ac uk
History
2023-10-25: last of 2 revisions
2022-10-21: received
See all versions
Short URL
https://ia.cr/2022/1439
License
No rights reserved
CC0

BibTeX

@misc{cryptoeprint:2022/1439,
      author = {Giacomo Bruno and Maria Corte-Real Santos and Craig Costello and Jonathan Komada Eriksen and Michael Meyer and Michael Naehrig and Bruno Sterner},
      title = {Cryptographic Smooth Neighbors},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1439},
      year = {2022},
      note = {\url{https://eprint.iacr.org/2022/1439}},
      url = {https://eprint.iacr.org/2022/1439}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.