格子問題

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

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

この記事全体を通して、格子Lにおける最短の非ゼロベクトルの長さを とします。つまり、 ${\displaystyle \lambda (L)}$

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

最短ベクトル問題（SVP）

これは最短ベクトル問題の図解です（基底ベクトルは青、最短ベクトルは赤）。

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

γ近似バージョンSVP _γでは、与えられた⁠ ⁠に対して、長さが最大である非ゼロの格子ベクトルを見つける必要があります。 ${\displaystyle \gamma \cdot \lambda (L)}$ ${\displaystyle \gamma \geq 1}$

硬度結果

この問題の正確なバージョンは、ランダム化削減に対してのみNP困難であることが知られています。^{[ 2 ] [ 3 ]}対照的に、均一ノルム に関する対応する問題はNP困難であることが知られています。^{[ 4 ]}

ユークリッドノルムのアルゴリズム

ユークリッドノルムの下での SVP の正確なバージョンを解くために、いくつかの異なるアプローチが知られており、それらは 2 つのクラスに分けられます。超指数時間 ( ) とメモリを必要とするアルゴリズムと、格子次元で指数時間と空間 ( ) の両方を必要とするアルゴリズムです。前者のクラスのアルゴリズムには、格子列挙^{[ 5 ] [ 6 ] [ 7 ]}とランダムサンプリング削減^{[ 8 ] [ 9 ]}が最も顕著に含まれます。一方、後者には、格子ふるい分け^{[ 10 ] [ 11 ] [ 12 ]}格子のボロノイセルの計算^{[ 13 ] [ 14 ]}と離散ガウスサンプリング^{[ 15 ]}が含まれます。未解決の問題は、正確な SVP を解くアルゴリズムが存在し、単一の指数時間 ( ) で実行され、格子次元で多項式的にスケーリングされるメモリを必要とするかどうかです。^{[ 16 ]}${\displaystyle 2^{\オメガ (n)}}$ ${\displaystyle \operatorname {poly} (n)}$ ${\displaystyle 2^{\Theta (n)}}$ ${\displaystyle 2^{O(n)}}$

ユークリッドノルムのγ 近似版 SVP _γを解くために、最もよく知られているアプローチは、格子基底縮小を使用するものです。 ⁠ ⁠が大きい場合、Lenstra–Lenstra–Lovász (LLL) アルゴリズムは、格子次元の時間多項式で解を見つけることができます。 より小さな値の場合、ブロック Korkine-Zolotarev アルゴリズム (BKZ) ^{[ 17 ] [ 18 ] [ 19 ]}が一般的に使用され、アルゴリズムへの入力 (ブロックサイズ) によって時間の複雑さと出力の品質が決まります。近似係数が大きい場合、ブロックサイズは小さくて十分であり、アルゴリズムはすぐに終了します。 が小さい場合、十分に短い格子ベクトルを見つけるために、より大きな が必要になり、アルゴリズムは解を見つけるのにより長い時間がかかります。 BKZ アルゴリズムは、内部的に正確な SVP アルゴリズムをサブルーチンとして使用します (最大 次元の格子で実行)。その全体的な複雑さは、次元⁠ ⁠でのこれらの SVP 呼び出しのコストに密接に関連しています。 ${\displaystyle \gamma >1}$ ${\displaystyle \gamma =2^{\オメガ (n)}}$ ${\displaystyle \gamma}$ ${\displaystyle \beta}$ ${\displaystyle \gamma}$ ${\displaystyle \beta}$ ${\displaystyle \gamma}$ ${\displaystyle \beta}$ ${\displaystyle \beta}$ ${\displaystyle \beta}$

ギャップSVP

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

問題のさらに別のバージョンは、関数 ζ と γ に対するGapSVP _ζ,γです。アルゴリズムへの入力は、基底と数です。グラム–シュミット直交化のすべてのベクトルの長さが少なくとも 1 であること、および⁠ ⁠であることが保証されています ( は次元です)。アルゴリズムは⁠ ⁠の場合に受け入れ、 ⁠ ⁠の場合は拒否する必要があります。大きい(つまり⁠ ⁠ ) 場合、問題は GapSVP _{γと同等です。} ^{[ 20 ]} LLL アルゴリズムを使用した前処理により、2 番目の条件 (および⁠ ⁠ ) が冗長になるためです。 ${\displaystyle B}$ ${\displaystyle d}$ ${\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}}$ ${\displaystyle \zeta }$

最近似ベクトル問題（CVP）

これは最近接ベクトル問題の図解です (基底ベクトルは青、外部ベクトルは緑、最近接ベクトルは赤)。

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

SVPとの関係

最近接ベクトル問題は、最短ベクトル問題の一般化である。CVP _γのオラクル（以下で定義）が与えられれば、そのオラクルにいくつかのクエリを実行することでSVP _{γを解けることは容易である。} ^{[ 21 ]} CVP _γオラクルを呼び出して0に最も近いベクトルを見つけることで最短ベクトルを見つけるという単純な方法は、0自体が格子ベクトルであり、アルゴリズムが0を出力する可能性があるため、機能しない。

_{SVP γ}からCVP _γへの縮約は以下のとおりです。SVP _γへの入力が格子 の基底であると仮定します。基底 を考え、CVP _γ ( B ⁱ , b _i )によって返されるベクトルを とします。集合 内の最短ベクトルは、与えられた格子 内の最短ベクトルであるという主張です。 ${\displaystyle B=[b_{1},b_{2},\ldots ,b_{n}]}$ ${\displaystyle B^{i}=[b_{1},\ldots ,2b_{i},\ldots ,b_{n}]}$ ${\displaystyle x_{i}}$ ${\displaystyle \{x_{i}-b_{i}\}}$

硬度結果

Goldreichらは、SVPの困難さはCVPの困難さと同じであることを意味していることを示した。^{[ 22 ]} AroraらはPCPツールを用いて、 CVPはでない限りの係数で近似することが難しいことを示した。^{[ 23 ]} Dinurらは、についてのNP困難性結果を与えることでこれを強化した。^{[ 24 ]}${\displaystyle 2^{\log ^{1-\epsilon }(n)}}$ ${\displaystyle \operatorname {NP} \subseteq \operatorname {DTIME} (2^{\operatorname {poly} (\log n)})}$ ${\displaystyle \epsilon =(\log \log n)^{c}}$ ${\displaystyle c<1/2}$

球面デコード

CVPアルゴリズム、特にフィンケとポストの変種^{[ 6 ]}は、多入力多出力（MIMO）無線通信システム（符号化信号と非符号化信号）におけるデータ検出に使用されています。^{[ 25 ] [ 13 ]}この文脈では、多くのCVPソリューションの内部で使用される半径のため、球面復号化と呼ばれています。 ^{[ 26 ]}

これは、搬送波位相GNSS（GPS）の整数アンビギュイティ解決の分野に応用されている。^{[ 27 ]}この分野ではLAMBDA法と呼ばれている。同分野において、一般的なCVP問題は整数最小二乗法と呼ばれている。

ギャップCVP

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

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

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

既知の結果

この問題は、任意の近似係数に対して NPに自明に含まれます。

1987年、シュノアは決定論的多項式時間アルゴリズムが の問題を解けることを示した。^{[ 28 ]}アジタイらは確率的アルゴリズムが のわずかに優れた近似係数を達成できることを示した。^{[ 10 ]}${\displaystyle \beta =2^{O(n(\log \log n)^{2}/\log n)}}$ ${\displaystyle \beta =2^{O(n\log \log n/\log n)}}$

1993年、バナシュチクはGapCVP _nが に属することを示した。^{[ 29 ]} 2000年、ゴールドライヒとゴールドワッサーは が問題をNPとcoAMの両方に置くことを示した。^{[ 30 ]} 2005年、アハロノフとレゲフは、ある定数 に対して、 の問題がに属することを示した。^{[ 31 ]}${\displaystyle {\mathsf {NP\cap conNP}}}$ ${\displaystyle \beta ={\sqrt {n/\log n}}}$ ${\displaystyle c}$ ${\displaystyle \beta =c{\sqrt {n}}}$ ${\displaystyle {\mathsf {NP\cap conNP}}}$

下限値については、Dinurらは1998年にこの問題がNP困難であることを示した。^{[ 32 ]}${\displaystyle \beta =n^{o(1/\log {\log {n}})}}$

最短独立ベクトル問題（SIVP）

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}\}}$

近似バージョンでは、次元nの格子 L が与えられた場合、長さ⁠ ⁠のn個の線形独立ベクトルを見つける必要があります。ここで、⁠ ⁠ は ⁠ ⁠番目の^連続する最小値です。 ${\displaystyle \gamma}$ ${\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困難問題がこの性質を欠いていることを示唆しています。つまり、おそらく最悪ケース困難であるに過ぎないということです。多くの格子問題は平均ケース困難であると推測または証明されており、暗号方式の基盤として魅力的な問題群となっています。さらに、一部の格子問題の最悪ケース困難性は、安全な暗号方式の作成に利用されてきました。このような暗号方式における最悪ケース困難性の利用により、これらの暗号方式は量子コンピュータに対しても安全である可能性が非常に高い、ごく少数の暗号方式の一つとなっています。

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

アジタイは彼の独創的な論文で、SVP問題がNP困難であることを示し、いくつかの格子問題の最悪ケースの複雑性と平均ケースの複雑性の間にいくつかの関係を発見しました。 ^{[ 2 ] [ 3 ]}これらの結果に基づいて、アジタイとドワークは、特定のバージョンのSVPの最悪ケースの困難性のみを使用してセキュリティを証明できる公開鍵暗号システムを作成しました。 ^{[ 34 ]}これにより、最悪ケースの困難性を使用して安全なシステムを作成する最初の結果となりました。^{[ 35 ]}

参照

• 間違いから学ぶ
• 短整数解問題

参考文献

1. Khot, Subhash (2005). 「格子における最短ベクトル問題の近似の困難さ」J. ACM . 52 (5): 789– 808. doi : 10.1145/1089023.1089027 . S2CID  13438130 .
2. Ajtai, M. (1996). 「格子問題の困難なインスタンス生成」 .第28回ACMコンピューティング理論シンポジウム議事録. ペンシルベニア州フィラデルフィア: ACM. pp.  99– 108. doi : 10.1145/237814.237838 . ISBN 978-0-89791-785-8. S2CID  6864824 .
3. Ajtai, Miklós (1998). 「 L ₂における最短ベクトル問題はランダム縮約に対してNP困難である」 .第30回ACMコンピューティング理論シンポジウム議事録. テキサス州ダラス、アメリカ合衆国: ACM. pp.  10– 19. doi : 10.1145/276698.276705 . ISBN 978-0-89791-962-3. S2CID  4503998 .
4. van Emde Boas, Peter (1981). 「もう一つのNP完全問題と格子内の短いベクトルの計算の複雑さ」 .技術報告書8104.アムステルダム大学数学部、オランダ.
5. Kannan, Ravi (1983). 「整数計画法および関連する格子問題のための改良アルゴリズム」.第15回ACMコンピューティング理論シンポジウム議事録 - STOC '83 . ニューヨーク、ニューヨーク州、米国: ACM. pp.  193– 206. doi : 10.1145/800061.808749 . ISBN 978-0-89791-099-6. S2CID  18181112 .
6. Fincke, U.; Pohst, M. (1985). 「格子内の短い長さのベクトルを計算するための改良法、計算量解析を含む」 . Math. Comp . 44 (170): 463– 471. doi : 10.1090/S0025-5718-1985-0777278-8 .
7. Gama, Nicolas; Nguyen, Phong Q.; Regev, Oded (2010-05-30). 「極端枝刈りを用いた格子列挙」 .暗号学の進歩 – EUROCRYPT 2010.コンピュータサイエンス講義ノート. 第6110巻. Springer, ベルリン, ハイデルベルク. pp.  257– 278. doi : 10.1007/978-3-642-13190-5_13 . ISBN 978-3-642-13189-9. S2CID  1938519 .
8. Schnorr, Claus Peter (2003-02-27). 「ランダムサンプリングと誕生日法による格子縮約」. Stacs 2003 . コンピュータサイエンス講義ノート. 第2607巻. Springer, ベルリン, ハイデルベルク. pp.  145– 156. CiteSeerX 10.1.1.137.4293 . doi : 10.1007/3-540-36494-3_14 . ISBN  978-3-540-36494-8。
9. 青野 義則; グエン フォン Q. (2017-04-30). 「ランダムサンプリング再考：離散枝刈りによる格子列挙」.暗号学の進歩 – EUROCRYPT 2017 (PDF) . コンピュータサイエンス講義ノート. 第10211巻. Springer, Cham. pp.  65– 102. doi : 10.1007/978-3-319-56614-6_3 . ISBN 978-3-319-56613-9. S2CID  39082279 .
10. Ajtai, Miklós; Kumar, Ravi; Sivakumar, D. (2001). 「最短格子ベクトル問題のためのふるいアルゴリズム」 .第33回ACMコンピューティング理論シンポジウム議事録. ギリシャ、ヘルソニソス: ACM. pp.  601– 610. doi : 10.1145/380752.380857 . ISBN 1-58113-349-9. S2CID  14982298 .
11. ミッチアンチョ, ダニエレ; ヴールガリス, パナギオティス (2010). 「最短ベクトル問題のための指数時間アルゴリズムの高速化」 .第21回ACM-SIAM離散アルゴリズムシンポジウム議事録. SODA '10. ペンシルベニア州フィラデルフィア: Society for Industrial and Applied Mathematics. pp.  1468– 1480. doi : 10.1137/1.9781611973075.119 . ISBN 978-0-89871-698-6. S2CID  90084 .
12. Becker, A.; Ducas, L.; Gama, N.; Laarhoven, T. (2015-12-21). 「最近傍探索の新たな方向性と格子ふるい分けへの応用」.第27回ACM-SIAM離散アルゴリズムシンポジウム議事録. Society for Industrial and Applied Mathematics. pp.  10– 24. doi : 10.1137/1.9781611974331.ch2 . ISBN 978-1-61197-433-1。
13. Agrell, E.; Eriksson, T.; Vardy, A.; Zeger, K. (2002). 「格子における最近点探索」(PDF) . IEEE Trans. Inf. Theory . 48 (8): 2201– 2214. doi : 10.1109/TIT.2002.800499 .
14. Micciancio, Daniele; Voulgaris, Panagiotis (2010). 「ボロノイセル計算に基づく、ほとんどの格子問題に対する決定論的単一指数時間アルゴリズム」.第42回ACM計算理論シンポジウム議事録. STOC '10. ニューヨーク、ニューヨーク州、米国: ACM. pp.  351– 358. CiteSeerX 10.1.1.705.3304 . doi : 10.1145/1806689.1806739 . ISBN  978-1-4503-0050-6. S2CID  2449948 .
15. Aggarwal, Divesh; Dadush, Daniel; Regev, Oded; Stephens-Davidowitz, Noah (2015). 「離散ガウスサンプリングを用いた最短ベクトル問題の2n時間解法」.^第47回ACM計算理論シンポジウム議事録. STOC '15. ニューヨーク、ニューヨーク州、米国: ACM. pp.  733– 742. doi : 10.1145/2746539.2746606 . ISBN 978-1-4503-3536-2. S2CID  10214330 .
16. Micciancio, Daniele (2017-07-01). 「格子暗号 – 最短ベクトル問題」 .
17. Schnorr, CP (1987-01-01). 「多項式時間格子基底縮約アルゴリズムの階層」 .理論計算機科学. 53 (2): 201– 224. doi : 10.1016/0304-3975(87)90064-8 .
18. Schnorr, CP; Euchner, M. (1994-08-01). 「格子基底縮約：改良された実用アルゴリズムと部分集合和問題の解法」(PDF) .数理計画. 66 ( 1–3 ): 181–199 . doi : 10.1007/bf01581144 . ISSN 0025-5610 . S2CID 15386054 .  
19. Chen, Yuanmi; Nguyen, Phong Q. (2011-12-04). 「BKZ 2.0: 格子暗号のセキュリティ推定精度の向上」. Advances in Cryptology – ASIACRYPT 2011 . Lecture Notes in Computer Science. Vol. 7073. Springer, Berlin, Heidelberg. pp.  1– 20. doi : 10.1007/978-3-642-25385-0_1 . ISBN 978-3-642-25384-3。
20. Peikert, Chris (2009). 「最悪ケース最短ベクトル問題からの公開鍵暗号システム：拡張概要」 .第41回ACMコンピューティング理論シンポジウム議事録. 米国メリーランド州ベセスダ: ACM. pp.  333– 342. doi : 10.1145/1536414.1536461 . ISBN 978-1-60558-506-2. S2CID  1864880 .
21. ミッチャンシオ、ダニエレ;ゴールドワッサー、シャフィ(2002)。格子問題の複雑さ。スプリンガー。
22. Goldreich, O.; et al. (1999). 「最短格子ベクトルの近似は、最近傍格子ベクトルの近似よりも難しくない」. Inf. Process. Lett . 71 (2): 55– 61. doi : 10.1016/S0020-0190(99)00083-6 .
23. Arora, Sanjeev; et al. (1993). 「1993 IEEE 34th Annual Foundations of Computer Science Proceedings」. J. Comput. Syst. Sci . Vol. 54. pp.  317– 331. doi : 10.1109/SFCS.1993.366815 . ISBN 978-0-8186-4370-5. S2CID  44988406 .
24. Dinur, I.; et al. (2003). 「CVPをほぼ多項式係数の範囲内に近似することはNP困難である」. Combinatorica . 23 (2): 205– 243. doi : 10.1007/s00493-003-0019-y . S2CID 45754954 . 
25. Biglieri, E.; Calderbank, R.; Constantinides, Anthony G .; Goldsmith, A.; Paulraj, A.; Poor, HV (2007). MIMOワイヤレス通信. ケンブリッジ: Cambridge UP
26. Wang, Ping; Le-Ngoc, Tho (2011). 「改良された半径設定戦略を備えたリスト球面復号アルゴリズム」.ワイヤレスパーソナルコミュニケーションズ. 61 (1): 189– 200. doi : 10.1007/s11277-010-0018-4 . S2CID 30919872 . 
27. Hassibi, A.; Boyd, S. (1998). 「線形モデルにおける整数パラメータ推定とGPSへの応用」. IEEE Trans. Sig. Proc . 46 (11): 2938– 2952. Bibcode : 1998ITSP...46.2938H . CiteSeerX 10.1.1.114.7246 . doi : 10.1109/78.726808 . 
28. Schnorr, CP「整数の因数分解とディオファントス近似による離散対数の計算」。暗号学の進歩 - Eurocrypt '91の議事録。
29. Banaszczyk, W. (1993). 「数の幾何学におけるいくつかの転移定理の新しい境界」. Math. Ann. 296 (1): 625– 635. doi : 10.1007/BF01445125 . S2CID 13921988 . 
30. Goldreich, Oded; Goldwasser, Shafi (1998). 「格子問題の非近似不可能性限界について」 .第30回ACM計算理論シンポジウム議事録. テキサス州ダラス、アメリカ合衆国: ACM. pp.  1– 9. doi : 10.1145/276698.276704 . ISBN 0-89791-962-9. S2CID  3051993 .
31. アハロノフ、ドリット;オデッド・レゲブ (2005)。 「NP coNPにおける格子問題」。 Ｊ．ＡＣＭ．52 ( 5 ) : 749–765。CiteSeerX 10.1.1.205.3730 。土井: 10.1145/1089023.1089025。S2CID 1669286。${\displaystyle \cap}$   
32. Dinur, I.; Kindler, G.; Safra, S. (1998). 「CVPをほぼ多項式因数の範囲内に近似することはNP困難である」 .第39回コンピュータサイエンス基礎シンポジウム議事録. IEEEコンピュータ協会. p. 99. ISBN 978-0-8186-9172-0。
33. Lenstra, AK; Lenstra, HW Jr.; Lovász, L. (1982). 「有理係数を持つ多項式の因数分解」(PDF) . Math. Ann. 261 (4): 515– 534. doi : 10.1007/BF01457454 . S2CID 5701340. 2011年7月17日時点のオリジナル(PDF)からのアーカイブ。 
34. Ajtai, Miklós; Dwork, Cynthia (1997). 「最悪ケース/平均ケースの等価性を備えた公開鍵暗号システム」 .第29回ACMコンピューティング理論シンポジウム議事録. テキサス州エルパソ、アメリカ合衆国: ACM. pp.  284– 293. doi : 10.1145/258533.258604 . ISBN 0-89791-888-6. S2CID  9918417 .
35. Cai, Jin-Yi (2000). 「いくつかの格子問題の計算量」.アルゴリズム的数論. コンピュータサイエンス講義ノート. 第1838巻. pp.  1– 32. doi : 10.1007/10722028_1 . ISBN 978-3-540-67695-9。

さらに読む

• Agrell, E.; Eriksson, T.; Vardy, A.; Zeger, K. (2002). 「格子における最近点探索」(PDF) . IEEE Trans. Inf. Theory . 48 (8): 2201– 2214. doi : 10.1109/TIT.2002.800499 .
• ミッチアンチョ, ダニエレ (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。