最短格子ベクトル問題求解におけるUbiquity Generator Frameworkを用いた大規模MPI並列化

• Item type: SIG Technical Reports(1)
• 公開日: 2020-09-18
• タイトル: 最短格子ベクトル問題求解におけるUbiquity Generator Frameworkを用いた大規模MPI並列化
• タイトル / 言語: en
• タイトル: Massive MPI Parallelization for Solving Shortest Vector Problem Based on Ubiquity Generator Framework
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: 大規模並列処理
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 九州大学
• 著者所属: Zuse Institute Berlin (ZIB)
• 著者所属: 九州大学
• 著者所属: 九州大学
• 著者所属: 立教大学
• 著者所属: 九州大学
• 著者名: 立岩, 斉明; 品野, 勇治; 吉田, 明広; 鍛冶, 静雄; 安田, 雅哉; 藤澤, 克樹
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 格子暗号は，古典計算機や量子計算機からの攻撃に対しても安全であると考えられており，次世代の暗号化技術として注目されている．その本質的な安全性は，最短ベクトル問題 (SVP) の求解困難性に依存しており，セキュリティレベルを決定するために大規模計算機により SVP の難易度を正確に推定することが重要である．本研究では，世界初の分散型非同期並列 SVP ソルバーである MAssively Parallel solver for SVP (MAP-SVP) を開発した．MAP-SVP は分枝限定ソルバの汎用ソフトフェアである Ubiquity Generator framework を適用することで非同期的に情報を共有しながら SVP アルゴリズムを大規模に並列実行することが可能になった．MAP-SVP の性能を実証するために Darmstadt SVP チャレンジのインスタンスを複数解き，最大 91,200 のコア数を用いた実行により 127 次元の記録を更新した．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Lattice-based cryptography is considered the next generation encryption technique because it is believed to be secure against attacks from classical and quantum computers. Its security depends essentially on the difficulty of solving the shortest vector problem (SVP). It is important to estimate the hardness of solving SVP by high-performance computers to determine the security level. In this study, we develop the world's first distributed and asynchronous parallel SVP solver, the MAssively Parallel solver for SVP (MAP-SVP). This solver can parallelize the SVP algorithm on a large scale while sharing information asynchronously by applying the Ubiquity Generator framework, which is a generic framework for branch-and-bound algorithms. We demonstrate the performance of the MAP-SVP by solving instances of the Darmstadt SVP challenge, and MAP-SVP marked a new record at 127 dimension by using up to 91,200 cores.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN10463942
• 書誌情報: 研究報告ハイパフォーマンスコンピューティング（HPC）; 巻 2020-HPC-176, 号 1, p. 1-10, 発行日 2020-09-18
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 2188-8841
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会