研究成果 Yuntao Wang講師が次世代暗号における数学的困難問題の解読に新記録を達成
電気電子情報通信工学専攻のYuntao Wang講師が、ドイツ・ダルムシュタット工科大学主催のLattice Challengeシリーズにおいて、イデアル格子問題やLWEチャレンジ問題の解読において新記録を達成しました。
現在、RSA暗号や楕円曲線暗号など様々な公開鍵暗号方式が安全な情報社会を実現する上で必要不可欠なものとなっていますが、量子計算機により、上記の暗号方式は多項式時間で解読できることが数学的に証明されています。量子計算機はすでに開発され、普及するまではあと十数年と期待されているため、アメリカ国立標準技術研究所(NIST)は次世代暗号(耐量子計算機暗号とも呼ばれ、PQCで略称されます)の標準化に向け活動を開始しました(図1)。現在、数学の研究対象である格子理論を利用した格子暗号が注目され、格子暗号は次世代暗号の有力な候補になると期待されています。
暗号方式の提案から社会展開までは繰り返し安全性解析を行う必要があります。即ち、暗号の安全性を代表的な困難問題に帰着させ、この問題の効率的な解法が見つかれば、対象とする暗号方式は効率的に破れるため、より強度が高いパラメータを調整することが安全性評価の目標となります。
格子暗号の安全性は、高次元の最短ベクトル問題(Shortest Vector Problem、 SVP)などのNP困難性を根拠としています。そこで、どの次元まで、どのぐらいの計算量で、最短ベクトルを求められるのかが格子暗号の安全性の評価に重要な課題になります。
最短ベクトル問題などの格子問題の困難性を評価するために、ドイツ・ダルムシュタット工科大学は2008年からLattice Challengeシリーズを主催し始めました。チャレンジが提供されて以来、世界中の研究者は活発的により高次元の困難問題の解読に取り組み、記録を更新しています。
この度、Yuntao Wang講師の研究グループは2年9ヶ月ぶり「イデアル格子チャレンジ」にて156次元から172次元まで、初めて基準より短い(近似)最短ベクトルを見つけて記録を更新しました(図2)。
本研究では、SVPを解読するためのアルゴリズムを改良し、計算シミュレーターを開発しました。シミュレーションの結果により、最適なストラテジーでローカルブロックの挙動に適用し、従来より解読に必須のメモリを削減しつつ、計算時間も大幅に短縮できました。その他、LWE Challengeにて40次元(エラーレート0.04)の記録を更新し、SVP Challengeにて170次元で従来より短いベクトルを登録しました。
これらの記録を上回ることで提案アルゴリズムの効率性を示すことができた上、PQCの標準化において安全性評価に大きく貢献できると思われます。本研究は交換留学生のLeizhang Wangさん、西安電子科技大学のBaocang Wang教授との共同研究になります。