ポスト量子暗号のソースを表示

{{翻訳中途|1=[https://en.wikipedia.org/w/index.php?title=Post-quantum_cryptography&oldid=1216419353]|date=2024年4月}}

{{混同|量子暗号|x1=暗号方式に量子重ね合わせを利用する}}

'''ポスト量子暗号''' (ポストりょうしあんごう、{{Lang-en-short|post-quantum cryptography}}、略してPQC)とは、[[量子コンピューティング|量子コンピュータ]]による[[暗号解読]]に対して安全だと考えられる[[暗号]]アルゴリズム (主に[[公開鍵暗号]]アルゴリズム) のことである。'''耐量子暗号'''(たいりょうしあんごう、[[英語|英]]: quantum-resistant cryptography、quantum-proof cryptography、もしくはquantum-safe cryptography)とも呼ばれる。現在よく使われているアルゴリズムの問題は、そのセキュリティーが[[素因数分解]]、[[離散対数]]、[[楕円曲線暗号]]という３つの数学的な難題に依拠していることにある。 これらの問題はすべて、十分に強力な量子コンピュータと[[ショアのアルゴリズム]]<ref name="shor-algorithm">{{Cite journal|last=Shor|first=Peter W.|author-link=Peter W. Shor|year=1997|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|arxiv=quant-ph/9508027|bibcode=1995quant.ph..8027S|doi=10.1137/S0097539795293172}}</ref><ref name="djb-intro">{{Cite book |last=Bernstein |first=Daniel J. |title=Post-Quantum Cryptography |year=2009 |language=en |chapter=Introduction to post-quantum cryptography |author-link=Daniel J. Bernstein |chapter-url=http://www.pqcrypto.org/www.springer.com/cda/content/document/cda_downloaddocument/9783540887010-c1.pdf}}</ref>や、それよりも高速で必要とする量子ビットも少ないアルゴリズム<ref name="renev-algorithm">{{Cite journal|last=Kramer|first=Anna|year=2023|title='Surprising and super cool.' Quantum algorithm offers faster way to hack internet encryption|url=https://www.science.org/content/article/surprising-and-supercool-quantum-algorithm-offers-faster-way-hack-internet-encryption|journal=Science|volume=381|issue=6664|page=1270|doi=10.1126/science.adk9443|pmid=37733849}}</ref>を用いることで容易に解くことができる。

2023年時点では、量子コンピュータの性能は広く用いられている暗号アルゴリズムを破る段階には達していないが<ref>{{Cite web |url=http://phys.org/news/2013-01-qubit-bodes-future-quantum.html |title=New qubit control bodes well for future of quantum computing |website=phys.org}}</ref>、暗号技術者たちは「'''Q-Day'''」(量子コンピュータが現在の暗号アルゴリズムを破ることができるようになる日)に備えて新しいアルゴリズムを開発している。この活動は、2006年から開催されている国際[[学会 (会議)|会議]]PQCrypto、[[欧州電気通信標準化機構]](ETSI)の耐量子暗号に関するワークショップ、{{仮リンク|量子コンピューティング研究所|en|Institute_for_Quantum_Computing}}などを通して大学、産業から関心を集めている<ref>{{Cite magazine2 |date=2009-01-01 |title=Cryptographers Take On Quantum Computers |url=https://spectrum.ieee.org/computing/software/cryptographers-take-on-quantum-computers |magazine=[[IEEE Spectrum]]}}</ref><ref name="ieee-jintai-ding">{{Cite magazine2 |date=2008-11-01 |title=Q&A With Post-Quantum Computing Cryptography Researcher Jintai Ding |url=https://spectrum.ieee.org/computing/networks/qa-with-postquantum-computing-cryptography-researcher-jintai-ding |magazine=[[IEEE Spectrum]]}}</ref><ref>{{Cite web |url=http://www.etsi.org/news-events/events/770-etsi-crypto-workshop-2014?highlight=YTozOntpOjA7czo3OiJxdWFudHVtIjtpOjE7czo0OiJzYWZlIjtpOjI7czoxMjoicXVhbnR1bSBzYWZlIjt9 |title=ETSI Quantum Safe Cryptography Workshop |date=October 2014 |access-date=24 February 2015 |website=ETSI Quantum Safe Cryptography Workshop |publisher=ETSI |archive-url=https://web.archive.org/web/20160817044813/http://www.etsi.org/news-events/events/770-etsi-crypto-workshop-2014?highlight=YTozOntpOjA7czo3OiJxdWFudHVtIjtpOjE7czo0OiJzYWZlIjtpOjI7czoxMjoicXVhbnR1bSBzYWZlIjt9 |archive-date=17 August 2016 |url-status=dead}}</ref>。 存在が広く噂されている{{仮リンク|Harvest now, decrypt later|en|Harvest now, decrypt later}}攻撃も、早急なポスト量子暗号導入への理由となっている<ref>{{Citation|title=Post-quantum Cryptography|last=Gasser|first=Linus|date=2023|journal=Trends in Data Protection and Encryption Technologies|publisher=Springer Nature Switzerland|editor-last=Mulder|editor-first=Valentin|pages=47–52|location=Cham|isbn=978-3-031-33386-6|editor2-last=Mermoud|editor2-first=Alain|editor3-last=Lenders|editor3-first=Vincent|editor4-last=Tellenbach|editor4-first=Bernhard|language=en|doi=10.1007/978-3-031-33386-6_10}}</ref><ref>{{Cite web |author=Townsend |first=Kevin |date=2022-02-16 |title=Solving the Quantum Decryption 'Harvest Now, Decrypt Later' Problem |url=https://www.securityweek.com/solving-quantum-decryption-harvest-now-decrypt-later-problem/ |access-date=2023-04-09 |website=SecurityWeek |language=en-US}}</ref><ref>{{Cite web |date=October 2021 |title=Quantum-Safe Secure Communications |url=https://uknqt.ukri.org/wp-content/uploads/2021/10/Quantum-Safe-Secure-Communications.pdf |access-date=2023-04-09 |website=UK National Quantum Technologies Programme}}</ref>。

量子コンピュータが現在の公開鍵暗号アルゴリズムへの脅威となっている一方で、現在の多くの[[共通鍵暗号]]や[[ハッシュ関数]]は量子コンピュータからの攻撃に対して比較的安全と考えられている<ref name="djb-intro">{{Cite book |last=Bernstein |first=Daniel J. |title=Post-Quantum Cryptography |year=2009 |language=en |chapter=Introduction to post-quantum cryptography |author-link=Daniel J. Bernstein |chapter-url=http://www.pqcrypto.org/www.springer.com/cda/content/document/cda_downloaddocument/9783540887010-c1.pdf}}</ref><ref name="collisioncost">{{Cite web |date=2009-05-17 |author=Daniel J. Bernstein |title=Cost analysis of hash collisions: Will quantum computers make SHARCS obsolete? |url=http://cr.yp.to/hash/collisioncost-20090823.pdf |authorlink=Daniel J. Bernstein}}</ref>。 量子コンピュータは[[グローバーのアルゴリズム]]によって共通鍵暗号の解読速度を上げることができるものの、これに対しては鍵長を倍にすることが効果的な対策となる<ref name="djb-groverr">{{Cite web |date=2010-03-03 |author=Daniel J. Bernstein |title=Grover vs. McEliece |url=http://cr.yp.to/codes/grovercode-20100303.pdf |authorlink=Daniel J. Bernstein}}</ref>。そのため、ポスト量子共通鍵暗号には現在の共通鍵暗号と大きく異なったものを用いる必要はない。

2024年8月13日、[[アメリカ国立標準技術研究所]](NIST)は初めて耐量子計算機暗号標準(Post-Quantum Cryptography Standards)を発表した。これには3つの耐量子暗号アルゴリズムが含まれている。<ref>{{Cite web |url=https://www.nist.gov/news-events/news/2024/08/nist-releases-first-3-finalized-post-quantum-encryption-standards |title=NIST Releases First 3 Finalized Post-Quantum Encryption Standards {{!}} NIST |access-date=2024-08-29 |publisher=The National Institute of Standards and Technology}}</ref><ref>{{Cite web |url=https://jp.newsroom.ibm.com/2024-08-16-ibm-developed-algorithms-announced-as-worlds-first-post-quantum-cryptography-standards |title=IBM Japan Newsroom - ニュースリリース |access-date=2024-08-29 |publisher=日本アイ・ビー・エム株式会社}}</ref>

== アルゴリズム ==
ポスト量子暗号の研究には、大きく分けて6つのアプローチがある。<ref name="djb-intro">{{Cite book |last=Bernstein |first=Daniel J. |title=Post-Quantum Cryptography |year=2009 |language=en |chapter=Introduction to post-quantum cryptography |author-link=Daniel J. Bernstein |chapter-url=http://www.pqcrypto.org/www.springer.com/cda/content/document/cda_downloaddocument/9783540887010-c1.pdf}}</ref><ref name="ieee-jintai-ding">{{Cite magazine2 |date=2008-11-01 |title=Q&A With Post-Quantum Computing Cryptography Researcher Jintai Ding |url=https://spectrum.ieee.org/computing/networks/qa-with-postquantum-computing-cryptography-researcher-jintai-ding |magazine=[[IEEE Spectrum]]}}</ref>

=== 格子暗号 ===
このアプローチには{{仮リンク|Learning with errors|en|Learning_with_errors|label=Learning with errors(LWE)}}、{{仮リンク|Ring learning with errors|en|Ring_learning_with_errors|label=Ring learning with errors(ring-LWE)}}<ref name=":0">{{Cite web |author=Peikert |first=Chris |title=Lattice Cryptography for the Internet |url=http://eprint.iacr.org/2014/070.pdf |publisher=IACR |access-date=10 May 2014 |archive-url=https://web.archive.org/web/20140512214902/http://eprint.iacr.org/2014/070.pdf |archive-date=12 May 2014 |year=2014 |url-status=bot: unknown}}</ref><ref name="Guneysu 2012">{{Cite web |url=http://emsec.rub.de/media/sh/veroeffentlichungen/2014/06/12/lattice_signature.pdf |title=Practical Lattice-Based Cryptography: A Signature Scheme for Embedded Systems |author=Güneysu |first=Tim |year=2012 |publisher=INRIA |access-date=12 May 2014}}</ref><ref>{{Cite web |author=Zhang |first=jiang |title=Authenticated Key Exchange from Ideal Lattices |url=http://eprint.iacr.org/2014/589.pdf |website=iacr.org |publisher=IACR |access-date=7 September 2014 |archive-url=https://web.archive.org/web/20140907212538/http://eprint.iacr.org/2014/589.pdf |archive-date=7 September 2014 |year=2014 |url-status=bot: unknown}}</ref> 、Ring learning with errors鍵交換、Ring learning with errors署名、[[NTRU暗号]]や[[GGH 暗号方式|GGH暗号方式]]、{{仮リンク|NTRUSign|en|NTRUSign}}、{{仮リンク|BLISS署名方式|en|BLISS_signature_scheme}}などの暗号方式がある。NTRU暗号など、このうちのいくつかはまだ効果的な攻撃方法は見つかっていない。ring-LWEなどのその他のアルゴリズムは、最悪時の格子問題と同等の安全性があることが分かっている。<ref>{{Cite web |author=Lyubashevsky |first=Vadim |title=On Ideal Lattices and Learning with Errors Over Rings |url=http://eprint.iacr.org/2012/230.pdf |publisher=IACR |access-date=14 May 2013 |archive-url=https://web.archive.org/web/20140131051244/http://eprint.iacr.org/2012/230.pdf |archive-date=31 January 2014 |year=2013 |url-status=bot: unknown}}</ref> [[欧州委員会]]から支援を受けたThe Post Quantum Cryptography Study Groupは、NTRU暗号ではなく、Stehle–Steinfeld variant of NTRUを標準化に向けて研究すべきだと提案している<ref name=":9">{{Cite web |url=http://pqcrypto.eu.org/docs/initial-recommendations.pdf |title=Initial recommendations of long-term secure post-quantum systems |date=7 September 2015 |access-date=13 September 2015 |website=PQCRYPTO |author=Augot |first=Daniel}}</ref><ref>{{Cite journal|last=Stehlé|first=Damien|last2=Steinfeld|first2=Ron|date=2013-01-01|title=Making NTRUEncrypt and NTRUSign as Secure as Standard Worst-Case Problems over Ideal Lattices|url=http://eprint.iacr.org/2013/004|journal=Cryptology ePrint Archive}}</ref>。現在のところ、NTRUは特許で保護されている。研究では、NTRU暗号は他の格子暗号アルゴリズムよりも安全な要素が多いとされている<ref>{{Cite book |date=2019-02-01 |first=Chuck |last=Easttom |title=2019 IEEE 9th Annual Computing and Communication Workshop and Conference (CCWC) |chapter=An Analysis of Leading Lattice-Based Asymmetric Cryptographic Primitives |pages=0811–0818 |doi=10.1109/CCWC.2019.8666459 |isbn=978-1-7281-0554-3}}</ref>。

=== 多変数暗号 ===
多変数方程式を解くことが困難であることを利用したRainbow ({{仮リンク|Unbalanced oil and vinegar方式|en|Unbalanced_oil_and_vinegar_scheme|label=Unbalanced oil and vinegar}})方式がある。多変数方程式を用いた安全な暗号方式を作る試みは失敗を重ねてきた。しかし、Rainbowは多変数方程式によるデジタル署名方式の基礎を築くことに成功した<ref>{{Cite book |last=Ding |first=Jintai |title=Applied Cryptography and Network Security |last2=Schmidt |date=7 June 2005 |isbn=978-3-540-26223-7 |editor-last=Ioannidis |editor-first=John |series=Lecture Notes in Computer Science |volume=3531 |pages=64–175 |language=en-us |chapter=Rainbow, a New Multivariable Polynomial Signature Scheme |doi=10.1007/11496137_12}}</ref> 。Rainbow方式は特許で保護されている。　

=== ハッシュ暗号 ===
これには、[[ランポート署名]]、{{仮リンク|Merkle署名方式|en|Merkle signature scheme}}、XMSS、<ref name="BuchmannDahmen2011">{{Cite conference|last=Buchmann|first1=Johannes|last2=Dahmen|first2=Erik|last3=Hülsing|first3=Andreas|series=Lecture Notes in Computer Science|volume=7071|pages=117–129|title=Post-Quantum Cryptography. PQCrypto 2011|year=2011|doi=10.1007/978-3-642-25405-5_8}}</ref> SPHINCS、<ref name="SPHINCS">{{Cite book |issue=Advances in Cryptology – EUROCRYPT 2015 |last=Bernstein |first=Daniel J. |last2=Hopwood |first2=Daira |last3=Hülsing |first3=Andreas |last4=Lange |first4=Tanja |author4-link=Tanja Lange |last5=Niederhagen |first5=Ruben |last6=Papachristodoulou |first6=Louiza |last7=Schneider |first7=Michael |last8=Schwabe |first8=Peter |last9=Wilcox-O'Hearn |first9=Zooko |chapter=SPHINCS: Practical Stateless Hash-Based Signatures |title=Advances in Cryptology -- EUROCRYPT 2015 |year=2015 |publisher=Springer Berlin Heidelberg |isbn=9783662467992 |editor-last=Oswald |editor-first=Elisabeth |editor-link=Elisabeth Oswald |series=Lecture Notes in Computer Science |volume=9056 |pages=368–397 |language=en |doi=10.1007/978-3-662-46800-5_15 |editor2=Fischlin}}</ref> WOTS方式などがある。ハッシュによるデジタル署名は1970年代後半に[[ラルフ・マークル]]によって発明され、 RSAやDSAといった数論的なデジタル署名に代わる方式として研究されてきた。これらの方式の大きな欠点は、どのハッシュ暗号でも、公開鍵と対となる秘密鍵を用いて署名できる数に限りがあるという点である。そのため、耐量子暗号への関心が高まるまでは、この方式はあまり注目を集めてこなかった。Merkle署名方式は特許で保護されておらず{{要出典|date=August 2015}}、この方式で使うことのできる特許で保護されていないハッシュ関数は多く存在する。{{仮リンク|ヨハネス・ブーフマン|en|Johannes_Buchmann}}の率いる研究チームによって開発された、ステートフルなハッシュ署名方式であるXMSSはRFC 8391に記述されている<ref>{{Cite journal|last=Huelsing|first=A.|last2=Butin|first2=D.|last3=Gazdag|first3=S.|last4=Rijneveld|first4=J.|last5=Mohaisen|first5=A.|year=2018|title=RFC 8391 – XMSS: eXtended Merkle Signature Scheme|url=https://datatracker.ietf.org/doc/html/rfc8391|language=en|doi=10.17487/RFC8391}}</ref>。

上で述べた方式はすべて一度、もしくは限られた回数の署名であるが、{{仮リンク|Moni Naor|en|Moni Naor}}と{{仮リンク|モチ・ユング|en|Moti Yung}} は1989年に{{仮リンク|Universal one-way hash function|en|Universal one-way hash function|label=UOWHF}}を発明し、何度でも使うことのできるハッシュ署名 (the Naor-Yung scheme)<ref>{{Citation|title=Universal One-Way Hash Functions and their Cryptographic Applications .STOC|last=Naor|first=Moni|last2=Yung|first2=Moti|date=1989|pages=33–43}}</ref>を設計した(the first such signature that does not require trapdoor properties)。

=== 符号暗号 ===
これには[[マックエリス暗号]]、{{仮リンク|Niederreiter暗号システム|en|Niederreiter cryptosystem}} やそれに関連するCourtois, Finiasz and Sendrier署名方式など、誤り訂正符号に依拠した暗号方式が含まれる。オリジナルなマックエリス暗号はランダムな{{仮リンク|Goppa符号|en|Binary Goppa code}} を使っており、これは40年以上もの時間と研究を経た今でも安全と考えられている。 しかし、鍵サイズを減らすために符号に構造を追加しようとして作られた、異なるバリエーションのマックエリス暗号は、その多くが安全ではないことが分かっている<ref>{{Cite book |last=Overbeck |first=Raphael |last2=Sendrier |title=Post-Quantum Cryptography |chapter=Code-based cryptography |date=2009 |pages=95–145 |doi=10.1007/978-3-540-88702-7_4 |editor-first=Daniel |editor-last=Bernstein |isbn=978-3-540-88701-0}}</ref>。 欧州委員会の支援するThe Post Quantum Cryptography Study Groupは、量子コンピュータの攻撃に長時間耐えることのできる暗号システムの候補として、マックエリス公開鍵暗号を推薦している<ref name=":9">{{Cite web |url=http://pqcrypto.eu.org/docs/initial-recommendations.pdf |title=Initial recommendations of long-term secure post-quantum systems |date=7 September 2015 |access-date=13 September 2015 |website=PQCRYPTO |author=Augot |first=Daniel}}</ref>。

=== 同種写像暗号 ===
[[有限体]]上の[[楕円曲線]]の[[同種 (数学)|同種写像]]グラフ(と高次元[[アーベル多様体]])、特に{{仮リンク|超特異同種写像グラフ|en|Supersingular isogeny graph}}の性質を用いた暗号システムである。この分野でよく知られているのは[[ディフィー・ヘルマン鍵共有]]と似ているCSIDH鍵共有であり、これは現在広く使われているディフィー・ヘルマン鍵共有や[[楕円曲線ディフィー・ヘルマン鍵共有]]の耐量子代替として単純に使うことができる<ref>{{Cite book |last=Castryck |first=Wouter |last2=Lange |first2=Tanja |last3=Martindale |first3=Chloe |last4=Panny |first4=Lorenz |last5=Renes |first5=Joost |title=Advances in Cryptology – ASIACRYPT 2018 |chapter=CSIDH: An Efficient Post-Quantum Commutative Group Action |date=2018 |editor-last=Peyrin |editor-first=Thomas |editor2-last=Galbraith |editor2-first=Steven |chapter-url=https://hdl.handle.net/handle/1854/LU-8619033 |series=Lecture Notes in Computer Science |volume=11274 |language=en |location=Cham |publisher=Springer International Publishing |pages=395–427 |doi=10.1007/978-3-030-03332-3_15 |hdl=1854/LU-8619033 |isbn=978-3-030-03332-3}}</ref>。また、超特異楕円曲線とあるタイプの[[四元数環]]の極大整環が圏同値であることに基づいた署名方式であるSQISignも知られている<ref>{{Cite book |last=De Feo |first=Luca |last2=Kohel |first2=David |last3=Leroux |first3=Antonin |last4=Petit |first4=Christophe |last5=Wesolowski |first5=Benjamin |title=Advances in Cryptology – ASIACRYPT 2020 |chapter=SQISign: Compact Post-quantum Signatures from Quaternions and Isogenies |date=2020 |editor-last=Moriai |editor-first=Shiho |editor2-last=Wang |editor2-first=Huaxiong |chapter-url=https://hal.archives-ouvertes.fr/hal-03038004/file/2020-1240.pdf |series=Lecture Notes in Computer Science |volume=12491 |language=en |location=Cham |publisher=Springer International Publishing |pages=64–93 |doi=10.1007/978-3-030-64837-4_3 |isbn=978-3-030-64837-4}}</ref>。もう一つのよく知られた方式である[[超特異同種写像ディフィー・ヘルマン]](SIDH/SIKE)は2022年に破られた<ref>{{Citation|title=An Efficient Key Recovery Attack on SIDH|last=Castryck|first=Wouter|last2=Decru|first2=Thomas|date=2023|url=https://link.springer.com/10.1007/978-3-031-30589-4_15|journal=Advances in Cryptology – EUROCRYPT 2023|publisher=Springer Nature Switzerland|editor-last=Hazay|editor-first=Carmit|volume=14008|pages=423–447|location=Cham|isbn=978-3-031-30588-7|editor2-last=Stam|editor2-first=Martijn|language=en|doi=10.1007/978-3-031-30589-4_15|access-date=2023-06-21}}</ref>。 この攻撃はSIDH/SIKE系の方式に特有のため、他の同種写像暗号に対して一般的に用いることはできない<ref>{{Cite web |title=Is SIKE broken yet? |url=https://issikebrokenyet.github.io/ |access-date=2023-06-23}}</ref>。

=== 共通鍵暗号の耐量子性 ===
十分に大きな鍵長を使った場合、[[Advanced Encryption Standard|AES]]や{{仮リンク|SNOW (ストリーム暗号)|en|SNOW|label=SNOW 3G}}のような共通鍵暗号方式はすでに量子コンピュータの攻撃に耐えられる。<ref>{{Cite conference|last=Perlner|first1=Ray|title=Quantum Resistant Public Key Cryptography: A Survey|url=https://www.nist.gov/manuscript-publication-search.cfm?pub_id=901595|conference=8th Symposium on Identity and Trust on the Internet (IDtrust 2009)|publisher=NIST|access-date=23 Apr 2015|last2=Cooper|year=2009}}</ref>その上、[[ケルベロス認証]]や3GPPモバイルネットワーク認証といった、公開鍵暗号ではなく共通鍵暗号を用いた鍵管理システムやプロトコルも量子コンピュータの攻撃に対して本質的に安全である。ケルベロス認証は既に世界中に普及しているため、いち早くポスト量子暗号に対応する効率的な方法として、ケルベロス認証のような鍵管理システムを広く用いることを推奨する研究者もいる<ref>{{Cite web |author=Campagna |first=Matt |title=Kerberos Revisited Quantum-Safe Authentication |url=http://docbox.etsi.org/Workshop/2013/201309_CRYPTO/S03_INDUSTRY_SESSION/PITNEYBOWES_PINTSOV.pdf |publisher=ETSI |year=2013}}</ref>。

== Security reductions ==
暗号研究においては、暗号アルゴリズムが既知の困難な数学問題と同等であることを証明することが望まれる。この証明はよく"security reductions"と呼ばれ、暗号アルゴリズムを破ることの難しさを示すために使われる。言い換えると、暗号アルゴリズムのセキュリティーは既知の難問のセキュリティーに換算される。研究者はポスト量子暗号のsecurity reductionsを活発に探している。現在の結果には以下のようなものがある。

=== 格子暗号 – Ring-LWE署名 ===
Ring-LWEのあるバージョンには、最短の格子を求める{{仮リンク|最短ベクトル問題|en|Shortest vector problem}}(SVP)のセキュリティーに帰着できるsecurity reductionがある。最短ベクトル問題は[[NP困難]]であることが知られている<ref>{{Cite web |author=Lyubashevsky |first=Vadim |title=On Ideal Lattices and Learning with Errors Over Rings |url=https://web.eecs.umich.edu/~cpeikert/pubs/ideal-lwe.pdf |publisher=Springer |access-date=19 June 2014 |date=25 June 2013}}</ref>。Güneysu、Lyubashevsky、Pöppelmannによる論文で定義されているLyubashevsky's ring-LWE署名<ref name="Guneysu 2012">{{Cite web |url=http://emsec.rub.de/media/sh/veroeffentlichungen/2014/06/12/lattice_signature.pdf |title=Practical Lattice-Based Cryptography: A Signature Scheme for Embedded Systems |author=Güneysu |first=Tim |year=2012 |publisher=INRIA |access-date=12 May 2014}}</ref>など、証明可能なsecurity reductionのあるring-LWEシステムもある。GLYPH署名方式はGüneysu、Lyubashevsky、Pöppelmann (GLP)署名の発表後の研究結果を考慮に入れた、GLP署名のバリエーションである。もう一つのRing-LWE署名はRing-TESLAである<ref>{{Cite journal|last=Akleylek|first=Sedat|last2=Bindel|first2=Nina|last3=Buchmann|first3=Johannes|last4=Krämer|first4=Juliane|last5=Marson|first5=Giorgia Azzurra|date=2016|title=An Efficient Lattice-Based Signature Scheme with Provably Secure Instantiation|url=https://eprint.iacr.org/2016/030|journal=Cryptology ePrint Archive}}</ref>。LWEの「脱ランダム化されたバリエーション」であるLearning with Rounding (LWR)は「速度(by eliminating sampling small errors from a Gaussian-like distribution with deterministic errors) と帯域の向上」がなされている<ref>{{Cite journal|last=Nejatollahi|first=Hamid|last2=Dutt|first2=Nikil|last3=Ray|first3=Sandip|last4=Regazzoni|first4=Francesco|last5=Banerjee|first5=Indranil|last6=Cammarota|first6=Rosario|date=2019-02-27|title=Post-Quantum Lattice-Based Cryptography Implementations: A Survey|url=https://dl.acm.org/doi/10.1145/3292548|journal=ACM Computing Surveys|volume=51|issue=6|pages=1–41|language=en|doi=10.1145/3292548|issn=0360-0300}}</ref>。LWEが下位ビットを隠すために小さなエラーを加えているのに対して、LWRはそのために丸め操作を利用している。

=== 格子暗号 – NTRU, BLISS ===
[[NTRU暗号|NTRU]]暗号方式とBLISS<ref name=":1">{{Cite journal|last=Ducas|first=Léo|last2=Durmus|first2=Alain|last3=Lepoint|first3=Tancrède|last4=Lyubashevsky|first4=Vadim|date=2013|title=Lattice Signatures and Bimodal Gaussians|url=http://eprint.iacr.org/2013/383|journal=Cryptology ePrint Archive|accessdate=2015-04-18}}</ref>署名は、格子における最近ベクトル問題(CVP)と関係しているが、おそらく等価ではないと考えられている。CVPは[[NP困難]]であることが知られている。[[欧州委員会]]から支援を受けているThe Post Quantum Cryptography Study Groupは、長期間利用できる暗号方式として、オリジナルのNTRUよりも、security reductionのあるStehle–SteinfeldバージョンのNTRUを研究すべきだと提唱している<ref name=":92">{{cite web |url=http://pqcrypto.eu.org/docs/initial-recommendations.pdf |title=Initial recommendations of long-term secure post-quantum systems |date=7 September 2015 |access-date=13 September 2015 |website=PQCRYPTO |last=Augot |first=Daniel}}</ref>。

=== 多変数暗号 – Unbalanced oil and vinegar ===
{{仮リンク|Unbalanced oil and vinegar方式|en|Unbalanced_oil_and_vinegar_scheme|label=Unbalanced oil and vinegar}}暗号方式は有限体上の多変数[[多項式]]に基づく非対称的な暗号プリミティブである。Bulygin、Petzoldt、Buchmannらは一般的な多変数二次UOVシステムがNP困難な多変数二次方程式問題に換算されることを示している。<ref>{{cite book |last1=Bulygin |first1=Stanislav |author2=Petzoldt |author3=Buchmann |contribution=Towards Provable Security of the Unbalanced Oil and Vinegar Signature Scheme under Direct Attacks |title=Progress in Cryptology – INDOCRYPT 2010 |date=2010 |volume=6498 |pages=17–32 |series=Lecture Notes in Computer Science |doi=10.1007/978-3-642-17401-8_3 |citeseerx=10.1.1.294.3105 |isbn=978-3-642-17400-1}}</ref>    

=== ハッシュ暗号 – Merkle署名方式 ===
2005年、Luis GarciaはMerkle署名方式がその基礎となっているハッシュ関数の安全性に換算できることを示した。Garciaは論文内で、もし一方向ハッシュ関数が計算上存在するなら、Merkle署名は安全であるだろうと示した。<ref>{{Cite journal|last=Pereira|first=Geovandro|last2=Puodzius|first2=Cassius|last3=Barreto|first3=Paulo|year=2016|title=Shorter hash-based signatures|journal=Journal of Systems and Software|volume=116|pages=95–100|doi=10.1016/j.jss.2015.07.007}}</ref>

それゆえ、 既知の難問へとセキュリティ的に換算できるハッシュ関数を使った場合、Merkle署名方式のSecurity reductionはその難問であることになる<ref>{{Cite web |author=Garcia |first=Luis |title=On the security and the efficiency of the Merkle signature scheme |url=http://eprint.iacr.org/2005/192.pdf |website=Cryptology ePrint Archive |publisher=IACR |access-date=19 June 2013}}</ref>。

[[欧州委員会]]から支援を受けているThe Post Quantum Cryptography Study Groupは、量子コンピュータの攻撃を長期間防ぐことのできる方式としてMerkle署名方式を推薦している<ref name=":9">{{Cite web |url=http://pqcrypto.eu.org/docs/initial-recommendations.pdf |title=Initial recommendations of long-term secure post-quantum systems |date=7 September 2015 |access-date=13 September 2015 |website=PQCRYPTO |author=Augot |first=Daniel}}</ref>。

=== 符号暗号 – マックエリス暗号 ===
マックエリス暗号方式は、シンドローム復号問題(SDP)にセキュリティ的に換算できる。SDPは[[NP困難]]であることが知られている<ref>{{Cite book |last=Blaum |first=Mario |last2=Farrell |last3=Tilborg |title=Information, Coding and Mathematics |date=31 May 2002 |publisher=Springer |isbn=978-1-4757-3585-7}}</ref>。欧州委員会から支援を受けているThe Post Quantum Cryptography Study Groupは、この暗号方式を量子コンピュータの攻撃を長期間防ぐことのできる方式として推薦している。<ref name=":9">{{Cite web |url=http://pqcrypto.eu.org/docs/initial-recommendations.pdf |title=Initial recommendations of long-term secure post-quantum systems |date=7 September 2015 |access-date=13 September 2015 |website=PQCRYPTO |author=Augot |first=Daniel}}</ref>

=== 符号暗号 – RLCE ===
2016年、Wangは[[マックエリス暗号]]に基づいたランダム線形符号暗号方式であるRLCE<ref>{{Cite journal|last=Wang|first=Yongge|date=2016|title=Quantum resistant random linear code based public key encryption scheme RLCE|journal=Proceedings of Information Theory (ISIT)|pages=2519–2523|arxiv=1512.08454|bibcode=2015arXiv151208454W}}</ref>を提唱した。RLCE方式は、元となっている[[線型符号]]の[[生成行列]]にランダムな列を挿入することで、[[リード・ソロモン符号]]など、いかなる線型符号を用いても構築することができる。

=== 超特異楕円曲線同種写像暗号 ===
この安全性は、２つの超特異曲線間に同じ数の点で同種写像を構築する問題と関連している。最近の研究では、DelfsとGalbraithがこの問題は鍵交換の発明者が示したのと同様に困難であることを示している<ref>{{Cite arXiv|arxiv=1310.7789|class=math.NT|last=Delfs|first=Christina|last2=Galbraith|title=Computing isogenies between supersingular elliptic curves over F_p}}</ref>。既知のNP困難な問題とのsecurity reductionは無い。

== 比較 ==
多くのポスト量子暗号が持つ特徴の一つは、一般的な「プレ量子」公開鍵アルゴリズムよりも大きな鍵長を必要とすることである。鍵長、計算上の効率性、暗号テキスト・署名テキストのサイズの間にはしばしばトレードオフが存在する。以下の表は、128bitの{{仮リンク|セキュリティレベル|en|Security level}}におけるポスト量子暗号方式の鍵サイズを比較したものである。  
{| class="wikitable sortable"
! class="unsortable" |アルゴリズム
! class="unsortable" |タイプ
!公開鍵
!秘密鍵
!署名
|-
|[[NTRU暗号]]<ref name=":5">{{Cite web |author=Hirschborrn |first=P |title=Choosing NTRUEncrypt Parameters in Light of Combined Lattice Reduction and MITM Approaches |url=https://www.securityinnovation.com/uploads/Crypto/params.pdf |publisher=NTRU |access-date=12 May 2014 |archive-url=https://web.archive.org/web/20130130160705/https://securityinnovation.com/uploads/Crypto/params.pdf |archive-date=30 January 2013 |url-status=dead}}</ref>
|格子暗号
|{{Number table sorting|766.25}} B
|{{Number table sorting|842.875}} B
|
|-
|Streamlined NTRU Prime{{要出典|date=March 2022}}
|格子暗号
|{{Number table sorting|154}} B
|
|
|-
|Rainbow<ref name=":6">{{Cite web |author=Petzoldt |first=Albrecht |title=Selecting Parameters for the Rainbow Signature Scheme – Extended Version - |url=http://eprint.iacr.org/2010/437.pdf |access-date=12 May 2014 |archive-date=4 March 2016 |archive-url=https://web.archive.org/web/20160304001111/http://eprint.iacr.org/2010/437.pdf |year=2010 |url-status=bot: unknown}}</ref>
|多変数暗号
|{{Ntsh|124000}}124 kB
|{{Ntsh|95000}}95 kB
|
|-
|SPHINCS<ref name="SPHINCS">{{Cite book |issue=Advances in Cryptology – EUROCRYPT 2015 |last=Bernstein |first=Daniel J. |last2=Hopwood |first2=Daira |last3=Hülsing |first3=Andreas |last4=Lange |first4=Tanja |author4-link=Tanja Lange |last5=Niederhagen |first5=Ruben |last6=Papachristodoulou |first6=Louiza |last7=Schneider |first7=Michael |last8=Schwabe |first8=Peter |last9=Wilcox-O'Hearn |first9=Zooko |chapter=SPHINCS: Practical Stateless Hash-Based Signatures |title=Advances in Cryptology -- EUROCRYPT 2015 |year=2015 |publisher=Springer Berlin Heidelberg |isbn=9783662467992 |editor-last=Oswald |editor-first=Elisabeth |editor-link=Elisabeth Oswald |series=Lecture Notes in Computer Science |volume=9056 |pages=368–397 |language=en |doi=10.1007/978-3-662-46800-5_15 |editor2=Fischlin}}</ref>
|ハッシュ署名
|{{Ntsh|1000}}1 kB
|{{Ntsh|1000}}1 kB
|{{Ntsh|41000}}41 kB
|-
|SPHINCS+<ref>[https://sphincs.org/data/sphincs+-specification.pdf SPHINCS+: Submission to the NIST post-quantum project]</ref>
|ハッシュ署名
|{{Number table sorting|32}} B
|{{Number table sorting|64}} B
|{{Ntsh|8000}}8 kB
|-
|BLISS-II
|格子暗号
|{{Ntsh|7000}}7 kB
|{{Ntsh|2000}}2 kB
|{{Ntsh|5000}}5 kB
|-
|GLP-Variant GLYPH Signature<ref name="Guneysu 2012">{{Cite web |url=http://emsec.rub.de/media/sh/veroeffentlichungen/2014/06/12/lattice_signature.pdf |title=Practical Lattice-Based Cryptography: A Signature Scheme for Embedded Systems |author=Güneysu |first=Tim |year=2012 |publisher=INRIA |access-date=12 May 2014}}</ref><ref>{{Cite journal|last=Chopra|first=Arjun|date=2017|title=GLYPH: A New Insantiation of the GLP Digital Signature Scheme|url=https://eprint.iacr.org/2017/766|journal=Cryptology ePrint Archive}}</ref>
|Ring-LWE
|{{Ntsh|2000}}2 kB
|{{Ntsh|400}}0.4 kB
|{{Ntsh|1800}}1.8 kB
|-
|{{仮リンク|NewHope|en|NewHope}}<ref name="newhope">{{Cite web |author=Alkim |first=Erdem <!--|archivedate=Peter--> |year=2015 |title=Post-quantum key exchange – a new hope |url=http://eprint.iacr.org/2015/1092 |access-date=1 September 2017 |publisher=Cryptology ePrint Archive, Report 2015/1092}}</ref>
|Ring-LWE
|{{Ntsh|2000}}2 kB
|{{Ntsh|2000}}2 kB
|
|-
|[[ゴッパ符号]]を用いた[[マックエリス暗号]]<ref name=":9">{{Cite web |url=http://pqcrypto.eu.org/docs/initial-recommendations.pdf |title=Initial recommendations of long-term secure post-quantum systems |date=7 September 2015 |access-date=13 September 2015 |website=PQCRYPTO |author=Augot |first=Daniel}}</ref>
|符号暗号
|{{Ntsh|1000000}}1 MB
|{{Ntsh|11500}}11.5 kB
|
|-
|Random Linear Code based encryption<ref>{{Cite journal|last=Wang|first=Yongge|date=2017|title=Revised Quantum Resistant Public Key Encryption Scheme RLCE and IND-CCA2 Security for McEliece Schemes|url=https://eprint.iacr.org/2017/206|journal=Cryptology ePrint Archive}}</ref>
|RLCE
|{{Ntsh|115000}}115 kB
|{{Ntsh|3000}}3 kB
|
|-
|Quasi-cyclic MDPC-based McEliece<ref>{{Cite book |last=Misoczki |first=R. |last2=Tillich |first2=J. P. |last3=Sendrier |first3=N. |last4=Barreto |first4=P. S. L. M. |title=2013 IEEE International Symposium on Information Theory |chapter=MDPC-McEliece: New McEliece variants from Moderate Density Parity-Check codes |date=2013 |pages=2069–2073 |doi=10.1109/ISIT.2013.6620590 |isbn=978-1-4799-0446-4}}</ref>
|符号暗号
|{{Number table sorting|1232}} B
|{{Number table sorting|2464}} B
|
|-
|SIDH<ref>{{Cite book |chapter-url=http://eprint.iacr.org/2016/413.pdf |year=2016 |last=Costello |first=Craig |last2=Longa |first2=Patrick |last3=Naehrig |first3=Michael |title=Advances in Cryptology – CRYPTO 2016 |chapter=Efficient Algorithms for Supersingular Isogeny Diffie-Hellman |series=Lecture Notes in Computer Science |volume=9814 |pages=572–601 |doi=10.1007/978-3-662-53018-4_21 |isbn=978-3-662-53017-7}}</ref>
|同種写像暗号
|{{Number table sorting|564}} B
|{{Number table sorting|48}} B
|
|-
|SIDH (compressed keys)<ref name="SIDHcompressed">{{Cite web |author=Costello |first=Craig |title=Efficient Compression of SIDH public keys |url=https://eprint.iacr.org/2016/963 |access-date=8 October 2016}}</ref>
|同種写像暗号
|{{Number table sorting|330}} B
|{{Number table sorting|48}} B
|
|-
|3072-bit Discrete Log
|'''非ポスト量子暗号'''
|{{Number table sorting|384}} B
|{{Number table sorting|32}} B
|{{Number table sorting|96}} B
|-
|256-bit 楕円曲線暗号
|'''非ポスト量子暗号'''
|{{Number table sorting|32}} B
|{{Number table sorting|32}} B
|{{Number table sorting|65}} B
|-
|}
ポスト量子暗号の選択における実用的な考慮事項としては、インターネット上で送信する公開鍵のサイズがある。この観点では、Ring-LWE、NTRU暗号、SIDHアルゴリズムが1kB以下で利便性が良い。ハッシュ署名暗号の公開鍵は5kB以下、 MDPC-based McElieceは約1kBである。その一方、Rainbow 方式は約125kB、ゴッパ符号を用いたマックエリス暗号は1MB近くの鍵サイズが必要となる。

=== 格子暗号 – LWE鍵交換とRing-LWE鍵交換 ===
LWEとRing-LWEを鍵交換に用いるアイデアの基礎は、Jintai Dingによって2011年にシンシナティ大学で提唱され、特許出願された。この基本的なアイデアは行列の乗法の結合性に基づいており、エラーはセキュリティを与えるために利用される。この論文<ref>{{Cite journal|last=Ding|first=Jintai|last2=Xie|first2=Xiang|last3=Lin|first3=Xiaodong|date=2012-01-01|title=A Simple Provably Secure Key Exchange Scheme Based on the Learning with Errors Problem|url=http://eprint.iacr.org/2012/688|journal=Cryptology ePrint Archive}}</ref> は、2012年に仮特許出願が提出された後、2012年に発表された。

2014年、Peikert<ref>{{Cite journal|last=Peikert|first=Chris|date=2014-01-01|title=Lattice Cryptography for the Internet|url=http://eprint.iacr.org/2014/070|journal=Cryptology ePrint Archive}}</ref>はDingによる基本的なアイデアを発展させた鍵交換方式を発表した。これは、丸めのため1ビットのシグナルを追加して送るという新しいアイディアを用いている。128ビット以上の{{仮リンク|セキュリティレベル|en|Security level}}のために、Singhは6956bitの公開鍵を持つパラメーターセットを Peikertの方式に提案した<ref name=":2">{{Cite journal|last=Singh|first=Vikram|date=2015|title=A Practical Key Exchange for the Internet using Lattice Cryptography|url=http://eprint.iacr.org/2015/138|journal=Cryptology ePrint Archive|accessdate=2015-04-18}}</ref>。これに対応する秘密鍵はおよそ14,000ビットとなる。

2015年、Eurocrypt 2015において、Dingの基本的なアイデアから発展した、証明可能な前方秘匿性を持つ認証鍵交換方式が発表された<ref name=":10">{{Cite book |chapter=Authenticated Key Exchange from Ideal Lattices |publisher=Springer Berlin Heidelberg |date=2015-04-26 |isbn=978-3-662-46802-9 |pages=719–751 |series=Lecture Notes in Computer Science |first=Jiang |last=Zhang |first2=Zhenfeng |last2=Zhang |first3=Jintai |last3=Ding |first4=Michael |last4=Snook |first5=Özgür |last5=Dagdelen |volume=9057 |editor-first=Elisabeth |editor-last=Oswald |editor2=Fischlin |doi=10.1007/978-3-662-46803-6_24 |title=Advances in Cryptology – EUROCRYPT 2015}}</ref>。これはCrypto2005におけるHMQV<ref>{{Cite book |publisher=Springer |date=2005-08-14 |isbn=978-3-540-28114-6 |pages=546–566 |series=Lecture Notes in Computer Science |first=Hugo |last=Krawczyk |editor-first=Victor |editor-last=Shoup |doi=10.1007/11535218_33 |title=Advances in Cryptology – CRYPTO 2005 |volume=3621 |chapter=HMQV: A High-Performance Secure Diffie-Hellman Protocol}}</ref>構築を拡張したものである。80bitから350bitまでの異なるセキュリティレベルに対するパラメーターと、それに対応する鍵サイズも論文中で示されている<ref name=":10" />。

=== 格子暗号 – NTRU暗号 ===
Hirschhorn、Hoffstein、Howgrave-Graham、Whyteらは、128bitの{{仮リンク|セキュリティレベル|en|Security level}}のNTRU暗号にはkey represented as a degree 613 polynomial with coefficients<math>\bmod{\left(2^{10}\right)}</math>を用いることを推奨している。これは6130bitの公開鍵となる。これに対応する秘密鍵は6743bitである<ref name=":5">{{Cite web |author=Hirschborrn |first=P |title=Choosing NTRUEncrypt Parameters in Light of Combined Lattice Reduction and MITM Approaches |url=https://www.securityinnovation.com/uploads/Crypto/params.pdf |publisher=NTRU |access-date=12 May 2014 |archive-url=https://web.archive.org/web/20130130160705/https://securityinnovation.com/uploads/Crypto/params.pdf |archive-date=30 January 2013 |url-status=dead}}</ref>。

=== 多変数暗号 – Rainbow署名 ===
Petzoldt、BulyginとBuchmannは、Rainbow多変数二次方程式署名方式において、128bitのセキュリティレベルで最小の署名サイズにするには、<math>\mathbb{F}_{31}</math>上の方程式と991,000bitをやや上回るサイズの公開鍵、740,000bitをやや上回るサイズの秘密鍵と、424bitの長さのデジタル署名を用いることを推奨している<ref name=":6">{{Cite web |author=Petzoldt |first=Albrecht |title=Selecting Parameters for the Rainbow Signature Scheme – Extended Version - |url=http://eprint.iacr.org/2010/437.pdf |access-date=12 May 2014 |archive-date=4 March 2016 |archive-url=https://web.archive.org/web/20160304001111/http://eprint.iacr.org/2010/437.pdf |year=2010 |url-status=bot: unknown}}</ref>。

=== ハッシュ暗号 – Merkle署名方式 ===
Naor ShenhavとWoolによるフラクタルMerkle木を用いた方式では、100万メッセージに署名するためのハッシュ署名において128bitのセキュリティレベルを得るには、約36,000bitの公開鍵と秘密鍵のサイズとなる<ref name=":7">{{Cite web |author=Naor |first=Dalit |title=One-Time Signatures Revisited: Practical Fast Signatures Using Fractal Merkle Tree Traversal |url=http://www.eng.tau.ac.il/~yash/Naor_Shenhav_Wool.pdf |publisher=IEEE |access-date=13 May 2014 |year=2006}}</ref>。

=== 符号暗号 – マックエリス暗号 ===
[[マックエリス暗号]]で128bitのセキュリティレベルを得るために、The European Commissions Post Quantum Cryptography Study groupは、最低<math>n=6960</math> の長さ、<math>k=5413</math>の次元、 <math>t=119</math> のエラーを訂正できる[[ゴッパ符号]]を用いることを推奨している。これらのパラメータによって、マックエリス暗号の公開鍵はのnon-identity partは

<math>k \times (n-k) = 8373911</math>bitの組織[[生成行列]]となる。The corresponding private key, which consists of the code support with <math>n=6960</math> elements from <math>\mathrm{GF}(2^{13})</math> and a generator polynomial of with <math>t=119</math> coefficients from <math>\mathrm{GF}(2^{13})</math>,will be 92,027 bits in length<ref name=":9">{{Cite web |url=http://pqcrypto.eu.org/docs/initial-recommendations.pdf |title=Initial recommendations of long-term secure post-quantum systems |date=7 September 2015 |access-date=13 September 2015 |website=PQCRYPTO |author=Augot |first=Daniel}}</ref>.

The group is also investigating the use of Quasi-cyclic MDPC codes of length at least <math>n=2^{16}+6 = 65542</math> and dimension at least <math>k=2^{15}+3=32771</math>, and capable of correcting <math>t=264</math> errors. With these parameters the public key for the McEliece system will be the first row of a systematic generator matrix whose non-identity part takes <math>k=32771</math> bits. The private key, a quasi-cyclic parity-check matrix with <math>d=274</math> nonzero entries on a column (or twice as much on a row), takes no more than <math>d\times 16 = 4384</math> bits when represented as the coordinates of the nonzero entries on the first row.

Barreto et al. recommend using a binary Goppa code of length at least <math>n=3307</math> and dimension at least <math>k=2515</math>, and capable of correcting <math>t=66</math> errors. With these parameters the public key for the McEliece system will be a systematic generator matrix whose non-identity part takes <math>k \times (n-k) = 1991880</math> bits.<ref name=":8">{{Cite book |title=A Panorama of Post-quantum Cryptography |publisher=Springer International Publishing |date=2014 |isbn=978-3-319-10682-3 |pages=387–439 |first=Paulo S. L. M. |last=Barreto |first2=Felipe Piazza |last2=Biasi |first3=Ricardo |last3=Dahab |first4=Julio César |last4=López-Hernández |first5=Eduardo M. de |last5=Morais |first6=Ana D. Salina de |last6=Oliveira |first7=Geovandro C. C. F. |last7=Pereira |first8=Jefferson E. |last8=Ricardini |editor-first=Çetin Kaya |editor-last=Koç |doi=10.1007/978-3-319-10683-0_16}}</ref> The corresponding private key, which consists of the code support with <math>n=3307</math> elements from <math>\mathrm{GF}(2^{12})</math> and a generator polynomial of with <math>t=66</math> coefficients from 

<math>\mathrm{GF}(2^{12})</math>, will be 40,476 bits in length.

=== 超特異楕円曲線同種写像暗号 ===
{{仮リンク|セキュリティレベル|en|Security level}}で128bitの[[超特異同種写像ディフィー・ヘルマン]](SIDH) 方式には、De Feo、Jao、Plutらは supersingular curve modulo a 768-bit primeを用いることを推奨している<ref>{{Cite web |author=De Feo |first=Luca |title=Towards Quantum-Resistant Cryptosystems From Supersingular Elliptic Curve Isogenies |url=http://eprint.iacr.org/2011/506.pdf |access-date=12 May 2014 |archive-date=11 February 2014 |archive-url=https://web.archive.org/web/20140211082622/http://eprint.iacr.org/2011/506.pdf |year=2011 |url-status=bot: unknown}}</ref>。Azarderakhsh、Jao、Kalach、Koziel、Leonardiらによる2016年3月の論文では、送信するビット数を半分に減らす方法が示されている。その後、Costello、Jao、Longa、Naehrig、Renes 、Urbanikらの論文ではさらに改良され、公開鍵のサイズが2640bitに圧縮されたSIDHプロトコルのバージョンが完成している<ref name="SIDHcompressed">{{Cite web |author=Costello |first=Craig |title=Efficient Compression of SIDH public keys |url=https://eprint.iacr.org/2016/963 |access-date=8 October 2016}}</ref>。 これは非量子暗号である[[RSA暗号]]や[[ディフィー・ヘルマン鍵共有]]とほぼ同じサイズの送信量で、同等のセキュリティレベルである<ref>{{Cite web |url=http://eprint.iacr.org/2016/229 |title=Cryptology ePrint Archive: Report 2016/229 |website=eprint.iacr.org |access-date=2016-03-02}}</ref>。

=== 対称鍵暗号 ===
一般的に、対称鍵暗号システムで128bitの{{仮リンク|セキュリティレベル|en|Security level}}には、256bitの鍵サイズを用いる。量子コンピュータによる一般的な対称鍵暗号への最も効率の良い攻撃方法は[[グローバーのアルゴリズム]]を用いたもので、これは鍵サイズの平方根と同等の計算量が必要となる。暗号化された鍵を、復号化するための対称鍵を持ったデバイスに送信するためにも約256bitが必要となる。対称鍵がポスト量子暗号において最も小さい鍵サイズとなるのは明らかである{{要出典|date=February 2024}}<sup class="noprint Inline-Template Template-Fact" style="white-space:nowrap;">&#x5B;''[[wikipedia:「要出典」をクリックされた方へ|<span title="This claim needs references to reliable sources. (February 2024)">citation needed</span>]]''&#x5D;</sup>。

== Forward secrecy(前方秘匿性) ==
公開鍵暗号システムは、鍵共有においてセッションごとにランダムな公開鍵を生成したときには、完全な[[forward secrecy]](前方秘匿性) と呼ばれる性質を持つ。すなわち、一つのメッセージのセキュリティが破られても、その他のメッセージのセキュリティは破られないし、複数のメッセージのセキュリティを破ることのできるような一つの秘密の値なども存在しない。セキュリティの専門家は、forward secrecyを持つ暗号アルゴリズムを、そうでないものよりも推奨している<ref>{{Cite web |author=Ristic |first=Ivan |title=Deploying Forward Secrecy |url=https://community.qualys.com/blogs/securitylabs/2013/06/25/ssl-labs-deploying-forward-secrecy |publisher=SSL Labs |access-date=14 June 2014 |date=2013-06-25}}</ref>。これは、forward secrecyを持っていれば、公開鍵・秘密鍵のペアと結びついた長期秘密鍵が破られたときにも、情報を守ることができるからである。これは諜報機関による大衆監視を防ぐ手段として考えられている。

Ring-LWE鍵交換と[[超特異同種写像ディフィー・ヘルマン]](SIDH) 鍵交換はどちらも、鍵交換ごとのforward secresyに対応している。 Ring-LWEとSIDHはまた、[[ElGamal暗号]]版の[[ディフィー・ヘルマン鍵共有]]を作ることで、forward secrecy無しで用いることもできる。

[[NTRU暗号]]など、この記事の他のアルゴリズムにはforward secrecyの性質はない。

どの認証公開鍵暗号システムもforward secrecyを持った鍵交換をすることができる<ref>{{Cite web |url=https://crypto.stackexchange.com/a/19115 |title=Does NTRU provide Perfect Forward Secrecy? |website=crypto.stackexchange.com}}</ref>。

== Open Quantum Safe project ==
The '''Open Quantum Safe''' ('''OQS''') プロジェクトは2016年後半に始まった、耐量子暗号の開発と試作を目的とするプロジェクトである<ref name="openquantumsafe.org">{{Cite web |url=https://openquantumsafe.org/ |title=Open Quantum Safe |website=openquantumsafe.org}}</ref><ref>{{Cite web |author=Stebila |first=Douglas |title=Post-Quantum Key Exchange for the Internet and the Open Quantum Safe Project |url=http://eprint.iacr.org/2016/1017 |website=Cryptology ePrint Archive, Report 2016/1017, 2016 |access-date=9 April 2017}}</ref>。 '''liboqs'''という一つのライブラリに、現在のポスト量子暗号方式を統合することを目標としている<ref>{{Cite web |url=https://github.com/open-quantum-safe/liboqs |title=liboqs: C library for quantum-resistant cryptographic algorithms |date=26 November 2017}}</ref>。 liboqsは耐量子暗号アルゴリズムの、オープンソースの[[C言語]]ライブラリである。初期は鍵交換アルゴリズムが中心であったが、現在はその他の暗号方式も含んでいる。liboqsはポスト量子鍵交換アルゴリズムのための一般的なAPIを提供し、 様々な実装を集める。 liboqsはまた、ポスト量子暗号の実装を比較するためのテストハーネスやベンチマークのルーチンを含む予定である。それに加え、OQSはliboqsの統合された[[OpenSSL]]も提供している<ref>{{Cite web |url=https://github.com/open-quantum-safe/openssl |title=openssl: Fork of OpenSSL that includes quantum-resistant algorithms and ciphersuites based on liboqs |date=9 November 2017}}</ref>。

2023年3月の段階では、以下の表の鍵交換アルゴリズムがサポートされている<ref name="openquantumsafe.org">{{Cite web |url=https://openquantumsafe.org/ |title=Open Quantum Safe |website=openquantumsafe.org}}</ref>。
{| class="wikitable"
!アルゴリズム
!タイプ
|-
|CRYSTALS-{{仮リンク|Kyber|en|Kyber}}
|Module {{仮リンク|Learning with errors|en|Learning with errors}}
|-
|[[マックエリス暗号|Classic McEliece]]
|goppa符号
|-
|BIKE<ref>{{Cite web |title=BIKE – Bit Flipping Key Encapsulation |url=https://bikesuite.org/ |access-date=2023-08-21 |website=bikesuite.org}}</ref>
|符号暗号
|-
|HQC<ref>{{Cite web |title=HQC |url=https://pqc-hqc.org/ |access-date=2023-08-21 |website=pqc-hqc.org}}</ref><ref>[https://csrc.nist.gov/csrc/media/Events/2022/fourth-pqc-standardization-conference/documents/papers/fast-and-efficient-hardware-impl-of-hqc-pqc2022.pdf Fast and Efficient Hardware Implementation of HQC]</ref>
|符号暗号
|-
|Frodo<ref>{{Cite journal|last=Bos|first=Joppe|last2=Costello|first2=Craig|last3=Ducas|first3=Léo|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|journal=Cryptology ePrint Archive}}</ref><ref>{{Cite web |title=FrodoKEM |url=https://frodokem.org/ |access-date=2023-08-21 |website=frodokem.org |language=en}}</ref>
|Learning with errors
|-
|{{仮リンク|NTRU|en|NTRU}}<ref>{{Cite web |url=https://github.com/NTRUOpenSourceProject/NTRUEncrypt |title=NTRUOpenSourceProject/NTRUEncrypt |website=GitHub |language=en |access-date=2017-04-10}}</ref>
|[[格子暗号]]
|-
|CRYSTALS-Dilithium<ref>{{Cite web |author=Schwabe |first=Peter |title=Dilithium |url=https://pq-crystals.org/dilithium/ |access-date=2023-08-19 |website=pq-crystals.org}}</ref><ref>[https://csrc.nist.gov/CSRC/media/Presentations/Crystals-Dilithium/images-media/CRYSTALS-Dilithium-April2018.pdf Cryptographic Suite for Algebraic Lattices, Digital Signature: Dilithium]</ref>
|Module {{仮リンク|短整数解問題|en|Short integer solution problem}}
|-
|Falcon
|短整数解問題
|-
|SPHINCS+
|ハッシュ暗号
|}
the NIST Post-Quantum Cryptography Standardization Projectの変更によって削除された、過去にサポートされていたアルゴリズムは以下である。
{| class="wikitable"
!Algorithm
!Type
|-
|BCNS15<ref>{{Cite web |author=Stebila |first=Douglas |date=26 Mar 2018 |title=liboqs nist-branch algorithm datasheet: kem_newhopenist |url=https://github.com/open-quantum-safe/liboqs/blob/7cc365a363a05cdb233b9d72d0164c123d7b0b65/docs/algorithms/kem_newhopenist.md |access-date=27 September 2018 |website=GitHub}}</ref>
|{{仮リンク|Ring learning with errors|en|Ring_learning_with_errors|label=}}鍵交換
|-
|{{仮リンク|NewHope|en|NewHope}}<ref>{{Cite web |date=19 Apr 2016 |title=Lattice Cryptography Library |url=https://www.microsoft.com/en-us/research/project/lattice-cryptography-library/ |access-date=27 September 2018 |website=Microsoft Research}}</ref><ref name="newhope">{{Cite web |author=Alkim |first=Erdem <!--|archivedate=Peter--> |year=2015 |title=Post-quantum key exchange – a new hope |url=http://eprint.iacr.org/2015/1092 |access-date=1 September 2017 |publisher=Cryptology ePrint Archive, Report 2015/1092}}</ref>
|{{仮リンク|Ring learning with errors|en|Ring_learning_with_errors|label=}}鍵交換
|-
|SIDH<ref>{{Cite news |title=SIDH Library – Microsoft Research |language=en-US |newspaper=Microsoft Research |url=https://www.microsoft.com/en-us/research/project/sidh-library/ |access-date=2017-04-10}}</ref><ref>{{Cite journal|last=Feo|first=Luca De|last2=Jao|first2=David|last3=Plût|first3=Jérôme|date=2011-01-01|title=Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies|url=https://eprint.iacr.org/2011/506|journal=Cryptology ePrint Archive}}</ref>
|[[超特異同種写像ディフィー・ヘルマン]]
|-
|McBits<ref>{{Cite journal|last=Bernstein|first=Daniel J.|last2=Chou|first2=Tung|last3=Schwabe|first3=Peter|date=2015-01-01|title=McBits: fast constant-time code-based cryptography|url=https://eprint.iacr.org/2015/610|journal=Cryptology ePrint Archive}}</ref>
|誤り訂正符号
|}

== 実装 ==
ポスト量子暗号における難問の一つは、現在のシステムにポスト量子暗号の実装を組み込むことであると考えられている。[[マイクロソフトリサーチ]]による、{{仮リンク|ハードウェアセキュリティモジュール|en|Hardware security module}}を用いた[[公開鍵基盤]]へのPICNICの実装<ref>{{Cite web |url=https://github.com/Microsoft/Picnic/blob/master/spec/design-v1.0.pdf |title=Microsoft/Picnic |website=GitHub |language=en |access-date=2018-06-27}}</ref>が一つの実験として行われている。[[Google]]による {{仮リンク|NewHope|en|NewHope}}アルゴリズムの実装の実験もハードウェアセキュリティモジュールのベンダーによって行われている。2023年8月、Googleは[[チューリッヒ工科大学]]と協同で、ECCとDilithiumのハイブリット署名方式による[[FIDO Alliance|FIDO2]]の秘密鍵の実装を発表した<ref>{{Cite web |title=Toward Quantum Resilient Security Keys |url=https://security.googleblog.com/2023/08/toward-quantum-resilient-security-keys.html |access-date=2023-08-19 |website=Google Online Security Blog |language=en}}</ref>。

2024年2月、[[Apple]]は[[iMessage]]のプロトコルを、ongoing keyingを利用した "PQ3"と呼ばれる、新しいポスト量子暗号プロトコルにアップグレードすることを発表した<ref name="apple-pq3-blog">
{{Cite web |url=https://security.apple.com/blog/imessage-pq3 |title=iMessage with PQ3: The new state of the art in quantum-secure messaging at scale |author=Apple Security Engineering and Architecture (SEAR) |date=February 21, 2024 |website=[[Apple Inc.| Apple Security Research]] |access-date=2024-02-22 |publisher=[[Apple Inc.]] |quote=With compromise-resilient encryption and extensive defenses against even highly sophisticated quantum attacks, PQ3 is the first messaging protocol to reach what we call Level 3 security — providing protocol protections that surpass those in all other widely deployed messaging apps.}}</ref><ref>
{{Cite web |url=https://www.macrumors.com/2024/02/21/apple-announces-imessage-security-upgrade/ |title=Apple Announces 'Groundbreaking' New Security Protocol for iMessage |first=Joe |author=Rossignoi |date=February 21, 2024 |website=[[:en:MacRumors|MacRumors]] |access-date=2024-02-22}}</ref><ref>
{{Cite web |url=https://9to5mac.com/2024/02/21/imessage-quantum-security-ios-17-4/ |title=Apple launching quantum computer protection for iMessage with iOS 17.4, here’s what that means |first=Michael |author=Potuck |date=February 21, 2024 |website=[[:en:9to5Mac|9to5Mac]] |access-date=2024-02-22}}</ref>。Appleは、量子コンピュータはまだ存在しないが、その将来の攻撃や{{仮リンク|Harvest now, decrypt later|en|Harvest now, decrypt later}}の攻撃シナリオを軽減したいと述べた。 Appleによると、PQ3の実装は「ongoing keyingを用いているため、他のすべての広く用いられているメッセージングアプリを上回る」保護を提供するという。Apple は現在のiMessageのすべてのプロトコルを2024年の終わりまでにPQ3に変更する意向を示している。また、メッセージアプリのセキュリティレベルを0から3に分類した基準を提唱している<ref name="apple-pq3-blog" />。

その他の主な実装を下に挙げる。

* {{仮リンク|Bouncy Castle|en|Bouncy Castle (cryptography)}}<ref>[https://downloads.bouncycastle.org/betas Bouncy Castle Betas]</ref>
* liboqs<ref>[https://openquantumsafe.org/liboqs/ Open Quantum Safe]</ref>

== 関連項目 ==

* {{仮リンク|NISTの耐量子暗号標準|en|NIST Post-Quantum Cryptography Standardization}}
* [[量子暗号]] – 量子力学に基づいた暗号
* {{仮リンク|クリプトシュレッディング|en|Crypto-shredding}}
* {{仮リンク|Harvest now, decrypt later|en|Harvest now, decrypt later}}

== 脚注 ==
{{Reflist}}

== 参考文献 ==
* {{Cite book |title=Post-Quantum Cryptography |url=https://www.springer.com/mathematics/numbers/book/978-3-540-88701-0 |publisher=Springer |pages=245 |isbn=978-3-540-88701-0 |year=2008}}
* [http://ecc2011.loria.fr/slides/jao.pdf Isogenies in a Quantum World] {{Webarchive|url=https://web.archive.org/web/20140502063037/http://ecc2011.loria.fr/slides/jao.pdf|date=2014-05-02}}
* [https://www.di.ens.fr/~pnguyen/LCD/LCD_Vadim.pdf On Ideal Lattices and Learning With Errors Over Rings]
* [http://docbox.etsi.org/Workshop/2013/201309_CRYPTO/S03_INDUSTRY_SESSION/PITNEYBOWES_PINTSOV.pdf Kerberos Revisited: Quantum-Safe Authentication]
* [https://github.com/Microsoft/Picnic/blob/master/spec/design-v1.0.pdf The picnic signature scheme]
* {{Cite journal|author=高木剛|year=2017|title=ポスト量子暗号の構成法とその安全性評価|url=https://www.jstage.jst.go.jp/article/essfr/11/1/11_17/_article/-char/ja/|journal=Fundamentals Review|volume=2017年11巻1号|page=p.17-27}}
* {{Cite journal|author=宮地充子|year=2021|title=楕円曲線の理論的及び実用的可能性 ―楕円曲線暗号から耐量子暗号まで―|url=https://www.jstage.jst.go.jp/article/essfr/14/4/14_329/_article/-char/ja/|journal=Fundamentals Review|volume=2021年14巻4号|page=p.329-336}}
* {{Cite journal|author=國廣昇|year=2022|title=量子計算機と暗号：耐量子計算機暗号への移行|url=https://www.jstage.jst.go.jp/article/jssmjournal/35/3/35_18/_article/-char/ja|journal=日本セキュリティ・マネジメント学会誌|volume=35 巻 3 号|page=p.18-24}}
* {{Cite journal|author=高木剛|year=2023|title=量子計算機時代のセキュリティ  ――耐量子計算機暗号の動向――|url=https://app.journal.ieice.org/trial/106_11/k106_11_966/index.html|journal=電子情報通信学会 - IEICE会誌|volume=Vol.106 No.11}}
* {{Cite journal|author=細山田光倫|year=2023|title=共通鍵暗号技術のポスト量子安全性について|url=https://www.jstage.jst.go.jp/article/essfr/17/1/17_59/_article/-char/ja|journal=Fundamentals Review|volume=2023年17巻1号|page=p.59-71}}
* {{Cite journal|url=https://www.nic.ad.jp/ja/newsletter/No81/0800.html|journal=JPNIC ニュースレター|volume=No.81|author=矢内直人|year=2022|title=暗号技術から見る量子計算機のいま}}
* {{Cite journal|author=矢内直人|year=2022|title=耐量子計算機暗号とは|url=https://www.nic.ad.jp/ja/newsletter/No82/0800.html|journal=JPNIC ニュースレター|volume=No.82}}
* {{Cite book|和書 |title=耐量子計算機暗号 |year=2020 |publisher=森北出版 |month=8 |author=縫田光司 |isbn=978-4-627-87211-0}}
* {{Cite book|和書 |title=暗号と量子コンピュータ |date=2019-08-25 |publisher=オーム社 |author=高木剛 |issn= |isbn=978-4-274-22410-2}}
* {{Cite book|和書 |title=暗号の理論と技術　量子時代のセキュリティ理解のために |date=2024-05-02 |publisher=講談社 |editor=國廣昇 |isbn=978-4-06-535635-7 |series=KS理工学専門書}}
* {{Cite book|和書 |title=現代暗号の誕生と発展 |date=2019-02-01 |publisher=近代科学社 |author=岡本龍明 |isbn=978-4-7649-0579-5}}
== 外部リンク ==
* [http://www.pqcrypto.org/ PQCrypto, the post-quantum cryptography conference]
* [http://www.etsi.org/news-events/news/947-2015-03-news-etsi-launches-quantum-safe-cryptography-specification-group ETSI Quantum Secure Standards Effort]
* [http://csrc.nist.gov/groups/ST/post-quantum-crypto/ NIST's Post-Quantum crypto Project]
* [https://ianix.com/pqcrypto/pqcrypto-deployment.html PQCrypto Usage & Deployment]
* [https://www.siscertifications.com/iso-27001-certification/ ISO 27001 Certification Cost]

{{DEFAULTSORT:ほすとりようしあんこう}}
[[Category:ポスト量子暗号|*]]
[[Category:未査読の翻訳があるページ]]