Cryptographic smooth neighbors
Bruno, Giacomo; Corte-Real Santos, Maria; Costello, Craig; Eriksen, Jonathan Komada; Meyer, Michael; Naehrig, Michael; Sterner, Bruno
Peer reviewed, Journal article
Published version
Permanent lenke
https://hdl.handle.net/11250/3121750Utgivelsesdato
2023Metadata
Vis full innførselSamlinger
Originalversjon
https://doi.org/10.1007/978-981-99-8739-9_7Sammendrag
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, 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 minimise 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.