ポスト量子暗号

この項目「ポスト量子暗号」は途中まで翻訳されたものです。（原文：[1]） 翻訳作業に協力して下さる方を求めています。ノートページや履歴、翻訳のガイドラインも参照してください。要約欄への翻訳情報の記入をお忘れなく。（2024年4月）

ポスト量子暗号 (ポストりょうしあんごう、英:Post-quantum cryptography、略してPQC)とは、量子コンピュータによる暗号解読に対して安全だと考えられる暗号アルゴリズム (主に公開鍵暗号アルゴリズム) のことである。耐量子暗号(たいりょうしあんごう、英:Quantum-resistant cryptgraphy、quantum-proof cryptgraphy、もしくはquantum-safe cryptgraphy)とも呼ばれる。現在よく使われているアルゴリズムの問題は、そのセキュリティーが素因数分解、離散対数、楕円曲線暗号という３つの数学的な難題に依拠していることにある。 これらの問題はすべて、十分に強力な量子コンピュータとショアのアルゴリズム^[1][2]や、それよりも高速で必要とする量子ビットも少ないアルゴリズム^[3]を用いることで容易に解くことができる。

2023年時点では、量子コンピュータの性能は広く用いられている暗号アルゴリズムを破る段階には達していないが^[4]、暗号技術者たちは「Q-Day」(量子コンピュータが現在の暗号アルゴリズムを破ることができるようになる日)に備えて新しいアルゴリズムを開発している。この活動は、2006年から開催されている国際会議PQCrypto、欧州電気通信標準化機構(ETSI)の耐量子暗号に関するワークショップ、量子コンピューティング研究所（英語版）などを通して大学、産業から関心を集めている^[5][6][7]。 存在が広く噂されているHarvest now, decrypt later（英語版）攻撃も、早急なポスト量子暗号導入への理由となっている^[8][9][10]。

量子コンピュータが現在の公開鍵暗号アルゴリズムへの脅威となっている一方で、現在の多くの共通鍵暗号やハッシュ関数は量子コンピュータからの攻撃に対して比較的安全と考えられている^[2][11]。 量子コンピュータはグローバーのアルゴリズムによって共通鍵暗号の解読速度を上げることができるものの、これに対しては鍵長を倍にすることが効果的な対策となる^[12]。そのため、ポスト量子共通鍵暗号には現在の共通鍵暗号と大きく異なったものを用いる必要はない。

2024年8月13日、アメリカ国立標準技術研究所(NIST)は初めて耐量子計算機暗号標準(Post-Quantum Cryptography Standards)を発表した。これには3つの耐量子暗号アルゴリズムが含まれている。^[13][14]

ポスト量子暗号の研究には、大きく分けて6つのアプローチがある。^[2][6]

このアプローチにはLearning with errors(LWE)（英語版）、Ring learning with errors(ring-LWE)（英語版）^[15][16][17] 、Ring learning with errors鍵交換、Ring learning with errors署名、NTRU暗号やGGH暗号方式、NTRUSign（英語版）、BLISS署名方式（英語版）などの暗号方式がある。NTRU暗号など、このうちのいくつかはまだ効果的な攻撃方法は見つかっていない。ring-LWEなどのその他のアルゴリズムは、最悪時の格子問題と同等の安全性があることが分かっている。^[18] 欧州委員会から支援を受けたThe Post Quantum Cryptography Study Groupは、NTRU暗号ではなく、Stehle–Steinfeld variant of NTRUを標準化に向けて研究すべきだと提案している^[19][20]。現在のところ、NTRUは特許で保護されている。研究では、NTRU暗号は他の格子暗号アルゴリズムよりも安全な要素が多いとされている^[21]。

多変数方程式を解くことが困難であることを利用したRainbow (Unbalanced oil and vinegar（英語版）)方式がある。多変数方程式を用いた安全な暗号方式を作る試みは失敗を重ねてきた。しかし、Rainbowは多変数方程式によるデジタル署名方式の基礎を築くことに成功した^[22] 。Rainbow方式は特許で保護されている。　

これには、ランポート署名、Merkle署名方式（英語版）、XMSS、^[23] SPHINCS、^[24] WOTS方式などがある。ハッシュによるデジタル署名は1970年代後半にラルフ・マークルによって発明され、 RSAやDSAといった数論的なデジタル署名に代わる方式として研究されてきた。これらの方式の大きな欠点は、どのハッシュ暗号でも、公開鍵と対となる秘密鍵を用いて署名できる数に限りがあるという点である。そのため、耐量子暗号への関心が高まるまでは、この方式はあまり注目を集めてこなかった。Merkle署名方式は特許で保護されておらず^[要出典]、この方式で使うことのできる特許で保護されていないハッシュ関数は多く存在する。ヨハネス・ブーフマン（英語版）の率いる研究チームによって開発された、ステートフルなハッシュ署名方式であるXMSSはRFC 8391に記述されている^[25]。

上で述べた方式はすべて一度、もしくは限られた回数の署名であるが、Moni Naor（英語版）とモチ・ユング（英語版） は1989年にUOWHF（英語版）を発明し、何度でも使うことのできるハッシュ署名 (the Naor-Yung scheme)^[26]を設計した(the first such signature that does not require trapdoor properties)。

これにはマックエリス暗号、Niederreiter暗号システム（英語版） やそれに関連するCourtois, Finiasz and Sendrier署名方式など、誤り訂正符号に依拠した暗号方式が含まれる。オリジナルなマックエリス暗号はランダムなGoppa符号（英語版） を使っており、これは40年以上もの時間と研究を経た今でも安全と考えられている。 しかし、鍵サイズを減らすために符号に構造を追加しようとして作られた、異なるバリエーションのマックエリス暗号は、その多くが安全ではないことが分かっている^[27]。 欧州委員会の支援するThe Post Quantum Cryptography Study Groupは、量子コンピュータの攻撃に長時間耐えることのできる暗号システムの候補として、マックエリス公開鍵暗号を推薦している^[19]。

有限体上の楕円曲線の同種写像グラフ(と高次元アーベル多様体)、特に超特異同種写像グラフ（英語版）の性質を用いた暗号システムである。この分野でよく知られているのはディフィー・ヘルマン鍵共有と似ているCSIDH鍵共有であり、これは現在広く使われているディフィー・ヘルマン鍵共有や楕円曲線ディフィー・ヘルマン鍵共有の耐量子代替として単純に使うことができる^[28]。また、超特異楕円曲線とあるタイプの四元数環の極大整環が圏同値であることに基づいた署名方式であるSQISignも知られている^[29]。もう一つのよく知られた方式である超特異同種写像ディフィー・ヘルマン(SIDH/SIKE)は2022年に破られた^[30]。 この攻撃はSIDH/SIKE系の方式に特有のため、他の同種写像暗号に対して一般的に用いることはできない^[31]。

十分に大きな鍵長を使った場合、AESやSNOW 3G（英語版）のような共通鍵暗号方式はすでに量子コンピュータの攻撃に耐えられる。^[32]その上、ケルベロス認証や3GPPモバイルネットワーク認証といった、公開鍵暗号ではなく共通鍵暗号を用いた鍵管理システムやプロトコルも量子コンピュータの攻撃に対して本質的に安全である。ケルベロス認証は既に世界中に普及しているため、いち早くポスト量子暗号に対応する効率的な方法として、ケルベロス認証のような鍵管理システムを広く用いることを推奨する研究者もいる^[33]。

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

Ring-LWEのあるバージョンには、最短の格子を求める最短ベクトル問題（英語版）(SVP)のセキュリティーに帰着できるsecurity reductionがある。最短ベクトル問題はNP困難であることが知られている^[34]。Güneysu、Lyubashevsky、Pöppelmannによる論文で定義されているLyubashevsky's ring-LWE署名^[16]など、証明可能なsecurity reductionのあるring-LWEシステムもある。GLYPH署名方式はGüneysu、Lyubashevsky、Pöppelmann (GLP)署名の発表後の研究結果を考慮に入れた、GLP署名のバリエーションである。もう一つのRing-LWE署名はRing-TESLAである^[35]。LWEの「脱ランダム化されたバリエーション」であるLearning with Rounding (LWR)は「速度(by eliminating sampling small errors from a Gaussian-like distribution with deterministic errors) と帯域の向上」がなされている^[36]。LWEが下位ビットを隠すために小さなエラーを加えているのに対して、LWRはそのために丸め操作を利用している。

NTRU暗号方式とBLISS^[37]署名は、格子における最近ベクトル問題(CVP)と関係しているが、おそらく等価ではないと考えられている。CVPはNP困難であることが知られている。欧州委員会から支援を受けているThe Post Quantum Cryptography Study Groupは、長期間利用できる暗号方式として、オリジナルのNTRUよりも、security reductionのあるStehle–SteinfeldバージョンのNTRUを研究すべきだと提唱している^[38]。

Unbalanced oil and vinegar（英語版）暗号方式は有限体上の多変数多項式に基づく非対称的な暗号プリミティブである。Bulygin、Petzoldt、Buchmannらは一般的な多変数二次UOVシステムがNP困難な多変数二次方程式問題に換算されることを示している。^[39]

2005年、Luis GarciaはMerkle署名方式がその基礎となっているハッシュ関数の安全性に換算できることを示した。Garciaは論文内で、もし一方向ハッシュ関数が計算上存在するなら、Merkle署名は安全であるだろうと示した。^[40]

それゆえ、 既知の難問へとセキュリティ的に換算できるハッシュ関数を使った場合、Merkle署名方式のSecurity reductionはその難問であることになる^[41]。

欧州委員会から支援を受けているThe Post Quantum Cryptography Study Groupは、量子コンピュータの攻撃を長期間防ぐことのできる方式としてMerkle署名方式を推薦している^[19]。

マックエリス暗号方式は、シンドローム復号問題(SDP)にセキュリティ的に換算できる。SDPはNP困難であることが知られている^[42]。欧州委員会から支援を受けているThe Post Quantum Cryptography Study Groupは、この暗号方式を量子コンピュータの攻撃を長期間防ぐことのできる方式として推薦している。^[19]

2016年、Wangはマックエリス暗号に基づいたランダム線形符号暗号方式であるRLCE^[43]を提唱した。RLCE方式は、元となっている線型符号の生成行列にランダムな列を挿入することで、リード・ソロモン符号など、いかなる線型符号を用いても構築することができる。

この安全性は、２つの超特異曲線間に同じ数の点で同種写像を構築する問題と関連している。最近の研究では、DelfsとGalbraithがこの問題は鍵交換の発明者が示したのと同様に困難であることを示している^[44]。既知のNP困難な問題とのsecurity reductionは無い。

多くのポスト量子暗号が持つ特徴の一つは、一般的な「プレ量子」公開鍵アルゴリズムよりも大きな鍵長を必要とすることである。鍵長、計算上の効率性、暗号テキスト・署名テキストのサイズの間にはしばしばトレードオフが存在する。以下の表は、128bitのセキュリティレベル（英語版）におけるポスト量子暗号方式の鍵サイズを比較したものである。

ポスト量子暗号の選択における実用的な考慮事項としては、インターネット上で送信する公開鍵のサイズがある。この観点では、Ring-LWE、NTRU暗号、SIDHアルゴリズムが1kB以下で利便性が良い。ハッシュ署名暗号の公開鍵は5kB以下、 MDPC-based McElieceは約1kBである。その一方、Rainbow 方式は約125kB、ゴッパ符号を用いたマックエリス暗号は1MB近くの鍵サイズが必要となる。

LWEとRing-LWEを鍵交換に用いるアイデアの基礎は、Jintai Dingによって2011年にシンシナティ大学で提唱され、特許出願された。この基本的なアイデアは行列の乗法の結合性に基づいており、エラーはセキュリティを与えるために利用される。この論文^[54] は、2012年に仮特許出願が提出された後、2012年に発表された。

2014年、Peikert^[55]はDingによる基本的なアイデアを発展させた鍵交換方式を発表した。これは、丸めのため1ビットのシグナルを追加して送るという新しいアイディアを用いている。128ビット以上のセキュリティレベル（英語版）のために、Singhは6956bitの公開鍵を持つパラメーターセットを Peikertの方式に提案した^[56]。これに対応する秘密鍵はおよそ14,000ビットとなる。

2015年、Eurocrypt 2015において、Dingの基本的なアイデアから発展した、証明可能な前方秘匿性を持つ認証鍵交換方式が発表された^[57]。これはCrypto2005におけるHMQV^[58]構築を拡張したものである。80bitから350bitまでの異なるセキュリティレベルに対するパラメーターと、それに対応する鍵サイズも論文中で示されている^[57]。

Hirschhorn、Hoffstein、Howgrave-Graham、Whyteらは、128bitのセキュリティレベル（英語版）のNTRU暗号にはkey represented as a degree 613 polynomial with coefficients${\displaystyle {\bmod {\left(2^{10}\right)}}}$を用いることを推奨している。これは6130bitの公開鍵となる。これに対応する秘密鍵は6743bitである^[45]。

Petzoldt、BulyginとBuchmannは、Rainbow多変数二次方程式署名方式において、128bitのセキュリティレベルで最小の署名サイズにするには、${\displaystyle \mathbb {F} _{31}}$上の方程式と991,000bitをやや上回るサイズの公開鍵、740,000bitをやや上回るサイズの秘密鍵と、424bitの長さのデジタル署名を用いることを推奨している^[46]。

Naor ShenhavとWoolによるフラクタルMerkle木を用いた方式では、100万メッセージに署名するためのハッシュ署名において128bitのセキュリティレベルを得るには、約36,000bitの公開鍵と秘密鍵のサイズとなる^[59]。

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

${\displaystyle k\times (n-k)=8373911}$bitの組織生成行列となる。The corresponding private key, which consists of the code support with ${\displaystyle n=6960}$ elements from ${\displaystyle \mathrm {GF} (2^{13})}$ and a generator polynomial of with ${\displaystyle t=119}$ coefficients from ${\displaystyle \mathrm {GF} (2^{13})}$,will be 92,027 bits in length^[19].

The group is also investigating the use of Quasi-cyclic MDPC codes of length at least ${\displaystyle n=2^{16}+6=65542}$ and dimension at least ${\displaystyle k=2^{15}+3=32771}$, and capable of correcting ${\displaystyle t=264}$ 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 ${\displaystyle k=32771}$ bits. The private key, a quasi-cyclic parity-check matrix with ${\displaystyle d=274}$ nonzero entries on a column (or twice as much on a row), takes no more than ${\displaystyle d\times 16=4384}$ 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 ${\displaystyle n=3307}$ and dimension at least ${\displaystyle k=2515}$, and capable of correcting ${\displaystyle t=66}$ errors. With these parameters the public key for the McEliece system will be a systematic generator matrix whose non-identity part takes ${\displaystyle k\times (n-k)=1991880}$ bits.^[60] The corresponding private key, which consists of the code support with ${\displaystyle n=3307}$ elements from ${\displaystyle \mathrm {GF} (2^{12})}$ and a generator polynomial of with ${\displaystyle t=66}$ coefficients from

${\displaystyle \mathrm {GF} (2^{12})}$, will be 40,476 bits in length.

セキュリティレベル（英語版）で128bitの超特異同種写像ディフィー・ヘルマン(SIDH) 方式には、De Feo、Jao、Plutらは supersingular curve modulo a 768-bit primeを用いることを推奨している^[61]。Azarderakhsh、Jao、Kalach、Koziel、Leonardiらによる2016年3月の論文では、送信するビット数を半分に減らす方法が示されている。その後、Costello、Jao、Longa、Naehrig、Renes 、Urbanikらの論文ではさらに改良され、公開鍵のサイズが2640bitに圧縮されたSIDHプロトコルのバージョンが完成している^[53]。 これは非量子暗号であるRSA暗号やディフィー・ヘルマン鍵共有とほぼ同じサイズの送信量で、同等のセキュリティレベルである^[62]。

一般的に、対称鍵暗号システムで128bitのセキュリティレベル（英語版）には、256bitの鍵サイズを用いる。量子コンピュータによる一般的な対称鍵暗号への最も効率の良い攻撃方法はグローバーのアルゴリズムを用いたもので、これは鍵サイズの平方根と同等の計算量が必要となる。暗号化された鍵を、復号化するための対称鍵を持ったデバイスに送信するためにも約256bitが必要となる。対称鍵がポスト量子暗号において最も小さい鍵サイズとなるのは明らかである^{[要出典][citation needed]}。

公開鍵暗号システムは、鍵共有においてセッションごとにランダムな公開鍵を生成したときには、完全なforward secrecy(前方秘匿性) と呼ばれる性質を持つ。すなわち、一つのメッセージのセキュリティが破られても、その他のメッセージのセキュリティは破られないし、複数のメッセージのセキュリティを破ることのできるような一つの秘密の値なども存在しない。セキュリティの専門家は、forward secrecyを持つ暗号アルゴリズムを、そうでないものよりも推奨している^[63]。これは、forward secrecyを持っていれば、公開鍵・秘密鍵のペアと結びついた長期秘密鍵が破られたときにも、情報を守ることができるからである。これは諜報機関による大衆監視を防ぐ手段として考えられている。

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

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

どの認証公開鍵暗号システムもforward secrecyを持った鍵交換をすることができる^[64]。

The Open Quantum Safe (OQS) プロジェクトは2016年後半に始まった、耐量子暗号の開発と試作を目的とするプロジェクトである^[65][66]。 liboqsという一つのライブラリに、現在のポスト量子暗号方式を統合することを目標としている^[67]。 liboqsは耐量子暗号アルゴリズムの、オープンソースのC言語ライブラリである。初期は鍵交換アルゴリズムが中心であったが、現在はその他の暗号方式も含んでいる。liboqsはポスト量子鍵交換アルゴリズムのための一般的なAPIを提供し、 様々な実装を集める。 liboqsはまた、ポスト量子暗号の実装を比較するためのテストハーネスやベンチマークのルーチンを含む予定である。それに加え、OQSはliboqsの統合されたOpenSSLも提供している^[68]。

2023年3月の段階では、以下の表の鍵交換アルゴリズムがサポートされている^[65]。

the NIST Post-Quantum Cryptography Standardization Projectの変更によって削除された、過去にサポートされていたアルゴリズムは以下である。

ポスト量子暗号における難問の一つは、現在のシステムにポスト量子暗号の実装を組み込むことであると考えられている。マイクロソフトリサーチによる、ハードウェアセキュリティモジュール（英語版）を用いた公開鍵基盤へのPICNICの実装^[82]が一つの実験として行われている。Googleによる NewHope（英語版）アルゴリズムの実装の実験もハードウェアセキュリティモジュールのベンダーによって行われている。2023年8月、Googleはチューリッヒ工科大学と協同で、ECCとDilithiumのハイブリット署名方式によるFIDO2の秘密鍵の実装を発表した^[83]。

2024年2月、AppleはiMessageのプロトコルを、ongoing keyingを利用した "PQ3"と呼ばれる、新しいポスト量子暗号プロトコルにアップグレードすることを発表した^[84][85][86]。Appleは、量子コンピュータはまだ存在しないが、その将来の攻撃やHarvest now, decrypt later（英語版）の攻撃シナリオを軽減したいと述べた。 Appleによると、PQ3の実装は「ongoing keyingを用いているため、他のすべての広く用いられているメッセージングアプリを上回る」保護を提供するという。Apple は現在のiMessageのすべてのプロトコルを2024年の終わりまでにPQ3に変更する意向を示している。また、メッセージアプリのセキュリティレベルを0から3に分類した基準を提唱している^[84]。

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

• Bouncy Castle（英語版）^[87]
• liboqs^[88]

• NISTの耐量子暗号標準（英語版）
• 量子暗号 – 量子力学に基づいた暗号
• クリプトシュレッディング（英語版）
• Harvest now, decrypt later（英語版）

• Post-Quantum Cryptography. Springer. (2008). pp. 245. ISBN 978-3-540-88701-0. https://www.springer.com/mathematics/numbers/book/978-3-540-88701-0 
• Isogenies in a Quantum World Archived 2014-05-02 at the Wayback Machine.
• On Ideal Lattices and Learning With Errors Over Rings
• Kerberos Revisited: Quantum-Safe Authentication
• The picnic signature scheme
• 高木剛 (2017). “ポスト量子暗号の構成法とその安全性評価”. Fundamentals Review 2017年11巻1号: p.17-27. https://www.jstage.jst.go.jp/article/essfr/11/1/11_17/_article/-char/ja/. 
• 宮地充子 (2021). “楕円曲線の理論的及び実用的可能性 ―楕円曲線暗号から耐量子暗号まで―”. Fundamentals Review 2021年14巻4号: p.329-336. https://www.jstage.jst.go.jp/article/essfr/14/4/14_329/_article/-char/ja/. 
• 國廣昇 (2022). “量子計算機と暗号：耐量子計算機暗号への移行”. 日本セキュリティ・マネジメント学会誌 35 巻 3 号: p.18-24. https://www.jstage.jst.go.jp/article/jssmjournal/35/3/35_18/_article/-char/ja. 
• 高木剛 (2023). “量子計算機時代のセキュリティ ――耐量子計算機暗号の動向――”. 電子情報通信学会 - IEICE会誌 Vol.106 No.11. https://app.journal.ieice.org/trial/106_11/k106_11_966/index.html. 
• 細山田光倫 (2023). “共通鍵暗号技術のポスト量子安全性について”. Fundamentals Review 2023年17巻1号: p.59-71. https://www.jstage.jst.go.jp/article/essfr/17/1/17_59/_article/-char/ja. 
• 矢内直人 (2022). “暗号技術から見る量子計算機のいま”. JPNIC ニュースレター No.81. https://www.nic.ad.jp/ja/newsletter/No81/0800.html. 
• 矢内直人 (2022). “耐量子計算機暗号とは”. JPNIC ニュースレター No.82. https://www.nic.ad.jp/ja/newsletter/No82/0800.html. 
• 縫田光司『耐量子計算機暗号』森北出版、2020年8月。ISBN 978-4-627-87211-0。 
• 高木剛『暗号と量子コンピュータ』オーム社、2019年8月25日。ISBN 978-4-274-22410-2。 
• 國廣昇 編『暗号の理論と技術　量子時代のセキュリティ理解のために』講談社〈KS理工学専門書〉、2024年5月2日。ISBN 978-4-06-535635-7。 
• 岡本龍明『現代暗号の誕生と発展』近代科学社、2019年2月1日。ISBN 978-4-7649-0579-5。 

• PQCrypto, the post-quantum cryptography conference
• ETSI Quantum Secure Standards Effort
• NIST's Post-Quantum crypto Project
• PQCrypto Usage & Deployment
• ISO 27001 Certification Cost