ポスト量子暗号
 |
ポスト量子暗号 (ポストりょうしあんごう、英: post-quantum cryptography、略してPQC)とは、量子コンピュータによる暗号解読に対して安全だと考えられる暗号アルゴリズム (主に公開鍵暗号アルゴリズム) のことである。耐量子暗号(たいりょうしあんごう、英: quantum-resistant cryptography、quantum-proof cryptography、もしくはquantum-safe cryptography)とも呼ばれる。現在よく使われているアルゴリズムの問題は、そのセキュリティーが素因数分解、離散対数、楕円曲線暗号という３つの数学的な難題に依拠していることにある。 これらの問題はすべて、十分に強力な量子コンピュータとショアのアルゴリズム[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"と呼ばれ、暗号アルゴリズムを破ることの難しさを示すために使われる。言い換えると、暗号アルゴリズムのセキュリティーは既知の難問のセキュリティーに換算される。研究者はポスト量子暗号のsecurity reductionsを活発に探している。現在の結果には以下のようなものがある。
格子暗号 – Ring-LWE署名
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
NTRU暗号方式とBLISS[37]署名は、格子における最近ベクトル問題(CVP)と関係しているが、おそらく等価ではないと考えられている。CVPはNP困難であることが知られている。欧州委員会から支援を受けているThe Post Quantum Cryptography Study Groupは、長期間利用できる暗号方式として、オリジナルのNTRUよりも、security reductionのあるStehle–SteinfeldバージョンのNTRUを研究すべきだと提唱している[38]。
多変数暗号 – Unbalanced oil and vinegar
Unbalanced oil and vinegar暗号方式は有限体上の多変数多項式に基づく非対称的な暗号プリミティブである。Bulygin、Petzoldt、Buchmannらは一般的な多変数二次UOVシステムがNP困難な多変数二次方程式問題に換算されることを示している。[39]
ハッシュ暗号 – Merkle署名方式
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]
符号暗号 – RLCE
2016年、Wangはマックエリス暗号に基づいたランダム線形符号暗号方式であるRLCE[43]を提唱した。RLCE方式は、元となっている線型符号の生成行列にランダムな列を挿入することで、リード・ソロモン符号など、いかなる線型符号を用いても構築することができる。
超特異楕円曲線同種写像暗号
この安全性は、２つの超特異曲線間に同じ数の点で同種写像を構築する問題と関連している。最近の研究では、DelfsとGalbraithがこの問題は鍵交換の発明者が示したのと同様に困難であることを示している[44]。既知のNP困難な問題とのsecurity reductionは無い。
比較
多くのポスト量子暗号が持つ特徴の一つは、一般的な「プレ量子」公開鍵アルゴリズムよりも大きな鍵長を必要とすることである。鍵長、計算上の効率性、暗号テキスト・署名テキストのサイズの間にはしばしばトレードオフが存在する。以下の表は、128bitのセキュリティレベルにおけるポスト量子暗号方式の鍵サイズを比較したものである。
| アルゴリズム | タイプ | 公開鍵 | 秘密鍵 | 署名 |
|---|---|---|---|---|
| NTRU暗号[45] | 格子暗号 | 766.25 B | 842.875 B | |
| Streamlined NTRU Prime[要出典] | 格子暗号 | 154 B | ||
| Rainbow[46] | 多変数暗号 |
124 kB |
95 kB |
|
| SPHINCS[24] | ハッシュ署名 |
1 kB |
1 kB |
41 kB |
| SPHINCS+[47] | ハッシュ署名 | 32 B | 64 B |
8 kB |
| BLISS-II | 格子暗号 |
7 kB |
2 kB |
5 kB |
| GLP-Variant GLYPH Signature[16][48] | Ring-LWE |
2 kB |
0.4 kB |
1.8 kB |
| NewHope[49] | Ring-LWE |
2 kB |
2 kB |
|
| ゴッパ符号を用いたマックエリス暗号[19] | 符号暗号 |
1 MB |
11.5 kB |
|
| Random Linear Code based encryption[50] | RLCE |
115 kB |
3 kB |
|
| Quasi-cyclic MDPC-based McEliece[51] | 符号暗号 | 1,232 B | 2,464 B | |
| SIDH[52] | 同種写像暗号 | 564 B | 48 B | |
| SIDH (compressed keys)[53] | 同種写像暗号 | 330 B | 48 B | |
| 3072-bit Discrete Log | 非ポスト量子暗号 | 384 B | 32 B | 96 B |
| 256-bit 楕円曲線暗号 | 非ポスト量子暗号 | 32 B | 32 B | 65 B |
ポスト量子暗号の選択における実用的な考慮事項としては、インターネット上で送信する公開鍵のサイズがある。この観点では、Ring-LWE、NTRU暗号、SIDHアルゴリズムが1kB以下で利便性が良い。ハッシュ署名暗号の公開鍵は5kB以下、 MDPC-based McElieceは約1kBである。その一方、Rainbow 方式は約125kB、ゴッパ符号を用いたマックエリス暗号は1MB近くの鍵サイズが必要となる。
格子暗号 – LWE鍵交換とRing-LWE鍵交換
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]。
格子暗号 – NTRU暗号
Hirschhorn、Hoffstein、Howgrave-Graham、Whyteらは、128bitのセキュリティレベルのNTRU暗号にはkey represented as a degree 613 polynomial with coefficients
- ポスト量子暗号のページへのリンク
