現代格子史

現代格子史

Latticeだよ, 束じゃなくて格子だよ. Point Latticeとも言うらしい.

数学関連で来た人はごめんなさい. Diophantine ApproximationやSphere Packingはここでは扱ってません. 二次体もあやふやな人が書いています.

古代

  • Euclid ユークリッド (325BC–265BC)
    • ユークリッドの互除法
      • 1次元格子の縮約と取れる.
  • Diophantus ディオファントス (200?-284?)
    • Diophantus方程式やDiophantus近似で有名ですね.

1800-1969

  • 1801, Gauss (ガウス) "Disquisitiones arithmeticae"
    • ユークリッドの互除法の拡張. 2次元格子の縮約.
    • この項嘘らしい. 実は2次元格子の縮約はLagrange. 一般化したのがHermiteだそうだ. The first lattice reduction algorithm in arbitrary dimension is due to Hermite [11], and is based on Lagrange's two-dimensional algorithm [13] (often wrongly attributed to Gauss). (Gama, Howgrave-Graham, Koy, and Nguyen "Rankin's Constant and Blockwise Lattice Reduction" (CRYPTO 2006))
  • Minkowski
    • 数の幾何の発祥.
    • Minkowski's LemmaとかMinkowski空間とかMinkowski和とか有名ですね.
  • Dirichlet
    • 代数的整数論でも色々. Diophantin Approximationやら何やら.
  • Lekkerkerker
    • 数の幾何の偉い人らしい.

1970- Complexity

1970-1990

  • 1981. P. Van Emde Boas. "Another NP-complete partition problem and the complexity of computing short vectors in lattices" (MI-UvA-81-04)
    • l_{p} normのCVPのNP困難性 (for all p \geq 1)と, l_\infty normのSVPのNP困難性.
  • 1985. J. C. Lagarias. "The computational complexity of simultaneous diophantine approximation problems" (SIAM J. Comp. 14(1): 196-209 (1985))
    • l_{\infty} normのSVPのNP困難性.
    • その名の通りDiophantus近似へ帰着.
  • 1987. A. Paz, C. P. Schnorr. "Approximitaing Integer Lattices by Lattice with Cyclic Factor Groups" (ICALP 1987, Automata, languages and programming 1987)
    • 1-cycleな格子で任意の格子を近似する. Smith Normal Formを上手く使う.
      • 後にTrolinの解析に繋がる流れ.
      • 近似の手法がミスプリントか間違っているので注意. 直したので纏めておかないとな. (2006/01/21)
  • 1990. J. C. Lagarias, H. W. Lenstra, C. P. Schnorr. "Korkin-Zolotarev Bases and Successive Minima of a Lattice and its Reciprocal Lattice". (Combinatorica 10(4), 1990)
    • NP≠coNPならば, 近似度nのSVPはNP困難でない.
    • Korkin-Zolotarev基底とTransference Theoremを使っている (らしい).

1991-2000

  • 1998. M. Ajtai. "The shortest vector problem in L_2 is NP-hard for randomized reductions".
    • Randomized Reductionのもとでのl_2 normのSVPのNP困難性. 近似度が1+\frac{1}{2^{n^{k}}}の場合も示してある.
    • 「NP \not\subseteq RP」を仮定しているともいえる.
  • 1998. J-Y. Cai and A. Nerurkar. "Approximating the SVP to within a factor (1+\frac{1}{\dim^{\epsilon}}) is NP-hard under randomized reduction".
    • Ajtaiの結果の拡張. 近似度1+\frac{1}{n^{\epsilon}}のSVPのNP困難性 (Randomized Reduction).
  • 1998. D. Micciancio. "The Shortest Vector in a Lattice is Hard to Approximate to within Some Constant".
    • 近似度\sqrt{2}-\epsilonのSVPのNP困難性 (Randomized Reduction).
    • ノルムがl_pノルムの場合はどうだったか. 一般的にやっていたはず.
  • 1998. O. Goldreich and S. Goldwasser "On the Limits of Non-Approximability of Lattice Problems".
    • 近似度\sqrt{n}のSVPがNP∩coAMに入る. 近似度が\sqrt{n/\log n}の場合も同様の方針で可能.
    • n次元球が重なるか重ならないかというイメージ.
  • 1998. J-Y. Cai. "A Relation of Primal-Dual Lattices and the Complexity of Shortest Lattice Vector Problem".
    • n^{1/4}-uSVPがNP∩coAMに入る. GG1998のアイデアを使っている.
    • quotent latticeという概念は色々と使えるかも.
  • 1999. I. Dumer, D. Micciancio and M. Sudan. "Hardness of Approximating the Minimum Distance of a Linear Code"
    • 符号理論よりの話. 未読なので詳細不明.
  • 2000. J. Blömer. "Closest Vectors, Successive Minima and Dual HKZ-Bases of Lattices" (ICALP 2000)
  • 2000. P. Klein. "Finding the closest lattice vector when it's unusually close" (SODA 2000)
    • Liu, Lyubashevsky, Micciancio (RANDOM 2006)を踏まえるに, 1/n-BDDPを多項式時間で解くアルゴリズム.

2001-

  • 2001. D. Micciancio. "The Shortest Vector in a Lattice is Hard to Approximate to within Some Constant".
    • Micciancio 1998のFull Paperか.
    • 近似度\sqrt{2}-\epsilonのSVPのNP困難性 (Randomized Reduction). l_p norm (p < \infty) で近似度2^{1/p}-\epsilon.
  • 2001. M. Trolin. "The Shortest Vector Problem in Lattices with Many Cycles" (CaLC 2001)
    • (n-1)-cyclic latticeのl_{\infty} normでのSVPがNP困難 (だった筈).
  • 2002. I. Dinur. "Approximating SVP_{\infty} to within almost-polynomial factors is NP-hard".
    • l_{\infty}-normでの近似度n^{O(1/\log \log n)}のSVPがNP困難.
    • l_{\infty}-normでの近似度n^{O(1/\log \log n)}のCVPもNP困難.
  • 2002. U. Feige and D. Micciancio. "The inapproximability of lattice and coding problems with preprocessing" (CCC 2002)
    • CVPPの方の話. NCPPについても結果あり.
  • 2002. E. Agrell, T. Eriksson, A. Vardy, K. Zeger. "Closest point search in lattices" (IEEE Trans. on Inf. Theo. 48-8, 2002)
    • 詳細不明.
  • 2003, D. Aharonov, O. Regev "A Lattice Problem in Quantum NP" (FOCS 2003)
    • その名の通り.
    • 格子の各点にボールを作って, 基本領域でmodulo取る. 実際にはボールじゃなくってGaussian. 量子で証拠を作らせるんだけど, ズル出来ないように上手いことしてあるらしい.
  • 2003. I. Dinur, G. Kindler, R. Raz and S. Safra. "Approximating CVP to within almost-ploynomial factor is NP-hard".
    • l_{p} normでの近似度n^{O(1/\log \log n)}のCVPがNP困難.
    • Dinur 2002の拡張か?
  • 2003. Khot. "Hardness of approximating the shortest vector problem in high L_p norms".
    • PCPのLabel Cover問題へ帰着.
  • 2004. Khot. "Hardness of approximating the shortest vector problem in lattices"
    • 「NP ⊆ RP」でないならば, l_{p} norm (p > 1) での近似度c (任意の定数) のSVPはNP困難.
    • 「NP \not\subseteq RTIME(2^{poly(\log n})」ならば, 近似度は2^{(\log n)^{1/2-\epsilon}}.
    • BDH符号を上手く使っている. 符号で作られる格子同士のテンソル積はまた符号で作られる格子になるんだったか. それを使ってboostingすることで後者の結果が出てくるようだ(斜め読み
  • 2004. D. Aharonov and O. Regev. "Lattice Problems in NP intersect coNP".
    • O(\sqrt{n})-SVPがNP∩coNPに入る.
    • Aharonov, Regev (FOCS 2003)の古典版. Gaussianを上手く使っている点がポイント.
  • 2004. M. Trolin. "Lattices with Many Cycles Are Dense" (ECCC 2004 TR-113)
    • んー, 任意の格子を(n-1)-cycleの格子で近似してしまうという話.
      • (n-1)-cycle格子のHardcore性と言っても良い.
      • 1-cycle格子のHardcore性と同様の証明方針. アイデアは違うが.
      • Ajtaiの結果も確かにn/c-cycleの格子のHardcore性になるね. Ajtaiの方はRandomized Reductionなので(ちょっと)弱いが.
      • これで1-cycleと(n-1)-cycleはHardcoreであることが解った. 他はどうだろう.
  • 2004. V. Guruswami, D. Micciancio, and O. Regev. "The complexity of the covering radius problem" (CCC 2004, Computational Complexity 2005)
    • CRP (Covering Radius Problem)は 近似度が
      • 1より大きいとBPP(2^{O(n)})
      • 2でAM
      • \sqrt{n/\log{n}}で coAM
      • \sqrt{n}でNP∩coNP
      • 2^{\Omega(n \log \log n/\log n)}でBPP
      • 2^{\Omega(n (\log \log n)^2/\log n)}でP
    • 線形符号の方についても結果あり.
  • 2005. S. Khot, M. Alekhonovich, G. Kindler, N. Vishnoi. “Hardness of approximating the closest vector problem with pre-processing.” (FOCS 2005)
  • 2005. S. Hayashi, M. Tada.. "A New NP-Complete Problem Associated with Lattice". (SCIS2005)
    • CCS2005だと署名についても言及あるらしい.
    • van Emde Boasの帰着をちょっと弄ってある.
  • 2006. O. Regev, R. Rosen. "Lattice Problems and Norm Embeddings". (STOC 2006)
    • 異なるl_{p} norm間でのインスタンスの変換.
  • 2006. I. Haviv, O. Regev. "Hardness of the Covering Radius Problem on Lattices" (CCC 2006)
    • ??
  • 2006, Y.-K. Liu, V. Lyubashevsky, D. Micciancio. "On bounded distance decoding for general lattices". (RANDOM 2006)
    • CVPの変種として, f-BDDを考える (ターゲットベクトルが格子に比較的近い). 同様にCVPPの変種としてf-BDDPを考えて, fが小さいと解けるよという話.
  • 2007. Hasegawa, Isobe, Koizumi, Shizuya. "Complexity of Lattice Distance Problem" (SCIS 2007)
    • 入力は格子が二つ. その最小の距離を求める問題をLDPとして定式化. 距離に0を許さないので, 二つの格子を同じにすれば, SVPへの帰着が各種ノルムで言える.
  • 2007. I. Haviv, O. Regev. "Tensor-based Hardness of the Shortest Vector Problem to within Almost Polynomial Factors" (STOC 2007)
    • Khot 2004の改良
    • 「NP \not\subseteq RTIME(2^{poly(\log n)})」ならば, 近似度は2^{(\log n)^{1-\epsilon}}にした.
  • 2007. J. Blömer, S. Naewe. "Sampling Methods for Shortest Vectors, Closest Vectors and Successive Minima" (ICALP 2007)

1970- Reduction (格子の縮約とその応用)

  • 1982, A. K. Lenstra, H. W. Lenstra and L. Lov\'{a}sz. "Factoring polynomials with rational coefficients" (Math. Annalen 261. 1982)
    • LLLの開発.
    • 多項式時間. 近似精度は2^{n/2}と悪いが, n=100位だと良い結果を出す.
  • 1987. C. P. Schnorr. "A Hierarchy of Polynomial Time Lattice Basis Reduction Algorithms" (Theoret. Comp. Sci. 1987)
  • 1988. C. P. Schnorr. "A More Efficient Algorithm for Lattice Reduction" (J. of Algo. 1988)
  • 1996. A. Storjohann. "Faster Algorithms for Integer Lattice Basis Reduction" (TR 1996)
  • 2001. H. Koy and C. P. Schnorr. "Segment LLL-Reduction of Lattice Bases" (CaLC 2001)
  • 2001. H. Koy and C. P. Schnorr. "Segment LLL-Reduction with Floating Point Orthogonalization" (CaLC 2001)
  • 2003. C. P. Schnorr. "Lattice Reduction by Random Sampling and Birthday Methods" (STACS 2003)
  • 2004. P. Q. Nguyen and D. Stehle. "Low-Dimensional Lattice Basis Reduction Revisited" (ANTS2004)
  • 2005. P. Q. Nguyen and D. Stehle. "Floating-Point LLL Revisited" (Eurocrypt 2005)
  • 2006. C. P. Schnorr. "Fast LLL-type Lattice Reduction" (Inf. Comput. 2006)
    • 手元にあるのは2004版.
  • 2006. N. Gama, N. Howgrave-Graham, H. Koy, annd P. Q. Nguyen. "Rankin's Constant and Blockwise Lattice Reduction"
    • Schnorrのblockwise-HZKとLLLと対比させている(らしい). Schnorrの解析結果をもうちょっと良くしてある(らしい). ついでにアルゴリズムも弄って改良した(らしい).
  • 2001. M. Ajtai, R. Kumar, D. Sivakumar. "A sieve algorithm for the shortest lattice vector problem" (STOC 2001)
    • 2^{O(n)}時間の近似アルゴリズム.
  • 2002. M. Ajtai, R. Kumar, D. Sivakumar. "Sampling Short Lattice Vectors and the Closest Lattice Vector Problem" (CCC 2002)
    • Ajtai, Kumar, Sivakumar 2001への2^{O(n)}時間での帰着.
    • 結果, 2^{O(n)}時間のランダムな近似アルゴリズムが得られる.
  • 2003. R. Kumar, D. Sivakumar. "On Polynomial-Factor Approximations to the Shortest Lattice Vector Length" (SIAM Journal on Discrete Mathematics 16(3) 2003)
    •  2^{O(n(1/2+1/\epsilon))}時間で近似度n^{3+\epsilon}のランダムなアルゴリズム

1970- Cryptography (応用方面?)

現代暗号史_格子

1970- Average-case/Worst-case

現代暗号史_格子. 一方向性関数やハッシュ関数扱いにしてるので.

1930- Transference Theorem

\lambda_i(L) \lambda_{n-i+1}(L^{*})について

  • 1939. K. Mahler. "Ein Übertragungsprinzip für konvexe Körper"
    • 全ての格子について(n!)^2で抑える.
  • 1959. J. W. S. Cassels. "An Introduction to the Geometry of Numbers" (単行本)
    • 全ての格子についてn!で抑える.
  • 1990. J. C. Lagarias, H. W. Lenstra, C. P. Schnorr. "Korkin-Zolotarev Bases and Successive Minima of a Lattice and its Reciprocal Lattice"
    • 全ての格子について cn^2 (n ≧ 6)だったかな(?)
  • 1993. W. Banaszczyk. "New Bounds in Some Transference Theorems in the Geometry of Numbers"
    • 全ての格子について Cnで抑える.
    • このLemma 1.5が計算機関係で良く引かれ, Gauss分布を利用したテクニックが広まる. フーリエ変換偉い.
  • 1998. Jin-Yi Cai. "A new transference theorem and applications to Ajtai's connection factor"
    • 上のBanaszczykの結果の拡張. 一次独立なベクトルではなく, 基底を重視した格子定数を使っている.
    • 最短ベクトルがuniqueな場合の考察もしている.

その他

  • W. Yu, D. He, Y. Zheng "Constructing SVK_Lattices from Cyclic Bases" (PDCAT 2005)
    • 格子とその最短ベクトルをセットで作る話
    • 基底がcyclicな格子だったら, 基底に制限を付けることでランダム生成も出来るのではないか?
    • 2次元はあってるけど, n次元でもあっているのか? 確認する.

参考文献

  • 1999. J.-Y. Cai. "Some Recent Progress on the Complexity of Lattice Problems" (ECCCTR99-6, IEEE Conference on Computational Complexity 1999)
    • 計算量的な観点からの切り込み. Ajtaiの論文より分かり易くてお勧め.
  • 2000. P. Q. Nguyen, J. Stern. "Lattice Reduction in Cryptology: An Update" (ANTS 2000)
  • 2001. P. Q. Nguyen. "The Two Faces of Lattices in Cryptology" (SAC 2001)
  • 2001. P. Q. Nguyen, J. Stern. "The Two Faces of Lattices in Cryptology" (CaLC 2001)
    • この3つは暗号との関わりをメインに扱っている. LLLの使い方などにも触れてある.
  • 2006. O. Regev, R. Rosen. "Lattice Problems and Norm Embeddings" (STOC 2006)
    • Complexityと近似度について, 近年の結果について纏まっている.