ニュース・イベント

お知らせ

学生の長谷川さんとWANG助教が格子の最短ベクトルチャレンジ問題の新記録を達成

 学生の長谷川 奨さん(博士前期課程2年、セキュリティ・ネットワーク領域藤﨑研究室)とセキュリティ・ネットワーク領域のWANG, Yuntao助教が、ドイツのダルムシュタット工科大学提供のLattice Challengeにおいて、格子の最短ベクトル問題の新記録を達成しました。

 将来、大容量の量子ビットを扱える量子計算機が出現すると、現在標準化されている多くの公開鍵暗号、署名が使えなくなってしまうことが知られています。もちろんこのような大容量量子計算機の実現には非常に高いハードルが幾つも残っていますが、米国政府機関であるNIST(National Institute of Standards and Technology)は、将来に備えて耐量子計算機の攻撃に耐えうる暗号の標準化を行っており、現在Round3まで選定が進んでいます。

 耐量子計算機暗号でもっとも有望視されているのは、格子問題の困難性に基づいた格子暗号です。格子暗号の実用上の1番の問題は、格子の次元設定です。格子暗号は、高次元格子の(非ゼロ)最短ベクトルを求めることが難しいことに安全性の根拠を置いているため、どの次元まで実際に解読できるか知ることが重要になります。

 格子暗号の安全性を評価するために、ドイツのダルムシュタット工科大学が中心となり2016年から格子の最短ベクトルチャレンジ問題をLattice Challengeという名称で提供しています。

 最短ベクトル問題はNP困難という計算量クラスにあるため真の最短ベクトルが何であるかは全数探索をしないと分かりません。そのため、Lattice Challengeでは(真の最短ベクトルではなく)ある基準より短いベクトルを見つけると登録することができ、さらにそれより短いベクトルが見つかった場合はそのベクトルに記録が更新される仕組みになっています。この度、長谷川さんとWANG助教は(ランダム)格子部門で、156,158次元におけるこれまででもっと短い(非ゼロ)ベクトルを発見しました。

*参考:SVP CHALLENGE

令和3年1月29日

PAGETOP