整数格子 Lは、線形独立なベクトルの組 b1,...,bn ∈ Zmに関する整数係数線形結合の全ての集合である。nを Lの次元といい、(b1,...,bn)を Lの基底という。また、 Lに属する要素を格子ベクトルという。以下では、格子によって整数格子を意味するものとする。n≦2のとき、同一の格子を生成する基底は無数に多く存在する。

原点を除く最も短い格子ベクトルを、最短ベクトルという。与えられた基底に対して、その基底が生成する格子における最短ベクトルを求める問題を最短ベクトル問題 (SVP)という。 SVPを解く多項式時間アルゴリズムは知られていない。一方、 SVPを解く多項式時間アルゴリズムの代替として、SVPの近似版である近似最短ベクトル問題 (近似 SVP)を解く多項式時間アルゴリズムがいくつか提案されている。近似 SVPとは、与えられた基底と定数 γ ∈ Rに対して、その基底が生成する格子における最短ベクトルのノルムのγ倍以内のノルムを持つ格子ベクトルを求める問題である。近似SVPの解を、近似最短ベクトルという。γが小さいとき、高次元の格子に関する近似SVPを解くことは困難である。

格子暗号として知られるGGH暗号システム(Goldreich, 1997)、Micciancio's GGH暗号システム (Micciancio, 2001)、NTRU暗号システム (Hoffstein, 1998)の秘密鍵は、格子ベクトル、または格子ベクトルの組から成っている。これらの暗号システムに関連付けられる格子をそれぞれ、 GGH格子、Micciancio's GGH格子、 NTRU格子という。これらの格子において秘密鍵の格子ベクトルを求める問題は、近似SVPに相当する。本論文では、秘密鍵の格子ベクトルをVSV(very short vector)と呼ぶことにする。 VSVは、小さな近似係数 (apfa)の近似最短ベクトルである。ここで、格子ベクトル vの apfaとは、vと最短ベクトルとのノルムの比である。また、 NTRU格子において、VSVは最短ベクトルに一致することが知られている。従って、このような場合は、 VSVを求める問題は SVPに相当すると考えられる。

基底簡約は、VSVを求めるための手段の一つである。基底簡約とは、与えられた任意の基底に対して、短い格子ベクトルから成る基底を求めることである。代表的な基底簡約アルゴリズムとして、 LLLアルゴリズム (Lenstra, 1982)、BKZアルゴリズム (Schnorr, 1994)、RSRアルゴリズム (Schnorr, 2003)が知られている。 BKZアルゴリズムと RSRアルゴリズムは、100以上の次元において、 VSVを求めることができる。しかし、これらのアルゴリズムは、 200前後の高次元において、また、それ以上の高次元において、 VSVを求めることができなくなる。これらのアルゴリズムにおいて、基底の格子ベクトルの apfaを縮小するために全探索手法が用いられているが、 apfaは一度の全探索において√0.99 のような小さい比率でしか縮小されない。高次元において VSVを求めるためには、全探索の効率を上げる必要がある。効率を上げる方法として、一度の全探索において VSVを求めることが考えられる。しかし、既存の全探索手法の中で最も効率の良い Enumeration(Schnorr, 1994)は、低次元においてしか VSVを求めることができない。

本研究の目的は、高次元において高確率で VSVを求める全探索手法を構築することである。このため、本研究では、 RSRアルゴリズムにおいて用いられる探索空間である SA空間を改良することにより、探索空間が VSVを包含する確率を高くする。本研究における結果を、以下に示す。

1. VSVの係数の分布が増加幾何数列に関連することを示した。特に、 VSVの係数の分布は、 GSA(Geometric Series Assumption)に直接的に関連していることを実験的に示した。また、 GSAと VSVの係数に関する仮定とに基づいて VSVの係数の上限値を導くことによって、 VSVの係数と増加幾何数列との関係を理論的に示した。

2. VSVの係数の分布に基づいて、拡張型探索空間 (ESS)を定義した。また、 ESSが VSVを高い確率で包含することを示した。例えば、 200次元の GGH格子において、ESSは SA空間に対して 25倍の頻度で VSVを包含することを実験的に示した。

3. ESSにおける VSV包含確率の計算法を示し、 VSV包含確率を最大にする ESSの適切なパラメータを決定するスキーム PR(Parameter Refi nement for ESS)を提案した。VSV包含確率の計算のためには、VSVの係数の期待値からのずれに関する分布を導入した。また、この分布を得るために、VSV既知の基底のセットであるサンプル基底を導入した。格子暗号においては、鍵生成アルゴリズムが知られているため、サンプル基底を得ることが可能である。 PRによって決定したパラメータを用いた場合、 ESSは、既知の VSVから計算したパラメータを用いた場合と同程度の確率で VSVを包含することを実験的に示した。ランダムな格子に近い Micciancio's GGH格子においては、 VSVの係数の期待値からのずれに関する分布を利用することができないために、PRを用いることができない。このような場合にも、実験的に適切なパラメータを決定することが可能であることを示した。

4. ESSにおける全探索が効果的であることを実験的に示した。特に、 ESSにおける探索の分散計算の効果を示した。8個の CPUを用いた実験によって、 CPUの台数から予想されるよりも高い効率で高速化が達成され得ることを示した。この実験結果から、十分に多くの CPUが得られる場合、ESSにおける全探索は BKZアルゴリズムよりも効率が良いと推定される。

以上の結果に基づいて、高次元において高確率で VSVを求める全探索手法が構築されたと結論する。本研究の応用としては、全探索のみで VSVを求める手法として用いることが考えられる。また、基底簡約アルゴリズムのサブルーチンとして用いるという応用が考えられる。本研究の手法を適用する格子に関して、本研究の手法はランダムに近い Micciancio's GGH格子にも適用できたことから、ランダムな格子に一般的に適用しうると考えられる。

離散格子の与えられた基底から、その格子に属する格子ベクトルのなかで最も短いベクトル(最短ベクトル)を求める問題はSVP(Shortest Vector Problem)と呼ばれているが、NP困難であることが知られている。応用においては十分短い格子ベクトルであれば有用であることがあり、最短ベクトルの定数倍の長さまでSVP問題の条件を緩和した``近似SVP問題''を解くアルゴリズムが研究されてきた。近似SVP問題を解くためには、格子の基底ベクトル全体を短くする基底簡約アルゴリズムが使われ、そのアルゴリズムはLLL(Lenstra, 1982)、BKZ(Schnorr, 1987)、RSR(Schnorr, 2003)と進歩してきた。しかし、これらの基底簡約アルゴリズムをもってしても、数百次元を超える格子における近似SVP問題は依然として難しい問題である。本論文は、近似SVP問題を解くために使える可能性のある新たな手法を提案したものである。本論文は6章からなる。

第1章は導入である。まず、近似SVP問題の背景と現状を説明した後で、現状の問題について述べ、本論文の目的を定めている。第2章では、本論文を理解するために必要となる基礎知識について説明している。そして、格子暗号で使われる、GGH格子、NTRU格子、Micciancio GGH格子において、秘密鍵を構成する短い格子ベクトルをVSV(Very Short Vector)と呼び、VSVを求めることで実験を評価したことが述べられている。格子暗号において秘密鍵を構成する格子ベクトルは十分短いと考えられており、意味のある評価であると審査委員会は判断した。

第3章と第4章が新たな手法を提案している部分である。第3章では、RSRにおけるVSVの探索手法を拡張し、VSVを探索する格子ベクトルの空間としてESS(Extended Search Space)を提案している。ESSの妥当性を検証するために、まず、その前提となるグラムシュミット基底ベクトルの分布に関するGSA仮説とVSVの係数ベクトルの分布の仮定が成り立つ事を実験により確認している。次に、最適なパラメータを用いた場合、同じ探索空間の大きさ(候補となる格子ベクトルの数)では、ESSを用いることで、RSRの探索よりも高確率でVSVを発見できることを実験的に示している。この実験では3種類の格子に対して有効性を確認しており、十分な一般性がある結果であると審査委員会は評価した。

第4章では、ESSのパラメータの決定方法が提案されている。VSVが未知の時に与えられた基底のみからESSのパラメータを決定するのは困難である。そこで、本論文では、対象となる基底と同様の方法で生成され、VSVが既知であるサンプル基底が多数利用できるという前提のもとで、サンプル基底の統計的性質を利用することで、より良いパラメータの推定が可能であることを実験的に示している。この方法は格子の生成アルゴリズムの"癖'"を利用する方法として有効であると審査委員会は評価した。

第5章では、8 CPUで並列にESSを探索し台数分の高速化の効果が得られたことが示されている。小規模な実験であるが、本論文の成果の応用の可能性を実際に示したものとして意味があると審査委員会は判断した。

第6章は結論である。

以上のように本論文は、従来、基底簡約アルゴリズムの補助的役割しか与えられてこなかった探索の部分を研究の主な対象とし、高い確率でVSVを含む新しい探索空間を提案したものであり、近似SVP問題に関連する研究成果として高く評価することができる。したがって、本審査委員会は博士(学術)の学位を授与するにふさわしいものと認定する。