- 著者
-
安田 雅哉
脇 隼人
青野 良範
- 出版者
- 九州大学
- 雑誌
- 基盤研究(B)
- 巻号頁・発行日
- 2016-04-01
本研究の目的は、近年暗号分野で非常に注目されているLWE(Learning with Errors)問題ベースの格子暗号の解読計算量を解析すると共に、LWEベースの格子準同型暗号の安全パラメータの抽出を行い、暗号方式の性能評価を行うことである。2017年度の研究目標は、LWE問題などの格子暗号の安全性を支える数学問題を効率的に解くアルゴリズムの開発を行い、LWE問題の求解実験を開始することである。2017年度の研究成果として、格子暗号の安全性を支える最短ベクトル問題(Shortest Vector Problem, SVP)を効率的に解く新しい格子基底簡約アルゴリズムの開発を行い、2010年からドイツ・Darmstadt大がWeb上で公開しているSVPチャレンジの102次元から127次元という高い格子次元において、これまでよりも短い格子ベクトルの探索に成功した。さらに、今回開発したアルゴリズムをLWE問題の求解に適用し、既存の解法アルゴリズムよりも高速に解けることを実験的に示すことができた。また、格子問題の解法の1つであるrandom samplingアルゴリズムの正確な解析に成功し、LWEベース暗号を含む格子暗号の解読計算量の上界を評価することが可能となった。さらに、SVPを整数二次計画問題に定式化し、代表的な最適化エンジンであるCPLEXでSVP求解にチャレンジし、50次元程度まで求解可能であることを示すことができた。一方、代表的なLWE準同型暗号スキームを実装し、統計・分析などにおける基礎演算である行列計算を暗号化したまま効率的に計算する手法を開発し、プライバシー保護利活用技術としてLWE格子準同型暗号が利用可能か判定するための準備を整えることができた。