Paper 2023/1576

Towards Optimally Small Smoothness Bounds for Cryptographic-Sized Twin Smooth Integers and its Isogeny-based Applications

Abstract

We give a new approach for finding large twin smooth integers. Those twins whose sum is a prime are of interest in the parameter setup of certain isogeny-based cryptosystems such as SQISign. The approach to find such twins is to find two polynomials in $\Q[x]$ that split into a product of small degree factors and differ by $1$; then evaluate them on a particular smooth integer. This was first explored by Costello, Meyer and Naehrig at EUROCRYPT'21 using polynomials that split completely into linear factors which were found from some Diophantine number theory. The polynomials used in this work split into mostly linear factors with the exception of a few quadratic factors. Some of these linear factors are repeated and so the overall smoothness probability is either better or comparable to that of the prior polynomials. We utilise these polynomials to search for large twin smooth integers whose sum is prime. In particular, the smoothness bound of the $384$ and $512$-bit instances that we find are significantly smaller than those found in EUROCRYPT'21.