ポスト量子暗号
ポスト量子暗号 (ポストりょうしあんごう、英:Post-quantum cryptography、略してPQC)とは、量子コンピュータによる暗号解読に対して安全だと考えられる暗号アルゴリズム (主に公開鍵暗号アルゴリズム) のことである。現在よく使われているアルゴリズムの問題は、そのセキュリティーが素因数分解、離散対数、楕円曲線暗号という3つの数学的な難題に依拠していることにある。 これらの問題はすべて、十分に強力な量子コンピュータとショアのアルゴリズム(英語版)[1][2]や、それよりも高速で必要とする量子ビットも少ないアルゴリズム[3]を用いることで容易に解くことができる。
2023年時点では、量子コンピュータの性能は広く用いられている暗号アルゴリズムを破る段階には達していないが[4]、暗号技術者たちは「Q-Day」(量子コンピュータが現在の暗号アルゴリズムを破ることができるようになる日)に備えて新しいアルゴリズムを開発している。この活動は、2006年から開催されている国際会議PQCrypto、欧州電気通信標準化機構(ETSI)の耐量子暗号に関するワークショップ、量子コンピューティング研究所(英語版)などを通して大学、産業から関心を集めている[5][6][7]。 存在が広く噂されているHarvest now, decrypt later(英語版)攻撃も、早急なポスト量子暗号導入への理由となっている[8][9][10]。
量子コンピュータが現在の公開鍵暗号アルゴリズムへの脅威となっている一方で、現在の多くの共通鍵暗号やハッシュ関数は量子コンピュータからの攻撃に対して比較的安全と考えられている[2][11]。 量子コンピュータはグローバーのアルゴリズムによって共通鍵暗号の解読速度を上げることができるものの、これに対しては鍵長を倍にすることが効果的な対策となる[12]。そのため、ポスト量子共通鍵暗号には現在の共通鍵暗号と大きく異なったものを用いる必要はない。
アルゴリズム
ポスト量子暗号の研究には、大きく分けて6つのアプローチがある。[2][6]
格子暗号
このアプローチにはLearning with errors(LWE)(英語版)、Ring learning with errors(ring-LWE)(英語版)[13][14][15] 、Ring learning with errors鍵交換、Ring learning with errors署名、NTRU暗号やGGH暗号方式、NTRUSign(英語版)、BLISS署名方式(英語版)などの暗号方式がある。NTRU暗号など、このうちのいくつかはまだ効果的な攻撃方法は見つかっていない。ring-LWEなどのその他のアルゴリズムは、最悪時の格子問題と同等の安全性があることが分かっている。[16] 欧州委員会から支援を受けたThe Post Quantum Cryptography Study Groupは、NTRU暗号ではなく、Stehle–Steinfeld variant of NTRUを標準化に向けて研究すべきだと提案している[17][18]。現在のところ、NTRUは特許で保護されている。研究では、NTRU暗号は他の格子暗号アルゴリズムよりも安全な要素が多いとされている[19]。
多変数暗号
多変数方程式を解くことが困難であることを利用したRainbow (Unbalanced oil and vinegar(英語版))方式がある。多変数方程式を用いた安全な暗号方式を作る試みは失敗を重ねてきた。しかし、Rainbowは多変数方程式によるデジタル署名方式の基礎を築くことに成功した[20] 。Rainbow方式は特許で保護されている。
ハッシュ暗号
これには、ランポート署名、Merkle署名方式(英語版)、XMSS、[21] SPHINCS、[22] WOTS方式などがある。ハッシュによるデジタル署名は1970年代後半にラルフ・マークルによって発明され、 RSAやDSAといった数論的なデジタル署名に代わる方式として研究されてきた。これらの方式の大きな欠点は、どのハッシュ暗号でも、公開鍵と対となる秘密鍵を用いて署名できる数に限りがあるという点である。そのため、耐量子暗号への関心が高まるまでは、この方式はあまり注目を集めてこなかった。Merkle署名方式は特許で保護されておらず[要出典]、この方式で使うことのできる特許で保護されていないハッシュ関数は多く存在する。ヨハネス・ブーフマン(英語版)の率いる研究チームによって開発された、ステートフルなハッシュ署名方式であるXMSSはRFC 8391に記述されている[23]。
上で述べた方式はすべて一度、もしくは限られた回数の署名であるが、Moni Naor(英語版)とモチ・ユング(英語版) は1989年にUOWHF(英語版)を発明し、何度でも使うことのできるハッシュ署名 (the Naor-Yung scheme)[24]を設計した(the first such signature that does not require trapdoor properties)。
符号暗号
これにはマックエリス暗号、Niederreiter暗号システム(英語版) やそれに関連するCourtois, Finiasz and Sendrier署名方式など、誤り訂正符号に依拠した暗号方式が含まれる。オリジナルなマックエリス暗号はランダムなGoppa符号(英語版) を使っており、これは40年以上もの時間と研究を経た今でも安全と考えられている。 しかし、鍵サイズを減らすために符号に構造を追加しようとして作られた、異なるバリエーションのマックエリス暗号は、その多くが安全ではないことが分かっている[25]。 欧州委員会の支援するThe Post Quantum Cryptography Study Groupは、量子コンピュータの攻撃に長時間耐えることのできる暗号システムの候補として、マックエリス公開鍵暗号を推薦している[17]。
同種写像暗号
有限体上の楕円曲線の同種写像グラフ(と高次元アーベル多様体)、特に超特異同種写像グラフ(英語版)の性質を用いた暗号システムである。この分野でよく知られているのはディフィー・ヘルマン鍵共有と似ているCSIDH鍵共有であり、これは現在広く使われているディフィー・ヘルマン鍵共有や楕円曲線ディフィー・ヘルマン鍵共有の耐量子代替として単純に使うことができる[26]。また、超特異楕円曲線とあるタイプの四元数環の極大整環が圏同値であることに基づいた署名方式であるSQISignも知られている[27]。もう一つのよく知られた方式である超特異同種写像ディフィー・ヘルマン(SIDH/SIKE)は2022年に破られた[28]。 この攻撃はSIDH/SIKE系の方式に特有のため、他の同種写像暗号に対して一般的に用いることはできない[29]。
共通鍵暗号の耐量子性
十分に大きな鍵長を使った場合、AESやSNOW 3G(英語版)のような共通鍵暗号方式はすでに量子コンピュータの攻撃に耐えられる。[30]その上、ケルベロス認証や3GPPモバイルネットワーク認証といった、公開鍵暗号ではなく共通鍵暗号を用いた鍵管理システムやプロトコルも量子コンピュータの攻撃に対して本質的に安全である。ケルベロス認証は既に世界中に普及しているため、いち早くポスト量子暗号に対応する効率的な方法として、ケルベロス認証のような鍵管理システムを広く用いることを推奨する研究者もいる[31]。
Security reductions
暗号研究においては、暗号アルゴリズムが既知の困難な数学問題と同等であることを証明することが望まれる。この証明はよく"security reductions"と呼ばれ、暗号アルゴリズムを破ることの難しさを示すために使われる。言い換えると、暗号アルゴリズムのセキュリティーは既知の難問のセキュリティーに換算される。研究者はポスト量子暗号のsecurity reductionsを活発に探している。現在の結果には以下のようなものがある。
格子暗号 – Ring-LWE署名
Ring-LWEのあるバージョンには、最短の格子を求める最短ベクトル問題(英語版)(SVP)のセキュリティーに帰着できるsecurity reductionがある。最短ベクトル問題はNP困難であることが知られている[32]。Güneysu、Lyubashevsky、Pöppelmannによる論文で定義されているLyubashevsky's ring-LWE署名[14]など、証明可能なsecurity reductionのあるring-LWEシステムもある。GLYPH署名方式はGüneysu、Lyubashevsky、Pöppelmann (GLP)署名の発表後の研究結果を考慮に入れた、GLP署名のバリエーションである。もう一つのRing-LWE署名はRing-TESLAである[33]。LWEの「脱ランダム化されたバリエーション」であるLearning with Rounding (LWR)は「速度(by eliminating sampling small errors from a Gaussian-like distribution with deterministic errors) と帯域の向上」がなされている[34]。LWEが下位ビットを隠すために小さなエラーを加えているのに対して、LWRはそのために丸め操作を利用している。
格子暗号 – NTRU, BLISS
NTRU暗号方式とBLISS[35]署名は、格子における最近ベクトル問題(CVP)と関係しているが、おそらく等価ではないと考えられている。CVPはNP困難であることが知られている。欧州委員会から支援を受けているThe Post Quantum Cryptography Study Groupは、長期間利用できる暗号方式として、オリジナルのNTRUよりも、security reductionのあるStehle–SteinfeldバージョンのNTRUを研究すべきだと提唱している[36]。
多変数暗号 – Unbalanced oil and vinegar
Unbalanced oil and vinegar(英語版)暗号方式は有限体上の多変数多項式に基づく非対称的な暗号プリミティブである。Bulygin、Petzoldt、Buchmannらは一般的な多変数二次UOVシステムがNP困難な多変数二次方程式問題に換算されることを示している。[37]
ハッシュ暗号 – Merkle署名方式
2005年、Luis GarciaはMerkle署名方式がその基礎となっているハッシュ関数の安全性に換算できることを示した。Garciaは論文内で、もし一方向ハッシュ関数が計算上存在するなら、Merkle署名は安全であるだろうと示した。[38]
それゆえ、 既知の難問へとセキュリティ的に換算できるハッシュ関数を使った場合、Merkle署名方式のSecurity reductionはその難問であることになる[39]。
欧州委員会から支援を受けているThe Post Quantum Cryptography Study Groupは、量子コンピュータの攻撃を長期間防ぐことのできる方式としてMerkle署名方式を推薦している[17]。
符号暗号 – マックエリス暗号
マックエリス暗号方式は、シンドローム復号問題(SDP)にセキュリティ的に換算できる。SDPはNP困難であることが知られている[40]。欧州委員会から支援を受けているThe Post Quantum Cryptography Study Groupは、この暗号方式を量子コンピュータの攻撃を長期間防ぐことのできる方式として推薦している。[17]
符号暗号 – RLCE
2016年、Wangはマックエリス暗号に基づいたランダム線形符号暗号方式であるRLCE[41]を提唱した。RLCE方式は、元となっている線型符号の生成行列にランダムな列を挿入することで、リード・ソロモン符号など、いかなる線型符号を用いても構築することができる。
超特異楕円曲線同種写像暗号
この安全性は、2つの超特異曲線間に同じ数の点で同種写像を構築する問題と関連している。最近の研究では、DelfsとGalbraithがこの問題は鍵交換の発明者が示したのと同様に困難であることを示している[42]。既知のNP困難な問題とのsecurity reductionは無い。
比較
多くのポスト量子暗号が持つ特徴の一つは、一般的な「プレ量子」公開鍵アルゴリズムよりも大きな鍵長を必要とすることである。鍵長、計算上の効率性、暗号テキスト・署名テキストのサイズの間にはしばしばトレードオフが存在する。以下の表は、128bitのセキュリティレベル(英語版)におけるポスト量子暗号方式の鍵サイズを比較したものである。
アルゴリズム | タイプ | 公開鍵 | 秘密鍵 | 署名 |
---|---|---|---|---|
NTRU暗号[43] | 格子暗号 | 7002766250000000000♠766.25 B | 7002842875000000000♠842.875 B | |
Streamlined NTRU Prime[要出典] | 格子暗号 | 7002154000000000000♠154 B | ||
Rainbow[44] | 多変数暗号 | 7005124000000000000♠ 124 kB | 7004950000000000000♠ 95 kB | |
SPHINCS[22] | ハッシュ署名 | 7003100000000000000♠ 1 kB | 7003100000000000000♠ 1 kB | 7004410000000000000♠ 41 kB |
SPHINCS+[45] | ハッシュ署名 | 7001320000000000000♠32 B | 7001640000000000000♠64 B | 7003800000000000000♠ 8 kB |
BLISS-II | 格子暗号 | 7003700000000000000♠ 7 kB | 7003200000000000000♠ 2 kB | 7003500000000000000♠ 5 kB |
GLP-Variant GLYPH Signature[14][46] | Ring-LWE | 7003200000000000000♠ 2 kB | 7002400000000000000♠ 0.4 kB | 7003180000000000000♠ 1.8 kB |
NewHope(英語版)[47] | Ring-LWE | 7003200000000000000♠ 2 kB | 7003200000000000000♠ 2 kB | |
ゴッパ符号を用いたマックエリス暗号[17] | 符号暗号 | 7006100000000000000♠ 1 MB | 7004115000000000000♠ 11.5 kB | |
Random Linear Code based encryption[48] | RLCE | 7005115000000000000♠ 115 kB | 7003300000000000000♠ 3 kB | |
Quasi-cyclic MDPC-based McEliece[49] | 符号暗号 | 7003123200000000000♠1,232 B | 7003246400000000000♠2,464 B | |
SIDH[50] | 同種写像暗号 | 7002564000000000000♠564 B | 7001480000000000000♠48 B | |
SIDH (compressed keys)[51] | 同種写像暗号 | 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年にシンシナティ大学で提唱され、特許出願された。この基本的なアイデアは行列の乗法の結合性に基づいており、エラーはセキュリティを与えるために利用される。この論文[52] は、2012年に仮特許出願が提出された後、2012年に発表された。
2014年、Peikert[53]はDingによる基本的なアイデアを発展させた鍵交換方式を発表した。これは、丸めのため1ビットのシグナルを追加して送るという新しいアイディアを用いている。128ビット以上のセキュリティレベル(英語版)のために、Singhは6956bitの公開鍵を持つパラメーターセットを Peikertの方式に提案した[54]。これに対応する秘密鍵はおよそ14,000ビットとなる。
2015年、Eurocrypt 2015において、Dingの基本的なアイデアから発展した、証明可能な前方秘匿性を持つ認証鍵交換方式が発表された[55]。これはCrypto2005におけるHMQV[56]構築を拡張したものである。80bitから350bitまでの異なるセキュリティレベルに対するパラメーターと、それに対応する鍵サイズも論文中で示されている[55]。
格子暗号 – NTRU暗号
Hirschhorn、Hoffstein、Howgrave-Graham、Whyteらは、128bitのセキュリティレベル(英語版)のNTRU暗号にはkey represented as a degree 613 polynomial with coefficientsを用いることを推奨している。これは6130bitの公開鍵となる。これに対応する秘密鍵は6743bitである[43]。
多変数暗号 – Rainbow署名
Petzoldt、BulyginとBuchmannは、Rainbow多変数二次方程式署名方式において、128bitのセキュリティレベルで最小の署名サイズにするには、上の方程式と991,000bitをやや上回るサイズの公開鍵、740,000bitをやや上回るサイズの秘密鍵と、424bitの長さのデジタル署名を用いることを推奨している[44]。
ハッシュ暗号 – Merkle署名方式
Naor ShenhavとWoolによるフラクタルMerkle木を用いた方式では、100万メッセージに署名するためのハッシュ署名において128bitのセキュリティレベルを得るには、約36,000bitの公開鍵と秘密鍵のサイズとなる[57]。
符号暗号 – マックエリス暗号
マックエリス暗号で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[17].
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.[58] 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を用いることを推奨している[59]。Azarderakhsh、Jao、Kalach、Koziel、Leonardiらによる2016年3月の論文では、送信するビット数を半分に減らす方法が示されている。その後、Costello、Jao、Longa、Naehrig、Renes 、Urbanikらの論文ではさらに改良され、公開鍵のサイズが2640bitに圧縮されたSIDHプロトコルのバージョンが完成している[51]。 これは非量子暗号であるRSA暗号やディフィー・ヘルマン鍵共有とほぼ同じサイズの送信量で、同等のセキュリティレベルである[60]。
対称鍵暗号
一般的に、対称鍵暗号システムで128bitのセキュリティレベル(英語版)には、256bitの鍵サイズを用いる。量子コンピュータによる一般的な対称鍵暗号への最も効率の良い攻撃方法はグローバーのアルゴリズムを用いたもので、これは鍵サイズの平方根と同等の計算量が必要となる。暗号化された鍵を、復号化するための対称鍵を持ったデバイスに送信するためにも約256bitが必要となる。対称鍵がポスト量子暗号において最も小さい鍵サイズとなるのは明らかである[要出典][citation needed]。
Forward secrecy(前方秘匿性)
公開鍵暗号システムは、鍵共有においてセッションごとにランダムな公開鍵を生成したときには、完全なforward secrecy(前方秘匿性) と呼ばれる性質を持つ。すなわち、一つのメッセージのセキュリティが破られても、その他のメッセージのセキュリティは破られないし、複数のメッセージのセキュリティを破ることのできるような一つの秘密の値なども存在しない。セキュリティの専門家は、forward secrecyを持つ暗号アルゴリズムを、そうでないものよりも推奨している[61]。これは、forward secrecyを持っていれば、公開鍵・秘密鍵のペアと結びついた長期秘密鍵が破られたときにも、情報を守ることができるからである。これは諜報機関による大衆監視を防ぐ手段として考えられている。
Ring-LWE鍵交換と超特異同種写像ディフィー・ヘルマン(SIDH) 鍵交換はどちらも、鍵交換ごとのforward secresyに対応している。 Ring-LWEとSIDHはまた、ElGamal暗号版のディフィー・ヘルマン鍵共有を作ることで、forward secrecy無しで用いることもできる。
NTRU暗号など、この記事の他のアルゴリズムにはforward secrecyの性質はない。
どの認証公開鍵暗号システムもforward secrecyを持った鍵交換をすることができる[62]。
Open Quantum Safe project
The Open Quantum Safe (OQS) プロジェクトは2016年後半に始まった、耐量子暗号の開発と試作を目的とするプロジェクトである[63][64]。 liboqsという一つのライブラリに、現在のポスト量子暗号方式を統合することを目標としている[65]。 liboqsは耐量子暗号アルゴリズムの、オープンソースのC言語ライブラリである。初期は鍵交換アルゴリズムが中心であったが、現在はその他の暗号方式も含んでいる。liboqsはポスト量子鍵交換アルゴリズムのための一般的なAPIを提供し、 様々な実装を集める。 liboqsはまた、ポスト量子暗号の実装を比較するためのテストハーネスやベンチマークのルーチンを含む予定である。それに加え、OQSはliboqsの統合されたOpenSSLも提供している[66]。
2023年3月の段階では、以下の表の鍵交換アルゴリズムがサポートされている[63]。
アルゴリズム | タイプ |
---|---|
CRYSTALS-Kyber(英語版) | Module Learning with errors(英語版) |
Classic McEliece | goppa符号 |
BIKE[67] | 符号暗号 |
HQC[68][69] | 符号暗号 |
Frodo[70][71] | Learning with errors |
NTRU(英語版)[72] | 格子暗号 |
CRYSTALS-Dilithium[73][74] | Module 短整数解問題(英語版) |
Falcon | 短整数解問題 |
SPHINCS+ | ハッシュ暗号 |
the NIST Post-Quantum Cryptography Standardization Projectの変更によって削除された、過去にサポートされていたアルゴリズムは以下である。
Algorithm | Type |
---|---|
BCNS15[75] | Ring learning with errors(英語版)鍵交換 |
NewHope(英語版)[76][47] | Ring learning with errors(英語版)鍵交換 |
SIDH[77][78] | 超特異同種写像ディフィー・ヘルマン |
McBits[79] | 誤り訂正符号 |
実装
ポスト量子暗号における難問の一つは、現在のシステムにポスト量子暗号の実装を組み込むことであると考えられている。マイクロソフトリサーチによる、ハードウェアセキュリティモジュール(英語版)を用いた公開鍵基盤へのPICNICの実装[80]が一つの実験として行われている。Googleによる NewHope(英語版)アルゴリズムの実装の実験もハードウェアセキュリティモジュールのベンダーによって行われている。2023年8月、Googleはチューリッヒ工科大学と協同で、ECCとDilithiumのハイブリット署名方式によるFIDO2の秘密鍵の実装を発表した[81]。
2024年2月、AppleはiMessageのプロトコルを、ongoing keyingを利用した "PQ3"と呼ばれる、新しいポスト量子暗号プロトコルにアップグレードすることを発表した[82][83][84]。Appleは、量子コンピュータはまだ存在しないが、その将来の攻撃やHarvest now, decrypt later(英語版)の攻撃シナリオを軽減したいと述べた。 Appleによると、PQ3の実装は「ongoing keyingを用いているため、他のすべての広く用いられているメッセージングアプリを上回る」保護を提供するという。Apple は現在のiMessageのすべてのプロトコルを2024年の終わりまでにPQ3に変更する意向を示している。また、メッセージアプリのセキュリティレベルを0から3に分類した基準を提唱している[82]。
その他の主な実装を下に挙げる。
- Bouncy Castle(英語版)[85]
- liboqs[86]
関連項目
- NISTの耐量子暗号標準(英語版)
- 量子暗号 – 量子力学に基づいた暗号
- クリプトシュレッディング(英語版)
- Harvest now, decrypt later(英語版)
脚注
- ^ Shor, Peter W. (1997). “Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer”. SIAM Journal on Computing 26 (5): 1484–1509. arXiv:quant-ph/9508027. Bibcode: 1995quant.ph..8027S. doi:10.1137/S0097539795293172.
- ^ a b c Bernstein, Daniel J. (2009). “Introduction to post-quantum cryptography” (英語). Post-Quantum Cryptography. http://www.pqcrypto.org/www.springer.com/cda/content/document/cda_downloaddocument/9783540887010-c1.pdf
- ^ Kramer, Anna (2023). “'Surprising and super cool.' Quantum algorithm offers faster way to hack internet encryption”. Science 381 (6664): 1270. doi:10.1126/science.adk9443. PMID 37733849. https://www.science.org/content/article/surprising-and-supercool-quantum-algorithm-offers-faster-way-hack-internet-encryption.
- ^ “New qubit control bodes well for future of quantum computing”. phys.org. Template:Cite webの呼び出しエラー:引数 accessdate は必須です。
- ^ "Cryptographers Take On Quantum Computers". IEEE Spectrum. 1 January 2009.
- ^ a b "Q&A With Post-Quantum Computing Cryptography Researcher Jintai Ding". IEEE Spectrum. 1 November 2008.
- ^ “ETSI Quantum Safe Cryptography Workshop”. ETSI Quantum Safe Cryptography Workshop. ETSI (October 2014). 17 August 2016時点のオリジナルよりアーカイブ。24 February 2015閲覧。
- ^ Gasser, Linus (2023), Mulder, Valentin; Mermoud, Alain; Lenders, Vincent et al., eds., “Post-quantum Cryptography” (英語), Trends in Data Protection and Encryption Technologies (Cham: Springer Nature Switzerland): 47–52, doi:10.1007/978-3-031-33386-6_10, ISBN 978-3-031-33386-6
- ^ Townsend (2022年2月16日). “Solving the Quantum Decryption 'Harvest Now, Decrypt Later' Problem” (英語). SecurityWeek. 2023年4月9日閲覧。
- ^ “Quantum-Safe Secure Communications”. UK National Quantum Technologies Programme (October 2021). 2023年4月9日閲覧。
- ^ Daniel J. Bernstein (2009年5月17日). “Cost analysis of hash collisions: Will quantum computers make SHARCS obsolete?”. Template:Cite webの呼び出しエラー:引数 accessdate は必須です。
- ^ Daniel J. Bernstein (2010年3月3日). “Grover vs. McEliece”. Template:Cite webの呼び出しエラー:引数 accessdate は必須です。
- ^ Peikert (2014年). “Lattice Cryptography for the Internet”. IACR. 12 May 2014時点のオリジナルよりアーカイブ。10 May 2014閲覧。
- ^ a b c Güneysu (2012年). “Practical Lattice-Based Cryptography: A Signature Scheme for Embedded Systems”. INRIA. 12 May 2014閲覧。
- ^ Zhang (2014年). “Authenticated Key Exchange from Ideal Lattices”. iacr.org. IACR. 7 September 2014時点のオリジナルよりアーカイブ。7 September 2014閲覧。
- ^ Lyubashevsky (2013年). “On Ideal Lattices and Learning with Errors Over Rings”. IACR. 31 January 2014時点のオリジナルよりアーカイブ。14 May 2013閲覧。
- ^ a b c d e f Augot (7 September 2015). “Initial recommendations of long-term secure post-quantum systems”. PQCRYPTO. 13 September 2015閲覧。
- ^ Stehlé, Damien; Steinfeld, Ron (2013-01-01). “Making NTRUEncrypt and NTRUSign as Secure as Standard Worst-Case Problems over Ideal Lattices”. Cryptology ePrint Archive. http://eprint.iacr.org/2013/004.
- ^ Easttom, Chuck (2019-02-01). “An Analysis of Leading Lattice-Based Asymmetric Cryptographic Primitives”. 2019 IEEE 9th Annual Computing and Communication Workshop and Conference (CCWC). pp. 0811–0818. doi:10.1109/CCWC.2019.8666459. ISBN 978-1-7281-0554-3
- ^ Ding, Jintai; Schmidt (7 June 2005). “Rainbow, a New Multivariable Polynomial Signature Scheme”. In Ioannidis, John (英語). Applied Cryptography and Network Security. Lecture Notes in Computer Science. 3531. pp. 64–175. doi:10.1007/11496137_12. ISBN 978-3-540-26223-7
- ^ Buchmann, Johannes; Dahmen, Erik; Hülsing, Andreas (2011). Post-Quantum Cryptography. PQCrypto 2011. Lecture Notes in Computer Science. Vol. 7071. pp. 117–129. doi:10.1007/978-3-642-25405-5_8。
- ^ a b Bernstein, Daniel J.; Hopwood, Daira; Hülsing, Andreas; Lange, Tanja; Niederhagen, Ruben; Papachristodoulou, Louiza; Schneider, Michael; Schwabe, Peter et al. (2015). “SPHINCS: Practical Stateless Hash-Based Signatures”. In Oswald, Elisabeth; Fischlin (英語). Advances in Cryptology -- EUROCRYPT 2015. Lecture Notes in Computer Science. 9056. Springer Berlin Heidelberg. pp. 368–397. doi:10.1007/978-3-662-46800-5_15. ISBN 9783662467992
- ^ Huelsing, A.; Butin, D.; Gazdag, S.; Rijneveld, J.; Mohaisen, A. (2018) (英語). RFC 8391 – XMSS: eXtended Merkle Signature Scheme. doi:10.17487/RFC8391. https://tools.ietf.org/html/rfc8391.
- ^ Naor, Moni; Yung, Moti (1989), Universal One-Way Hash Functions and their Cryptographic Applications .STOC, pp. 33–43
- ^ Overbeck, Raphael; Sendrier (2009). “Code-based cryptography”. In Bernstein, Daniel. Post-Quantum Cryptography. pp. 95–145. doi:10.1007/978-3-540-88702-7_4. ISBN 978-3-540-88701-0
- ^ Castryck, Wouter; Lange, Tanja; Martindale, Chloe; Panny, Lorenz; Renes, Joost (2018). “CSIDH: An Efficient Post-Quantum Commutative Group Action”. In Peyrin, Thomas; Galbraith, Steven (英語). Advances in Cryptology – ASIACRYPT 2018. Lecture Notes in Computer Science. 11274. Cham: Springer International Publishing. pp. 395–427. doi:10.1007/978-3-030-03332-3_15. hdl:1854/LU-8619033. ISBN 978-3-030-03332-3. https://hdl.handle.net/handle/1854/LU-8619033
- ^ De Feo, Luca; Kohel, David; Leroux, Antonin; Petit, Christophe; Wesolowski, Benjamin (2020). “SQISign: Compact Post-quantum Signatures from Quaternions and Isogenies”. In Moriai, Shiho; Wang, Huaxiong (英語). Advances in Cryptology – ASIACRYPT 2020. Lecture Notes in Computer Science. 12491. Cham: Springer International Publishing. pp. 64–93. doi:10.1007/978-3-030-64837-4_3. ISBN 978-3-030-64837-4. https://hal.archives-ouvertes.fr/hal-03038004/file/2020-1240.pdf
- ^ Castryck, Wouter; Decru, Thomas (2023), Hazay, Carmit; Stam, Martijn, eds., “An Efficient Key Recovery Attack on SIDH” (英語), Advances in Cryptology – EUROCRYPT 2023 (Cham: Springer Nature Switzerland) 14008: 423–447, doi:10.1007/978-3-031-30589-4_15, ISBN 978-3-031-30588-7, https://link.springer.com/10.1007/978-3-031-30589-4_15 2023年6月21日閲覧。
- ^ “Is SIKE broken yet?”. 2023年6月23日閲覧。
- ^ Perlner, Ray; Cooper (2009). Quantum Resistant Public Key Cryptography: A Survey. 8th Symposium on Identity and Trust on the Internet (IDtrust 2009). NIST. 2015年4月23日閲覧。
- ^ Campagna (2013年). “Kerberos Revisited Quantum-Safe Authentication”. ETSI. Template:Cite webの呼び出しエラー:引数 accessdate は必須です。
- ^ Lyubashevsky (25 June 2013). “On Ideal Lattices and Learning with Errors Over Rings”. Springer. 19 June 2014閲覧。
- ^ Akleylek, Sedat; Bindel, Nina; Buchmann, Johannes; Krämer, Juliane; Marson, Giorgia Azzurra (2016). “An Efficient Lattice-Based Signature Scheme with Provably Secure Instantiation”. Cryptology ePrint Archive. https://eprint.iacr.org/2016/030.
- ^ Nejatollahi, Hamid; Dutt, Nikil; Ray, Sandip; Regazzoni, Francesco; Banerjee, Indranil; Cammarota, Rosario (2019-02-27). “Post-Quantum Lattice-Based Cryptography Implementations: A Survey” (英語). ACM Computing Surveys 51 (6): 1–41. doi:10.1145/3292548. ISSN 0360-0300. https://dl.acm.org/doi/10.1145/3292548.
- ^ Ducas, Léo; Durmus, Alain; Lepoint, Tancrède; Lyubashevsky, Vadim (2013). “Lattice Signatures and Bimodal Gaussians”. Cryptology ePrint Archive. http://eprint.iacr.org/2013/383 2015年4月18日閲覧。.
- ^ Augot, Daniel (7 September 2015). “Initial recommendations of long-term secure post-quantum systems”. PQCRYPTO. 13 September 2015閲覧。
- ^ Bulygin, Stanislav; Petzoldt; Buchmann (2010). “Towards Provable Security of the Unbalanced Oil and Vinegar Signature Scheme under Direct Attacks”. Progress in Cryptology – INDOCRYPT 2010. Lecture Notes in Computer Science. 6498. pp. 17–32. doi:10.1007/978-3-642-17401-8_3. ISBN 978-3-642-17400-1
- ^ Pereira, Geovandro; Puodzius, Cassius; Barreto, Paulo (2016). “Shorter hash-based signatures”. Journal of Systems and Software 116: 95–100. doi:10.1016/j.jss.2015.07.007.
- ^ Garcia. “On the security and the efficiency of the Merkle signature scheme”. Cryptology ePrint Archive. IACR. 19 June 2013閲覧。
- ^ Blaum, Mario; Farrell; Tilborg (31 May 2002). Information, Coding and Mathematics. Springer. ISBN 978-1-4757-3585-7
- ^ Wang, Yongge (2016). “Quantum resistant random linear code based public key encryption scheme RLCE”. Proceedings of Information Theory (ISIT): 2519–2523. arXiv:1512.08454. Bibcode: 2015arXiv151208454W.
- ^ Delfs, Christina; Galbraith. "Computing isogenies between supersingular elliptic curves over F_p". arXiv:1310.7789 [math.NT]。
- ^ a b Hirschborrn. “Choosing NTRUEncrypt Parameters in Light of Combined Lattice Reduction and MITM Approaches”. NTRU. 30 January 2013時点のオリジナルよりアーカイブ。12 May 2014閲覧。
- ^ a b Petzoldt (2010年). “Selecting Parameters for the Rainbow Signature Scheme – Extended Version -”. 4 March 2016時点のオリジナルよりアーカイブ。12 May 2014閲覧。
- ^ SPHINCS+: Submission to the NIST post-quantum project
- ^ Chopra, Arjun (2017). “GLYPH: A New Insantiation of the GLP Digital Signature Scheme”. Cryptology ePrint Archive. https://eprint.iacr.org/2017/766.
- ^ a b Alkim (2015年). “Post-quantum key exchange – a new hope”. Cryptology ePrint Archive, Report 2015/1092. 1 September 2017閲覧。
- ^ Wang, Yongge (2017). “Revised Quantum Resistant Public Key Encryption Scheme RLCE and IND-CCA2 Security for McEliece Schemes”. Cryptology ePrint Archive. https://eprint.iacr.org/2017/206.
- ^ Misoczki, R.; Tillich, J. P.; Sendrier, N.; Barreto, P. S. L. M. (2013). “MDPC-McEliece: New McEliece variants from Moderate Density Parity-Check codes”. 2013 IEEE International Symposium on Information Theory. pp. 2069–2073. doi:10.1109/ISIT.2013.6620590. ISBN 978-1-4799-0446-4
- ^ Costello, Craig; Longa, Patrick; Naehrig, Michael (2016). “Efficient Algorithms for Supersingular Isogeny Diffie-Hellman”. Advances in Cryptology – CRYPTO 2016. Lecture Notes in Computer Science. 9814. pp. 572–601. doi:10.1007/978-3-662-53018-4_21. ISBN 978-3-662-53017-7. http://eprint.iacr.org/2016/413.pdf
- ^ a b Costello. “Efficient Compression of SIDH public keys”. 8 October 2016閲覧。
- ^ Ding, Jintai; Xie, Xiang; Lin, Xiaodong (2012-01-01). “A Simple Provably Secure Key Exchange Scheme Based on the Learning with Errors Problem”. Cryptology ePrint Archive. http://eprint.iacr.org/2012/688.
- ^ Peikert, Chris (2014-01-01). “Lattice Cryptography for the Internet”. Cryptology ePrint Archive. http://eprint.iacr.org/2014/070.
- ^ Singh, Vikram (2015). “A Practical Key Exchange for the Internet using Lattice Cryptography”. Cryptology ePrint Archive. http://eprint.iacr.org/2015/138 2015年4月18日閲覧。.
- ^ a b Zhang, Jiang; Zhang, Zhenfeng; Ding, Jintai; Snook, Michael; Dagdelen, Özgür (2015-04-26). “Authenticated Key Exchange from Ideal Lattices”. In Oswald, Elisabeth; Fischlin. Advances in Cryptology – EUROCRYPT 2015. Lecture Notes in Computer Science. 9057. Springer Berlin Heidelberg. pp. 719–751. doi:10.1007/978-3-662-46803-6_24. ISBN 978-3-662-46802-9
- ^ Krawczyk, Hugo (2005-08-14). “HMQV: A High-Performance Secure Diffie-Hellman Protocol”. In Shoup, Victor. Advances in Cryptology – CRYPTO 2005. Lecture Notes in Computer Science. 3621. Springer. pp. 546–566. doi:10.1007/11535218_33. ISBN 978-3-540-28114-6
- ^ Naor (2006年). “One-Time Signatures Revisited: Practical Fast Signatures Using Fractal Merkle Tree Traversal”. IEEE. 13 May 2014閲覧。
- ^ Barreto, Paulo S. L. M.; Biasi, Felipe Piazza; Dahab, Ricardo; López-Hernández, Julio César; Morais, Eduardo M. de; Oliveira, Ana D. Salina de; Pereira, Geovandro C. C. F.; Ricardini, Jefferson E. (2014). Koç, Çetin Kaya. ed. A Panorama of Post-quantum Cryptography. Springer International Publishing. pp. 387–439. doi:10.1007/978-3-319-10683-0_16. ISBN 978-3-319-10682-3
- ^ De Feo (2011年). “Towards Quantum-Resistant Cryptosystems From Supersingular Elliptic Curve Isogenies”. 11 February 2014時点のオリジナルよりアーカイブ。12 May 2014閲覧。
- ^ “Cryptology ePrint Archive: Report 2016/229”. eprint.iacr.org. 2016年3月2日閲覧。
- ^ Ristic (2013年6月25日). “Deploying Forward Secrecy”. SSL Labs. 14 June 2014閲覧。
- ^ “Does NTRU provide Perfect Forward Secrecy?”. crypto.stackexchange.com. Template:Cite webの呼び出しエラー:引数 accessdate は必須です。
- ^ a b “Open Quantum Safe”. openquantumsafe.org. Template:Cite webの呼び出しエラー:引数 accessdate は必須です。
- ^ Stebila. “Post-Quantum Key Exchange for the Internet and the Open Quantum Safe Project”. Cryptology ePrint Archive, Report 2016/1017, 2016. 9 April 2017閲覧。
- ^ “liboqs: C library for quantum-resistant cryptographic algorithms” (26 November 2017). Template:Cite webの呼び出しエラー:引数 accessdate は必須です。
- ^ “openssl: Fork of OpenSSL that includes quantum-resistant algorithms and ciphersuites based on liboqs” (9 November 2017). Template:Cite webの呼び出しエラー:引数 accessdate は必須です。
- ^ “BIKE – Bit Flipping Key Encapsulation”. bikesuite.org. 2023年8月21日閲覧。
- ^ “HQC”. pqc-hqc.org. 2023年8月21日閲覧。
- ^ Fast and Efficient Hardware Implementation of HQC
- ^ Bos, Joppe; Costello, Craig; Ducas, Léo; Mironov, Ilya; Naehrig, Michael; Nikolaenko, Valeria; Raghunathan, Ananth; Stebila, Douglas (2016-01-01). “Frodo: Take off the ring! Practical, Quantum-Secure Key Exchange from LWE”. Cryptology ePrint Archive. http://eprint.iacr.org/2016/659.
- ^ “FrodoKEM” (英語). frodokem.org. 2023年8月21日閲覧。
- ^ “NTRUOpenSourceProject/NTRUEncrypt” (英語). GitHub. 2017年4月10日閲覧。
- ^ Schwabe. “Dilithium”. pq-crystals.org. 2023年8月19日閲覧。
- ^ Cryptographic Suite for Algebraic Lattices, Digital Signature: Dilithium
- ^ Stebila (26 Mar 2018). “liboqs nist-branch algorithm datasheet: kem_newhopenist”. GitHub. 27 September 2018閲覧。
- ^ “Lattice Cryptography Library”. Microsoft Research (19 Apr 2016). 27 September 2018閲覧。
- ^ “SIDH Library – Microsoft Research” (英語). Microsoft Research. https://www.microsoft.com/en-us/research/project/sidh-library/ 2017年4月10日閲覧。
- ^ Feo, Luca De; Jao, David; Plût, Jérôme (2011-01-01). “Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies”. Cryptology ePrint Archive. https://eprint.iacr.org/2011/506.
- ^ Bernstein, Daniel J.; Chou, Tung; Schwabe, Peter (2015-01-01). “McBits: fast constant-time code-based cryptography”. Cryptology ePrint Archive. https://eprint.iacr.org/2015/610.
- ^ “Microsoft/Picnic” (英語). GitHub. 2018年6月27日閲覧。
- ^ “Toward Quantum Resilient Security Keys” (英語). Google Online Security Blog. 2023年8月19日閲覧。
- ^ a b Apple Security Engineering and Architecture (SEAR) (February 21, 2024). “iMessage with PQ3: The new state of the art in quantum-secure messaging at scale”. Apple Security Research. Apple Inc.. 2024年2月22日閲覧。 “With compromise-resilient encryption and extensive defenses against even highly sophisticated quantum attacks, PQ3 is the first messaging protocol to reach what we call Level 3 security — providing protocol protections that surpass those in all other widely deployed messaging apps.”
- ^ Rossignoi (February 21, 2024). “Apple Announces 'Groundbreaking' New Security Protocol for iMessage”. MacRumors. 2024年2月22日閲覧。
- ^ Potuck (February 21, 2024). “Apple launching quantum computer protection for iMessage with iOS 17.4, here’s what that means”. 9to5Mac. 2024年2月22日閲覧。
- ^ Bouncy Castle Betas
- ^ Open Quantum Safe
参考文献
- 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
- 高木剛 (2017). “ポスト量子暗号の構成法とその安全性評価”. Fundamentals Review 2017年11巻1号: p.17-27. https://www.jstage.jst.go.jp/article/essfr/11/1/11_17/_article/-char/ja/.
- 宮地充子 (2021). “楕円曲線の理論的及び実用的可能性 ―楕円曲線暗号から耐量子暗号まで―”. Fundamentals Review 2021年14巻4号: p.329-336. https://www.jstage.jst.go.jp/article/essfr/14/4/14_329/_article/-char/ja/.
- 國廣昇 (2022). “量子計算機と暗号:耐量子計算機暗号への移行”. 日本セキュリティ・マネジメント学会誌 35 巻 3 号: p.18-24. https://www.jstage.jst.go.jp/article/jssmjournal/35/3/35_18/_article/-char/ja.
- 高木剛 (2023). “量子計算機時代のセキュリティ ――耐量子計算機暗号の動向――”. 電子情報通信学会 - IEICE会誌 Vol.106 No.11. https://app.journal.ieice.org/trial/106_11/k106_11_966/index.html.
- 細山田光倫 (2023). “共通鍵暗号技術のポスト量子安全性について”. Fundamentals Review 2023年17巻1号: p.59-71. https://www.jstage.jst.go.jp/article/essfr/17/1/17_59/_article/-char/ja.
外部リンク
- PQCrypto, the post-quantum cryptography conference
- ETSI Quantum Secure Standards Effort
- NIST's Post-Quantum crypto Project
- PQCrypto Usage & Deployment
- ISO 27001 Certification Cost