ポスト量子暗号

ポスト量子暗号（ポストりょうしあんごう、、略してPQC）とは、量子コンピュータによる暗号解読に対して安全だと考えられる暗号アルゴリズム (主に公開鍵暗号アルゴリズム) のことである。耐量子計算機暗号（たいりょうしけいさんきあんごう、、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年にを発明し、何度でも使うことのできるハッシュ署名 (Naor-Yung方式)を設計した。これは、落とし戸を利用しない初の署名方式である。

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

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

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

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

格子暗号 – Ring-LWE署名 Ring-LWEのあるバージョンには、(SVP) の困難性への安全性帰着がある。最短ベクトル問題はNP困難であることが知られている。証明可能な安全性帰着をもつRing-LWEシステムもあり、たとえばGüneysu、Lyubashevsky、Pöppelmannによる論文で定義されているLyubashevsky's Ring-LWE署名などが挙げられる。GLYPH署名方式はGüneysu、Lyubashevsky、Pöppelmann (GLP)署名の発表後の研究結果を考慮に入れた、GLP署名の変種である。もう一つのRing-LWE署名はRing-TESLAである。LWEの「脱ランダム化された変種」として、Learning with Rounding (LWR)が挙げられる。ここでは「ガウス分布のような分布からの小さいエラーのサンプリングを排除し、決定性のエラーを用いることで速度を、また帯域の向上を行っている」。LWEが下位ビットを隠すために小さなエラーを加えているのに対して、LWRはそのために丸め操作を利用している。

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

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

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

それゆえ、既知の難問へと安全性帰着が行えるハッシュ関数を使った場合、Merkle署名方式の安全性からその難問への帰着が存在する。

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

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

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

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

比較多くのポスト量子暗号が持つ特徴の一つは、一般的な「プレ量子」公開鍵アルゴリズムよりも大きな鍵長を必要とすることである。鍵長、計算上の効率性、暗号文・署名のサイズの間にはしばしばトレードオフが存在する。以下の表は、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暗号には、係数の613次多項式で表現される鍵を用いることを推奨している。これは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は、最低の長さ、の次元、のエラーを訂正できるゴッパ符号を用いることを推奨している。これらのパラメータによって、マックエリス暗号の公開鍵は組織生成行列で表され、その単位行列でないパートのサイズは bitになる。対応する秘密鍵は、の個の要素からなる符号の台および個の係数の生成多項式からなり、そのサイズは92,027bit になる。

同グループはまた、符号長以上、次元以上, 訂正能力の擬巡回MDPC (QC-MDPC) 符号の利用も研究している。これらのパラメータで設計されたマックエリス暗号の公開鍵は、組織生成行列の単位行列でないパートの最初の行で表現され、そのサイズは bitになる。秘密鍵は, 擬巡回なパリティ検査行列で、その列にはの1が含まれる（また、その行には最大でも2倍の1が含まれる）。そのサイズは、最初の行の非ゼロ係数の位置で表現すると、高々 bitになる。

Barreto et al. は符号長以上, 次元 , エラー訂正能力の二元ゴッパ符号の利用を推奨している。これらのパラメータによって生成されたマックエリス暗号の公開鍵は、組織生成行列で表され、その単位行列でないパートのサイズは bitになる。対応する秘密鍵は、の個の要素からなる符号の台および個の係数の生成多項式からなり、そのサイズは40,476bit になる。

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

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

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-KyberModule 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実用化の先駆例として注目される。

ポスト量子暗号

Źródło i licencja