Microsoft PowerPoint - kyoto

Size: px

Start display at page:

Download "Microsoft PowerPoint - kyoto"

つづるつくとの
7 years ago
Views:

1 研究集会代数系アルゴリズムと言語および計算理論知識の証明と暗号技術情報セキュリティ大学大学院学院有田正剛 1

2 はじめに暗号技術の面白さとむずかしさシステムには攻撃者が存在する条件が整ったときのベストパフォーマンスより条件が整わないときの安全性攻撃者は約束事 ( プロトコル ) には従わない表面上は従っているふり放置すると正直者が損をするそれを防ぐには知識の証明が基本手段約束事を守っていることをお互いに証明する証明が不適切なら相手をしない正直者にも多少の負荷がかかる 2

3 目次 Section 1: 知識の証明とは知識の証明とは? 知識とは? 離散対数問題知識のゼロ知識証明プロトコルシュノアプロトコル Section 2: 知識の証明の公開鍵暗号への応用公開鍵暗号とはエルガマル暗号 CPA 攻撃とCCA 攻撃知識の証明による安全性強化署名付きエルガマル暗号(Tsiounis, Yung 98, Jakobsson 98) 改良署名付きエルガマル暗号 ( 石井鶴留有田 '09) 3

4 Section 1: 知識の証明とは? 4

5 知識の証明とは? 証明者 Pと検証者 Vからなるプロトコル証明者 P は検証者 Vに自分がステートメント x に関する知識 w をもっていることを証明したい x w x 証明者 P 検証者 V 受理 / 拒否認証プロトコルディジタル署名公開鍵暗号などさまざまな暗号技術で用いられる重要な要素プロトコル 5

6 知識とは? 効率的に計算可能な関係 R = {(x,w)} ( {0,1}* x {0,1}* ) NP 言語 L = {x w, (x,w) R} ( {0,1}*) x L をステートメントといい (x,w) R となる w をステートメントx L を証明する知識 (witness) という ( 通常 xからwを求めることが難しいときを扱う ) 例 : 離散対数の知識 G=<g>: ( 効率的に群演算可能な ) 有限巡回群 R dl = {(x, w) x = g w } L dl = { x w, x = g w } w =DL g (x) (x の g に関する離散対数 ) は x G を証明する知識である離散対数仮定 : ランダムな群要素の離散対数を求めることは困難 6

7 知識のゼロ知識証明言語 L をパラメータとする証明者 P と検証者 V からなるプロトコル証明者 P は検証者 Vに自分がステートメント x L を証明する知識 wをもっていることを知識 w 自体はまったく明かさずに証明したい x w x 証明者 P 検証者 V 受理 / 拒否 7

8 知識のゼロ知識証明の 3 要件プロトコル (P, V) が言語 Lの知識のゼロ知識証明であるとは任意知識証明であるとは任意のx L について ( 完全性 ) P が知識 w をもっているとき V は必ず受理 ( 健全性 ) P* が知識 w をもっていないとき P* がどのように振る舞おうと V は拒否 ( ゼロ知識 ) 検証者 V は P が知識 w をもっていること以外のいかなる情報も入手しない ( 上で知識 w とはステートメント x L を証明する知識 w の意味 ) 1 ビット情報 8

9 シュノアプロトコル : 離散対数のゼロ知識証明以下の (P, V) は言語 L dl = { x w, x = g w } の知識のゼロ知識証明である (w を x の離散対数と呼ぶ ) x w x P r $ {1,..., q 1} V h = g r h c c $ {1,..., q 1} y= r + c w y g y =? h x c 受理 / 拒否 ( ただし q = ord(g) は素数とする ) 9

10 シュノアプロトコルの 3 要件 ( 完全性 ) g y = g r + c w = g r (g w ) c = h x c. ( 健全性 )V が ( 無視できない確率で ) x L dl を受理するなら P* は異なるc 1, c 2 について g y1 = h x c1, g y2 = h x c2 となるy 1,y 2 を答えられるハズこのとき g y1 y2 = x c1 c2. x = g (y1 y2)/(c1 c2). よって P* は w = (y 1 y 2 )/(c 1 c 2 ) を知っている ( ゼロ知識 ) V が P とのやりとりで得る情報は (h,c,y) : h $ G, c $ {1,...,q 1}, y = r + cw. これは w を使わなくても (h,c,y) : c $ {1,...,q 1}, y $ {1,...,q 1}, h = g y x c として生成できるよって P から得られている情報は x L dl 以外にはない 10

11 Section 2: 知識の証明の公開鍵暗号への応用 11

12 公開鍵暗号 3 つの確率的で効率的なアルゴリズムの組 Π=(Gen, Enc, Dec): (pk, sk) Gen(1 k ) c Enc pk (m) m Dec sk (c) ただし ( 完全性 ) Pr[ (pk, sk) Gen(1 k ), c Enc pk (m) : Dec sk (c) = m ] = 1 ( 識別不可能性 ) sk を知っている正当な復号者以外は c を見てもメッセージ mに関する情報はまったく得られない 12

13 CPA 攻撃に対する識別不可能性 Π=(Gen, Enc, Dec): 公開鍵暗号 A: ( 効率的な ) 攻撃者 [ CPA ゲーム ] pk (pk, sk) Gen(1 k ) A の勝ち b = b A b m 0, m 1 // 同じ長さ b $ {0,1} c Enc pk (m b ) ΠがIND CPA 攻撃に対し識別不可能 A について Pr[ A が CPAゲームに勝つ ] 1/2 +negl. 13

a, b, c $ {1,...,q 1} のときどのような効率的なアルゴリズムも (g a, g b, g ab ) と (g a, g b, g c ) を識別できない Enc(pk=(g,y), m): // m G このとき r $ {1,.

14 エルガマル暗号 G=<g> q = ord(g) : 素数 Gen: x $ {1,...,q 1} y = g x return pk= (g,y), sk = (g,x) 暗号文 C c 1 = g r c 2 = my r c 2 = m y r = m g xr c 1x = g xr c 2 / c 1x = m 決定的 DH 仮定 : a, b, c $ {1,...,q 1} のときどのような効率的なアルゴリズムも (g a, g b, g ab ) と (g a, g b, g c ) を識別できない Enc(pk=(g,y), m): // m G このとき r $ {1,...,q 1} 1} (y, c 1, c 2 /m) (g x, g r, g xr ) c 1 = g r, c 2 = m y r c (g x, g r, g c ) return c = (c 1, c 2 ) Dec(sk=(g,x), c = (c 1, c 2)): return c 2 / c x 1 よって c 2 /m は CPA 攻撃者にはランダムよって m もランダムエルガマル暗号はCPA 攻撃に対し識別不可能 14

15 CCA 攻撃に対する識別不可能性 Π=(Gen, Enc, Dec): 公開鍵暗号 A: ( 効率的な ) 攻撃者 [ CCA ゲーム ] pk (pk, sk) Gen(1 k ) A の勝ち b = b A (*) (*) // 復号オラクル c m Dec sk (c) m 0, m 1 // 同じ長さ b $ {0,1} c Enc pk (m b ) // 復号オラクル c (=c) m Dec sk (c) ΠがIND CCA 攻撃に対し識別不可能 A について Pr[ A が CCAゲームに勝つ ] 1/2 +negl. b 15

16 エルガマル暗号は CCA 攻撃に対しては識別可能 Π=(Gen, Enc, Dec): エルガマル暗号 pk = (g, y) (y=g x ) A 異なる m 0, m 1 ( G) を選択 c = (c 1, c 2 ) = (c 1, c 2 g) m =? m 0 g : return 0 else return 1 m 0, m 1 b $ {0,1} c = (c 1, c 2 ) = (g r, m b y r ) c (=c) m = c 2 / c 1 x = c 2 g / c 1x = m g Pr[ A の勝ち ] = 1 > 1/2 16

17 知識の証明による安全性強化署名付きエルガマル暗号 [Tsiounis, Yung '98, Jakobsson '98]: エルガマル暗号 + 暗号化に用いた乱数の知識の証明証明はシュノアプロトコル ( 離散対数の知識の証明 ) を変形して用いる先のAは c = (c 1, c 2 g) について c 1 の離散対数 r を知らないので証明にパスできず攻撃に失敗する定理 1 [Schnorr, Jakobsson '00] ランダムオラクルモデルとジェネリック群モデルにおいて署名付きエルガマル暗号は CCA 攻撃に対して識別不可能である 17

18 署名付きエルガマル暗号 G=<g>, q = ord(g) : 素数 H : {0,1}* {0,1,,q 1} : ハッシュ関数 Gen: x $ {1,...,q 1} h = g x return pk= (g,h), sk = (g,x) 暗号文 C (c 1,c 2 ) σ Enc(pk=(g,h), m): // m G r, s $ {1,...,q 1} 1} c 1 = g r, c 2 = m h r, u =g s c = H(c 1,c 2,u), z = s + c r return C = (c 1, c 2, σ=(u,z)) Dec(sk=(g,x), C = (c 1, c 2, σ=(u,z))): c = H(c 1,c 2,u) u =? g z c c 1 : return c 2 / c x

19 署名 σの役割 : 言語 L dl ={c 1 r, c 1 =g r } について知識の証明攻撃者 A が暗号文 C = (c 1,c 2,σ=(u,z)) を復号してもらうには正しい σ を生成しなければならないつまり攻撃者 A は与えられた g, c (=g r 1 ) とランダムな c に対し u = g z c c 1 となる u, z を作らなければならないこの状況はシュノアプロトコルの検証と同じ [*] よってシュノアプロトコルの健全性より攻撃者 A は r c 1 = g r となる r を知っている必要があるつまり約束事を守って暗号文 (c 1,c 2 ) を作らなければならない [* シュノアプロトコルの検証者をハッシュ関数 c=h(c 1,c 2,u) で置き換えた状況フィアットシャミア変換 ] 19

20 ランダムオラクルモデルランダムオラクル H $ { {0,1}* {0,1} n } (*) u v = H(u) ランダムオラクルモデル : 関数 v H(u) の実行をランダムオラクルへの問い合わせに置き換えるアルゴリズムの実行モデル 20

21 ジェネリック群モデル群演算オラクル (*) (g 1,, g i ), (a 1,..., a i ) g a1 1 g ai i ジェネリック群モデル : 群演算の実行を群演算オラクルへの問い合わせに置き換えるアルゴリズムの実行モデル ( アルゴリズムは自身では群演算できないとする ) ジェネリック群モデルでは離散対数仮定や決定的 DH 仮定は証明可能 21

22 改良署名付きエルガマル暗号 ( 石井鶴留有田 '09) 改良署名付きエルガマル暗号 : エルガマル暗号 + 暗号化に用いた乱数の知識の証明知識の証明について : シュノアプロトコル DH 指数のゼロ知識証明プロトコルジェネリック群モデルに依存しないで安全性の証明ができる ( 復号オラクルのシュミレーションが可能となるションが可能となる ) 定理 2 [ 石井鶴留有田 '09] ランダムオラクルモデルにおいて決定的 DH 仮定のもとで改良署名付きエルガマル暗号はCCA 攻撃に対して識別不可能である 22

23 改良署名付きエルガマル暗号 G<g> G=<g>, q = ord(g) : 素数 H : {0,1}* G : ハッシュ関数 G : {0,1}* {0,1,,q 1} 1} : ハッシュ関数暗号文 C Gen: a $ {1,...,q 1} (c 1,c 2 ) σ b = g a return pk = (g,b), sk = (g,a) Dec(sk=(g,a), C = (c 1, c 2, σ=(z,s,u,v))): h = H(u,c1), c = G(c Enc(pk=(g,b), m): m G 1,c 2,g,h,z,u,v) (g, // x, k $ {1,...,q 1} u =? g s c c 1, v =? h s z c : c 1 = g x, u = g k, c 2 = m b x return c 2 / c a 1 h = H(u,c 1 ), z = h x, v = h k c = G(c 1,c 2,g,h,z,u,v), s = k + c x return C = (c 1, c 2, σ=(zsuv)) σ=(z,s,u,v)) 23

24 DH 指数のゼロ知識証明プロトコル以下の (P, V) は言語 L dh = { (x,y) w, x = g w, y = h w } の知識のゼロ知識証明である ( w を (x,y) の DH 指数と呼ぶ ) x w x P r $ {1,..., q 1} V u = g r, v = h r u,v c c $ {1,..., q 1} s= r + c w y g s =? u x c, h s =? v y c 受理 / 拒否 24

25 署名 σの役割 : 言語 L dh ={(c 1,z) x, c 1 =g x, z=h x } の知識の証明攻撃者 A が暗号文 C = (c 1,c 2,σ=(z,s,u,v)) を復号してもらうには正しい σ を生成しなければならないつまり攻撃者 A は与えられた g, c (=g x z(=h x 1 ), h, ) とランダムな c に対し u = g s c c 1, v = h s z c となる u,v,s を作らなければならないこの状況は DH 指数のゼロ知識証明プロトコルの検証と同じ [*] よって DH 指数のゼロ知識証明プロトコルの健全性より攻撃者 Aは c 1 = g x, z = h x となる x を知っている必要があるつまり約束事を守って暗号文 (c 1,c 2 ) を作らなければならない [* DH 指数のゼロ知識証明プロトコルの検証者をハッシュ関数 c=g(c,g,h,z,u,v) で置き換えた状況フィアットシャミア変換 ] 25

26 定理 2 の証明の方針改良署名付きエルガマル暗号を破る CCA 攻撃における攻撃者 A が存在したと仮定する A を用いてエルガマル暗号を破る CPA 攻撃における攻撃者 B が構成できることを示す ( 背理法 ) 攻撃者 B は攻撃者 A の能力を用いてエルガマル暗号を破る攻撃者 B は攻撃者 A に対し復号オラクルを提供しなければならないしかし攻撃者 B は秘密鍵も復号オラクルも持たないどうする? 26

27 pk = (g, b) B H list = {}, G list = {} pk = (g, b) A (*) (*) /* ランダムオラクル H */ (u,c 1 ) d $ {1,...,q}, h = b g d ((u,c 1 ),d,h) をH list に追加 h /* 復号オラクル */ C = (c 1,c 2,σ=(z,s,u,v)) h = H(u,c 1 ) /* (u,c 1,d,h) dh) H list */ c = G(c 1,c 2,g,h,z,u,v) u =? g s c c 1, v =? h s z c : c d 2 c 1d / z /* 知識証明より c 1 = g x, z = h x z = h x = (b g d ) x = g (a+d)x c 1a = (g x ) a = (g a+d ) x / g dx = z / c d 1 m = c 2 /c 1a = c 2 c 1d / z */ 27

28 B A /* チャレンジオラクル */ (*) (m 0,m 1 ) (c 1 c,c 2 ) に署名 σ を追加 (c 1,c 2,σ) /* 復号オラクル */ C = (c 1,c 2,σ=(z,s,u,v)) c 2 c 1d / z (m 0,m 1 ) (c 1,c 2 ) = (g x, m e b x ) with e $ {0,1} e このような Bについて Pr[B が CPA 攻撃によって識別不可能性を破る ] Pr[A が CCA 攻撃によって識別不可能性を破る ] - (negligible) よって B は CPA 攻撃によってエルガマル暗号の識別不可能性を破よって B は CPA 攻撃によってエルガマル暗号の識別不可能性を破るこれは矛盾 Q.E.D. 28

知識のゼロ知識証明によるエルガマル暗号の安全性強化エルガマル暗号 CPA 攻撃に対して安全署名付きエルガマル暗号 CCA 攻撃に対しても安全

29 知識のゼロ知識証明まとめ言語 Lをパラメータとする証明者 Pと検証者 Vからなるプロトコル証明者 Pは検証者 Vに自分がステートメントx Lを証明する知識 w をもっていることを知識 w 自体はまったく明かさずに証明する知識のゼロ知識証明によるエルガマル暗号の安全性強化エルガマル暗号 CPA 攻撃に対して安全署名付きエルガマル暗号 CCA 攻撃に対しても安全ただし安全性証明にはジェネリック群モデルが必要安全性証改良署名付きエルガマル暗号 CCA 攻撃に対しても安全ただし安全性証明にジェネリック群モデルは不要 ( ランダムオラクルモデルは必要 ) 29

チェビシェフ多項式の2変数への拡張と公開鍵暗号（ElGamal暗号）への応用

チェビシェフ多項式の2変数への拡張と公開鍵暗号（ElGamal暗号）への応用チェビシェフ多項式の変数への拡張と公開鍵暗号 Ell 暗号への応用 Ⅰ. チェビシェフ Chbhv Chbhv の多項式よりであるからよってここでとおくと coθ iθ coθ iθ iθ coθcoθ 4 4 iθ iθ iθ iθ iθ i θ i θ i θ i θ co θ co θ} co θ coθcoθ co θ coθ coθ したがってが成り立つこの漸化式とであることより