格子問題

コンピュータサイエンスにおいて、格子問題は格子と呼ばれる数学的対象に関連する最適化問題の一種です。このような問題の難解さは、安全な格子ベースの暗号システムの構築において中心的な役割を果たします。格子問題は、平均ケースで困難であることが示されているNP困難問題の一例であり、暗号アルゴリズムの安全性のテストケースとなります。さらに、最悪ケースで困難な格子問題の中には、極めて安全な暗号方式の基礎として使用できるものもあります。このような方式で最悪ケースの困難性を利用することで、量子コンピュータに対しても非常に安全である可能性の高い数少ない方式の一つとなります。このような暗号システムへの応用では、ベクトル空間上の格子（多くの場合）が用いられます。$\displaystyle \mathbb {Q} ^{n}}$）または無料モジュール（多くの場合）${\displaystyle \mathbb {Z} ^{n}}$）は一般的に考えられています。

以下のすべての問題については、（他のより具体的な入力に加えて）ベクトル空間Vの基底とノルムNが与えられていると仮定します。通常考慮されるノルムはユークリッドノルムL ^{2です。ただし、他のノルム（} L ^pなど）も考慮され、さまざまな結果に現れます。^{[ 1 ]}

この記事全体を通して、${\displaystyle \lambda (L)}$格子L内の最短の非ゼロベクトルの長さを表す。すなわち、

${\displaystyle \lambda (L)=\min _{v\in L\smallsetminus \{\mathbf {0} \}}\|v\|_{N}。}$

SVPでは、格子Lに対してベクトル空間Vの基底とノルムN（多くの場合L² ^）が与えられ、 Nで測ったV内の最短非ゼロベクトルをL内で見つける必要があります。言い換えれば、アルゴリズムは、次の条件を満たす非ゼロベクトルvを出力する必要があります。${\displaystyle \|v\|_{N}=\lambda (L)}$以下では、問題のサイズはベクトル空間Vの次元nで指定されます。

γ近似版SVPγでは_、長さが最大でゼロでない格子ベクトルを見つける必要がある。${\displaystyle \gamma \cdot \lambda (L)}$与えられた⁠${\displaystyle \gamma \geq 1}$⁠ .

_{GapSVP β}問題は、最短ベクトルの長さが最大で である SVP のインスタンスを区別することから成ります。${\displaystyle 1}$またはより大きい⁠${\displaystyle \beta }$⁠、そこで${\displaystyle \beta }$格子の次元の固定関数となる可能性がある${\displaystyle n}$格子の基底が与えられた場合、アルゴリズムは、${\displaystyle \lambda (L)\leq 1}$または⁠${\displaystyle \lambda (L)>\beta }$他のプロミス問題と同様に、このアルゴリズムは他のすべてのケースでエラーを起こすことが許容されます。

この問題の別のバージョンは、関数 ζ と γ に対する GapSVP _ζ,γです。アルゴリズムへの入力は基底です。${\displaystyle B}$そして数${\displaystyle d}$グラム・シュミット直交化におけるすべてのベクトルの長さが少なくとも 1 であり、${\displaystyle \lambda (L(B))\leq \zeta (n)}$そしてそれは${\displaystyle 1\leq d\leq \zeta (n)/\gamma (n)}$⁠、そこで${\displaystyle n}$は次元です。アルゴリズムは、 の場合に受け入れる必要があります。${\displaystyle \lambda (L(B))\leq d}$⁠、そして拒否する場合⁠${\displaystyle \lambda (L(B))\geq \gamma (n)\cdot d}$⁠。大規模な場合${\displaystyle \zeta }$（つまり⁠${\displaystyle \zeta (n)>2^{n/2}}$⁠ _{)、この問題は GapSVP γ}と同等です。なぜなら^{[ 20 ]} LLL アルゴリズムを使用した前処理により、2 番目の条件 (したがって、 ⁠${\displaystyle \zeta }$冗長です。

CVPでは、格子Lに対してベクトル空間Vの基底と計量M（多くの場合L2）が与えられ、 Vに含まれるが必ずしもLに含ま^れるとは限らないベクトルvも与えられる。Mによって測定されたvに最も近いL内のベクトルを見つけることが求められる。${\displaystyle \gamma }$-近似バージョン CVP _γでは、最大距離にある格子ベクトルを見つける必要があります${\displaystyle \gamma }$。

この問題はGapSVP問題に似ています。GapSVPβの場合、入力は格子基底とベクトルで構成されます_。${\displaystyle v}$、そしてアルゴリズムは、以下のいずれかが成り立つかどうかを答える必要がある。

• 格子ベクトルが存在し、それととの距離は${\displaystyle v}$最大で 1 であり、
• すべての格子ベクトルは、${\displaystyle \beta }$離れて${\displaystyle v}$。

反対の条件は、最も近い格子ベクトルが距離にあることです。${\displaystyle 1<\lambda (L)\leq \beta }$そのため、 Gap CVPという名前が付けられました。

n次元の格子Lが与えられたとき、アルゴリズムはn個の線形独立な値を出力しなければならない。${\displaystyle v_{1},v_{2},\ldots ,v_{n}}$となることによって${\displaystyle \max \|v_{i}\|\leq \max _{B}\|b_{i}\|}$右辺はすべての基底を考慮している${\displaystyle B=\{b_{1},\ldots ,b_{n}\}}$格子の。

では${\displaystyle \gamma }$-近似版では、次元nの格子 L が与えられた場合、 n個の線形独立なベクトルを見つける必要がある。${\displaystyle v_{1},v_{2},\ldots ,v_{n}}$長さ⁠${\displaystyle \max \|v_{i}\|\leq \gamma \lambda _{n}(L)}$⁠、そこで${\displaystyle \lambda _{n}(L)}$は⁠${\displaystyle n}$⁠^の連続する最小値⁠${\displaystyle L}$⁠ .

この問題はCVPに似ています。格子からの距離が最大で${\displaystyle \lambda (L)/2}$アルゴリズムは、それに最も近い格子ベクトルを出力する必要がある。

格子の基底が与えられた場合、アルゴリズムは任意のベクトルから格子までの最大距離（または一部のバージョンではその近似値）を見つける必要がある。

入力基底が短いベクトルで構成されている場合、多くの問題が容易になります。最短基底問題 (SBP) を解くアルゴリズムは、格子基底が与えられた場合、${\displaystyle B}$⁠、同等の基底を出力する${\displaystyle B'}$最長ベクトルの長さは${\displaystyle B'}$できるだけ短く。

近似版SBPγ_問題は、最長ベクトルが最大で${\displaystyle \gamma }$最短基底における最長ベクトルよりも倍長い。

問題の平均ケースの困難性は、ほとんどの暗号方式のセキュリティ証明の基礎となる。しかし、実験的証拠によれば、ほとんどのNP困難問題はこの性質を欠いており、おそらく最悪ケースの困難性しか持たない。多くの格子問題は平均ケースの困難性が予想または証明されており、暗号方式の基礎となる魅力的な問題群となっている。さらに、一部の格子問題の最悪ケースの困難性は、安全な暗号方式を作成するために利用されてきた。このような方式で最悪ケースの困難性を利用することで、量子コンピュータに対しても非常に安全である可能性の高い、ごく少数の方式の一つとなっている。

上記の格子問題は、「良い」基底が与えられれば簡単に解くことができます。格子縮小アルゴリズムは、格子の基底が与えられたときに、比較的短く、ほぼ直交するベクトルからなる新しい基底を出力することを目的としています。Lenstra –Lenstra–Lovász格子基底縮小アルゴリズム（LLL）は、この問題に対する初期の効率的なアルゴリズムであり、ほぼ縮小された格子基底を多項式時間で出力できました。^{[ 33 ]}このアルゴリズムとその後の改良版は、いくつかの暗号方式を破るために使用され、暗号解読における非常に重要なツールとしての地位を確立しました。実験データに対するLLLの成功により、格子縮小は実際には簡単な問題であるという考えが生まれましたが、1990年代後半に、 Ajtaiの結果から始まる格子問題の困難性に関するいくつかの新しい結果が得られたことで、この考えは疑問視されました。^{[ 2 ]}

Ajtai は、その画期的な論文で SVP 問題が NP 困難であることを示し、いくつかの格子問題の最悪ケースの複雑さと平均ケースの複雑さの間にいくつかの関連性があることを発見しました。 ^{[ 2 ] [ 3 ]}これらの結果に基づいて、Ajtai とDwork は、SVP のあるバージョンの最悪ケースの困難性のみを使用して安全性を証明できる公開鍵暗号システムを作成しました。 ^{[ 34 ]}これにより、最悪ケースの困難性を使用して安全なシステムを構築した最初の結果となりました。^{[ 35 ]}

• 失敗から学ぶ
• 短い整数解問題

• Agrell, E.; Eriksson, T.; Vardy, A.; Zeger, K. (2002). "格子における最近点探索" (PDF) . IEEE Trans. Inf. Theory . 48 (8): 2201– 2214. doi : 10.1109/TIT.2002.800499 .
• Micciancio, Daniele (2001). "最短ベクトル問題は、ある定数の範囲内で近似するのがNP困難である" . SIAM Journal on Computing . 30 (6): 2008–2035 . CiteSeerX 10.1.1.93.6646 . doi : 10.1137/S0097539700373039 . S2CID 42794945 .  
• Nguyen, Phong Q.; Stern, Jacques (2000). 「暗号学における格子縮小：最新情報」 .第4回アルゴリズム数論国際シンポジウム議事録. Springer-Verlag. pp. 85–112 . ISBN  978-3-540-67695-9。