格子暗号

1996年にミクロス・Ajtaiは、良く知られた格子問題の困難性を利用した最初の格子暗号の構成を示した[1]。 シンシア・ドワークは、短整数解問題 (SIS) と呼ばれる格子問題の平均時の計算困難性が、ある格子問題の最悪時の計算困難性と同等かそれ以上であることを示した[2]。そして、SIS問題の計算困難性と等価な安全性を持つハッシュ関数を示した。

1998年に、Jeffrey Hoffstein、Jill Pipher、Joseph H. Silvermanの3人は、NTRU暗号と呼ばれる格子ベースの公開鍵暗号方式を提案した[3]。 しかし、彼らの方式は、最悪時の格子問題を解くことと等価 (あるいはそれ以上) な安全性を持つかどうかは知られていない。最悪時の計算量的困難性の仮定の下で安全性が証明された最初の方式は、2005年にOded Regevによって提案されている[4]。この論文では、計算困難な問題としてLWE問題 (Learning with Errors問題) も提案されている。それ以降、多くの後続研究がRegevの安全性証明を改善したり[5][6] 、方式の効率を改善している [7][8][9][10]。 さらに多くの研究が、LWE問題や関連した問題を元にして、暗号プリミティブを構築することに専念してきた。例えば、2009年にGentryは初めての 完全準同型暗号方式を提案したが、これは格子問題に基づいている[11]。

格子 ${\displaystyle L\subset \mathbb {R} ^{n}}$ とは、基底ベクトル${\displaystyle \mathbf {b} _{1},\ldots ,\mathbf {b} _{n}\in \mathbb {R} ^{n}}$の整数線形結合で表現できる全てのベクトルから成る集合である。つまり、${\displaystyle L={\Big \{}\sum a_{i}\mathbf {b} _{i}\$ :\ a_{i}\in \mathbb {Z} {\Big \}}} である。例えば${\displaystyle \mathbb {Z} ^{n}}$ は、普通の直交基底${\displaystyle \mathbb {R} ^{n}}$から生成される格子である。重要なのは、異なる基底が同一の格子を生成しうるということである。たとえば、直交基底 ${\displaystyle (1,0,0)}$、${\displaystyle (0,1,0)}$、${\displaystyle (0,0,1)}$から${\displaystyle \mathbb {Z} ^{3}}$が生成されるが，${\displaystyle (3,1,4)}$、${\displaystyle (1,5,9)}$、${\displaystyle (2,-1,0)}$も同じ格子を生成する別の基底である。

格子を用いた計算量的な問題で最も重要なものは最短ベクトル問題 (SVP，あるいはGapSVP) であり、これは、格子内の非ゼロのベクトルのうち最短のベクトルを求めよ、という問題である。この問題は、近似解 (最短ベクトル長の高々${\displaystyle n}$の多項式倍の長さのベクトル) であっても、効率的に見つけられないと考えられており、さらには量子コンピュータを使ったとしても難しいと考えられている。多くの格子ベース暗号では、SVPを解くのが実際に難しいならば、暗号が破られないことが保障されている。

格子暗号は、耐量子公開鍵暗号の主力候補である[20]。現在の主な公開鍵暗号方式は、素因数分解問題 (あるいはRSA問題) と離散対数問題 (あるいはDiffie-Hellman問題) の困難性に基づく方式である。しかし、素因数分解も離散対数問題も、量子コンピュータを用いると多項式時間で解けることが知られている[21]。また、素因数分解アルゴリズムから離散対数を求めるアルゴリズムが作られたり、逆に離散対数のアルゴリズムが素因数分解に利用される傾向がある。つまり、これらのどちらかを効率的に解く方法が (量子コンピュータ以外の方法で) 見つかった時には、他方も解けてしまう恐れがある。この事実が、格子問題のような、素因数分解と離散対数問題以外の困難性仮定に基づく暗号方式を研究する動機となっている。

多くの格子ベース暗号は、ある格子問題の最悪時の困難性を仮定して、安全性が示されている[1][4][5]。つまり、もしその暗号方式を無視できない確率で破る効率的なアルゴリズムが存在したとすれば、格子問題にどんな入力が与えられたとしても効率的に解いてしまうようなアルゴリズムが作れる。これに対して，例えば素因数分解問題に基づく暗号方式の場合は、平均時の困難性を仮定して安全性が示されている。したがって、最悪の入力の素因数分解が困難であったとしても、平均的な入力の素因数分解が簡単である場合には、暗号が破られてしまうかもしれない。とはいえ、効率が良く実用的な格子暗号 (NTRUに基づく方式や、よりaggressiveなパラメータを用いたLWEに基づく方式など) では、最悪ケースの困難性に基づく結果は知られていない。いくつかの方式では、最悪時の困難性に対する安全性は全く知られていないか、structured lattices によるものだけが知られている[7]。

暗号プリミティブによっては、今のところ格子 (やそれに密接に関係したもの) に基づいた方式しか知られていないというものも多い。例えば、完全準同型暗号[11]や識別不可能性を持つ難読化[22] cryptographic multilinear maps、関数暗号[22]などである。

1. Ajtai, Miklos (1996). “Generating Hard Instances of Lattice Problems”. Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing. pp. 99?108. doi:10.1145/237814.237838. ISBN 978-0-89791-785-8
2. Public-Key Cryptosystem with Worst-Case/Average-Case Equivalence
3. Hoffstein, Jeffrey; Pipher, Jill; Silverman, Joseph H. (1998). “NTRU: A ring-based public key cryptosystem”. Algorithmic Number Theory. Lecture Notes in Computer Science. 1423. pp. 267?288. doi:10.1007/bfb0054868. ISBN 978-3-540-64657-0
4. Regev, Oded (2005-01-01). “On lattices, learning with errors, random linear codes, and cryptography”. Proceedings of the thirty-seventh annual ACM symposium on Theory of computing - STOC '05. ACM. pp. 84?93. doi:10.1145/1060590.1060603. ISBN 978-1581139600
5. Peikert, Chris (2009-01-01). “Public-key cryptosystems from the worst-case shortest vector problem”. Proceedings of the 41st annual ACM symposium on Symposium on theory of computing - STOC '09. ACM. pp. 333?342. doi:10.1145/1536414.1536461. ISBN 9781605585062
6. Brakerski, Zvika; Langlois, Adeline; Peikert, Chris; Regev, Oded; Stehle, Damien (2013-01-01). “Classical hardness of learning with errors”. Proceedings of the 45th annual ACM symposium on Symposium on theory of computing - STOC '13. ACM. pp. 575?584. arXiv:1306.0281. doi:10.1145/2488608.2488680. ISBN 9781450320290
7. Lyubashevsky, Vadim; Peikert, Chris; Regev, Oded (2010-05-30) (英語). On Ideal Lattices and Learning with Errors over Rings. Lecture Notes in Computer Science. 6110. 1?23. doi:10.1007/978-3-642-13190-5_1. ISBN 978-3-642-13189-9
8. Peikert, Chris (2014年7月16日). “Lattice Cryptography for the Internet”. IACR. 2017年1月11日閲覧。
9. Alkim, Erdem; Ducas, Leo; Poppelmann, Thomas; Schwabe, Peter (2015-01-01). Post-quantum key exchange - a new hope. http://eprint.iacr.org/2015/1092.
10. Bos, Joppe; Costello, Craig; Ducas, Leo; Mironov, Ilya; Naehrig, Michael; Nikolaenko, Valeria; Raghunathan, Ananth; Stebila, Douglas (2016-01-01). Frodo: Take off the ring! Practical, Quantum-Secure Key Exchange from LWE. http://eprint.iacr.org/2016/659.
11. Gentry, Craig (1 January 2009). A Fully Homomorphic Encryption Scheme (Thesis). Stanford, CA, USA: Stanford University.
12. “IBMの研究者、NISTの耐量子標準の開発を支援へ | Think Blog Japan”. IBM. 2022年10月24日閲覧。
13. Peter Schwabe. “Kyber”. 2022年10月24日閲覧。
14. Guneysu, Tim; Lyubashevsky, Vadim; Poppelmann, Thomas (2012). “Practical Lattice-Based Cryptography: A Signature Scheme for Embedded Systems”. Cryptographic Hardware and Embedded Systems ? CHES 2012. Lecture Notes in Computer Science. 7428. IACR. pp. 530?547. doi:10.1007/978-3-642-33027-8_31. ISBN 978-3-642-33026-1. https://www.iacr.org/archive/ches2012/74280529/74280529.pdf 2017年1月11日閲覧。
15. Peter Schwabe. “Dilithium”. 2022年10月24日閲覧。
16. “LASH: A Lattice Based Hash Function”. 2008年10月16日時点のオリジナルよりアーカイブ。2008年7月31日閲覧。 (broken)
17. Scott Contini, Krystian Matusiewicz, Josef Pieprzyk, Ron Steinfeld, Jian Guo, San Ling and Huaxiong Wang (2008). “Cryptanalysis of LASH”. Fast Software Encryption. Lecture Notes in Computer Science. 5086. pp. 207-223. doi:10.1007/978-3-540-71039-4_13. ISBN 978-3-540-71038-7. https://eprint.iacr.org/2007/430.pdf
18. Brakerski, Zvika; Vaikuntanathan, Vinod (2011). Efficient Fully Homomorphic Encryption from (Standard) LWE. https://eprint.iacr.org/2011/344.
19. Brakerski, Zvika; Vaikuntanathan, Vinod (2013). Lattice-Based FHE as Secure as PKE. https://eprint.iacr.org/2013/541.
20. Micciancio, Daniele; Regev, Oded (2008-07-22). Lattice-based cryptography. https://www.cims.nyu.edu/~regev/papers/pqc.pdf 2017年1月11日閲覧。.
21. Shor, Peter W. (1997-10-01). “Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer”. SIAM Journal on Computing 26 (5): 1484?1509. arXiv:quant-ph/9508027. doi:10.1137/S0097539795293172. ISSN 0097-5397.
22. Garg, Sanjam; Gentry, Craig; Halevi, Shai; Raykova, Mariana; Sahai, Amit; Waters, Brent (2013-01-01). Candidate Indistinguishability Obfuscation and Functional Encryption for all circuits. https://eprint.iacr.org/2013/451.

• Oded Goldreich, Shafi Goldwasser, and Shai Halevi. "Public-key cryptosystems from lattice reduction problems". In CRYPTO ’97: Proceedings of the 17th Annual International Cryptology Conference on Advances in Cryptology, pages 112-131, London, UK, 1997. Springer-Verlag.
• Phong Q. Nguyen. "Cryptanalysis of the Goldreich-Goldwasser-Halevi cryptosystem from crypto ’97". In CRYPTO ’99: Proceedings of the 19th Annual International Cryptology Conference on Advances in Cryptology, pages 288-304, London, UK, 1999. Springer-Verlag.
• Oded Regev. Lattice-based cryptography. In Advances in cryptology (CRYPTO), pages 131-141, 2006.