最適化問題に対する超高速&安定計算

大規模最適化問題、グラフ探索、機械学習やデジタルツインなどの研究のお話が中心

Massively parallel sharing lattice basis reduction

2022年02月22日 21時38分38秒 | Weblog

Massively parallel sharing lattice basis reduction

Nariaki Tateiwa, Yuji Shinano, Masaya Yasuda, Shizuo Kaji, Keiichiro Yamamura, Katsuki Fujisawa

For cryptanalysis in lattice-based schemes, the performance evaluation of lattice basis reduction using high-performance computers is becoming increasingly important for the determination of the security level. We propose a distributed and asynchronous parallel reduction algorithm based on randomization and DeepBKZ, which is an improved variant of the block Korkine-Zolotarev (BKZ) reduction algorithm. Randomized copies of a lattice basis are distributed to up to 103,680 cores and independently reduced in parallel, while some basis vectors are shared asynchronously among all processes via MPI. There is a trade-off between randomization and information sharing; if a substantial amount of information is shared, all processes will work on the same problem, thereby diminishing the benefit of parallelization. To monitor this balance between randomness and sharing, we propose a metric to quantify the variety of lattice bases. We empirically find an optimal parameter of sharing for high-dimensional lattices. We demonstrate the efficacy of our proposed parallel algorithm and implementation with respect to both performance and scalability through our experiments.

コメント
  • X
  • Facebookでシェアする
  • はてなブックマークに追加する
  • LINEでシェアする