Title: Cryptographic Smooth Neighbors
Abstract: We explore the number-theoretic problem
of finding two large and consecutive smooth integers
(which we call smooth twins). This has been the subject
of many recent isogeny-based cryptosystems whereby
finding parameters is related to this problem. Despite
the simplicity of the problems description, it is actually
not easy to find these integers. This is in large part due
to the fact that, for a smoothness bound B, there are
finitely many B-smooth twins. So extracting these
smooth twins from a large set is very difficult.
We revisit this problem 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 twins, 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.
Additionally, we present a new general method for
finding smooth twins that draws inspiration from
the probabilistic methods that have been presented
in the literature. One can view this new method has
a hierarchy of the known methods since they appear
as a special case of this more general framework.
Subsequently, we use the twins that were found from these
computations to produce cryptographic parameters for the
isogeny-based signature scheme SQISign which requires a
slightly modified setup compared to the pure twin smooth
problem. In particular, the corresponding computable
isogeny degrees within our NIST-I parameters are
significantly smoother than that of prior work. In addition
we propose the first parameter sets geared towards
efficient SQISign instantiations at NIST’s security
levels III and V.
