現代暗号史_格子

現代暗号史_格子

公開鍵暗号 (with w/a reductions)

  • 1996. M. Ajtai, C. Dwork. “A public-key cryptosystem with worst-case/average-case equivalence.” (STOC 1997, ECCC 1996)
    • O(n^{8})-uSVPに基づいた公開鍵暗号. w/aあり.
  • 1997. O. Goldreich, S. Goldwasser, and S. Halevi. “Eliminating decryption errors in the Ajtai-Dwork cryptosystem.” (CRYPTO 1997, ECCC 1997)
    • AD暗号をエラーレスにする方法.
  • 1998. P. Nguyen and J. Stern. “A Converse to the Ajtai-Dwork Security Proof and its Cryptographic Implications.” (ECCC TR98-010)
  • 1998. P. Nguyen and J. Stern. “Cryptanalysis of the Ajtai-Dwork Cryptosystem.” (CRYPTO 1998)
    • AD暗号に対するアタック.
    • n=32まではLLLで解けるらしい.
    • 一般のnについても, 近似度cn^{4/3}のCVPオラクルがあればdistinguishできる. SVPオラクルの近似度は(忘れた)
  • 1999. C. Hall, I. Goldberg, and B. Schneier. “Reaction Attacks Against Several Public-Key Cryptosystems.” (ICICS 1999)
    • AD暗号に対するCCA1アタックの例が載っている.
  • 2003. O. Regev. “New Lattice Based Cryptographic Constructions.” (STOC 2003, J. of ACM 2004)
    • n^{1.5}-uSVPに基づいた公開鍵暗号. w/aあり.
  • 2005. Goldwasser, Kharchenko. “Proof of Plaintext Knowledge for the Ajtai-Dwork Cryptosystem.” (TCC 2005)
    • AD暗号のPPK. Nguyen and Sternを使ってGapCVPに落とし込む. のちMicciancio and VadhanのGavCVP用のHVSZKを使う.
  • 2005. M. Ajtai. “Representing hard lattices with O(n \log n) bits.” (STOC 2005)
    • Diophantus近似に基づいた公開鍵暗号. 帰着はw/aでは無い.
  • 2005. O. Regev. “On Lattices, Learnin with Errors, Random Linear Codes, and Cryptography.” (STOC 2005)
    • 近似度\tilde{O}(n^{1.5})SVPに基づいた公開鍵暗号. w/aあり. しかしquantum帰着が必要.
  • 2007. A. Kawachi, K. Tanaka, K. Xagawa. “A Lattice-Based Cryptosystem and Proof of Knowledge on Its Secret Key.” (SCIS 2007)
    • Regev05暗号を改変して知識証明と署名に乗せる話.
  • 2007. A. Kawachi, K. Tanaka, K. Xagawa. “Proof of Plaintext Knowledge for the Regev Cryptosystems.” (SCIS 2007)
    • Regev04暗号とRegev05暗号に平文知識証明を作る話. Goldwasser and Kharchenko (2005)の応用.
  • 2007. A. Kawachi, K. Tanaka, K. Xagawa. “Multi-Bit Public-Key Cryptosystems Based on Lattice Problems.” (SCIS 2006, PKC 2007)
    • Ajtai-Dwork暗号, Regev04暗号, Regev05暗号, Ajtai05暗号を複数ビット化する話. ただし, O(log n)ビットまで.
  • 2007. C. Peikert, B. Waters. “Lossy Trapdoor Functions and Their Applications.” (ePrint 2007/279)
    • Regev05暗号を元に色々. IND-CCA2 w/o RO (!).
  • 2007. C. Peikert, V. Vaikuntanathan, B. Waters. “A Framework for Efficient and Composable Oblivious Transfer.” (ePrint 2007/348, STOC 2008)
    • Regev05暗号の簡単な拡張. ただし証明をし直す必要があるのでそこそこ大変そう.
  • 2007. M. Ajtai, C. Dwork. “The First and Fourth Public-Key Cryptosystems with Worst-Case/Average-Case Equivalence.” (ECCC TR07-097)
    • AD96の拡張と安全性評価の改良.

公開鍵暗号 (without w/a reductions)

GGH暗号

  • 1997. O. Goldreich, S. Goldwasser, and S. Halevi. “Public-key cryptosystem from lattice reduction problems.” (CRYPTO 1997, ECCC 1997?)
    • CVPベース. 安全性の証明がない. McEliece暗号の格子版と見ても良い(らしい)
  • 1999, Phong Q. Nguyen. “Cryptanalysis of the Goldreich-Goldwasser-Halevi Cryptosystem from Crypto '97.” (CRYPTO 1999)
    • オリジナルのGGH暗号に対するアタック.
  • 2001. D. Micciancio. “Improving Lattice Based Cryptosystems Using the Hermite Normal Form.” (CaLC 2001)
    • HNFを使うテクニックで公開鍵のサイズを小さくしました.
    • オリジナルのGGH暗号へ帰着.
  • 2003. S.-H. Paeng, B. E. Jung, K.-C. Ha. “A Lattice Based Public Key Cryptosystem Using Polynomial Representations.” (PKC 2003)
    • 多項式を使ってGGHの格子を表現すれば良いんじゃないの案.
    • 秘密鍵はそれでいいけど, 公開鍵はどうなんだっけ. 忘れた.
  • 2007. D. Han, M.-H. Kim, Y. Yeom. “Cryptanalysis of the Paeng-Jung-Ha Cryptosystem from PKC 2003.” (PKC 2007)
    • PJHの性質をフルに活用してLLLでアタック. 実験した結果, 1000次元でも戻せる.

NTRU暗号

  • 1998. J. Hoffstein, J. Pipher, J. H. Silverman. “NTRU: A Ring-Based Public Key Cryptosystem.” (ANTS-III)
  • 色々ある.
パディング
  • 2003. N. Howgrave-Graham, P. Q. Nguyen, D. Pointcheval, J. A. Proos, J. H. Silverman, A. Singer, W. Whyte. “The Impact of Decryption Failures on the Security of NTRU Encryption.” (Crypto 2003)
攻撃
  • 1997. D. Coppersmith, A. Shamir. “Lattice attacks on NTRU.” (Eurocrypt 1997)
    • NTRU Latticeへの帰着だったか.
  • 2000. E. Jaulmes, A. Joux. “A Chosen-Ciphertext Attack against NTRU.” (CRYPTO 2000)
    • 読んでない.
  • 2002. P. Q. Nguyen, D. Pointcheval. “Analysis and Improvements of NTRU Encryption Paddings.” (CRYPTO 2002)
  • 2003. N. Howgrave-Graham, P. Q. Nguyen, D. Pointcheval, J. A. Proos, J. H. Silverman, A. Singer, W. Whyte. “The Impact of Decryption Failures on the Security of NTRU Encryption.” (Crypto 2003)
  • 2003. D. Han, J. Hong, J. W. Han, D. Kwon. “Key Recovery Attacks on NTRU without Ciphertext Validation Routine.” (ACISP 2003)
    • 読んでない.
  • 2004. T. E. Seidel, D. Socek, M. Sramka. “Parallel Symmetric Attack on NTRU using Non-Deterministic Lattice Reduction.” (Designs, Codes and Cryptography. Vol. 32, 2004)
    • LLLやらのアルゴリズムは基底の中でのベクトルの並び順によるので並列化しづらい.
    • 最初にベクトルの並び順を変えた基底をm個作って並列処理して, 一番短いの取る. birotateという関数を使って, local minimunに落ちるのも防ぐ.
    • 実験結果はSocekだったかの修論に載ってたが, 微妙.
  • 2005. W. Yu, D. He, S. Zhu. “Study on NTRU Decryption Failures.” (ICITA 2005)
  • 2006. Symplectic Lattice Reduction and NTRU (Eurocrypt 2006)
    • NTRU Lattice を数学の方の Symplectic Lattice に対応させて, 上手くGram-Schmidt orthgonalization や LLL の速度を上げられました, という話. 攻撃そのものの話はしていない.
  • 2007. J. H. Silverman, W. Whyte. “Timing Attacks on NTRUEncrypt via Variation in the NUmber of Hash Calls.” (CT-RSA 2007)
    • NAEPみたいにハッシュ関数使ってパディングしてある形式だと, 復号時のハッシュ関数の呼び出し回数を調べることで秘密鍵を求められるという話(らしい).
  • 2007. N. Gama, P. Q. Nguyen. “New Chosen-Ciphertext Attacks on NTRU.” (PKC 2007)
  • 2008. P. Mol and M. Yung, “Recovering NTRU Secret Key From Inversion Oracles.” (PKC 2008)
改変・改良
  • 2002. W. D. Banks, I. Shparlinski. “A Variant of NTRU with Non-invertible Polynomials.” (INDOCRYPT 2002)
  • 2003. C. O'Rourke, B. Sunar. “Achieving NTRU with Montgomery Multiplication.” (IEEE Trans. Computers 52(4), 2003)
  • 2004. J. H. Silverman, N. P. Smart, F. Vercauteren. “An Algebraic Approach to NTRU (q=2n) via Witt Vectors and Overdetermined Systems of Nonlinear Equations. (SCN 2004)
  • 2005. M. Coglianese, B.-M. Goi. “MaTRU: A New NTRU-Based Cryptosystem.” (INDCRYPT 2005)
    • 行列を使うらしい.
  • 2005. X. Lv, B. Yang, C. Pei. “Efficient Traitor Tracing Scheme Based on NTRU.” (PDCAT 2005).
  • 2005. M. Stam. “A Key Encapsulation Mechanism for NTRU.” (WCC 2005)
    • 詳細不明. そもそもここで良いのか?
そのほか
  • 2003. M. Naslund, I. Shparlinski, W. Whyte. “On the Bit Security of NTRUEncrypt.” (PKC 2003)
実装?
  • 2001. D. V. Bailey, D. Coffin, A. J. Elbirt, J. H. Silverman, A. D. Woodbury. “NTRU in Constrained Devices.” (CHES 2001)
    • 読んでない.

Cai-Cusick暗号

  • 1998. J-Y. Cai, T. Cusick. “A Lattice-Based Public-Key Cryptosystem.” (SAC 1998, Inf. Comput. Vol.151(1999))
    • AD暗号+Knapsack. 安全性証明無し.

符号ベース

  • 1999. R. Fischlin, J.-P. Seifert. “Tensor-based Trapdoors for CVP and their Application to Public Key Cryptography.” (WCC 1999)
    • 符号ベース. どうだろうね.

認証および署名

一般の格子

  • 2007. C. Gentry, C. Peikert, V. Vaikuntanathan. “Trapdoors for Hard Lattices and New Cryptographic Constructions.” (ePrint 2007/432)
    • ROMでsEUF-CMAな格子ベースの署名! Ajtai99の短い基底が秘密鍵.

イデアル格子

  • 2007. V. Lyubashevsky, D. Micciancio. “Asymptotically efficient lattice-based digital signatures.” (TCC 2008)
    • LMハッシュの考えを用いて, 効率の良い使い捨て署名を構成.
  • 2008. K. Xagawa, K. Tanaka. “イデアル格子問題に基づくコンパクトな署名方式.” (SCIS 2008)

GGH系

  • 1997. O. Goldreich, S. Goldwasser, S. Halevi. “Public-key cryptosystem from lattice reduction problems.” (CRYPTO 1997)
    • CVPベース. 安全性の証明がない.
  • 2006. P. Q. Nguyen, O. Regev. “Learning a Parallelepiped: Cryptanalysis of GGH and NTRU Signatures.” (EuroCrypt 2006)
    • その名の通り, GGHとNTRU署名に対するアタック.
    • 署名のサンプルを集めて秘密鍵の格子の基本領域を再現しましょう, という話.
  • 2007. T. Plantard, W. Susilo, K. T. Win. “A Digital Signature Scheme based on CVP_{\infty}.” (PKC 2008)
    • GGHをノルムを変えて考えてみた. Nguyen and Regevの攻撃には耐えられそう?

NTRU系

  • NSS
    • 2001. J. Hoffstein, J. Pipher, J. H. Silverman. “NSS: An NTRU lattice-based signature scheme.” (Eurocrypt 2001)
    • 2001. C. Gentry, J. Jonsson, J. Stern, M. Szydlo. “Cryptoanalysis of the NTRU signature scheme (NSS) from Eurocrypt 2001.” (Asiacrypt 2001)
    • 2002. C. Gentry, M. Szydlo. “Cryptoanalysis of the revised NTRU signature scheme.” (Eurocrypt 2002)
  • NTRUSign.
    • 2003. J. Hoffstein, N. A. Howgrave-Graham, J. Pipher, J. H. Silverman, W. Whyte. “NTRUSIGN: Digital signature using the NTRU lattice.” (CT-RSA 2003)
    • 2003. K. Geisler, N. P. Smart. “Computing the M=U U^t Integer Matrix Decomposition.” (WCC 2003)
    • 2006. P. Q. Nguyen, O. Regev. “Learning a Parallelepiped: Cryptanalysis of GGH and NTRU Signatures.” (EuroCrypt 2006)
      • その名の通り, GGHとNTRU署名に対するアタック.
      • 署名のサンプルを集めて秘密鍵の格子の基本領域を再現しましょう, という話.

その他

  • 2003. D. Micciancio, S. Vadhan (CRYPTO 2003)
    • GapSVPとGapCVPのSZKを構成. 上手く使うと認証方式が出来る.
  • 2008. V. Lyubashevsky. “Lattice-based identification schemes secure under active attacks.” (PKC 2008)
    • 2-sided errorにすることによって上手く認証方式を構成.
  • 2008. K. Xagawa, A. Kawachi, K. Tanaka. “格子問題に基づく高い安全性をもつ認証方式.” (SICS 2008)
    • Stern認証方式を使う.

一方向性関数とハッシュ関数

一般の格子

  • 1996. M. Ajtai. “Generating Hard Instances of Lattice Problems.” (ECCC 1996, STOC 1996)
    • Worst-case/Average-case connectionが言える一方向性関数の構成.
  • 1996. O. Goldreich, S. Goldwasser, S. Halevi. “Collision-Free Hashing from Lattice Problems.” (ECCC 1996)
    • Ajtaiの一方向性関数の構成からCollision-resistantなハッシュ関数族が作れるよという話.
  • 1999. J.-Y. Cai. “A new transference theorem in the geometry of numbers and new bounds for Ajtai's connection factor.” (CCC 1999, Discrete Applied Mathematics 2003)
    • n^8という数字はここから?
  • 2002, D. Micciancio. “Improved cryptographic hash functions with worst-case/average-case connetion.” (STOC 2002, CCC 2002)
    • 近似度を縮める話. 近似度忘れた.
  • 2002, D. Micciancio. “Almost perfect lattices, the covering radius problem, and applications to Ajtai's connection factor.” (STOC 2002, ECCC 2003, SIAM J. on Comp. 2004)
    • 近似度は\tilde{O}(n^{2.5})から\tilde{O}(n^3)くらい.
  • 2004. D. Micciancio, O. Regev. “Worst-case to Average-case Reduction based on Gaussian Measures.” (FOCS 2004, SIAM J. of Comp.)
    • 近似度\tilde{O}(n)のSVP, SIVP, Covering radius, GDD.
    • smoothing parameterという格子にのみ依存する定数の導入. ガウス分布を使い帰着効率を高める. ガウス分布はAharonov, Regevから.
  • 2007. C. Peikert. “Limits on the Hardness of Lattice Problems in l_p Norms.” (CCC 2007, ECCC 2007)
    • ガウス分布をl_p normで考えるんだったか. Banaczyckのもう一つの結果から導くらしい.

特殊な格子

Cyclic LatticeとIdeal Lattice

多項式とベクトル.

  • 2002. D. Micciancio. “Generalized Compact Knapsacks, Cyclic Lattices, and Efficient One-Way Functions from Worst-Case Complexity Assumptions.” (FOCS 2002)
    • Cyclic Lattice上でのO(n^3)-SVPがベースでOne-way functionを作る話.
  • 2006. C. Peikert, A. Rosen. “Efficient collision-resistant hashing from worst-case assumptions on cyclic lattices.” (TCC 2006)
    • Miccaincio (FOCS 2002)の改良. Universal one-wayになっていないことを示し, 結果Collision-resistantじゃないことを言っている. 定義域を上手く調節するとCollision-resistantになって, 更に効率がよくなることを言っている.
  • 2006. V. Lyubashevsky, D. Micciancio. “Generalized Compact Knapsacks are Collision Resistant.” (ICALP 2006, ECCC 2005)
    • Micciancio (FOCS 2002)の改良. Collision-resistantじゃないことをApp. Aで言っている. 元々は環の上で関数を考えていたけどそれを体にすればCollision-resistantになったよという話. 代数的な構造に着目して話を進めているので読み易いといえば読み易いが. Peikert and Rosenに比べると面倒臭い.
  • 2004, 2006. D. Micciancio. “Generalized compact knapsacks, cyclic lattices, and efficient one-way functions from worst-case complexity assumptions.” (Computational Complexity. To Appear)
    • 2006/03版出た. Micciancio (FOCS 2002)のFull Paper. Micciancio and Regev (FOCS 2004)で使われたガウス分布を用いるテクニックを使って改良してある.
  • 2006. V. Lybashevsky, D. Micciancio, C. Peikert, A. Rosen. “Provable secure FFT hashing.” (NIST 2nd Hash Workshop)
    • Peikert and RosenとLybashevsky and Micciancioの混合. 格子ベースでないものも提案している.
  • 2006. K. Bentahar, D. Page, M.-J. O. Saarinen, J. H. Silverman, N. Smart. “LASH.” (NIST 2nd Hash Workshop?)
    • Regev and Micciancioを使って具体的にパラメータを設定してみた論文か? ベースがAjtai-GGHになってるのは何でだろ. 疑似乱数生成器を使ってランダムな格子を設定.
    • 2007. S. Contini, K. Matusiewicz, J. Pieprzyk, R. Steinfeld, J. Guo, S. Ling, H. Wang. “Cryptanalysis of LASH.” (ePrint 2007/430)
      • LASHに対する攻撃. 衝突一歩手前までの実例あり.
  • 2007. C. Peikert, A. Rosen. “.” (STOC 2007, ECCC 2007)
    • 代数体のイデアルと同型な格子だと近似度が\tilde{O}(\log n)でいけるとか.
    • ただ元の格子のGapSVPはPに入るとか.

ELVP

おもに千葉大の林・多田さんがやっているらしい.

実装

LASH
  • 2007. K. Bentahar, D. Page, M.-J.- O. Saarinen, J. H. Silverman, N. Smart. “LASH.” (NIST Second Cryptographic Hash Workshop)
  • 2008. S. Contini, K. Matusiewicz, J. Pieprzyk, R. Steinfeld, G. Jian, L. San, H. Wang. “Cryptanalysis of LASH.” (FSE 2008)
Lattice-based FFT Hashing
  • 2007. V. Lyubashevsky, D. Micciancio, C. Peikert, A. Rosen “Provably Secure FFT Hashing.” (NIST Second Cryptographic Hash Workshop)
  • 2008. V. Lyubashevsky, D. Micciancio, C. Peikert, A. Rosen “SWIFFT: A Modest Proposal for FFT Hashing.” (FSE 2008)

その他

OT

  • 2007. C. Peikert, V. Vaikuntanathan, B. Waters. “A Framework for Efficient and Composable Oblivious Transfer.” (ePrint 2007/348, CRYPTO 2008?)
    • UCOTらしい.
  • 2007. C. Gentry, C. Peikert, V. Vaikuntanathan. “Trapdoors for Hard Lattices and New Cryptographic Constructions.” (ePrint 2007/432, STOC 2008)
    • UCOTとIBEの構成 (IBEはRegev05に似た暗号を考えてそこから作る. QRベースの1ビットIBEと似ている.)

PIR

  • 2007. C. Aguilar Melchor, P. Gaborit. “A Lattice-Based Computationally-Efficient Private Information Retrieval Protocol.” (Cryptology ePrint Archive: Report 2007/446)
    • NTRUぽい感じ? Hidden Lattice Problemというのを考えているらしい.

NISZK

  • 2008. C. Peikert, V. Vaikuntanathan. “ ” (CRYPTO 2008)
    • NISZK. GPV08のアイデアで理解できる.