大規模並列計算によるポスト量子暗号の安全性解析

本研究課題ではポスト量子暗号の安全性評価を目的としている。本年度は、有限体上の多変数多項式の求解問題に対する改良アルゴリズム、高次元のユークリッド格子の基底縮約アルゴリズムの高速化、暗号ソフトウェアの効率的な開発環境の作成などに関する成果を得た。ポスト量子暗号の一つである多変数多項式暗号は、多変数多項式の求解問題の困難性を安全性の根拠としている。本年度は、多項式の個数が変数の個数がより少ない場合(underdetermined system)の困難性を考察し、有限体の標数が奇数の場合でも多項式時間を実現する初めてのアルゴリズムを提案した。この成果はトロントで開催された国際会議Post-Quantum Cryptography 2014において発表した。また、格子基底縮約アルゴリズムのガウス篩法に対して、GPUによる超並列実装方法の考察を行った。これらの実装では、ドメイン特化言語を利用したガウス篩法のベンチマークテストを行った。初期実験の結果は、国際会議IWSEC 2014での査読付き論文、JAIST宮地研究室の招待講演として発表した。

本研究課題ではポスト量子暗号の安全性評価を目的としている。本年度は、有限体上の多変数多項式の求解問題に対する改良アルゴリズム、高次元のユークリッド格子の基底縮約アルゴリズムの高速化、暗号ソフトウェアの効率的な開発環境の作成などに関する成果を得た。ポスト量子暗号の一つである多変数多項式暗号は、多変数多項式の求解問題の困難性を安全性の根拠としている。本年度は、多項式の個数が変数の個数がより少ない場合(underdetermined system)の困難性を考察し、有限体の標数が奇数の場合でも多項式時間を実現する初めてのアルゴリズムを提案した。この成果はトロントで開催された国際会議Post-Quantum Cryptography 2014において発表した。また、格子基底縮約アルゴリズムのガウス篩法に対して、GPUによる超並列実装方法の考察を行った。これらの実装では、ドメイン特化言語を利用したガウス篩法のベンチマークテストを行った。初期実験の結果は、国際会議IWSEC 2014での査読付き論文、JAIST宮地研究室の招待講演として発表した。