International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Paper: Sieving for twin smooth integers with solutions to the Prouhet-Tarry-Escott problem

Authors:
Craig Costello , Microsoft Research USA
Michael Meyer , University of Applied Sciences Wiesbaden, Germany
Michael Naehrig , Microsoft Research USA
Download:
DOI: 10.1007/978-3-030-77870-5_10 (login may be required)
Search ePrint
Search Google
Conference: EUROCRYPT 2021
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 l in Z such that a(l) = b(l) = 0 mod C , the two integers a(l)/C and b(l)/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 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 <= 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.
Video from EUROCRYPT 2021
BibTeX
@inproceedings{eurocrypt-2021-30840,
  title={Sieving for twin smooth integers with solutions to the Prouhet-Tarry-Escott problem},
  publisher={Springer-Verlag},
  doi={10.1007/978-3-030-77870-5_10},
  author={Craig Costello and Michael Meyer and Michael Naehrig},
  year=2021
}