Massive Parallelization for Finding Shortest Lattice Vectors Based on Ubiquity Generator Framework
SessionPorting Applications to Specific Hardware
Authors:
Nariaki Tateiwa, Yuji Shinano, Satoshi Nakamura, Akihiro Yoshida, Masaya Yasuda, Shizuo Kaji, Katsuki Fujisawa
Event :
TypePaper
Time:
Wednesday, 18 November 20202pm - 2:30pmadd to Flagged
LocationTrack :
4
Description:
Lattice-based cryptography has received attention as a next-generation encryption technique, because it is believed to be secure against attacks by classical and quantum computers. Its essential security depends on the hardness of solving the shortest vector problem (SVP). In cryptography, to determine security levels, it is becoming significantly more important to estimate the hardness of the SVP by high-performance computing. In this study, we develop the world's first distributed and asynchronous parallel SVP solver, the MAssively Parallel solver for SVP (MAP-SVP). It can parallelize algorithms for solving the SVP by applying the Ubiquity Generator framework, which is a generic framework for branch-and-bound algorithms. The MAP-SVP is suitable for massive-scale parallelization, owing to its small memory footprint, low communication overhead, and rapid checkpoint and restart mechanisms. We demonstrate the performance and scalability of the MAP-SVP by using up to 100,032 cores to solve instances of the Darmstadt SVP Challenge.
SessionPorting Applications to Specific Hardware
Authors:
Nariaki Tateiwa, Yuji Shinano, Satoshi Nakamura, Akihiro Yoshida, Masaya Yasuda, Shizuo Kaji, Katsuki Fujisawa
Event :
TypePaper
Time:
Wednesday, 18 November 20202pm - 2:30pmadd to Flagged
LocationTrack :
4
Description:
Lattice-based cryptography has received attention as a next-generation encryption technique, because it is believed to be secure against attacks by classical and quantum computers. Its essential security depends on the hardness of solving the shortest vector problem (SVP). In cryptography, to determine security levels, it is becoming significantly more important to estimate the hardness of the SVP by high-performance computing. In this study, we develop the world's first distributed and asynchronous parallel SVP solver, the MAssively Parallel solver for SVP (MAP-SVP). It can parallelize algorithms for solving the SVP by applying the Ubiquity Generator framework, which is a generic framework for branch-and-bound algorithms. The MAP-SVP is suitable for massive-scale parallelization, owing to its small memory footprint, low communication overhead, and rapid checkpoint and restart mechanisms. We demonstrate the performance and scalability of the MAP-SVP by using up to 100,032 cores to solve instances of the Darmstadt SVP Challenge.
アクセス
トータル
