情報セキュリティ特論（8）

情報セキュリティ特論（8）
黒澤馨（茨城大学）
[email protected]
前回演習
• DDH仮定の下で、ElGamal暗号が
IND-CPA安全であることを示せ。
ElGamal暗号
• 公開鍵：
p, q, g, y(=gx mod p)
• 秘密鍵: x
• 平文： m
• 暗号化：
r ← zp-1
E(m)=(gr, myr)
2015/9/30
confidential
3
IND-CPAを定義するゲーム
チャレンジャー
x←ランダム
y=gx mod p
敵
g, y
m0, m1
b←{0,1}
C=(gr, mbyr)
C
b’
Game 0
チャレンジャー
x←ランダム
y=gx mod p
敵
g, y
m0, m1
b←{0,1}
C=(gr, mbyr)
C
b’
p0 = Pr( b’=b )
Game 1
チャレンジャー
x←ランダム
y=gx mod p
敵
g, y
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
敵
g, y
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
敵
g, y
m0, m1
b←{0,1}
z←ランダム
C=(gr, mbgz)
mb×乱数：
One-time pad
C
b’
p1 = Pr( b’=b )
補題１： p1=Pr(b’=b)=1/2
チャレンジャー
x←ランダム
y=gx mod p
敵
g, y
m0, m1
b←{0,1}
z←ランダム
C=(gr, mbgz)
mb×乱数：
One-time pad
C
b’
p1 = Pr( b’=b )
敵は、mbについて何もわからない
補題１
p1=1/2
• （証明）
• C=(gr, mbgz)において、
mbgz = mb×乱数： one-time pad
• よって、 mb に関する情報は何ももれていない。
• ゆえに、
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を
以下のように構成する。
g, y, gr, w=yr or w=gz
チャレンジャー
D
敵
g, y
m0, m1
C=(gr, mbw)
C
b’
1 if b’=b
0 else
g, y, gr, w=yr or w=gz
チャレンジャー
D
敵
g, y
m0, m1
C=(gr, mbw)
C
Game 0
Pr(D=1)=Pr(b’=b)=p0
b’
1 if b’=b
0 else
g, y, gr, w=yr or w=gz
チャレンジャー
D
敵
g, y
m0, m1
C=(gr, mbw)
C
Game 1
Pr(D=1)=Pr(b’=b)=p1
b’
1 if b’=b
0 else
証明の続き
• 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|<ε
チャレンジャー
x←ランダム
y=gx mod p
敵
y
m0, m1
b←{0,1}
C= E(mb)
=(gr, mbyr)
C
b’
補題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
B
A
x
c
c←ランダム
ただし、0≤c<e
y
x =vcye mod N
をチェック
y=rsc mod N
2015/9/30
confidential
21
演習 (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
r←ランダム
x=re mod N
B
A
A
x
c=H(x,m)
平文m
x =vcye mod N
を計算
y=rsc mod N
σ=(c,y)
y
署名文
2015/9/30
confidential
c=H(x,m)
をチェック
26
演習 (6)
• ROモデルにおいて、
ＧＱの署名に対し、確率εで
偽造に成功する敵Aが存在する。
ただし、
AはHオラクルに高々h回質問すると仮定する。
• ＧＱの認証法において、確率ε/hで
なりすましに成功する敵Bが存在する、を示せ。
2015/9/30
confidential
27

Download Report