ポスト量子暗号

量子暗号は暗号方式に量子重ね合わせを利用した暗号です。ポスト量子暗号とは異なります。

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

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

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

アルゴリズム

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

格子暗号

このアプローチにはLearning with errors(LWE)、Ring learning with errors(ring-LWE) 、Ring learning with errors鍵交換、Ring learning with errors署名、NTRU暗号やGGH暗号方式、NTRUSign、BLISS署名方式などの暗号方式がある。NTRU暗号など、このうちのいくつかはまだ効果的な攻撃方法は見つかっていない。 Others like the ring-LWE algorithms have proofs that their security reduces to a worst-case problem. 欧州委員会から支援を受けたThe Post Quantum Cryptography Study Groupは、NTRU暗号ではなく、Stehle–Steinfeld variant of NTRUを標準化に向けて研究すべきだと提案している。現在のところ、、NTRUは特許で保護されている。研究では、NTRU暗号は他の格子暗号アルゴリズムよりも安全な要素が多いとされている。

多変数暗号

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

ハッシュ暗号

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

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

符号暗号

これにはマックエリス暗号、Niederreiter暗号システム やそれに関連するCourtois, Finiasz and Sendrier署名方式など、誤り訂正符号に依拠した暗号方式が含まれる。オリジナルなマックエリス暗号はランダムなGoppa符号 を使っており、これは40年以上もの時間と研究を経た今でも安全と考えられている。 However, many variants of the McEliece scheme, which seek to introduce more structure into the code used in order to reduce the size of the keys, have been shown to be insecure. 欧州委員会の支援するThe Post Quantum Cryptography Study Groupは、量子コンピュータの攻撃に長時間耐えることのできる暗号システムの候補として、マックエリス公開鍵暗号を推薦している。

同種写像暗号

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

共通鍵暗号の耐量子性

十分に大きな鍵長を使った場合、AESやSNOW 3Gのような共通鍵暗号方式はすでに量子コンピュータの攻撃に耐えられる。その上、ケルベロス認証や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 sponsored by the European Commission suggested that the Stehle–Steinfeld variant of NTRU, which does have a security reduction be studied for long term use instead of the original NTRU algorithm.

多変数暗号 – Unbalanced oil and vinegar

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は無い。

比較

多くのポスト量子暗号が持つ特徴の一つは、一般的な「プレ量子」公開鍵アルゴリズムよりも大きな鍵長を必要とすることである。鍵長、計算上の効率性、暗号テキスト・署名テキストのサイズの間にはしばしばトレードオフが存在する。The table lists some values for different schemes at a 128-bit post-quantum security level.

Algorithm	Type	Public Key	Private Key	Signature
NTRU暗号	格子暗号	7002766250000000000♠766.25 B	7002842875000000000♠842.875 B
Streamlined NTRU Prime	格子暗号	7002154000000000000♠154 B
Rainbow	多変数暗号	7005124000000000000♠ 124 kB	7004950000000000000♠ 95 kB
SPHINCS	ハッシュ署名	7003100000000000000♠ 1 kB	7003100000000000000♠ 1 kB	7004410000000000000♠ 41 kB
SPHINCS+	ハッシュ署名	7001320000000000000♠32 B	7001640000000000000♠64 B	7003800000000000000♠ 8 kB
BLISS-II	格子暗号	7003700000000000000♠ 7 kB	7003200000000000000♠ 2 kB	7003500000000000000♠ 5 kB
GLP-Variant GLYPH Signature	Ring-LWE	7003200000000000000♠ 2 kB	7002400000000000000♠ 0.4 kB	7003180000000000000♠ 1.8 kB
NewHope	Ring-LWE	7003200000000000000♠ 2 kB	7003200000000000000♠ 2 kB
ゴッパ符号を用いたマックエリス暗号	符号暗号	7006100000000000000♠ 1 MB	7004115000000000000♠ 11.5 kB
Random Linear Code based encryption	RLCE	7005115000000000000♠ 115 kB	7003300000000000000♠ 3 kB
Quasi-cyclic MDPC-based McEliece	符号暗号	7003123200000000000♠1,232 B	7003246400000000000♠2,464 B
SIDH	同種写像暗号	7002564000000000000♠564 B	7001480000000000000♠48 B
SIDH (compressed keys)	同種写像暗号	7002330000000000000♠330 B	7001480000000000000♠48 B
3072-bit Discrete Log	非ポスト量子暗号	7002384000000000000♠384 B	7001320000000000000♠32 B	7001960000000000000♠96 B
256-bit 楕円曲線暗号	非ポスト量子暗号	7001320000000000000♠32 B	7001320000000000000♠32 B	7001650000000000000♠65 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${\bmod {\left(2^{10}\right)}}$を用いることを推奨している。これは6130bitの公開鍵となる。これに対応する秘密鍵は6743bitである。

多変数暗号 – Rainbow署名

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

ハッシュ暗号 – Merkle署名方式

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

符号暗号 – マックエリス暗号

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

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

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

$\mathrm {GF} (2^{12})$, 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が必要となる。対称鍵がポスト量子暗号において最も小さい鍵サイズとなるのは明らかである。

Forward secrecy(前方秘匿性)

公開鍵暗号システムは、鍵共有においてセッションごとにランダムな公開鍵を生成したときには、完全なforward secrecy(前方秘匿性) と呼ばれる性質を持つ。すなわち、一つのメッセージのセキュリティが破られても、その他のメッセージのセキュリティは破られないし、複数のメッセージのセキュリティを破ることのできるような一つの秘密の値なども存在しない。セキュリティの専門家は、forward secrecyを持つ暗号アルゴリズムを、そうでないものよりも推奨している。The reason for this is that forward secrecy can protect against the compromise of long term private keys associated with public/private key pairs.これは諜報機関による大衆監視を防ぐ手段として考えられている。

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月の段階では、以下の表の鍵交換アルゴリズムがサポートされている。

Algorithm	Type
CRYSTALS-Kyber	Module Learning with errors
Classic McEliece	goppa codes
BIKE	codes
HQC	codes
Frodo	Learning with errors
NTRU	格子暗号
CRYSTALS-Dilithium	Module 短整数解問題
Falcon	短整数解問題
SPHINCS+	hash based

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

Algorithm	Type
BCNS15	Ring learning with errors鍵交換
NewHope	Ring learning with errors鍵交換
SIDH	超特異同種写像ディフィー・ヘルマン
McBits	誤り訂正符号

実装

ポスト量子暗号における難問の一つは、現在のシステムにポスト量子暗号の実装を組み込むことであると考えられている。マイクロソフトリサーチによる、ハードウェアセキュリティモジュールを用いた公開鍵基盤へのPICNICの実装が一つの実験として行われている。Googleによる NewHopeアルゴリズムの実装の実験もハードウェアセキュリティモジュールのベンダーによって行われている。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
• liboqs

関連項目

• 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

外部リンク

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