学生の宮城　勇雅さん（博士前期課程2年、セキュリティ・ネットワーク領域・藤﨑研究室）が、ドイツのダルムシュタット工科大学提供のLattice Challengeにおいて、イデアル格子とランダム格子の最短ベクトルの新記録を達成しました。

　将来、大容量の量子ビットを扱える量子計算機が出現すると、現在標準化されている多くの公開鍵暗号、署名が使えなくなってしまうことが知られています。
　もちろんこのような大容量量子計算機の実現には非常に高いハードルが幾つも残っており、現時点では完成の見通しは立っていません。
　しかし、米国政府機関である NIST (National Institute of Standards and Technology) は、このような場合に備えて耐量子計算機の攻撃に耐えうる暗号の標準化を始めることを2016年に宣言し、2017年11月を公募〆切、2018年1月30日に Round 2 に進む方式の発表を行いました。

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

　格子暗号の安全性を評価するために、ドイツのダルムシュタット工科大学が中心となり2016年から格子の最短ベクトルチャレンジ問題を Lattice Challenge という名称で提供しています。
　最短ベクトル問題はNP困難という計算量クラスにあるため真の最短ベクトルが何であるかは全数探索をしないと分かりません。そのため、Lattice Challenge では（真の最短ベクトルではなく）ある基準より短いベクトルを見つけると登録することができ、さらにそれより短いベクトルが見つかった場合はそのベクトルに記録が更新される仕組みになっています。
　この度、宮城さんはイデアル格子部門で、144,148,150次元の基準を満たす短いベクトルを初めて発見し、イデアル格子ベクトル部門では115, 120, 127, 129, 137, 138, 139, 142, 146, 150次元で、従来より短いベクトルを発見しました。

参考URL: https://www.latticechallenge.org/ideallattice-challenge/index.php
　　　　 https://www.latticechallenge.org/svp-challenge/index.php

令和2年3月17日