Sieving for large twin smooth integers using single solutions to Prouhet-Tarry-Escott
DOI:
https://doi.org/10.13069/jacodesmath.v13i2.426Keywords:
Isogeny-based cryptography, Post-quantum cryptography, Twin smooth integers, Prouhet-Tarry-Escott problem, SQISignAbstract
In the isogeny-based track of post-quantum cryptography, optimal instances of the signature scheme SQISign rely on primes \( p \) such that \( p \pm 1 \) 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 we 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 larger 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 optimized for the corresponding \( C \) and allows to check smoothness only for 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 - both heuristically and empirically. Along the way we compute the number of roots of a given polynomial modulo prime powers and give an upper bound for the number of roots modulo a composite number.
Downloads
References
K. Ahrens, SIGNITC: Supersingular isogeny graph non-interactive timed commitments, Cryptology ePrint Archive Paper 2024/1225 (2024).
D. J. Bernstein, How to find smooth parts of integers, (2004).
P. Borwein and C. Ingalls, The Prouhet-Tarry-Escott problem revisited, Enseign. Math. (2) 40(1-2) (1994) 3–27.
G. Bruno, M. Corte-Real Santos, C. Costello, J. K. Eriksen, M. Meyer, M. Naehrig, and B. Sterner, Cryptographic smooth neighbors. In J. Guo and R. Steinfeld, editors, Advances in Cryptology – ASIACRYPT 2023, Springer Nature Singapore (2023) 190–221.
T. Caley, The Prouhet-Tarry-Escott problem, PhD thesis University of Waterloo (2012).
W. Castryck, T. Lange, C. Martindale, L. Panny, and J. Renes, CSIDH: An efficient post-quantum commutative group action, In T. Peyrin and S. Galbraith, editors, Advances in Cryptology – ASIACRYPT 2018, pages 395–427, Cham. Springer International Publishing (2018).
J. Chavez-Saab, M. Corte-Real Santos, L. De Feo, J. Komada Eriksen, B. Hess, D. Kohel, A. Leroux, P. Longa, M. Meyer, L. Panny, S. Patranabis, C. Petit, F. Rodríguez Henríquez, S. Schaeffler, and B. Wesolowski, SQISign algorithm specifications and supporting documentation, Project Homepage (2023).
J. Chernick, Ideal solutions of the Tarry-Escott Problem, Amer. Math. Monthly 44(10) (1937) 626–633.
C. Costello, B-SIDH: Supersingular isogeny diffie-hellman using twisted torsion, In S. Moriai and H. Wang, editors, Advances in Cryptology – ASIACRYPT 2020, Cham. Springer International Publishing (2020) 440–463.
C. Costello, M. Meyer, and M. Naehrig, Sieving for twin smooth integers with solutions to the Prouhet-Tarry-Escott problem, In A. Canteaut and F.-X. Standaert, editors, Advances in Cryptology – EUROCRYPT 2021, Cham. Springer International Publishing (2021) 272–301.
L. De Feo, D. Kohel, A. Leroux, C. Petit, and B. Wesolowski, SQISign: compact post-quantum signatures from quaternions and isogenies, In S. Moriai and H. Wang, editors, Advances in Cryptology – ASIACRYPT 2020, Cham. Springer International Publishing (2020) 64–93.
J. Franke, T. Kleinjung, F. Morain, and T. Wirth, Proving the primality of very large numbers with fastECPP, In D. Buell, editor, Algorithmic Number Theory, Berlin Heidelberg, Springer Berlin Heidelberg (2004) 194–207.
G. H. Hardy and S. Ramanujan. The normal number of prime factors of a number n, Quart. J. 48 (1917) 76–92.
D. Jao and L. De Feo, Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies, In B.-Y. Yang, editor, Post-Quantum Cryptography, Springer Berlin Heidelberg (2011) 19–34.
J. H. Loxton and R. C. Vaughan, The estimation of complete exponential sums, Canad. Math. Bull. 28(4) (1985) 440–454.
National Institute of Standards and Technology. Post-quantum cryptography: additional digital signature schemes, (2023).
C. Shuwen. The Prouhet-Tarry-Escott problem. Equal Sums of Like Powers, (2022).
C. L. Stewart, On the number of solutions of polynomial congruences and the equations, J. Amer. Math. Soc. 4 (1991) 793–835.
