最短ベクトル問題における新しいsieving計算の手法の開発

本研究は、格子の最短ベクトル問題に対して、基底簡約問題に帰着させて考えるアプローチを用いて効率的なアルゴリズムの開発を目指す。最短ベクトル問題は、公開鍵暗号である格子暗号の安全性の基礎になる問題である。基底簡約アルゴリズムにおいては、短い格子ベクトルを見つけるステップとそれを使って基底を簡約するステップに分かれ、交互に繰り返す。われわれのアプローチではsievingという手法によって短い格子ベクトルを見つけて、そのベクトルで基底簡約を行い、基底を改善していく。sievingは、既知の短い格子ベクトルの組みを足し合わせることにより短い格子ベクトルを見つける手法である。われわれのアプローチの特徴は、基底簡約するときに、どの短い格子ベクトルを使うかを戦略的に選択することにある。本研究では大規模な並列計算機上で実行可能なプロセス並列な効率的なアルゴリズムを開発している。また、SVP Challengeというドイツのダルムシュタット工科大学が運営する格子の最短ベクトル問題へのチャレンジサイトへのエントリーを目標にしている。次元ごとに定められた長さ以下の格子ベクトルを見つけるとサイトへのエントリーが可能になる。2022年度は、主にアルゴリズムの効率的な実装に取り組み、基底簡約するときに、小さいindexの基底ベクトルを少しずつ簡約するのではなく、一気に複数の短い格子ベクトルを使って簡約することで効率的に基底簡約する方法を実装した。それにより、われわれが開発中のプログラムの効率があがり、SVP Challengeにも162次元や164次元の記録を登録することができた。

本研究は、格子の最短ベクトル問題に対して、基底簡約問題に帰着させて考えるアプローチを用いて効率的なアルゴリズムの開発を目指す。最短ベクトル問題は、公開鍵暗号である格子暗号の安全性の基礎になる問題である。基底簡約アルゴリズムにおいては、短い格子ベクトルを見つけるステップとそれを使って基底を簡約するステップに分かれ、交互に繰り返す。われわれのアプローチではsievingという手法によって短い格子ベクトルを見つけて、そのベクトルで基底簡約を行い、基底を改善していく。sievingは、既知の短い格子ベクトルの組みを足し合わせることにより短い格子ベクトルを見つける手法である。われわれのアプローチの特徴は、基底簡約するときに、どの短い格子ベクトルを使うかを戦略的に選択することにある。本研究では大規模な並列計算機上で実行可能なプロセス並列な効率的なアルゴリズムを開発している。また、SVP Challengeというドイツのダルムシュタット工科大学が運営する格子の最短ベクトル問題へのチャレンジサイトへのエントリーを目標にしている。次元ごとに定められた長さ以下の格子ベクトルを見つけるとサイトへのエントリーが可能になる。2022年度は、主にアルゴリズムの効率的な実装に取り組み、基底簡約するときに、小さいindexの基底ベクトルを少しずつ簡約するのではなく、一気に複数の短い格子ベクトルを使って簡約することで効率的に基底簡約する方法を実装した。それにより、われわれが開発中のプログラムの効率があがり、SVP Challengeにも162次元や164次元の記録を登録することができた。