ポスト量子暗号

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

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

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

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

 アルゴリズム 
ポスト量子暗号の研究には、大きく分けて6つのアプローチがある。

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

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

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

上で述べた方式はすべて一度、もしくは限られた回数の署名であるが、と は1989年にを発明し、何度でも使うことのできるハッシュ署名 (the Naor-Yung scheme)を設計した(the first such signature that does not require trapdoor properties)。

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

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

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

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

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

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

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

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

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

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

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

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

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

 比較 
多くのポスト量子暗号が持つ特徴の一つは、一般的な「プレ量子」公開鍵アルゴリズムよりも大きな鍵長を必要とすることである。鍵長、計算上の効率性、暗号テキスト・署名テキストのサイズの間にはしばしばトレードオフが存在する。以下の表は、128bitのにおけるポスト量子暗号方式の鍵サイズを比較したものである。  
アルゴリズムタイプ公開鍵秘密鍵署名NTRU暗号格子暗号 B BStreamlined NTRU Prime格子暗号 BRainbow多変数暗号124 kB95 kBSPHINCSハッシュ署名1 kB1 kB41 kBSPHINCS+SPHINCS+: Submission to the NIST post-quantum projectハッシュ署名 B B8 kBBLISS-II格子暗号7 kB2 kB5 kBGLP-Variant GLYPH SignatureRing-LWE2 kB0.4 kB1.8 kBRing-LWE2 kB2 kBゴッパ符号を用いたマックエリス暗号符号暗号1 MB11.5 kBRandom Linear Code based encryptionRLCE115 kB3 kBQuasi-cyclic MDPC-based McEliece符号暗号 B BSIDH同種写像暗号 B BSIDH (compressed keys)同種写像暗号 B B3072-bit Discrete Log非ポスト量子暗号 B B B256-bit 楕円曲線暗号非ポスト量子暗号 B B B
ポスト量子暗号の選択における実用的な考慮事項としては、インターネット上で送信する公開鍵のサイズがある。この観点では、Ring-LWE、NTRU暗号、SIDHアルゴリズムが1kB以下で利便性が良い。ハッシュ署名暗号の公開鍵は5kB以下、 MDPC-based McElieceは約1kBである。その一方、Rainbow 方式は約125kB、ゴッパ符号を用いたマックエリス暗号は1MB近くの鍵サイズが必要となる。

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

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

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

 格子暗号 – NTRU暗号 
Hirschhorn、Hoffstein、Howgrave-Graham、Whyteらは、128bitののNTRU暗号にはkey represented as a degree 613 polynomial with coefficientsを用いることを推奨している。これは6130bitの公開鍵となる。これに対応する秘密鍵は6743bitである。

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

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

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

bitの組織生成行列となる。The corresponding private key, which consists of the code support with  elements from  and a generator polynomial of with  coefficients from ,will be 92,027 bits in length.

The group is also investigating the use of Quasi-cyclic MDPC codes of length at least  and dimension at least , and capable of correcting  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  bits. The private key, a quasi-cyclic parity-check matrix with  nonzero entries on a column (or twice as much on a row), takes no more than  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  and dimension at least , and capable of correcting  errors. With these parameters the public key for the McEliece system will be a systematic generator matrix whose non-identity part takes  bits. The corresponding private key, which consists of the code support with  elements from  and a generator polynomial of with  coefficients from 

, will be 40,476 bits in length.

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

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

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

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

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

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

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

2023年3月の段階では、以下の表の鍵交換アルゴリズムがサポートされている。
アルゴリズムタイプCRYSTALS-Module Classic McEliecegoppa符号BIKE符号暗号HQCFast and Efficient Hardware Implementation of HQC符号暗号FrodoLearning with errors格子暗号CRYSTALS-DilithiumCryptographic Suite for Algebraic Lattices, Digital Signature: DilithiumModule Falcon短整数解問題SPHINCS+ハッシュ暗号
the NIST Post-Quantum Cryptography Standardization Projectの変更によって削除された、過去にサポートされていたアルゴリズムは以下である。
AlgorithmTypeBCNS15鍵交換鍵交換SIDH超特異同種写像ディフィー・ヘルマンMcBits誤り訂正符号

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

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

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

 Bouncy Castle Betas
 liboqsOpen Quantum Safe

 日本での医療分野への適用 
 2023年3月、凸版印刷と国立研究開発法人情報通信研究機構（NICT）は、耐量子計算機暗号（PQC）を組み込んだプライベート認証局を構築し、医療データの長期保管・交換システム（H-LINCOS）に適用した。これは、電子カルテなどの機密データを量子コンピュータの脅威から守るための実証実験で、秘密分散技術や量子暗号と組み合わせた総合的なセキュリティ基盤を実現した。この成果は、医療分野でのPQC実用化の先駆例として注目される。

 関連項目 


 量子暗号 – 量子力学に基づいた暗号

 Harvest now, decrypt later

 脚注 

 参考文献 

 Isogenies in a Quantum World 
 On Ideal Lattices and Learning With Errors Over Rings
 Kerberos Revisited: Quantum-Safe Authentication
 The picnic signature scheme











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

*
Category:未査読の翻訳があるページ