An Improved Coppersmith Algorithm Based on Block Preprocessing

Lu Zhang, Baodong Qin (), Wen Gao and Yiyuan Luo
Additional contact information
Lu Zhang: School of Cyberspace Security, Xi’an University of Posts and Telecommunications, Xi’an 710121, China
Baodong Qin: School of Cyberspace Security, Xi’an University of Posts and Telecommunications, Xi’an 710121, China
Wen Gao: School of Cyberspace Security, Xi’an University of Posts and Telecommunications, Xi’an 710121, China
Yiyuan Luo: School of Computer Science and Engineering, Huizhou University, Huizhou 516007, China

Mathematics, 2024, vol. 12, issue 2, 1-15

Abstract: Since Coppersmith proposed the use of the LLL algorithm to solve univariate modular polynomial equations at EUROCRYPT’96, it has sparked a fervent research interest in lattice analysis among cryptographers. Despite its polynomial-time nature, the LLL algorithm exhibits a high-order polynomial upper bound in terms of theoretical complexity, particularly with longer computation times when applied to high-dimensional lattices. In addressing this issue, we propose an improved algorithm based on block preprocessing, building on the original Coppersmith algorithm and thus providing proof of correctness for this algorithm. This approach effectively reduces the solution time of the algorithm, offering a maximum improvement of 8.1% compared to the original Coppersmith algorithm. Additionally, we demonstrate the compatibility of our algorithm with the rounding algorithm proposed at PKC 2014. The combined utilization of these approaches further enhances the efficiency of our algorithm. The experimental results show that the combined algorithm achieves a maximum improvement of 22.4% in solution time compared to the original Coppersmith algorithm. It also outperforms the standalone rounding algorithm with a maximum improvement of 12.1%. When compared to the improved Coppersmith algorithm based on row common factor extraction, our proposed algorithm demonstrates comparable or even superior performance in certain dimensions. The block preprocessing algorithm in our approach enables independent execution without data exchange, making it suitable for leveraging multi-processing advantages in scenarios involving higher degrees of modular polynomial equations. This offers a new perspective for achieving the parallel computation of the Coppersmith algorithm, facilitating parallel execution and providing valuable insights.

Keywords: LLL algorithm; Coppersmith algorithm; block preprocessing; RSA attack (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2024
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/12/2/173/pdf (application/pdf)
https://www.mdpi.com/2227-7390/12/2/173/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:12:y:2024:i:2:p:173-:d:1313888

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().