Sieving for large twin smooth integers using single solutions to Prouhet-Tarry-Escott

Knud Ahrens

Paper 2023/219

Sieving for large twin smooth integers using single solutions to Prouhet-Tarry-Escott

Knud Ahrens, University of Passau

Abstract

In the isogeny-based track of post-quantum cryptography the signature scheme SQISign relies on primes $p$ such that $p\pm1$ is smooth. In 2021 a new approach to find those numbers was discovered using solutions to the Prouhet-Tarry-Escott (PTE) problem. With these solutions one can sieve for smooth integers $A$ and $B$ with a difference of $|A-B|=C$ fixed by the solution. Then some $2A/C$ and $2B/C$ are smooth integers hopefully enclosing a prime. They took many different PTE solutions and combined them into a tree to process them more efficiently. But for bigger numbers there are fewer promising PTE solutions so their advantage over the naive approach (checking a single solution at a time) fades. For a single PTE solution the search can be optimised for the corresponding $C$ and allows to only sieve those integers that are divisible by $C$. In this work we investigate such optimisations and show a significant speed-up compared to the naive approach.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Preprint.
Keywords: isogeny-based cryptography post-quantum cryptography twin smooth integers Prouhet-Tarry-Escott problem SQISign
Contact author(s): knud ahrens @ uni-passau de
History: 2023-02-20: approved; 2023-02-17: received; See all versions
Short URL: https://ia.cr/2023/219
License: CC BY

BibTeX

@misc{cryptoeprint:2023/219,
      author = {Knud Ahrens},
      title = {Sieving for large twin smooth integers using single solutions to Prouhet-Tarry-Escott},
      howpublished = {Cryptology {ePrint} Archive, Paper 2023/219},
      year = {2023},
      url = {https://eprint.iacr.org/2023/219}
}