格子暗号のソースを表示

'''格子暗号''' (あるいは格子ベース暗号) とは、方式自体あるいは安全性証明において[[格子 (数学)|格子]]を用いる[[暗号プリミティブ]]を示す一般的用語である。格子ベースの暗号方式 (公開鍵暗号方式や鍵共有方式) は現在、{{仮リンク|耐量子暗号|en|Post-quantum cryptography}}の重要な候補となっている。広く利用されている公開鍵方式である [[RSA暗号|RSA]]や [[楕円曲線暗号]]、[[ディフィー・ヘルマン鍵共有]]は、[[量子コンピュータ]]上で実行できる[[ショアのアルゴリズム]]によって破られるが、いくつかの格子暗号は古典コンピュータと量子コンピュータの両方に対して攻撃耐性があると考えられている。さらに、多くの格子ベースの方式は、良く研究されている何らかの{{仮リンク|格子問題|en|Lattice problem}} (格子に関連した問題) が効率的に解けないという計算量的な仮定のもとで、安全であると考えられている。

==歴史==
1996年に{{仮リンク|ミクロス・Ajtai|en|Miklos Ajtai}}は、良く知られた格子問題の困難性を利用した最初の格子暗号の構成を示した<ref name=":1">{{Cite book
| first = Miklos
| last = Ajtai
| year = 1996
| chapter = Generating Hard Instances of Lattice Problems
| title = Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing
| pages = 99?108
| publisher =
| doi = 10.1145/237814.237838
| isbn = 978-0-89791-785-8| citeseerx = 10.1.1.40.2489
}}</ref>。
{{仮リンク|シンシア・ドワーク|en|Cynthia Dwork}}は、{{仮リンク|短整数解問題|en|Short Integer Solutions}} (SIS) と呼ばれる格子問題の平均時の計算困難性が、ある格子問題の最悪時の計算困難性と同等かそれ以上であることを示した<ref>[https://eccc.weizmann.ac.il/report/1996/065/ Public-Key Cryptosystem with Worst-Case/Average-Case Equivalence]</ref>。そして、SIS問題の計算困難性と等価な安全性を持つ[[暗号学的ハッシュ関数|ハッシュ関数]]を示した。

1998年に、Jeffrey Hoffstein、Jill Pipher、Joseph H. Silvermanの3人は、[[NTRU暗号]]と呼ばれる格子ベースの[[公開鍵暗号方式]]を提案した<ref>{{Cite book|last=Hoffstein|first=Jeffrey|last2=Pipher|first2=Jill|last3=Silverman|first3=Joseph H. |
doi=10.1007/bfb0054868|series=Lecture Notes in Computer Science|isbn=978-3-540-64657-0|citeseerx=10.1.1.25.8422|
chapter=NTRU: A ring-based public key cryptosystem|title=Algorithmic Number Theory|
volume=1423|pages=267?288|year=1998}}</ref>。
しかし、彼らの方式は、最悪時の格子問題を解くことと等価 (あるいはそれ以上) な安全性を持つかどうかは知られていない。最悪時の計算量的困難性の仮定の下で安全性が証明された最初の方式は、2005年にOded Regevによって提案されている<ref name=":2">{{Cite book|last=Regev|first=Oded|date=2005-01-01 |publisher=ACM|pages=84?93|doi=10.1145/1060590.1060603|isbn=978-1581139600|citeseerx=10.1.1.110.4776|chapter=On lattices, learning with errors, random linear codes, and cryptography|title=Proceedings of the thirty-seventh annual ACM symposium on Theory of computing - STOC '05}}</ref>。この論文では、計算困難な問題として{{仮リンク|LWE問題|en|Learning with Errors}} (Learning with Errors問題) も提案されている。それ以降、多くの後続研究がRegevの安全性証明を改善したり<ref name=":3">{{Cite book|last=Peikert|first=Chris|date=2009-01-01 |publisher=ACM|pages=333?342|doi=10.1145/1536414.1536461|isbn=9781605585062|citeseerx=10.1.1.168.270|chapter=Public-key cryptosystems from the worst-case shortest vector problem|title=Proceedings of the 41st annual ACM symposium on Symposium on theory of computing - STOC '09}}
</ref><ref>{{Cite book|last=Brakerski|first=Zvika|last2=Langlois|first2=Adeline|last3=Peikert|first3=Chris|last4=Regev|first4=Oded|last5=Stehle|first5=Damien|date=2013-01-01 |publisher=ACM|pages=575?584|doi=10.1145/2488608.2488680|isbn=9781450320290|arxiv=1306.0281|chapter=Classical hardness of learning with errors|title=Proceedings of the 45th annual ACM symposium on Symposium on theory of computing - STOC '13}}</ref> 
、方式の効率を改善している
<ref name=":4">{{Cite book|last=Lyubashevsky|first=Vadim|last2=Peikert|first2=Chris|last3=Regev|first3=Oded|date=2010-05-30|title=On Ideal Lattices and Learning with Errors over Rings|journal=Advances in Cryptology ? EUROCRYPT 2010|volume=6110|language=en|pages=1?23|doi=10.1007/978-3-642-13190-5_1|series=Lecture Notes in Computer Science|isbn=978-3-642-13189-9|citeseerx=10.1.1.352.8218}}
</ref><ref name=":0" /><ref>
{{Cite journal|last=Alkim|first=Erdem|last2=Ducas|first2=Leo|last3=Poppelmann|first3=Thomas|last4=Schwabe|first4=Peter|date=2015-01-01|title=Post-quantum key exchange - a new hope|url=http://eprint.iacr.org/2015/1092}}
</ref><ref>{{Cite journal|last=Bos|first=Joppe|last2=Costello|first2=Craig|last3=Ducas|first3=Leo|last4=Mironov|first4=Ilya|last5=Naehrig|first5=Michael|last6=Nikolaenko|first6=Valeria|last7=Raghunathan|first7=Ananth|last8=Stebila|first8=Douglas|date=2016-01-01|title=Frodo: Take off the ring! Practical, Quantum-Secure Key Exchange from LWE|url=http://eprint.iacr.org/2016/659}}</ref>。
さらに多くの研究が、LWE問題や関連した問題を元にして、暗号プリミティブを構築することに専念してきた。例えば、2009年にGentryは初めての [[準同型暗号|完全準同型暗号]]方式を提案したが、これは格子問題に基づいている<ref name=":5">{{Cite thesis|last=Gentry|first=Craig|title=A Fully Homomorphic Encryption Scheme|date=2009-01-01|publisher=Stanford University|url=http://dl.acm.org/citation.cfm?id=1834954|place=Stanford, CA, USA}}</ref>。提案されたこの暗号方式では、暗号化されたデータは暗号化された状態のままで任意の計算が可能となり、{{仮リンク|イデアル格子|en|Ideal lattice}}を用いGentryによって初めて実現されている<ref>{{Cite book|和書 | author= 岡本龍明 | title=現代暗号の誕生と発展－ポスト量子暗号・仮想通貨・新しい暗号－  | year=2019  | date=2019-1-31 | publisher=株式会社近代科学社 |isbn = 978-4-7649-0579-5 |page=115 }}</ref>。

== 数学的な背景 ==
{{仮リンク|格子問題 (数学)|en|Lattice problem|label=格子}} <math>L \subset \mathbb{R}^n</math> とは、基底ベクトル<math>\mathbf{b}_1,\ldots, \mathbf{b}_n \in \mathbb{R}^n</math>の整数線形結合で表現できる全てのベクトルから成る集合である。つまり、<math>L = \Big\{ \sum a_i \mathbf{b}_i \ : \ a_i \in \mathbb{Z} \Big\}</math>である。例えば<math>\mathbb{Z}^n</math> は、普通の直交基底<math>\mathbb{R}^n</math>から生成される格子である。重要なのは、異なる基底が同一の格子を生成しうるということである。たとえば、直交基底 <math>(1,0,0)</math>、<math>(0,1,0)</math>、<math>(0,0,1)</math>から<math>\mathbb{Z}^3</math>が生成されるが，<math>(3, 1, 4)</math>、<math>(1,5,9)</math>、<math>(2, -1, 0)</math>も同じ格子を生成する別の基底である。

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

==代表的な格子暗号==
===暗号方式===
* [[NTRU暗号]]
* [[Ring learning with errors key exchange|Peikert's Ring - Learning With Errors (Ring-LWE) Key Exchange]]<ref name=":0">{{cite web
| url=https://eprint.iacr.org/2014/070.pdf
| title=Lattice Cryptography for the Internet
| last=Peikert
| first=Chris
| date=2014-07-16
| publisher=[[International Association for Cryptologic Research|IACR]]
| accessdate=2017-01-11}}</ref>
* [[GGH encryption scheme]]
* CRYSTALS-Kyber<ref>{{Cite web|和書|url=https://www.ibm.com/blogs/think/jp-ja/nist-quantum-safe-protocols/ |title=IBMの研究者、NISTの耐量子標準の開発を支援へ {{!}} Think Blog Japan |access-date=2022-10-24 |publisher=IBM}}</ref><ref>{{Cite web |url=https://pq-crystals.org/kyber/ |title=Kyber |access-date=2022-10-24 |author=Peter Schwabe}}</ref>

===署名方式===
* [[NTRU署名]]
* Guneysu, Lyubashevsky, Popplemanによる Ring-LWE署名<ref>{{cite book
| chapter-url=https://www.iacr.org/archive/ches2012/74280529/74280529.pdf
| first1=Tim
| title=Cryptographic Hardware and Embedded Systems ? CHES 2012
| volume=7428
| pages=530?547
| last1=Guneysu
| first2=Vadim
| last2=Lyubashevsky
| first3=Thomas
| last3=Poppelmann
| publisher=IACR
| doi=10.1007/978-3-642-33027-8_31
| accessdate=2017-01-11
| year=2012| series=Lecture Notes in Computer Science
| isbn=978-3-642-33026-1
| chapter=Practical Lattice-Based Cryptography: A Signature Scheme for Embedded Systems
}}</ref>
* [[GGH signature scheme]]
* CRYSTALS-Dilithium<ref>{{Cite web |url=https://pq-crystals.org/dilithium/ |title=Dilithium |access-date=2022-10-24 |author=Peter Schwabe}}</ref>

===ハッシュ関数===
* [[SWIFFT]]
* LASH (Lattice Based Hash Function)<ref>{{cite web|url=http://www.cs.bris.ac.uk/~page/research/lash.html |title=LASH: A Lattice Based Hash Function |accessdate=2008-07-31 |url-status=bot: unknown |archiveurl=https://web.archive.org/web/20081016235719/http://www.cs.bris.ac.uk/~page/research/lash.html |archivedate=October 16, 2008 }} (broken)</ref><ref>{{cite book
| chapter-url=https://eprint.iacr.org/2007/430.pdf
| authors=Scott Contini, Krystian Matusiewicz, Josef Pieprzyk, Ron Steinfeld, Jian Guo, San Ling and Huaxiong Wang
| title=Fast Software Encryption
| volume=5086
| pages=207-223
| year=2008
| doi=10.1007/978-3-540-71039-4_13| series=Lecture Notes in Computer Science
| isbn=978-3-540-71038-7
| chapter=Cryptanalysis of LASH
}}</ref>

===完全準同型暗号===
<!-- {{See also|Fully homomorphic encryption}} -->
*Gentryが最初に提案した完全準同型暗号方式<ref name=":5" />
*BrakerskiとVaikuntanathanによる方式<ref>{{Cite journal|last=Brakerski|first=Zvika|last2=Vaikuntanathan|first2=Vinod|date=2011|title=Efficient Fully Homomorphic Encryption from (Standard) LWE|url=https://eprint.iacr.org/2011/344}}</ref><ref>{{Cite journal|last=Brakerski|first=Zvika|last2=Vaikuntanathan|first2=Vinod|date=2013|title=Lattice-Based FHE as Secure as PKE|url=https://eprint.iacr.org/2013/541}}</ref>

==安全性==
格子暗号は、[[耐量子]][[公開鍵暗号]]の主力候補である<ref>{{cite paper|title=Lattice-based cryptography|first1=Daniele|last1=Micciancio|first2=Oded|last2=Regev|date=2008-07-22|url=https://www.cims.nyu.edu/~regev/papers/pqc.pdf|accessdate=2017-01-11}}</ref>。現在の主な公開鍵暗号方式は、[[素因数分解]]問題 (あるいはRSA問題) と[[離散対数問題]] (あるいは[[Diffie-Hellman問題]]) の困難性に基づく方式である。しかし、素因数分解も離散対数問題も、量子コンピュータを用いると多項式時間で解けることが知られている<ref>{{Cite journal|last=Shor|first=Peter W.|date=1997-10-01|title=Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer|journal=SIAM Journal on Computing|volume=26|issue=5|pages=1484?1509|doi=10.1137/S0097539795293172|issn=0097-5397|arxiv=quant-ph/9508027}}</ref>。また、素因数分解アルゴリズムから離散対数を求めるアルゴリズムが作られたり、逆に離散対数のアルゴリズムが素因数分解に利用される傾向がある。つまり、これらのどちらかを効率的に解く方法が (量子コンピュータ以外の方法で) 見つかった時には、他方も解けてしまう恐れがある。この事実が、格子問題のような、素因数分解と離散対数問題以外の困難性仮定に基づく暗号方式を研究する動機となっている。

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

== 機能 ==
暗号プリミティブによっては、今のところ格子 (やそれに密接に関係したもの) に基づいた方式しか知られていないというものも多い。例えば、[[完全準同型暗号]]<ref name=":5" />や[[indistinguishability obfuscation|識別不可能性を持つ難読化]]<ref name=":6">{{Cite journal|last=Garg|first=Sanjam|last2=Gentry|first2=Craig|last3=Halevi|first3=Shai|last4=Raykova|first4=Mariana|last5=Sahai|first5=Amit|last6=Waters|first6=Brent|date=2013-01-01|title=Candidate Indistinguishability Obfuscation and Functional Encryption for all circuits|url=https://eprint.iacr.org/2013/451|citeseerx=10.1.1.400.6501}}</ref> [[Cryptographic multilinear map|cryptographic multilinear maps]]、[[関数暗号]]<ref name=":6" />などである。
<!-- 情報が古いかもしれない -->

<!--
== 関連項目 ==
* [[格子問題]]
* [[耐量子暗号]]
* [[Learning with errors]]
* [[Ring learning with errors]]
-->

== 脚注 ==
<references/>

== 参考文献 ==
* 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.

{{デフォルトソート:こうしあんこう}}
[[Category:格子暗号|*]]
[[Category:ポスト量子暗号]]
[[Category:暗号]]