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
Metadaten
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
Volume:40
Issue:1
First Page:13
Last Page:56
Year of first publication:2023
DOI:https://doi.org/10.1007/s13160-023-00580-z
Accept ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.