最短ベクトル問題を2^{0.6039n}時間で解く新アルゴリズム

Solving the Shortest Vector Problem in $2^{0.6039n}$ Time via Mid-Point Hessian

本論文では、n次元格子L上の最短ベクトル問題(SVP)に対する乱択アルゴリズムを提案する。古典計算で2^{0.6039n+o(n)}時間、量子計算で2^{0.5411n+o(n)}時間、空間2^{0.5n+o(n)}で解く。これはAggarwalら(STOC'15)の2^{n+o(n)}時間・空間を改善する。鍵となるのは、周期ガウス関数のヘッセ行列を最短ベクトルの半分の点で評価する手法で、前処理付き有界距離復号を用いてベクトルを復元する。候補の中点はL/2Lのパリティクラスで索引付けされ、離散ガウスサンプリングでヘッセ行列を推定して探索する。ランダム部分格子コセットとサンプリング技術で最適化し、最終的な複雑度を達成する。