ポスト量子暗号

Takami Torao #PQC
  • このエントリーをはてなブックマークに追加

概要

ポスト量子暗号 (PQC; post-quantum cryptography) は量子計算耐性を持つ暗号アルゴリズムのこと。現在広く使用されている暗号アルゴリズムの多くは素因数分解問題 (RSA など)、または離散対数問題 (楕円曲線や BLS など) の困難性に基づいている。これらは現代のコンピュータにおいて堅牢なセキュリティを提供することができるが、将来的に十分な安全性を確保できなくなる可能性が指摘されている。

例えば Shor のアルゴリズムは量子コンピュータの計算を用いて多項式時間で素因数分解問題を解く量子アルゴリズムである。ただし、このためには量子誤りのない理想的な環境で 4098 量子ビット、量子誤り訂正が必要な環境で 2000 万量子ビットが必要と見積もられており、現在の数十量子ビットの量子コンピュータではすぐに危殆化(きたいか)することはないとされている[1]。

量子コンピュータに対する防衛策の一つは、現在の暗号アルゴリズムで使用されているキーサイズを倍以上に増加することである (例えば 128 ビットを 256 ビット以上へといったように)。もう一つの方法は本質的に量子計算耐性を持つ暗号へ移行することである。このような暗号スキームをポスト量子暗号と呼ぶ。

  • 格子暗号 (LBC; lattice-based cryptography) - 多次元格子の幾何学的問題の困難性に基づく暗号スキーム。これらは最短ベクトル問題、最近接ベクトル問題、LWE 問題に基づく NP 困難問題である。PQC の他にも完全準同型暗号でも盛んに研究されている。
    • NTRU
  • ハッシューベース暗号 (hash-based cryptography) - 現在広く利用されている暗号論的ハッシュ関数は離散対数問題のような困難性を根拠にしておらず、量子計算による攻撃の影響を受けないと考えられている (ただし一部のハッシュアルゴリズムは Grover のアルゴリズムを使用して、量子重ね合わせにより全ての入力値を同時にテストできる可能性がある)。ハッシュベース暗号は現在のところ電子署名スキームに限定されている。
    • マークル署名スキーム (MSS) -
    • 拡張マークル署名スキーム (XMSS; 2011) - MSS の拡張版でセキュリティが高められている。
    • Leighton-Micali 署名 (LMS) - 基本構成はマークル署名の one-time 署名。
    • SPHINCS / SPHINCS+ (2015) - ステートレス署名スキーム。SPHINCS の署名は 41kB とかなり大きく、SPHINCS+ でも最高強度で 30kB、最低強度で 8kB の大きさとなる。
  • コードベース暗号 (CBC; code-based cryptography) - エラー訂正コード (ECC) に基づく暗号および署名スキーム。最適化されたコードベース暗号は非常に軽量で高速であるため省電力デバイスに適している。
    • McEliece 暗号 - バイナリ Goppa というエラー訂正コードを使用する。Goppa は特定の値を超えたらゼロに戻るモジュラー演算に基づいている。Goppa 符号は堅牢だが公開鍵がかなり大きくなる傾向を持つ。
    • Niederreiter 暗号 - McEliece 暗号を補強したスキーム。全体的なセキュリティレベルは MacEliece と同等とみなされているが、暗号化において MacEliece よりも高速になる。
  • 多変量暗号 - 多変量多項式に基づく暗号プリミティブ。PQC に対して非常に強力な見立てがあるが、2020 年の時点ではまだ完全に熟成しておらず将来的に未発見の攻撃ベクトルが問題になる可能性がある。
    • Hidden Field Equations (HFE; 1996) - 二次方程式の解の難しさに基づいて構築されている。
    • Unbalanced oil and vinegar (UOV) - "Oil" と "Vinegar" と呼ばれる 2 種類の変数を区別することの難しさに基づく。ほとんどの UOV は加算と乗算に基づいているため非力なハードウェアでも高速に実装できるが、鍵はかなり大きくなる傾向がある。balanced oil and vinegar と呼ばれる UOV の前バージョンは 1998 に突破された。
    • Rainbow (2005) - UOV の多層実装に基づく署名スキーム。UOV と同様に鍵と署名のサイズが大きいが程度はより小さい。

ハッシュベース暗号

ハッシュベース暗号 (hash-based cryptography) は素因数分解や離散対数のような数学的な問題の困難性を利用するのではなく、暗号論的ハッシュ関数によって確立されるセキュリティに基づいている。…

2020年10月22日(Thu) #WOTS #MSS

格子暗号

格子暗号 (lattice-based cryptography) は多次元の格子構造を用いた公開鍵暗号スキーム。証明可能な強力なセキュリティの保証や量子計算耐性、完全準同型暗号へ応用可能といった特性を持っている。…

2020年4月1日(Wed) #NTRU

参照

  1. CRYPTREC 暗号技術評価委員会 (2020) 現在の量子コンピュータによる暗号技術の安全性への影響. CRYPTREC ER-0001-2019