Solving Modular Linear Equations via Automated Coppersmith and Its Applications
摘要
At Asiacrypt’23, Meers and Nowakowski introduced a new automated method called Automated Coppersmith, which can be viewed as a generalization of Jochemsz-May Strategy for systems of polynomial equations. It selects monomials first, then constructs polynomials to construct the lattice in Coppersmith’s method. However, their strategy raises a new heuristic assumption. In this paper, We try to eliminate this heuristic assumption on linear equation systems. Finally, we apply this method to analyze the Generalized Extended Implicit Factorization Problem (G-EIFP), a generalization of the Extended Implicit Factorization Problem (EIFP), even when the shared contiguous bits are arbitrary.