第 16 回情報セキュリティ シンポジウム 2015 年 3 月 11 日 ( 水 ) - 講演 3- 量子コンピュータによる解読に耐えうる 格子暗号 を巡る最新動向 日本銀行金融研究所情報技術研究センター清藤武暢 本発表は ( 独 ) 情報通信研究機構青野良範研究員 横浜国立大学四方順司准教授と共

Transcription

1 第 16 回情報セキュリティ シンポジウム 2015 年 3 月 11 日 ( 水 ) - 講演 3- 量子コンピュータによる解読に耐えうる 格子暗号 を巡る最新動向 日本銀行金融研究所情報技術研究センター清藤武暢 本発表は ( 独 ) 情報通信研究機構青野良範研究員 横浜国立大学四方順司准教授と共同で実施した 1 研究に基づく また 本発表に示されている意見は 発表者個人に属し 日本銀行 ( 独 ) 情報通信研究機構及び横浜国立大学の公式見解を示すものではない

2 本講演の概要 2 金融分野に限らず データの保護や通信相手の認証等を行うため に暗号アルゴリズムが広く利用されている 暗号アルゴリズムの種類 : 公開鍵暗号 共通鍵暗号等 現在主流の公開鍵暗号であるRSAや楕円曲線暗号は 量子コンピュータ ( 量子デジタル型 ) が実現すれば容易に解読できることが知られている 技術進歩により 同コンピュータの実現可能性は高まっていくものと推測される 量子コンピュータでも容易に解読できない暗号アルゴリズム ( 耐量子暗号 ) の研究が不可欠 耐量子暗号の 1 つとして 格子暗号 が学界で注目されている 本講演では 格子暗号の概要や研究動向について紹介したうえで 同暗号の利用を考えた場合に留意すべき点等について考察する 学界では 量子デジタル型は 量子ゲート方式 ( 量子チューリングマシン ) と呼ばれる

3 本講演の流れ 3 量子コンピュータが暗号アルゴリズムに与える影響 格子暗号 : 概要 イメージ おわりに 安全性評価動向

4 量子コンピュータが 暗号アルゴリズムに与える影響 4

5 金融分野における暗号アルゴリズムの利用 5 IC カードの真正性確認 (AES RSA) 通信内容の保護 IC カード ATM/POS 利用者 金融機関のホストシステム等 PC 携帯端末 インターネット 通信内容の保護 (TripleDES,AES,Camellia 等 ) 通信相手の認証 (RSA 楕円曲線暗号等 )

6 公開鍵暗号 : 概要 6 送信者 公開鍵 秘密鍵 受信者 メッセージ ( 平文 ) 暗号化 暗号文 安全ではない通信路 復号 メッセージ ( 平文 ) 公開鍵暗号の安全性 : 公開鍵から秘密鍵を求めるのが困難 数学的問題 により保証 例 : 素因数分解問題 (RSA の安全性の根拠 ) N(=P Q) 公開鍵 困難 容易 素数 P,Q 秘密鍵 数値例 : 桁数 2 桁 : 桁数 3 桁 : 桁数 5 桁 : 73, 桁数が大きくなるほど難しい ( 推奨桁長 :600 桁程度 )

7 RSA と楕円曲線暗号の潜在的な脅威と耐量子暗号 7 量子コンピュータ ( 量子デジタル型 ) が実用化されると RSA( 素因数分解問題 ) や楕円曲線暗号 ( 楕円曲線離散対数問題 ) が容易に解けることが知られている 同コンピュータでも容易に解読できない公開鍵暗号 ( 耐量子暗号 ) は 将来的に必ず必要となる技術 耐量子暗号 楕円曲線暗号 RSA 160 ビット 224 ビット 256 ビット 1,024 ビット 2,048 ビット 3,072 ビット 量子コンピュータ ( 量子デジタル型 ) の実用化 年 2xxx

8 耐量子暗号の 1 つ : 格子暗号 8 これまでにいろいろな種類の耐量子暗号が提案されている 近年 量子コンピュータへの耐性に加えて 利便性の高い機能を実現可能な格子暗号が学界で注目されている 暗号アルゴリズムの分類 公開鍵暗号 情報理論的暗号 特に クラウドサービスや医療分野等への同暗号の応用に関する研究が活発化しており 既に製品化も始まっている [1] 耐量子暗号の代表例 格子暗号 符号ベース暗号 多変数暗号 量子暗号 本講演では 耐量子暗号として格子暗号にフォーカス [1] 清藤 四方 高機能暗号を活用した情報漏えい対策 暗号化状態処理技術 の最新動向 金融研究 第 33 巻第 4 号 2014 年

9 格子暗号 : 概要 9

10 格子暗号 : 概要 10 格子暗号 (Lattice-based Cryptography) とは 格子 と呼ばれる数学的な構造を利用した公開鍵暗号の総称 格子暗号の特徴 : メリット 量子コンピュータでも容易に解読できないと期待されている データを暗号化したまま処理を行う技術 ( 暗号化状態処理技術 ) を実現可能 [1] データを暗号化したままキーワード検索 ( 秘匿検索 ) データを暗号化したまま統計解析等の数値計算 ( 秘匿計算 ) デメリット 鍵サイズが大きい 公開鍵のサイズについては 数キロビットの方式もあるが 数ペタ (10 15 ) ビットとなる方式もある 格子 (2 次元 ) の 1 例

11 格子暗号 : 主な実現方式の整理 (1/2) 11 現在提案されている格子暗号の主な実現方式は 4 種類存在し 観点 1: 暗号化処理に利用する数学的な構造 や 観点 2: 安全性の根拠 から それらの特徴を整理できる 観点 1: 暗号化処理 ( イメージ ) 実現方式の名称 LWE 方式 [2] NTRU 方式 [3] GGH 方式 [4] 暗号化処理に利用する数学的構造 行列演算 多項式演算 暗号化処理 ( イメージ ) [ 暗号文 1]=[ 乱数 ] [ 公開鍵 1], [ 暗号文 2]=[ 乱数 ] [ 公開鍵 2]+[ 平文 ]. 暗号文 =2 公開鍵 乱数 + 平文. 暗号文 = 平文 公開鍵 + 乱数. AD 方式 [5] 格子上のベクトル演算 はじめて安全性が厳密に証明された格子暗号 平文 =1 の場合 : 暗号文 = 乱数 公開鍵. 平文 =0 の場合 : 暗号文 = 乱数. [2]O. Regev, On Lattices, Learning with Errors, Random Linear Codes, and Cryptography, J.ACM 56(6), [3]J. Hoffstein, J. Pipher, and J. H. Silverman, NTRU: A Ring based Public Key Cryptosystem, ANTS-III, [4]O. Goldreich, S. Goldwasser, and S. Halevi, Public-Key Cryptosystems from Lattice Reduction Problems, CRYPTO1997. [5]M. Ajtai and C. Dwork, A Public-Key Cryptosystem with Worst/Average Case Equivalence, STOC1997.

12 観点 2: 安全性の根拠 実現方式の名称 LWE 方式 NTRU 方式 格子暗号 : 主な実現方式の整理 (2/2) 12 格子上で定義される数学的問題 を安全性の根拠として利用する公開鍵暗号が 格子暗号 と呼ばれる 利用される主な数学的問題 : 最近ベクトル問題 (Closest Vector Problem) GGH 方式 AD 方式 補足 最短ベクトル問題 (Shortest Vector Problem) これらの問題は 量子コンピュータで効率よく解けないと期待されている 安全性と格子上の数学的問題の関係 同方式を解く問題 = 最近ベクトル問題 同方式を解く問題 < 最短ベクトル問題 同方式を解く問題 < 最近ベクトル問題 同方式を解く問題 = 最短ベクトル問題 問題 A= 問題 B: 問題 A と B が同程度に難しいことが厳密に証明 問題 A< 問題 B: 問題 A よりも B の方が難しいことが厳密に証明 安全性と実用性のバランスが現時点では相対的に良い これらの方式を解く問題の難しさの下限は明らかにされていないため 安全性評価の進展に伴い 安全性が低下する場合あり [6,7] 安全に利用するために必要なパラメータ ( 次元数 鍵長 ) が膨大なため 実用性は低い [8] [6]Y. Chen and P. Nguyen, BKZ2.0: Better Lattice Security Estimate, ASIACRYPT2011. [7]P. Nguyen, Cryptanalysis of the Goldreich-Goldwasser-Halevi Cryptosystem from CRYPTO 97, CRYPTO1999. [8]P. Nguyen and J. Stern, Cryptanalysis of the Ajtai-Dwork Cryptosystem, CRYPTO1998.

13 格子暗号 : 実用化動向 13 暗号化状態処理技術の実現への利用事例 (LWE 方式 )[1,9,10]: 処理の名称主な用途処理性能 秘匿検索 秘匿計算 ビッグデータ分析 生体認証 国際標準化 (NTRU 方式 ): 1 万 6 千文字の暗号化データの全数検索が約 1 秒で可能 100 万件の暗号化データ (16 ビット整数 ) の共分散や相関係数が約 20 分で可能 100 万件の暗号化データの線形回帰係数の計算が約 40 分で可能 生体情報 (2,048 次元の生体特徴ベクトル ) の照合が約 5 ミリ秒で可能 IEEE Public-Key Cryptographic Techniques Based on Hard Problems over Lattices(2009 年 ). ANSI X9.98 Lattice-Based Polynomial Public-Key Establishment Algorithm for the Financial Services Industry(2010 年 ). ただし これらの標準の規格化後も安全性評価の進展に伴い 同標準に記載されている推奨パラメータの安全性は低下しうることに留意が必要 [9] 安田 下山 小暮 準同型暗号による秘匿統計計算 SCIS2015 [10] 青野 林 フォン 王 セキュリティアップデータブル準同型暗号を用いた秘匿データの線形回帰計算 SCIS2015

14 格子暗号 : イメージ 本講演では 暗号化処理と安全性の根拠に格子を利用し かつ処理の流れを視覚化できる GGH 方式 をベースとした格子暗号のイメージを紹介 14

15 準備 : 格子の定義 15 格子 とは 空間上に規則正しく並んでいる点の集合 次元 や 基底ベクトル と呼ばれるパラメータにより 格子の構造や特徴が一意に定まる 基底ベクトルの種類 2 次元空間 ( 基底ベクトル :2 本 ) 3 次元空間 ( 基底ベクトル :3 本 ) 数千次元空間 ( 基底ベクトル : 数千本 ) 直交している基底ベクトル 原点 原点? 数千 直交していない基底ベクトル 原点 原点? 数千 ( : 格子点 ) 本講演では 2 次元空間上の格子を利用して格子暗号のイメージについて説明 ( 暗号で利用される格子は主に数千次元 )

16 準備 : 格子の 2 つの性質 16 性質 1 性質 2 全ての格子点は基底ベクトル (n 個のベクトルの組 n は次元数 ) の組合せで表現可能 つの格子において 複数の基底ベクトルが存在 (0,4) = + (20,4) (0,1) 原点 2 (2,0) (4,2) (0,1) 原点 (2,0) (4,1) 2 (6,1) (8,2) 2

17 鍵の設定 : 秘密鍵 1 秘密鍵として直交している基底ベクトル (, ) を選ぶ (0,1) 原点 (2,0) ある点に近い格子点を見つけやすい (0,1) 原点 (2,0) 点 容易 特徴 格子上の任意の格子点を表現しやすい ( 格子の全体像を把握するのが容易 ) 最も近い格子点! 困難 格子暗号 : 鍵の設定 ( イメージ ) 17 公開鍵 2(, ) を利用して 同じ格子を表現できる直交していない基底ベクトル (, ) を計算する (4,1) (6,1) 原点 どの直交ベクトルを使っているのか特定できない特徴 格子上の任意の格子点を表現しにくい ( 格子の全体像を把握するのが困難 ) 原点? (4,1) ある点に近い格子点を見つけにくい 格子暗号では これらの特徴を利用 (6,1) 点最も近い格子点?

18 暗号化処理 : 格子暗号 : 暗号化処理 ( イメージ ) 暗号化したい平文を 2 つの整数 (m 1,m 2 ) で表現 2. 公開鍵 ( ) を利用して 格子点 Pを以下のように計算 格子点 P=m 1 +m 2 3. 小さな実数ベクトルをランダムに選び 暗号文 C=P+ を計算 例 :(m 1, m 2 )=(2,2), =(0.2,0.2) の場合 : 2 格子点 P (20,4) 暗号文 C (20.2,4.2) (4,1) 2 (6,1) (8,2) (14,3) ベクトル を足して格子点 P の位置をずらす

19 格子暗号の安全性 : 格子点 P を求めることの難しさ 秘密鍵を利用した場合 秘密鍵 (, ) から 格子の全体像を把握するのは容易 格子点 P を容易に求めることができる 格子暗号 : 復号処理と安全性 ( イメージ ) 19 復号処理 : 格子点 P を求めることができれば 以下の手順で平文 (m 1,m 2 ) を容易に計算できる 1 格子点 Pを基底ベクトルの式で表現,,,. (0,1) 原点 (2,0) 格子点 P 暗号文 C 最近ベクトル問題 22 元 1 次連立方程式を解き 平文 (m 1,m 2 ) を計算 未知数,. 公開鍵を利用した場合 公開鍵 (, ) では 格子の全体像を把握するのが難しい 暗号文 C の周辺にある格子点 P となり得る候補をしらみつぶしに探索する必要がある この探索は指数関数時間かかる ( 次元数 n を大きくすると解くのが困難 )? (4,1) 暗号文 C 原点 (6,1)

20 格子暗号 : 安全性評価動向 20

21 格子暗号に対する一般的な攻撃手法 攻撃者の目的 : 格子点 Pの特定 攻撃者が利用可能な情報 : 公開鍵 (, ) 暗号文 C 処理 1: 探索範囲の絞り込み ( 格子基底簡約処理 ) 確率の高い探索範囲 格子点 P の探索 暗号文 C 主な方式 LLL 手法 BKZ 手法 BKZ2.0 手法 処理 2 しらみつぶしに探索 ( 探索処理 ) 公開鍵 公開鍵 暗号文 C 格子点 P 主な方式 Babai 手法 ランダムサンプリング手法 格子暗号 : 攻撃手法の整理 攻撃者 21 同手法に要する時間は指数関数時間 ( 次元数 n が大きくなると現実的な時間で解くのが困難 ) 量子コンピュータで効率よく解けないと期待されている 耐量子暗号 に分類される根拠

22 格子暗号 : 安全性評価の動向 22 等価安全性に基づく格子暗号と RSA 楕円曲線暗号の鍵長比較 : 128 ビット安全性 RSA 楕円曲線暗号(ECC) は NISTの評価 [11] を参照 格子暗号の各方式 (LWE 方式 GGH 方式 AD 方式 ) の鍵長と次元数は 文献 [10,12] の評価手法に基づき 最低限必要な値を算出 NTRU 方式は 国際標準 ANSI X9.98を参照 NTRU 方式 ( 約 7,000) 次元数 : 約 600 GGH 方式 ( 約 280M) 次元数 : 約 5,000 ECC (256) RSA (3,024) 1M ビット (10 6 ) LWE 方式 ( 約 7.8M) 次元数 : 約 250 1G ビット (10 9 ) [11]NIST, SP800-57:Recommendation for Key Management Part I: General (Revision 3), [12]R. Linder and C. Peikert, Better Key Sizes (and Attacks) for LWE-Based Encryption, CT-RSA2011. ~ 1P ビット (10 15 ) AD 方式 ( 約 490P) 次元数 : 約 15,000 鍵長

23 格子暗号 : 研究動向 23 格子暗号の各実現方式に関する最近の主な研究動向 : 主にパラメータ ( 鍵長等 ) の効率性向上や安全性評価に関する研究が活発 方式の名称 LWE 方式 NTRU 方式 GGH 方式 AD 方式 主な研究動向 鍵長を数千分の 1 程度 ( 数 K~ 数十 K ビット ) まで削減できる改良方式 (ring-lwe 方式 ) が提案され [13] 学界で活発に研究されている ただし 安全性については 格子上の数学的問題と同程度に難しいことが 現時点では証明されていない 同方式と LWE 方式を組み合わせることにより より厳密な安全性を証明可能な改良方式が提案 [14] NTRU 方式で用いている格子は 特殊な構造を有しているため 同構造に特有の脆弱性を利用した攻撃手法の提案および安全性の再評価が行われている ([6] 等 ) 安全に利用するために必要な鍵長等のパラメータが大きく かつ大幅な効率化も難しいと考えられているため これらの方式に関する研究については大きな進展なし [13]V. Lyubashevsky, C. Peikert, and O. Regev, On Ideal Lattices and Learning with Errors over Rings, EUROCRYPT2010. [14]D. Stehle and R. Steinfeld, Making NTRU as Secure as Worst-Case Problems over Ideal Lattices, EUROCRYPT2011.

24 耐量子暗号の 1 つ 格子暗号 おわりに 24 量子コンピュータにより 現在主流の公開鍵暗号である RSA や楕円曲線暗号は容易に解読できることが知られている ( 鍵長を伸ばしたとしても 安全性を確保できない ) 格子暗号は 量子コンピュータが実用化された状況下においても 容易に解読できないと期待されている 近年 格子暗号 (LWE 方式 ) を利用した暗号化状態処理 ( 秘匿検索 秘匿計算 ) の実装および製品化事例が増加 一部の実現方式 (NTRU 方式 ) は 国際標準 IEEE や ANSI において規定 格子暗号を選択する際の留意点 格子暗号を利用する際には その特徴 ( 鍵長が長い等 ) も理解したうえで適切な環境下での利用を検討する 例 :ICカードや組込み機器等の計算機性能( メモリ等 ) が制限されている環境での利用には 現時点では適さない点等 さらに 最新の安全性評価の結果に基づき パラメータ ( 次元 基底 鍵長等 ) を適切に選択する必要がある ただし 同評価の基準は定まっていないため 学界における評価動向を定期的にフォローすることが重要である

25 付録 量子コンピュータの研究開発動向 25 量子デジタル型 : 計算過程で利用する量子の 重ね合わせ状態 を維持することが難しく 現時点では理論研究および実験段階であり 実用化段階には至っていない 同コンピュータ上で動く ショア (Shor) のアルゴリズム により 素因数分解問題や楕円曲線離散対数問題が容易に解けることが知られているが [15] 現時点では 15=3 5 の素因数分解を実験的に計算可能な段階 [16] 量子アナログ型 : カナダのD-Wave Systems, Incが同コンピュータを販売したと発表 (2011 年 )[17] 量子人工知能研究所 (GoogleとNASA 等が共同開設 ) や ロッキード マーチン社等が購入したとの報道 [18] 学界では 量子アナログ型は 量子イジングマシン方式 と呼ばれる [15]P. Shor, Algorithms for Quantum Computation: Discrete Logarithms and Factoring, STOC1994. [16]L. M. K. Vandersypen, M. Steffen, G. Breyta, C. S. Yannoni, M. H. Sherwood, and I. L. Chuang, Experimental Realization of Shor s Quantum Factoring Algorithm using Nnclear Magnetic Resonance, Nature 414, [17]D-Wave Systems Press Releases, D-Wave Systems sells its first Quantum Computing System to Lockheed Martin Corporation, 2011/5/25. [18] [19] [19]

26 付録 量子コンピュータの共通鍵暗号への影響 26 量子コンピュータ ( 量子デジタル型 ) で動く グローバー (Grover) のアルゴリズム [20] により 共通鍵暗号 (AES 等 ) に対する鍵の全数探索の回数を削減できることが知られている [21] 等価安全性 鍵サイズ (AES) 鍵の全数探索に要する計算量 従来のコンピュータ環境 量子コンピュータ環境 128 ビット 128 ビット ビット 256 ビット 同脅威への対策 : 鍵長を 2 倍に増やすことにより対応可能 等価安全性 対策後の鍵サイズ (AES) 鍵の全数探索に要する計算量 従来のコンピュータ環境 量子コンピュータ環境 128 ビット 256 ビット ビット 512 ビット NIST FIPS197 に規定されている AES で利用可能な鍵長は 128 ビット 192 ビット 256 ビットの 3 種類のみとなっているため 別途 鍵長の拡張等の対応が必要 指数部の値が半分になる ( 等価安全性のレベル低下 ) 等価安全性のレベルを維持できると考えられている [20]L. K. Grover, A Fast Quantum Mechanical Algorithm for Database Search, STOC1996. [21]C. H. Bennett, E. Bernstein, G. Brassard, and U. Vazirani, A Fast Quantum Mechanical Algorithm for Database Search, SIAM J. Compt. 26(5), 1997.

27 付録 格子暗号 : 安全性評価の動向 ビット安全性 を実現するために必要な各方式の鍵長比較 : 256 ビット安全性 NTRU 方式 ( 約 13,000) 次元数 : 約 1,200 GGH 方式 ( 約 1.6G) 次元数 : 約 11,400 ECC (512) RSA (15,360) 1M ビット (10 6 ) LWE 方式 ( 約 30M) 次元数 : 約 460 1G ビット (10 9 ) ~ 1E ビット (10 18 ) AD 方式 ( 約 2.2E) 次元数 : 約 21,000 鍵長

28 現在のコンピュータ環境量子コンピュータが実現した場 付録 量子コンピュータが暗号アルゴリズムの安全性に与える影響 ( まとめ ) 28 公開鍵暗号 共通鍵暗号 2010 年 ~2030 年 2031 年 ~ RSA(2,048) ECC(224) AES(128) 3KeyTDES RSA(3,072) ECC(256) AES(128) カッコ内は鍵長 RSA(15,360) ECC(512) AES(256) ビット安全性 256ビット合112ビット 128ビット 共通鍵 AES(256) AES(256) 暗号? RSA(2,048) 危殆化! ECC(224) 同コンピュータが実現した場合 ( 鍵長を伸ばしても容易に解読 ) でも安全に利用できると期待 公開鍵格子暗号 暗号 LWE 方式 ( 約 ) LWE 方式 ( 約 ) LWE 方式 ( 約 ) NTRU 方式 ( 約 6,000) NTRU 方式 ( 約 7,000) NTRU 方式 ( 約 13,000) GGH 方式 ( 約 ) GGH 方式 ( 約 ) GGH 方式 ( 約 ) AD 方式 ( 約 ) AD 方式 ( 約 ) AD 方式 ( 約 2, )