TY - JOUR
A1 - Tateiwa, Nariaki
A1 - Shinano, Yuji
A1 - Yasuda, Masaya
A1 - Kaji, Shizuo
A1 - Yamamura, Keiichiro
A1 - Fujisawa, Katsuki
T1 - Development and analysis of massive parallelization of a lattice basis reduction algorithm
T2 - Japan Journal of Industrial and Applied Mathematics
N2 - 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.
Y1 - 2023
UR - https://opus4.kobv.de/opus4-zib/frontdoor/index/index/docId/9056
VL - 40
IS - 1
SP - 13
EP - 56
ER -