PowerPoint プレゼンテーション

Size: px

Start display at page:

Download "PowerPoint プレゼンテーション"

のぶあきおおふさ
4 years ago
Views:

1 Attacks against search Poly-LWE 工藤桃成九州大学大学院数理学府 * *Research conducted while at Fujitsu Laboratories of America, Inc. 日本応用数理学会 2017 年研究部会連合発表会数論アルゴリズムとその応用 3/7/2017 1

2 Contents: 1. Introduction 2. Our extended attacks against the search-variant of Poly-LWE 3. Future works 本講演の主結果は以下の論文より : [1] M. Kudo, Attacks against search Poly-LWE, IACR Cryptology eprint Archive 2016/1153 [2] M. Kudo, Attacks against search Poly-LWE, In: Proceedings of 2017 Symposium on Cryptography and Information Security (SCIS2017), 2B4-5, /7/2017 2

3 Our contribution in this talk 格子暗号における Polynomial Learning With Errors 問題に対する既存攻撃の拡張既存攻撃一般化今回の拡張攻撃適用 f が素体 F q 上で完全分解する場合適用 f が素体 F q 上で完全分解するとは限らない場合 f : Polynomial Learning With Errors (Poly-LWE) 問題における定義方程式 ( 後述 ) 3/7/2017 3

Introduction 格子ベース暗号方式の安全性は数学問題の計算量的求解困難性に基づく [3] e.g. - 最短ベクトル問題 (SVP) - 最近ベクトル問題 (CVP) - Learning with errors (LWE) 問題 - Plain-LWE - Ring-LWE - Poly-LWE ( 本研究 ) 解析が必要!

4 Introduction 格子ベース暗号方式の安全性は数学問題の計算量的求解困難性に基づく [3] e.g. - 最短ベクトル問題 (SVP) - 最近ベクトル問題 (CVP) - Learning with errors (LWE) 問題 - Plain-LWE - Ring-LWE - Poly-LWE ( 本研究 ) 解析が必要! 普及 ( 将来 ) 実用化企業等での情報通信技術 ( 数学的に定義された ) 格子ベース暗号方式 [3] D. Miciciancio and S. Goldwasser, Complexity of Lattice Problem: A Cryptographic Perspective, Kluwer, 2002 実装安全性の基盤格子に関する計算問題の困難性 (e.g. SVP, CVP, Plain-LWE, Poly-LWE, Ring-LWE) 3/7/2017 4

5 Introduction Poly-LWE (PLWE) 問題は, - [4] で紹介 - Ring-LWE と深く関係 (Ring-LWE の polynomial version と呼ばれる ) - [4, 5, 6] における暗号方式の安全性基盤格子暗号理論における計算問題 LWE Plain-LWE SVP Poly-LWE (Our focus) CVP Ring-LWE [4] Z. Brakerski and V. Vaikuntanathan, Fully homomorphic encryption from Ring-LWE and security for key dependent messages, In: Proceedings of CRYPTO 2011, LNCS 6841, pp , Springer [5] Z. Brakerski, C. Gentry and V. Vaikuntanathan, (Leveled) Fully Homomorphic Encryption without Bootstrapping, ACM Transactions on Computation Theory 6 (2014), Issue 3, Article No. 13 [6] C. Gentry, S. Halevi and N.P. Smart, Fully homomorphic encryption with polylog overhead, In: Proceedings of EUROCRYPTO 2012, LNCS 7237, pp , Springer Heidelberg 3/7/2017 5

6 Notation n Z 1, q : 素数 f Z[x] : 次数 n のモニック多項式 P Z[x] f f (q) F q [x] : 整係数多項式 f の mod q reduction (square-free と仮定 ) P q P qp F q [x] f q h h + f q : 多項式 h F q [x] の同値類 Note : P q の各元は n 1 j=0 [c j ]x j の形に一意的に書けるここで [c j ] F q は整数 c j q 2, q 2 Z の同値類 3/7/2017 6

7 Poly-LWE sample χ : 区間 q 2, q 2 Z 上の確率分布 s P q P qp F q x f q : 各係数は一様分布に従い選ばれるこの s を秘密情報と呼ぶ Def. Poly-LWE サンプルとは, P q P q の元で (a, b as + e) の形のものここで, a の各係数は一様分布に従い, e の各係数は確率分布 χ に従い選ばれる実用上, χ = G σ を平均 0, 分散 σ > 0 の離散正規分布にとる 3/7/2017 7

たちから, s を見つけよ Poly-LWE 識別型 (Decision) 探索型 (Search) 格子暗号理論における他の計算問題

8 Definition of Poly-LWE 識別型 (Decision Poly-LWE) : サンプル (a, b) たちが Poly-LWE 分布に従い選ばれたか, 一様分布に従い選ばれたか探索型 (Search Poly-LWE) : Poly-LWE 分布に従い選ばれたサンプル a, b たちから, s を見つけよ Poly-LWE 識別型 (Decision) 探索型 (Search) 格子暗号理論における他の計算問題 (Plain-LWE, Ring-LWE, SVP, etc.) Note : 上記の問題間には ( 適当な仮定のもと ) reduction が存在する 3/7/2017 8

9 Existing attacks against Poly-LWE (or Ring-LWE) LWE 問題に対する攻撃法は数多く提案されている [9] e.g. - Plain-LWE に対する攻撃 +reduction - ( 本研究 ) Eisentraeger et al. s による ( 識別型 Poly-LWE に対する ) 攻撃 [7, 8] [7] K. Eisenstraeger, S. Hallgren and K. Lauter, Weak Instances of PLWE, In: Proceedings of Selected Areas of Cryptography 2014 (SAC 14), LNCS 8781, pp [8] Y. Elias, K. E. Lauter, E. Ozman and K. E. Stange, Probably weak instances of Ring-LWE, In: Proceedings of CRYPTO 2015, LNCS 9215, pp [9] C. Peikert, How (Not) to Instantiate Ring-LWE, IACR Cryptology eprint Archive 2016/351 3/7/2017 9

10 Our contribution 既存攻撃 [7] の拡張型攻撃を提案 [1, 2]: f の既約因子の次数が小さい値で bound されているとき, 多項式時間で終了既存攻撃一般化今回の拡張攻撃適用 f が素体 F q 上で完全分解する場合適用 f が素体 F q 上で完全分解するとは限らない場合 f : Polynomial Learning With Errors (Poly-LWE) 問題における定義方程式 3/7/

11 Contents: 1. Introduction 2. Our extended attacks against the search-variant of Poly-LWE 3. Future works Remark : 今回の攻撃は Eisentraeger et al. による攻撃 [7] の拡張であるため, 本講演においては Eisentraeger et al. による攻撃の紹介を含む形で説明する 3/7/

12 Our generalization of Eisentraeger et al. s attacks 以降では, f は素体 F q 上で完全分解するとは限らないとする Our idea : 各既約因子の ( 最小 ) 分解体上の Poly-LWE (PLWE) 問題に帰着させる PLWE with general f = P 1 P t PLWE over K P1 F q d1 PLWE over K P2 F q d2 PLWE over K Pt F q d t 3/7/

13 f q Idea of our generalization = P 1 P t, ここで P i F q x : 次数 d i = deg P i の既約多項式 P i を1つ選び, K Pi F q [x] P i F q d i とする簡単のため, i = 1, P = P 1, d = d 1, K P = K P1. α K P : a root of P of order r Note : α qk 0 k d 1 は K P における P の根全ての集合 3/7/

14 Idea of our generalization n = n r + r (0 r r 1) と書く e(α) は次の形の元の集合 S α K P に含まれる : r j=0 1 l j α j + r 1 j =r l j α j, ここで l j 2σ n + 1, 2σ n + 1 Z, l j 2σn, 2σn Z. Small interval Small interval 証明は [1, 2] を参照 3/7/

15 l : サンプル数 Recovery of s α Step 0. l 個のサンプル a, b as + e P q P q ( ただし a α 0) を入手 Step 1. 集合 S α K P を計算 Step 2. 元 g K P で b α ga α S α なるものを集め, for all l samples. G を集められた元 g 全体の集合とする Step 3. G = {g} のとき, g = s(α) を得るこのアルゴリズムは d : fixed で S α が十分小さいとき, 多項式時間 ( 詳細は [1, 2] を参照 ) #S α 4σn/r r < q d, ここで r = ord(α) 3/7/

16 Embedding into the smallest splitting field of f q 次数 d lcm(d 1,, d t ) の既約多項式 Q F q [x] を選ぶ K f q F q x Q F q d : 多項式 f q の ( 最小 ) 分解体 K i c K f q c qdi = c K Pi F q d i for 1 i t β i : 多項式 P i の K i における根を1つ選ぶ φ i を次で定義 : φ i K Pi K i K f q ; x + P i β i. φ 1 F q [x] Q F q [x] P 1 F q φ t F q [x] P t Note : φ i α i q k 0 k d i 1 は K f q における P i の全ての根の集合 s(φ i α i q k ) (1 i t and 0 k d i 1) を計算することで, s(x) を復元できる ( 次項 ) 3/7/

17 Our general attack against search-plwe Step 1. f (q) を F q 上で因数分解 : f q = P 1 P t Step 2. 次数 lcm(d 1,, d t ) の既約多項式 Q F q [x] を選び, K f (q) F q x Q F q deg Q Step 3. 各 1 i t に対して, (3-1) P i の根 α i K Pi (3-2) s α i K Pi を計算 ( 前述 ) (3-3) 1 k d i 1 に対して s(α i q k ) を計算 F q [x] P i を 1 つ選ぶ K Pi F q d i 上の PLWE へ帰着 (3-4) P i の根 β i K i c K f q c qdi = c を 1 つ選ぶ (3-5) s(φ i (α i q k )) を計算, ここで φ i K Pi K i K f q ; x + P i β i K Pi F q d i の K i K f q F q deg Q への埋入 3/7/

18 Our general attack against search-plwe Step 3. s(φ i (α i q k )) を用いて, 多項式補間により s を復元 (K f (q) 上の計算 ). 本攻撃は d i が小さい値で fix され, S αi たちが十分小さいとき, 多項式時間で終了し, s を復元 ( 詳細は [1, 2]) #S αi 4σn/r i r i < q d i, ここで r i = ord(α i ) 3/7/

19 Summary of our generalized attack f F q [x] : 定義方程式 s F q [x] : 秘密情報 PLWE with general f = P 1 P t reduce PLWE over K P1 F q d1 PLWE over K P2 F q d2 PLWE over K Pt F q d t Recover s α j 1 K P1 Recover s α j 2 K P2 Recover s α j t K Pt d i deg P i d lcm(d 1,, d t ) α j i K Pi : a root of P i 埋入 Recover s (F q d 内の計算 ) 3/7/

20 Contents: 1. Introduction 2. Our extended attacks against the search-variant of Poly-LWE 3. Future works 3/7/

21 Future works 1. 拡張型攻撃法の, 提案されている暗号方式の具体的なinstanceへの適用 - 今回, 攻撃の ( 理論的な ) フレームワーク+ 攻撃が成功するパラメータの条件を与えたが, 実用性は未検証 ( この条件はどれほど strict なのか?) 2. 関連して, 実装によって実際の効果や効率性を調べる 3. Ring-LWE に適用できる攻撃に拡張できないかご清聴ありがとうございました 3/7/

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

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