黒澤 馨 （茨城大学） kurosawa@mx.ibaraki.ac.jp 情報セキュリティ特論（8） 黒澤　馨 （茨城大学） kurosawa@mx.ibaraki.ac.jp.

Presentation on theme: "黒澤 馨 （茨城大学） kurosawa@mx.ibaraki.ac.jp 情報セキュリティ特論（8） 黒澤　馨 （茨城大学） kurosawa@mx.ibaraki.ac.jp."— Presentation transcript:

1 黒澤 馨 （茨城大学） kurosawa@mx.ibaraki.ac.jp
情報セキュリティ特論（8） 黒澤　馨 （茨城大学）

2 前回演習 DDH仮定の下で、ElGamal暗号が IND-CPA安全であることを示せ。

3 ElGamal暗号 公開鍵： p, q, g, y(=gx mod p) 秘密鍵: x 平文： m 暗号化： r ← zp-1
E(m)=(gr, myr) 2019/6/7 confidential

4 IND-CPAを定義するゲーム チャレンジャー 敵 x←ランダム y=gx mod p m0, m1 b←{0,1}
g, y x←ランダム y=gx mod p m0, m1 b←{0,1} C=(gr, mbyr) C b’

5 Game 0 チャレンジャー 敵 x←ランダム y=gx mod p m0, m1 b←{0,1} C=(gr, mbyr) g, y C
p0 = Pr( b’=b )

6 Game 1 チャレンジャー 敵 x←ランダム y=gx mod p m0, m1 b←{0,1} z←ランダム C=(gr, mbgz)
g, y x←ランダム y=gx mod p m0, m1 b←{0,1} z←ランダム C=(gr, mbgz) C b’ p1 = Pr( b’=b )

7 補題１： p1=Pr(b’=b)=1/2 チャレンジャー 敵 x←ランダム y=gx mod p m0, m1 b←{0,1} z←ランダム
g, y x←ランダム y=gx mod p m0, m1 b←{0,1} z←ランダム C=(gr, mbgz) C b’ p1 = Pr( b’=b )

8 補題１： p1=Pr(b’=b)=1/2 mb×乱数： One-time pad チャレンジャー 敵 x←ランダム y=gx mod p
g, y x←ランダム y=gx mod p m0, m1 b←{0,1} z←ランダム C=(gr, mbgz) C b’ p1 = Pr( b’=b ) mb×乱数： One-time pad

9 補題１： p1=Pr(b’=b)=1/2 mb×乱数： One-time pad 敵は、mbについて何もわからない チャレンジャー 敵
g, y x←ランダム y=gx mod p m0, m1 b←{0,1} z←ランダム C=(gr, mbgz) C b’ p1 = Pr( b’=b ) mb×乱数： One-time pad 敵は、mbについて何もわからない

10 補題１ p1=1/2 （証明） C=(gr, mbgz)において、 mbgz = mb×乱数： one-time pad
ゆえに、 p1=Pr(b’=b)=1/2

11 補題２ DDH仮定の下で、|p0- p1 |<ε （証明） DDH仮定より、(g,y,gr,yr)と(g,y,gr,gz)は
　 区別不可能。ただし、r,zは乱数 (g,y,gr,yr)と(g,y,gr,gz)を区別しようとする Dを 以下のように構成する。

12 D g, y, gr, w=yr or w=gz 1 if b’=b 0 else チャレンジャー 敵 g, y m0, m1
C=(gr, mbw) C b’ 1 if b’=b 0 else

13 D Game 0 Pr(D=1)=Pr(b’=b)=p0 g, y, gr, w=yr or w=gz 1 if b’=b 0 else
チャレンジャー 敵 g, y m0, m1 C=(gr, mbw) C Game 0 b’ 1 if b’=b 0 else Pr(D=1)=Pr(b’=b)=p0

14 D Game 1 Pr(D=1)=Pr(b’=b)=p1 g, y, gr, w=yr or w=gz 1 if b’=b 0 else
チャレンジャー 敵 g, y m0, m1 C=(gr, mbw) C Game 1 b’ 1 if b’=b 0 else Pr(D=1)=Pr(b’=b)=p1

15 証明の続き w=yr のとき、Pr(D=1)=Pr(b’=b)=p0 w=gz のとき、Pr(D=1)=Pr(b’=b)=p1
DDH仮定より、 w=yr と w=gz は区別できない 　 すなわち、 　　　　　|Pr(D=1)-Pr(D=1)|<ε よって、 　　　　　|p0-p1|<ε

16 |Pr(b’=b) - 1/2|=|p0 - p1|<ε
チャレンジャー x←ランダム y=gx mod p 敵 m0, m1 y b←{0,1} C= E(mb) 　=(gr, mbyr) b’ C 補題1,2より、 　　|Pr(b’=b) - 1/2|=|p0 - p1|<ε

17 演習(1) N次剰余仮定の下で、Paillier暗号が 　 IND-CPA安全であることを証明せよ。

18 Paillier暗号 公開鍵 N=pq 秘密鍵 p, q 暗号化 x ←{1,2,…, N-1} xN=a+bN mod N2
C=(a, b+m mod N)

19 N次剰余仮定 xN = a+bN mod N2 としたとき、 (a,b) と (a, 乱数）は
　　computationally indistinguishable ただし、 　　x←{1,2,…, N-1}

20 GQの認証法 センタの公開鍵： (N,e), ただし、eは大きな素数 アリスの公開鍵： v=s-e mod N アリスの秘密鍵： s

21 GQの認証法 v =s-e mod N s r←ランダム x=re mod N x c c←ランダム ただし、0≤c<e
B A s r←ランダム x=re mod N x c c←ランダム ただし、0≤c<e y=rsc mod N y x =vcye mod N をチェック 2019/6/7 confidential

22 演習 (2) x =vcye mod N が成り立つことを示せ。

23 演習 (3) 零知識性、すなわち、Bは自分で通信系列(x,c,y)を生成できることを示せ。

24 演習 (4) 健全性、すなわち、AがBをacceptさせることができるなら、Aを使ってsを求めることができることを示せ。 （ヒント）
「現代暗号の基礎数理」 　　の式(13.12)～(13.17)参照

25 演習 (5) 学習段階の後、なりすましに成功する敵が 　 存在したと仮定すると、 RSA問題を解けることを示せ。

26 GQのデジタル署名 公開鍵：v =s-e mod N 秘密鍵：s x =vcye mod N を計算 c=H(x,m) をチェック A B
r←ランダム x=re mod N x c=H(x,m) 平文m x =vcye mod N を計算 y=rsc mod N σ=(c,y) y c=H(x,m) をチェック 署名文 2019/6/7 confidential

27 演習 (6) ROモデルにおいて、 ＧＱの署名に対し、確率εで 偽造に成功する敵Aが存在する。 ただし、
　ＧＱの署名に対し、確率εで 偽造に成功する敵Aが存在する。 　ただし、 　AはHオラクルに高々h回質問すると仮定する。 ＧＱの認証法において、確率ε/hで なりすましに成功する敵Bが存在する、を示せ。 2019/6/7 confidential