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

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

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

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’

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

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 )

補題１： 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 )

補題１： 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

補題１： 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について何もわからない

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

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

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

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

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

証明の続き 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|<ε

|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|<ε

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

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

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

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

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

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

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

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

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

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

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