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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Solving Modular Linear Equations via Automated Coppersmith and Its Applications

  • Yansong Feng,
  • Zhen Liu,
  • Abderrahmane Nitaj,
  • Yanbin Pan

摘要

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.