IDEAS home Printed from https://ideas.repec.org/a/gam/jmathe/v12y2024i2p173-d1313888.html
   My bibliography  Save this article

An Improved Coppersmith Algorithm Based on Block Preprocessing

Author

Listed:
  • Lu Zhang

    (School of Cyberspace Security, Xi’an University of Posts and Telecommunications, Xi’an 710121, China
    National Engineering Research Center for Secured Wireless, 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
    National Engineering Research Center for Secured Wireless, 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)

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.

Suggested Citation

  • Lu Zhang & Baodong Qin & Wen Gao & Yiyuan Luo, 2024. "An Improved Coppersmith Algorithm Based on Block Preprocessing," Mathematics, MDPI, vol. 12(2), pages 1-15, January.
  • Handle: RePEc:gam:jmathe:v:12:y:2024:i:2:p:173-:d:1313888
    as

    Download full text from publisher

    File URL: https://www.mdpi.com/2227-7390/12/2/173/pdf
    Download Restriction: no

    File URL: https://www.mdpi.com/2227-7390/12/2/173/
    Download Restriction: no
    ---><---

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:gam:jmathe:v:12:y:2024:i:2:p:173-:d:1313888. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    We have no bibliographic references for this item. You can help adding them by using this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: MDPI Indexing Manager (email available below). General contact details of provider: https://www.mdpi.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.