Paper 2026/423
Coppersmith's Method for Solving Modular Inversion Hidden Number Problem via Determinant-Based Elimination
, State Key Laboratory of Cyberspace Security Defense, Institute of Information Engineering, Chinese Academy of Sciences, Beijing, China, University of Chinese Academy of Sciences, Beijing, China, Beijing Electronic Science and Technology Institute, Beijing, ChinaAbstract
The selection of shift polynomials is a pivotal yet challenging step in Coppersmith's method for computing modular roots of multivariate polynomials. We propose a novel, determinant-based strategy for generating these polynomials, thereby presenting an improved variant of Coppersmith's method tailored for certain multivariate modular equations. Our approach is first validated on solving the Modular Inversion Hidden Number Problem (MIHNP) and predicting the Inversive Congruential Generator (ICG), where it is shown to outperform prior methods both in theory and in practice. Furthermore, when applied to the Modular Inversion Double Hidden Numbers Problem (MIDHNP), our analysis reveals that MIDHNP is not harder than MIHNP, thereby disproving a conjecture by Boneh et al. (Asiacrypt 2001).
Metadata
- Available format(s)
-
PDF
- Category
- Attacks and cryptanalysis
- Publication info
- Preprint.
- Keywords
- Coppersmith's MethodMIHNPMIDHNPICGLattice.
- Contact author(s)
-
16678784491 @ 163 com
dzpeng @ amss ac cn
wubaofeng @ iie ac cn
2025023284 @ qdu edu cn
zhang_yanshuo @ 163 com - History
- 2026-03-03: approved
- 2026-03-02: received
- See all versions
- Short URL
- https://ia.cr/2026/423
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2026/423,
author = {Zhaopeng Ding and Zhaopeng Dai and Baofeng Wu and Rundong Wang and Yanshuo Zhang},
title = {Coppersmith's Method for Solving Modular Inversion Hidden Number Problem via Determinant-Based Elimination},
howpublished = {Cryptology {ePrint} Archive, Paper 2026/423},
year = {2026},
url = {https://eprint.iacr.org/2026/423}
}
