研究集会 代数系アルゴリズムと言語および計算理論 知識の証明と暗号技術 情報セキュリティ大学大学院学院 有田正剛 1
はじめに 暗号技術の面白さとむずかしさ システムには攻撃者が存在する 条件が整ったときのベストパフォーマンスより 条件が整わないときの安全性 攻撃者は約束事 ( プロトコル ) には従わない 表面上は従っているふり 放置すると 正直者が損をする それを防ぐには 知識の証明 が基本手段 約束事を守っていることをお互いに証明する 証明が不適切なら 相手をしない 正直者にも多少の負荷がかかる 2
目次 Section 1: 知識の証明とは 知識の証明とは? 知識とは? 離散対数問題 知識のゼロ知識証明プロトコル シュノアプロトコル Section 2: 知識の証明の公開鍵暗号への応用 公開鍵暗号とは エルガマル暗号 CPA 攻撃とCCA 攻撃 知識の証明による安全性強化 署名付きエルガマル暗号(Tsiounis, Yung 98, Jakobsson 98) 改良署名付きエルガマル暗号 ( 石井 鶴留 有田 '09) 3
Section 1: 知識の証明とは? 4
知識の証明とは? 証明者 Pと検証者 Vからなるプロトコル 証明者 P は検証者 Vに 自分がステートメント x に関する知識 w をもっていることを証明したい x w x 証明者 P 検証者 V 受理 / 拒否 認証プロトコル ディジタル署名 公開鍵暗号など さまざまな暗号技術で用いられる重要な要素プロトコル 5
知識 とは? 効率的に計算可能な関係 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
知識のゼロ知識証明 言語 L をパラメータとする 証明者 P と検証者 V からなるプロトコル 証明者 P は検証者 Vに 自分がステートメント x L を証明する知識 wをもっていることを 知識 w 自体はまったく明かさずに 証明したい x w x 証明者 P 検証者 V 受理 / 拒否 7
知識のゼロ知識証明 の 3 要件 プロトコル (P, V) が言語 Lの知識のゼロ知識証明であるとは 任意知識証明であるとは 任意のx L について ( 完全性 ) P が知識 w をもっているとき V は必ず受理 ( 健全性 ) P* が知識 w をもっていないとき P* がどのように振る舞おうと V は拒否 ( ゼロ知識 ) 検証者 V は P が知識 w をもっていること 以外のいかなる情報も入手しない ( 上で知識 w とはステートメント x L を証明する知識 w の意味 ) 1 ビット情報 8
シュノアプロトコル : 離散対数のゼロ知識証明 以下の (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
シュノアプロトコルの 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
Section 2: 知識の証明の公開鍵暗号への応用 11
公開鍵暗号 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
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
エルガマル暗号 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
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
エルガマル暗号は 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
知識の証明による安全性強化 署名付きエルガマル暗号 [Tsiounis, Yung '98, Jakobsson '98]: エルガマル暗号 + 暗号化に用いた乱数の知識の証明 証明はシュノアプロトコル ( 離散対数の知識の証明 ) を変形して用いる 先のAは c = (c 1, c 2 g) について c 1 の離散対数 r を知らないので 証明にパスできず 攻撃に失敗する 定理 1 [Schnorr, Jakobsson '00] ランダムオラクルモデルとジェネリック群モデルにおいて 署名付きエルガマル暗号は CCA 攻撃に対して識別不可能である 17
署名付きエルガマル暗号 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 1 2 1 18
署名 σの役割 : 言語 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
ランダムオラクルモデル ランダムオラクル H $ { {0,1}* {0,1} n } (*) u v = H(u) ランダムオラクルモデル : 関数 v H(u) の実行をランダムオラクルへの問い合わせに置き換える アルゴリズムの実行モデル 20
ジェネリック群モデル 群演算オラクル (*) (g 1,, g i ), (a 1,..., a i ) g a1 1 g ai i ジェネリック群モデル : 群演算の実行を群演算オラクルへの問い合わせに置き換える アルゴリズムの実行モデル ( アルゴリズムは自身では群演算できないとする ) ジェネリック群モデルでは離散対数仮定や決定的 DH 仮定は証明可能 21
改良署名付きエルガマル暗号 ( 石井 鶴留 有田 '09) 改良署名付きエルガマル暗号 : エルガマル暗号 + 暗号化に用いた乱数の知識の証明 知識の証明について : シュノアプロトコル DH 指数のゼロ知識証明プロトコル ジェネリック群モデルに依存しないで 安全性の証明ができる ( 復号オラクルのシュミレーションが可能となるションが可能となる ) 定理 2 [ 石井 鶴留 有田 '09] ランダムオラクルモデルにおいて 決定的 DH 仮定のもとで 改良署名付きエルガマル暗号はCCA 攻撃に対して識別不可能である 22
改良署名付きエルガマル暗号 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
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
署名 σの役割 : 言語 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
定理 2 の証明の方針 改良署名付きエルガマル暗号を破る CCA 攻撃における攻撃者 A が存在したと仮定する A を用いて エルガマル暗号を破る CPA 攻撃における攻撃者 B が構成できることを示す ( 背理法 ) 攻撃者 B は攻撃者 A の能力を用いてエルガマル暗号を破る 攻撃者 B は 攻撃者 A に対し 復号オラクルを提供しなければならない しかし 攻撃者 B は秘密鍵も復号オラクルも持たない どうする? 26
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
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
知識のゼロ知識証明 まとめ 言語 Lをパラメータとする 証明者 Pと検証者 Vからなるプロトコル 証明者 Pは検証者 Vに 自分がステートメントx Lを証明する知識 w をもっていることを 知識 w 自体はまったく明かさずに 証明する 知識のゼロ知識証明によるエルガマル暗号の安全性強化 エルガマル暗号 CPA 攻撃に対して安全 署名付きエルガマル暗号 CCA 攻撃に対しても安全 ただし安全性証明にはジェネリック群モデルが必要 安全性証 改良署名付きエルガマル暗号 CCA 攻撃に対しても安全 ただし安全性証明にジェネリック群モデルは不要 ( ランダムオラクルモデルは必要 ) 29