Overview Statistic: PDF-Downloads (blue) and Frontdoor-Views (gray)

Development and analysis of massive parallelization of a lattice basis reduction algorithm

  • The security of lattice-based cryptography relies on the hardness of solving lattice problems. Lattice basis reduction is a strong tool for solving lattice problems, and the block Korkine–Zolotarev (BKZ) reduction algorithm is the de facto standard in cryptanalysis. We propose a parallel algorithm of BKZ-type reduction based on randomization. Randomized copies of an input lattice basis are independently reduced in parallel, while several basis vectors are shared asynchronously among all processes. There is a trade-off between randomization and information sharing; if a substantial amount of information is shared, all processes might work on the same problem, which diminishes the benefit of parallelization. To monitor the balance between randomness and sharing, we propose a new metric to quantify the variety of lattice bases, and we empirically find an optimal parameter of sharing for high-dimensional lattices. We also demonstrate the effectiveness of our parallel algorithm and metric through experiments from multiple perspectives.

Export metadata

Additional Services

Share in Twitter Search Google Scholar Statistics - number of accesses to the document
Author:Nariaki Tateiwa, Yuji Shinano, Masaya Yasuda, Shizuo Kaji, Keiichiro Yamamura, Katsuki FujisawaORCiD
Document Type:Article
Parent Title (English):Japan Journal of Industrial and Applied Mathematics
First Page:13
Last Page:56
Year of first publication:2023
Accept ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.