@article{TateiwaShinanoYasudaetal., author = {Tateiwa, Nariaki and Shinano, Yuji and Yasuda, Masaya and Kaji, Shizuo and Yamamura, Keiichiro and Fujisawa, Katsuki}, title = {Development and analysis of massive parallelization of a lattice basis reduction algorithm}, series = {Japan Journal of Industrial and Applied Mathematics}, volume = {40}, journal = {Japan Journal of Industrial and Applied Mathematics}, number = {1}, doi = {10.1007/s13160-023-00580-z}, pages = {13 -- 56}, abstract = {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.}, language = {en} }