ポスト量子暗号

格子暗号

このアプローチには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（英語版）を発明し、何度でも使うことのできるハッシュ署名 (Naor-Yung方式)^[26]を設計した。これは、落とし戸を利用しない初の署名方式である。

符号暗号

これにはマックエリス暗号、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]。

格子暗号 – Ring-LWE署名

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

格子暗号 – NTRU, BLISS

NTRU暗号方式とBLISS^[37]署名は、格子における最近ベクトル問題(CVP)と関係しているが、おそらく等価ではないと考えられている。CVPはNP困難であることが知られている。欧州委員会から支援を受けているThe Post Quantum Cryptography Study Groupは、長期間利用できる暗号方式として、オリジナルのNTRUよりも、安全性帰着のある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署名方式の安全性からその難問への帰着が存在する^[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困難な問題への安全性帰着は存在しない。

格子暗号 – 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暗号には、${\displaystyle (\mathbb {Z} /2^{10}\mathbb {Z} )}$係数の613次多項式で表現される鍵を用いることを推奨している。これは6130bitの公開鍵となる。これに対応する秘密鍵は6743bitである^[45]。

多変数暗号 – Rainbow署名

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

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

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}$ のエラーを訂正できるゴッパ符号を用いることを推奨している。これらのパラメータによって、マックエリス暗号の公開鍵は組織生成行列で表され、その単位行列でないパートのサイズは ${\displaystyle k\times (n-k)=8373911}$ bitになる。対応する秘密鍵は、${\displaystyle \mathrm {GF} (2^{13})}$の ${\displaystyle n=6960}$個の要素からなる符号の台および ${\displaystyle t=119}$ 個の${\displaystyle \mathrm {GF} (2^{13})}$係数の生成多項式からなり、そのサイズは92,027bit になる^[19]。

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

Barreto et al. は符号長 ${\displaystyle n=3307}$ 以上, 次元 ${\displaystyle k=2515}$, エラー訂正能力 ${\displaystyle t=66}$ の二元ゴッパ符号の利用を推奨している。これらのパラメータによって生成されたマックエリス暗号の公開鍵は、組織生成行列で表され、その単位行列でないパートのサイズは ${\displaystyle k\times (n-k)=1991880}$ bitになる^[60]。対応する秘密鍵は、${\displaystyle \mathrm {GF} (2^{12})}$の ${\displaystyle n=3307}$個の要素からなる符号の台および ${\displaystyle t=66}$ 個の${\displaystyle \mathrm {GF} (2^{12})}$係数の生成多項式からなり、そのサイズは40,476bit になる。

超特異楕円曲線同種写像暗号

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

対称鍵暗号

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

日本での医療分野への適用

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