### Cryptographic Smooth Neighbors

##### 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.

Available format(s)
Category
Foundations
Publication info
Preprint.
Keywords
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
History
2022-10-25: approved
See all versions
Short URL
https://ia.cr/2022/1439

CC0

BibTeX

@misc{cryptoeprint:2022/1439,
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{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.