格子暗号の安全性を検証する最短ベクトル問題に対する解読

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