文献

J-GLOBAL ID：202002230410094245   整理番号：20A2302395

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

Massive MPI Parallelization for Solving Shortest Vector Problem Based on Ubiquity Generator Framework

著者 (6件)： 立岩斉明 (九大) ,  品野勇治 (Zuse Inst. Berlin (ZIB)) ,  吉田明広 (九大) ,  鍛冶静雄 (九大) ,  安田雅哉 (立教大) ,  藤澤克樹 (九大)
資料名： 情報処理学会研究報告(Web)  (IPSJ Technical Report (Web))
巻： 2020  号： HPC-176  ページ： Vol.2020-HPC-176,No.1,1-10 (WEB ONLY)  発行年： 2020年09月18日 
JST資料番号： U0451A  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： 格子暗号は,古典計算機や量子計算機からの攻撃に対しても安全であると考えられており,次世代の暗号化技術として注目されている.その本質的な安全性は,最短ベクトル問題(SVP)の求解困難性に依存しており,セキュリティレベルを決定するために大規模計算機によりSVPの難易度を正確に推定することが重要である.本研究では,世界初の分散型非同期並列SVPソルバーであるMAssively Parallel solver for SVP(MAP-SVP)を開発した.MAP-SVPは分枝限定ソルバの汎用ソフトフェアであるUbiquity Generator frameworkを適用することで非同期的に情報を共有しながらSVPアルゴリズムを大規模に並列実行することが可能になった.MAP-SVPの性能を実証するためにDarmstadt SVPチャレンジのインスタンスを複数解き,最大91,200のコア数を用いた実行により127次元の記録を更新した.(著者抄録)

シソーラス用語： *通信 ,  暗号 ,  *アルゴリズム ,  *格子 ,  並列演算 ,  符号 ,  情報セキュリティ ,  量子コンピュータ ,  フレームワーク【ソフトウェア開発】 ,  *情報通信 ,  *暗号アルゴリズム
準シソーラス用語： 暗号化 ,  *暗号化アルゴリズム ,  格子基底コード ,  並列計算 ,  量子計算機

分類 (2件)： 符号理論  (ND02030R) ,  計算理論  (JB02000A)

引用文献 (32件)：

• P. W. Shor, “Algorithms for quantum computation: Discrete logarithms and factoring,” in Symposium on Foundations of Computer Science (FOCS 1994). IEEE, 1994, pp. 124-134.
• The National Institute of Standards and Technology (NIST), “Post-quantum cryptography.” [Online]. Available: https://csrc.nist.gov/projects/post-quantum-cryptography/post-quantum-cryptography-standardization
• M. Schneider, N. Gama, P. Baumann, and L. Nobach, “SVP challenge (2010),” URL: http://latticechallenge.org/svp-challenge.
• M. Albrecht, L. Ducas, G. Herold, E. Kirshanova, E. W. Postlethwaite, and M. Stevens, “The general sieve kernel and new records in lattice reduction,” in Advances in Cryptology-EUROCRYPT 2019, ser. Lecture Notes in Computer Science, vol. 11477. Springer, 2019, pp. 717-746.
• N. Tateiwa, Y. Shinano, S. Nakamura, A. Yoshida, S. Kaji, M. Yasuda, and K. Fujisawa, “Massive parallelization for finding shortest lattice vectors based on ubiquity generator framework,” in the International Conference for High Performance Computing, Networking, Storage, and Analysis (SC20), to be held as a virtual conference from 9-19 November 2020.

タイトルに関連する用語 (6件)： 格子 ,  ベクトル ,  求解 ,  大規模 ,  MPI ,  並列化