第16回情報セキュリティ・シンポジウム 2015年3月11日（水） -講演3- 量子コンピュータによる解読に耐えうる 『格子暗号』を巡る最新動向 日本銀行金融研究所 情報技術研究センター 清藤武暢 本発表は、（独）情報通信研究機構 青野良範研究員、横浜国立大学 四方順司准教授と共同で実施した 1 研究に基づく。また、本発表に示されている意見は、発表者個人に属し、日本銀行、（独）情報通信研究機構 及び横浜国立大学の公式見解を示すものではない。 本講演の概要 2 ■ 金融分野に限らず、データの保護や通信相手の認証等を行うため に暗号アルゴリズムが広く利用されている。 暗号アルゴリズムの種類：公開鍵暗号、共通鍵暗号等 ■ 現在主流の公開鍵暗号であるRSAや楕円曲線暗号は、「量子コン ピュータ（量子デジタル型※）」が実現すれば容易に解読できること が知られている。 技術進歩により、同コンピュータの実現可能性は高まっていくものと 推測される。 量子コンピュータでも容易に解読できない 暗号アルゴリズム（耐量子暗号）の研究が不可欠 ■ 耐量子暗号の1つとして「格子暗号」が学界で注目されている。 ■ 本講演では、格子暗号の概要や研究動向について紹介したうえ で、同暗号の利用を考えた場合に留意すべき点等について考察 する。 ※学界では、量子デジタル型は「量子ゲート方式（量子チューリングマシン）」と呼ばれる。 本講演の流れ ■ 量子コンピュータが暗号アルゴリズムに与える影響 ■ 格子暗号： 概要 イメージ 安全性評価動向 ■ おわりに 3 量子コンピュータが 暗号アルゴリズムに与える影響 4 金融分野における暗号アルゴリズムの利用 ICカードの真正性確認 （AES、RSA） ICカード 5 通信内容の保護 ATM/POS 金融機関の ホストシステム等 利用者 PC 携帯端末 インターネット ・ 通信内容の保護 （TripleDES,AES,Camellia等） ・ 通信相手の認証 （RSA、楕円曲線暗号等） 公開鍵暗号：概要 秘密鍵 公開鍵 送信者 暗号化 メッセージ （平文） 暗号文 受信者 復号 安全ではない 通信路 メッセージ （平文） 公開鍵暗号の安全性： 公開鍵から秘密鍵を求めるのが困難⇒「数学的問題」により保証 例：素因数分解問題（RSAの安全性の根拠） 数値例： 困難 N（=P×Q） 公開鍵 素数P,Q 容易 秘密鍵 桁数2桁： 33 → 3×11 桁数3桁： 989 → 43×23 桁数5桁： 73,903 → 263×281 桁数が大きくなるほど難しい （推奨桁長：600桁程度） 6 RSAと楕円曲線暗号の潜在的な脅威と耐量子暗号 7 ■ 量子コンピュータ（量子デジタル型）が実用化されると、RSA（素因 数分解問題）や楕円曲線暗号（楕円曲線離散対数問題）が容易に 解けることが知られている。 同コンピュータでも容易に解読できない公開鍵暗号 （耐量子暗号）は、将来的に必ず必要となる技術。 耐量子暗号 楕円曲線 160ビット 暗号 RSA 1,024ビット 2000 224ビット 2,048ビット 2010 256ビット 量子コンピュータ （量子デジタル型） の実用化 3,072ビット 2030 2xxx 年 耐量子暗号の1つ：格子暗号 ■ これまでにいろいろな種類の耐量子暗号が提案されている。 暗号アルゴリズムの分類 公開鍵暗号 情報理論的暗号 耐量子暗号の代表例 格子暗号 符号ベース暗号 多変数暗号 量子暗号 ■ 近年、量子コンピュータへの耐性に加えて、利便性の高い機能を 実現可能な格子暗号が学界で注目されている。 特に、クラウドサービスや医療分野等への 同暗号の応用に関する研究が活発化 しており、既に製品化も始まっている[1]。 本講演では、耐量子暗号として格子暗号にフォーカス [1]清藤・四方、「高機能暗号を活用した情報漏えい対策『暗号化状態処理技術』の最新動向」、『金融研究』、第33巻第4号、2014年 8 格子暗号：概要 9 格子暗号：概要 10 ■ 格子暗号（Lattice-based Cryptography） とは、「格子」と呼ばれる数学的な構造を 利用した公開鍵暗号の総称。 ■ 格子暗号の特徴： 格子（2次元）の1例 メリット 量子コンピュータでも容易に解読できないと期待されている。 データを暗号化したまま処理を行う技術（暗号化状態処理技術） を実現可能[1]。 データを暗号化したままキーワード検索（秘匿検索）。 データを暗号化したまま統計解析等の数値計算（秘匿計算）。 デメリット 鍵サイズが大きい。 公開鍵のサイズについては、数キロビットの方式もあるが、 数ペタ（1015）ビットとなる方式もある。 格子暗号：主な実現方式の整理（1/2） 11 ■ 現在提案されている格子暗号の主な実現方式は4種類存在し、 「観点1：暗号化処理に利用する数学的な構造」や「観点2：安全 性の根拠」から、それらの特徴を整理できる。 観点1：暗号化処理（イメージ） 実現方式 の名称 LWE方式[2] NTRU方式[3] 暗号化処理に 利用する数学的構造 暗号化処理（イメージ） 行列演算 [暗号文1]=[乱数]×[公開鍵1], [暗号文2]=[乱数]×[公開鍵2]＋[平文]. 多項式演算 GGH方式[4] AD方式[5] 暗号文=2×公開鍵×乱数＋平文. 暗号文=平文×公開鍵+乱数. 格子上のベクトル演算 ・ 平文=1の場合：暗号文=乱数×公開鍵. ・ 平文=0の場合：暗号文=乱数. はじめて安全性が厳密に証明された格子暗号 [2]O. Regev, “On Lattices, Learning with Errors, Random Linear Codes, and Cryptography,” J.ACM 56(6), 2009. [3]J. Hoffstein, J. Pipher, and J. H. Silverman, “NTRU: A Ring based Public Key Cryptosystem,” ANTS-III, 1998. [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. 格子暗号：主な実現方式の整理（2/2） 12 観点2：安全性の根拠 ■ 「格子上で定義される数学的問題」を安全性の根拠として利用す る公開鍵暗号が「格子暗号」と呼ばれる。 利用される主な数学的問題：最近ベクトル問題（Closest Vector Problem）、 最短ベクトル問題（Shortest Vector Problem）。 これらの問題は、量子コンピュータで効率よく解けないと期待されている。 実現方式 の名称 安全性と格子上の 数学的問題の関係 LWE方式 同方式を解く問題=最近ベクトル問題 NTRU方式 同方式を解く問題<最短ベクトル問題 GGH方式 同方式を解く問題<最近ベクトル問題 AD方式 同方式を解く問題=最短ベクトル問題。 ※補足 ・問題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 ■ 暗号化状態処理技術の実現への利用事例（LWE方式）[1,9,10]： 処理の名称 主な用途 処理性能 1万6千文字の暗号化データの全数検索 が約1秒で可能。 秘匿検索 ビッグデータ 100万件の暗号化データ（16ビット整数） の共分散や相関係数が約20分で可能。 分析 100万件の暗号化データの線形回帰係数 の計算が約40分で可能。 秘匿計算 生体認証 生体情報（2,048次元の生体特徴ベクト ル）の照合が約5ミリ秒で可能。 ■ 国際標準化（NTRU方式）： IEEE1363.1 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 格子暗号：イメージ 本講演では、暗号化処理と安全性の根拠に格子を利用し、かつ処理の 流れを視覚化できる「GGH方式」をベースとした格子暗号のイメージを紹介。 14 準備：格子の定義 15 ■ 「格子」とは、空間上に規則正しく並んでいる点の集合。「次元」や 「基底ベクトル」と呼ばれるパラメータにより、格子の構造や特徴 が一意に定まる。 基底ベクトル の種類 2次元空間 （基底ベクトル：2本） 3次元空間 数千次元空間 ・・・ （基底ベクトル：3本） （基底ベクトル：数千本） 直交している 基底ベクトル ・・・ 原点 ・・・ 数千 原点 直交していない 基底ベクトル ・・・ 原点 原点 ？ ？ ・・・ 数千 （ ：格子点） 本講演では、2次元空間上の格子を利用して格子暗号の イメージについて説明（暗号で利用される格子は主に数千次元）。 準備：格子の2つの性質 性質1 性質2 全ての格子点は基底ベク トル（n個のベクトルの組、 nは次元数）の組合せで 表現可能。 1つの格子において、複数の基底ベクトルが存在。 + = 20 + 2 原点 2 (2,0) + (0,4) (20,4) 4 (0,1) 16 (4,2) 2 2 (8,2) (4,1) (0,1) (6,1) 原点 (2,0) 格子暗号：鍵の設定（イメージ） 17 ■ 鍵の設定： 秘密鍵 公開鍵 ①秘密鍵として直交している基底ベクトル （ , ）を選ぶ。 (0,1) 容易 原点 ② （ , ）を利用して、同じ格子を表現で きる直交していない基底ベクトル（ , ） を計算する。 (4,1) (6,1) 原点 (2,0) どの直交ベクトルを使って いるのか特定できない 困難 特徴 特徴 格子上の任意の格子点を表現しやすい 格子上の任意の格子点を表現しにくい （格子の全体像を把握するのが容易）。 （格子の全体像を把握するのが困難）。 ある点に近い格子点を見つけにくい ある点に近い格子点を見つけやすい (0,1) 原点 点 (2,0) 最も近い格子点！ ？ (4,1) 原点 点 (6,1) 格子暗号では、これらの特徴を利用。 最も近い格子点？ 格子暗号：暗号化処理（イメージ） 18 ■ 暗号化処理： 1. 暗号化したい平文を2つの整数（m1,m2）で表現。 2. 公開鍵（ 、 ）を利用して、格子点Pを以下のように計算。 格子点P=m1× +m2× 3. 小さな実数ベクトル をランダムに選び、暗号文C=P+ を計算。 例：(m1, m2)=(2,2), =(0.2,0.2)の場合： 暗号文C 格子点P (20.2,4.2) 2 2 (14,3) (8,2) (4,1) (6,1) (20,4) ベクトル を足して 格子点Pの位置をずらす 格子暗号：復号処理と安全性（イメージ） 19 ■ 復号処理：格子点Pを求めることができれば、以下の手順で平文 （m1,m2）を容易に計算できる。 ②2元1次連立方程式を解き、 平文（m1,m2）を計算。 未知数 ①格子点Pを基底ベクトルの式で表現 , , , , . . 格子暗号の安全性：格子点Pを求めることの難しさ 秘密鍵を利用した場合 公開鍵を利用した場合 秘密鍵（ , ）から、格子の全体像を 把握するのは容易。 格子点Pを容易に求めることができる。 公開鍵（ , ）では、格子の全体像を把握す るのが難しい。 暗号文Cの周辺にある格子点Pとなり得る候 補をしらみつぶしに探索する必要がある。 暗号文C 格子点P 最近ベクトル問題 (0,1) 原点 (2,0) この探索は指数関数時間かかる。 （次元数nを大きくすると解くのが困難） ？ 暗号文C (4,1) 原点 (6,1) 格子暗号：安全性評価動向 20 格子暗号：攻撃手法の整理 21 ■ 格子暗号に対する一般的な攻撃手法 攻撃者の目的：格子点Pの特定 攻撃者が利用可能な情報：公開鍵（ , ）、暗号文C 処理①：探索範囲の絞り込み （格子基底簡約処理） 確率の高い 探索範囲 暗号文C 公開鍵 主な方式 ・LLL手法 ・BKZ手法 ・BKZ2.0手法 攻撃者 処理②しらみつぶしに探索（探索処理） 格子点P の探索 暗号文C 主な方式 ・Babai手法 ・ランダムサンプリング手法 公開鍵 格子点P 同手法に要する時間は 指数関数時間（次元数n が大きくなると現実的な 時間で解くのが困難）。 量子コンピュータで効率 よく解けないと期待され ている。 「耐量子暗号」に 分類される根拠 格子暗号：安全性評価の動向 22 ■ 等価安全性に基づく格子暗号とRSA、楕円曲線暗号の鍵長比較： RSA、楕円曲線暗号（ECC）は、NISTの評価[11]を参照。 格子暗号の各方式（LWE方式、GGH方式、AD方式）の鍵長と次元数は、 文献[10,12]の評価手法に基づき、最低限必要な値を算出。 NTRU方式は、国際標準ANSI X9.98を参照。 128ビット安全性 NTRU方式 （約7,000） GGH方式 （約280M） 次元数：約600 次元数：約5,000 ECC RSA （256） （3,024） LWE方式 （約7.8M） AD方式 （約490P） 次元数：約250 1Mビット （106） 次元数：約15,000 ～ ～ 1Gビット 1Pビット （109） （1015） [11]NIST, “SP800-57:Recommendation for Key Management –Part I: General (Revision 3),” 2012. [12]R. Linder and C. Peikert, “Better Key Sizes (and Attacks) for LWE-Based Encryption,” CT-RSA2011. 鍵長 格子暗号：研究動向 23 ■ 格子暗号の各実現方式に関する最近の主な研究動向： 主にパラメータ（鍵長等）の効率性向上や安全性評価に関する研究が活発。 方式の名称 主な研究動向 LWE方式 鍵長を数千分の1程度（数K～数十Kビット）まで削減できる改良 方式（ring-LWE方式）が提案され[13]、学界で活発に研究され ている。ただし、安全性については、格子上の数学的問題と同 程度に難しいことが、現時点では証明されていない。 NTRU方式 同方式とLWE方式を組み合わせることにより、より厳密な安 全性を証明可能な改良方式が提案[14]。 NTRU方式で用いている格子は、特殊な構造を有しているた め、同構造に特有の脆弱性を利用した攻撃手法の提案およ び安全性の再評価が行われている（[6]等)。 GGH方式 AD方式 安全に利用するために必要な鍵長等のパラメータが大きく、か つ大幅な効率化も難しいと考えられているため、これらの方式 に関する研究については大きな進展なし。 [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つ「格子暗号」 量子コンピュータにより、現在主流の公開鍵暗号であるRSAや楕円曲線暗 号は容易に解読できることが知られている（鍵長を伸ばしたとしても、安全 性を確保できない）。 格子暗号は、量子コンピュータが実用化された状況下においても、容易に 解読できないと期待されている。 近年、格子暗号（LWE方式）を利用した暗号化状態処理（秘匿検索、 秘匿計算）の実装および製品化事例が増加。 一部の実現方式（NTRU方式）は、国際標準IEEEやANSIにおいて規定。 ■ 格子暗号を選択する際の留意点 格子暗号を利用する際には、その特徴（鍵長が長い等）も理解したうえで 適切な環境下での利用を検討する。 例：ICカードや組込み機器等の計算機性能（メモリ等）が制限されている環境 での利用には、現時点では適さない点等。 さらに、最新の安全性評価の結果に基づき、パラメータ（次元、基底、鍵長 等）を適切に選択する必要がある。ただし、同評価の基準は定まっていない ため、学界における評価動向を定期的にフォローすることが重要である。 【付録】量子コンピュータの研究開発動向 25 ■ 量子デジタル型：計算過程で利用する量子の「重ね合わせ状態」 を維持することが難しく、現時点では理論研究および実験段階で あり、実用化段階には至っていない。 同コンピュータ上で動く「ショア（Shor）のアルゴリズム」により、素因数分解 問題や楕円曲線離散対数問題が容易に解けることが知られているが[15]、 現時点では「15=3×5」の素因数分解を実験的に計算可能な段階[16]。 ■ 量子アナログ型※：カナダのD-Wave Systems, Incが同コン ピュータを販売したと発表（2011年）[17]。 量子人工知能研究所（GoogleとNASA等が 共同開設）や、ロッキード・マーチン社等が 購入したとの報道[18]。 ※学界では、量子アナログ型は「量子イジングマシン方式」 と呼ばれる。 [19] [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, 2001. [17]D-Wave Systems Press Releases, “D-Wave Systems sells its first Quantum Computing System to Lockheed Martin Corporation,” 2011/5/25. [18]http://www.dwavesys.com/our-company/customers [19]http://www.dwavesys.com/tutorials/background-reading-series/introduction-d-wave-quantum-hardware 【付録】量子コンピュータの共通鍵暗号への影響 ■ 量子コンピュータ（量子デジタル型）で動く「グローバー（Grover）のアルゴリズ ム[20]」により、共通鍵暗号（AES等）に対する鍵の全数探索の回数を削減でき ることが知られている[21]。 等価安全性 ■ 26 鍵サイズ （AES） 鍵の全数探索に要する計算量 従来の コンピュータ環境 量子 コンピュータ環境 128ビット 128ビット 2128 264 256ビット 256ビット 2256 2128 指数部の値が 半分になる。 （等価安全性の レベル低下） 同脅威への対策：鍵長を2倍に増やすことにより対応可能。 等価安全性 対策後の 鍵サイズ（AES） 128ビット 256ビット 鍵の全数探索に要する計算量 従来の コンピュータ環境 量子 コンピュータ環境 256ビット 2256 2128 512ビット※ 2512 2256 等価安全性のレベル ※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ビット安全性」を実現するために必要な各方式の鍵長比較： 256ビット安全性 ECC （512） NTRU方式 （約13,000） GGH方式 （約1.6G） 次元数：約1,200 次元数：約11,400 RSA （15,360） LWE方式 （約30M） AD方式 （約2.2E） 次元数：約460 1Mビット （106） 1Gビット （109） 次元数：約21,000 ～ ～ 1Eビット （1018） 鍵長 現在のコンピュータ環境 【付録】量子コンピュータが暗号アルゴリズムの安全性に与える影響（まとめ） ※カッコ内は鍵長。 2010年～2030年 2031年～ 公開鍵 暗号 RSA（2,048） RSA（3,072） RSA（15,360） ECC（224） ECC（256） ECC（512） 共通鍵 暗号 AES（128） AES（128） AES（256） 128ビット 256ビット 量子コンピュータが実現した場合 ビット安全性 公開鍵 暗号 共通鍵 暗号 3KeyTDES 112ビット 28 RSA（2,048） 危殆化！ 同コンピュータが実現した場合 ECC（224） （鍵長を伸ばしても容易に解読） でも安全に利用できると期待。 格子暗号 LWE方式（約6.6×106） LWE方式（約7.8×106） LWE方式（約30×106） NTRU方式（約6,000） NTRU方式（約7,000） NTRU方式（約13,000） GGH方式（約180×106） GGH方式（約280×106） GGH方式（約1.6×109） AD方式（約360×1015） AD方式（約490×1015） AD方式（約2,2×1018） AES（256） AES（256） ？
© Copyright 2024 ExpyDoc
