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 Naehrig, Microsoft Research
Michael Meyer, University of Regensburg
Bruno Sterner, University of Surrey

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.

Available format(s)
Publication info
Post-quantum cryptography isogeny-based cryptography twin smooth integers smooth neighbors Pell equation SQISign.
Contact author(s)
giako13 @ gmail com
maria santos 20 @ ucl ac uk
craigco @ microsoft com
jonathan k eriksen @ ntnu no
mnaehrig @ microsoft com
michael @ random-oracles org
b sterner @ surrey ac uk
2022-10-25: approved
2022-10-21: received
See all versions
Short URL
No rights reserved


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