格子暗号の大規模解読実験と解読計算量評価

点击翻译按钮获取中文摘要

量子計算機による暗号解読にも耐性のある耐量子計算機暗号（Post-Quantum Cryptography）の有力候補である格子暗号の安全性は、格子上の最短ベクトル問題（SVP, Shortest Vector Problem）や最近ベクトル問題（CVP, Closest Vector Problem）などの格子問題の計算困難性に基づく。本年度（2022年度）は、格子問題に対する解読アルゴリズムの大規模並列化フレームワークの設計・開発・求解実験に成功した。具体的には、昨年度までに開発した並列化システムをベースに、代表的な格子問題の求解法である格子基底簡約・列挙法・篩法の異なる3つの格子アルゴリズムを大規模計算機システム上で同時に動作可能とする並列化フレームワークCMAP-LAP（Configurable Massively Parallel Solver for Lattice Problems）の開発に成功した。特に、格子基底簡約アルゴリズムとしてDeepBKZをCMAP-LAPフレームワークに組み込むと共に、最大100,032並列プロセスを持つ大規模計算機上で130次元程度のSVPをおよそ100時間以内で求解可能であることを示した。これらの大規模並列化システムの設計・開発からSVPの求解実験データに関する研究成果は、応用数学に関する国際雑誌JJIAM（Japan Journal of Industrial and Applied Mathematics）に採択された。また、耐量子性を持つ格子暗号方式の安全性を支えるLWEやNTRU問題に対する解読法を拡張し、その研究成果を国内会議で発表した。