Paper 2020/1283

Sieving for twin smooth integers with solutions to the Prouhet-Tarry-Escott 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 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 Z such that a()b()0modC, the two integers a()/C and b()/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 . When searching for cryptographic parameters with , an implementation of our sieve found primes where and are -smooth; the smoothest prior parameters had a similar sized prime for which and were -smooth. In targeting higher security levels, our sieve found a 376-bit prime lying between two -smooth integers, a 384-bit prime lying between two -smooth integers, and a 512-bit prime lying between two -smooth integers. Our analysis shows that using previously known methods to find high-security instances subject to these smoothness bounds is computationally infeasible.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
A minor revision of an IACR publication in EUROCRYPT 2021
Keywords
Post-quantum cryptographyisogeny-based cryptographyProuhet-Tarry-Escott problemtwin smooth integersB-SIDHSQISign
Contact author(s)
michael meyer @ hs-rm de
History
2021-05-20: last of 3 revisions
2020-10-14: received
See all versions
Short URL
https://ia.cr/2020/1283
License
Creative Commons Attribution
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 Prouhet-Tarry-Escott problem},
      howpublished = {Cryptology {ePrint} Archive, Paper 2020/1283},
      year = {2020},
      url = {https://eprint.iacr.org/2020/1283}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.