@inproceedings{costello2021sieving, author = {Costello, Craig}, title = {Sieving for twin smooth integers with solutions to the Prouhet-Tarry-Escott problem}, booktitle = {EUROCRYPT 2021}, year = {2021}, month = {May}, abstract = {We give a sieving algorithm for finding pairs of consecutive smooth numbers that utilizes solutions to the Prouhet-Tarry-Escott (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 $\Z[x]$. It follows that for any $\ell \in \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 \emph[twin smooth] integers lies in their application to compact isogeny-based post-quantum protocols. The recent key exchange scheme B-SIDH 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 $p-1$ are $2^[15]$-smooth; the smoothest prior parameters had a similar sized prime for which $p-1$ and $p+1$ were $2^[19]$-smooth. In targeting higher security levels, our sieve found a 376-bit prime lying between two $2^[21]$-smooth integers, a 384-bit prime lying between two $2^[22]$-smooth integers, and a 512-bit prime lying between two $2^[29]$-smooth integers. Our analysis shows that using previously known methods to find high-security instances subject to these smoothness bounds is computationally infeasible.}, publisher = {Springer-Verlag}, url = {http://approjects.co.za/?big=en-us/research/publication/sieving-for-twin-smooth-integers-with-solutions-to-the-prouhet-tarry-escott-problem/}, }