Paper 2024/1330
Newton Polytope-Based Strategy for Finding Small Roots of Multivariate Polynomials
Abstract
Coppersmith's method plays an important role in cryptanalysis. By introducing a new tool called Sumsets theory from Additive Combinatorics, we propose a novel strategy for Coppersmith's method based on Newton polytope. With our novel strategy, we provide the first provable and efficient algorithm for calculating the asymptotic bounds of Coppersmith's method, which is typically a tedious and non-trivial task. Moreover, our new perspective offers a better understanding of Coppersmith's method. As a byproduct, we apply our new technique and prove the new heuristic introduced by Meers and Nowakowski at Asiacrypt'23 and improve the cryptanalytic result for the Commutative Isogeny Hidden Number Problem.
Metadata
- Available format(s)
-
PDF
- Category
- Attacks and cryptanalysis
- Publication info
- Preprint.
- Keywords
- CoppersmithSumsetsNewton polytopesAdditive combinatorics
- Contact author(s)
-
fengyansong @ amss ac cn
abderrahmane nitaj @ unicaen fr
panyanbin @ amss ac cn - History
- 2024-10-04: last of 2 revisions
- 2024-08-25: received
- See all versions
- Short URL
- https://ia.cr/2024/1330
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2024/1330,
author = {Yansong Feng and Abderrahmane Nitaj and Yanbin Pan},
title = {Newton Polytope-Based Strategy for Finding Small Roots of Multivariate Polynomials},
howpublished = {Cryptology {ePrint} Archive, Paper 2024/1330},
year = {2024},
url = {https://eprint.iacr.org/2024/1330}
}
