Cryptographic Smooth Neighbors (original) (raw)

Paper 2022/1439

Cryptographic Smooth Neighbors

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

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}, url = {https://eprint.iacr.org/2022/1439} }