Paper 2020/1283
Sieving for twin smooth integers with solutions to the ProuhetTarryEscott problem
Craig Costello, Michael Meyer, and Michael Naehrig
Abstract
We give a sieving algorithm for finding pairs of consecutive smooth numbers that utilizes solutions to the ProuhetTarryEscott (PTE) problem. Any such solution induces two degree$n$ polynomials, $a(x)$ and $b(x)$, that differ by a constant integer $C$ and completely split into linear factors in $\mathbb{Z}[x]$. It follows that for any $\ell \in \mathbb{Z}$ such that $a(\ell) \equiv b(\ell) \equiv 0 \bmod{C}$, the two integers $a(\ell)/C$ and $b(\ell)/C$ differ by 1 and necessarily contain $n$ factors of roughly the same size. For a fixed smoothness bound $B$, restricting the search to pairs of integers that are parameterized in this way increases the probability that they are $B$smooth. Our algorithm combines a simple sieve with parametrizations given by a collection of solutions to the PTE problem. The motivation for finding large twin smooth integers lies in their application to compact isogenybased postquantum protocols. The recent key exchange scheme BSIDH and the recent digital signature scheme SQISign both require large primes that lie between two smooth integers; finding such a prime can be seen as a special case of finding twin smooth integers under the additional stipulation that their sum is a prime $p$. When searching for cryptographic parameters with $2^{240} \leq p <2^{256}$, an implementation of our sieve found primes $p$ where $p+1$ and $p1$ are $2^{15}$smooth; the smoothest prior parameters had a similar sized prime for which $p1$ and $p+1$ were $2^{19}$smooth. In targeting higher security levels, our sieve found a 376bit prime lying between two $2^{21}$smooth integers, a 384bit prime lying between two $2^{22}$smooth integers, and a 512bit prime lying between two $2^{28}$smooth integers. Our analysis shows that using previously known methods to find highsecurity instances subject to these smoothness bounds is computationally infeasible.
Metadata
 Available format(s)
 Category
 Publickey cryptography
 Publication info
 A minor revision of an IACR publication in EUROCRYPT 2021
 Keywords
 Postquantum cryptographyisogenybased cryptographyProuhetTarryEscott problemtwin smooth integersBSIDHSQISign
 Contact author(s)
 michael meyer @ hsrm de
 History
 20210520: last of 3 revisions
 20201014: received
 See all versions
 Short URL
 https://ia.cr/2020/1283
 License

CC BY
BibTeX
@misc{cryptoeprint:2020/1283, author = {Craig Costello and Michael Meyer and Michael Naehrig}, title = {Sieving for twin smooth integers with solutions to the ProuhetTarryEscott problem}, howpublished = {Cryptology ePrint Archive, Paper 2020/1283}, year = {2020}, note = {\url{https://eprint.iacr.org/2020/1283}}, url = {https://eprint.iacr.org/2020/1283} }