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

RSA暗号 C=Me mod N C=0のとき、M=0とわかってしまう。 C=1のとき、M=1とわかってしまう。 平文Mのどんな部分情報も 　 漏れないようにするには？

公開鍵暗号系 鍵生成アルゴリズム G 暗号化アルゴリズム E 復号アルゴリズム D

公開鍵暗号系の安全性 IND-CPA安全性 Chosen Plaintext（平文）Attack IND-CCA安全性 Chosen Ciphertext（暗号文） Attack

IND-CPAを定義するゲーム チャレンジャー 敵 pk (pk,sk)←G m0, m1 b←{0,1} C=E(mb) b’

IND-CPA安全 if |Pr(b’=b)-1/2|<ε チャレンジャー 敵 pk (pk,sk)←G m0, m1 b←{0,1} C=E(mb) b’

IND-CPA安全 if |Pr(b’=b)-1/2|<ε for 全ての多項式時間の敵 チャレンジャー 敵 pk (pk,sk)←G m0, m1 b←{0,1} C=E(mb) b’

ElGamal暗号のIND-CPA安全性 チャレンジャー 敵 g, y x←ランダム y=gx mod p m0, m1 b←{0,1} C=(gr, mbyr) C b’ Pr( b’=b )≃1/2

定理 ElGamal暗号はIND-CPA安全 　 under DDH仮定 （証明） 演習

RSA≠IND-CPA安全 チャレンジャー 敵の動作 m0=0, m1=1 b←{0,1} C=mbe mod N (N,e) b’=0 if C=0 b’=1 if C=1 Pr( b’=b )=1

Pr(b’=b)=1なので、 |Pr(b’=b)-1/2|=|1-1/2|=1/2≧ε よって、 　　　RSA暗号≠IND-CPA安全

IND-CPA安全なRSA-based暗号 c1=re mod N c2=M + H(r) mod N ただし、Hはハッシュ関数 暗号文 C=(c1, c2)

IND-CPA安全なRSA-based暗号 K=H(r) c1=re mod N c2=M+擬似乱数生成器(K) (One-Time-PAD) 暗号文 C=(c1, c2) 公開鍵暗号でKを暗号化 共通鍵暗号で平文Mを暗号化

IND-CPA安全なRSA-based暗号 c1=re mod N c2=M + H(r) mod N 暗号文 C=(c1, c2)

AES暗号を利用した擬似乱数生成器 Seed 出力 AES AES AES … … AES暗号が擬似ランダム置換と仮定すると、 これは、標準モデルで擬似乱数生成器

ハイブリッド暗号 C=　公開鍵暗号(共通鍵K) 　　　　　+ 共通鍵暗号（K,平文m) 公開鍵を使うので、 ハイブリッド暗号は公開鍵暗号の１つ

ハイブリッド暗号 C= 公開鍵暗号(共通鍵K) ← KEM + 共通鍵暗号（K,平文m) ← DEM 公開鍵を使うので、 ハイブリッド暗号は公開鍵暗号の１つ

KEM-DEMフレームワーク CPA安全なKEM 　 + One-Time-PAD 　= IND-CPA安全な 　　公開鍵暗号（ハイブリッド暗号）

KEM 鍵生成アルゴリズム G 暗号化アルゴリズム E E(pk)=(暗号文 C, 鍵 K) 復号アルゴリズム D D(C, sk)=K

RSA-KEM 公開鍵 (N,e) 暗号化 r ← ランダム 暗号文 C=re mod N 鍵　 K=H(r)

KEMのCPA安全性 チャレンジャー 敵 (pk,sk)←G (C, K0) ← E(pk) K1=ランダム b←{0,1} C, Kb Pr( b’=b )～1/2

KEMはCPA安全 If 全ての多項式時間の敵に対し、 　　　　|Pr(b’=b)-1/2|<ε

KEMのＣPＡ安全性 in RO 敵 b’ H r1, r2, H(r1), H(r2), pk, C, Kb Pr( b’=b )～1/2

RSA-KEMのＣPＡ安全性 in RO 敵 b’ (N,e), C(=re mod N), K0 =H(r) or K1 =乱数 H r1, r2, H(r1), H(r2), (N,e), C(=re mod N), K0 =H(r) or K1 =乱数

定理 RSA仮定の下で、 RSA-KEMはCPA安全 in the ランダム・オラクル・モデル

補題 Pr(b’=b)-1/2=ε　(non-negligible) 　と仮定すると 　Pr(敵がrをHオラクルに質問する)≧2ε

証明 X=敵がrをHオラクルに質問する事象 Pr(b’=b)= Pr(b’=b, X)+ Pr(b’=b, ￢X)

証明 X=敵がrをHオラクルに質問する事象 Pr(b’=b)= Pr(b’=b, X)+ Pr(b’=b, ￢X) =Pr(b’=b | X) Pr(X) + Pr(b’=b | ￢ X) Pr(￢ X)

証明 X=敵がrをHオラクルに質問する事象 Pr(b’=b)= Pr(b’=b, X)+ Pr(b’=b, ￢X) =Pr(b’=b | X) Pr(X) + Pr(b’=b | ￢ X) Pr(￢ X) ≦Pr(X) + 1/2 Pr(￢ X)

証明 X=敵がrをHオラクルに質問する事象 Pr(b’=b)= Pr(b’=b, X)+ Pr(b’=b, ￢X) =Pr(b’=b | X) Pr(X) + Pr(b’=b | ￢ X) Pr(￢ X) ≦Pr(X) + 1/2 Pr(￢ X) =Pr(X) + 1/2 (1-Pr(X))

証明 X=敵がrをHオラクルに質問する事象 Pr(b’=b)= Pr(b’=b, X)+ Pr(b’=b, ￢X) =Pr(b’=b | X) Pr(X) + Pr(b’=b | ￢ X) Pr(￢ X) ≦Pr(X) + 1/2 Pr(￢ X) =Pr(X) + 1/2 (1-Pr(X)) =1/2+1/2Pr(X)

証明 X=敵がrをHオラクルに質問する事象 Pr(b’=b)= Pr(b’=b, X)+ Pr(b’=b, ￢X) =Pr(b’=b | X) Pr(X) + Pr(b’=b | ￢ X) Pr(￢ X) ≦Pr(X) + 1/2 Pr(￢ X) =Pr(X) + 1/2 (1-Pr(X)) =1/2+1/2Pr(X) ゆえに、1/2Pr(X)≧ Pr(b’=b)-1/2=ε

補題 Pr(b’=b)-1/2=ε (non-negligible) 　と仮定すると 　Pr(敵がrをHオラクルに質問する)≧2ε （証明完了）

RSA-KEMのCPA安全性の証明 敵 b’ (N, e), C=re mod N (N, e), C, b←{0,1}、Kb =乱数 H r1, r2, H(r1), H(r2), b’ (N, e), C=re mod N (N, e), C, b←{0,1}、Kb =乱数 r

(N, e), C=re mod N (N, e), C, Kb =乱数 補題より どこかでr H 敵

(N, e), C=re mod N (N, e), C, Kb =乱数 補題より どこかでr H 敵 r if C=re mod N

(N, e), C=re mod N (N, e), C, Kb =乱数 r1 H 敵 r=r1 if C=r1e mod N

(N, e), C=re mod N (N, e), C, Kb =乱数 r1 H 敵 C≠r1e mod Nのとき H(r1)=乱数

(N, e), C=re mod N (N, e), C, Kb =乱数 r2 H 敵 r=r2 if C=r2e mod N

定理 RSA仮定の下で、 RSA-KEMはCPA安全 in the RO モデル （証明完了）

定理 RSA仮定の下で、以下の暗号系はCPA安全 in the RO モデル r←ランダム、K=H(r) c1=re mod N c2=M+擬似乱数生成器(K) (One-Time-PAD) 暗号文 C=(c1, c2) RSA-KEM

証明 CPA安全なKEM（公開鍵暗号） + One-Time-PAD = IND-CPA安全な公開鍵暗号 RSA-KEMはCPA安全、を証明した。 　　　　　　　　　　　　　　　　　　　　（証明終）

ハイブリッド暗号の効能 IND-CPA (IND-CCA) 安全な公開鍵暗号 を簡単に作れる 平文は、任意の長さのビット列でよい。

ハイブリッド暗号に関する定理 CPA安全なKEM（公開鍵暗号） 　 + One-Time-PAD 　= IND-CPA安全な公開鍵暗号 （証明）

ハイブリッド暗号のIND-CPA チャレンジャー 敵 (pk,sk)←G m0, m1 b←{0,1} (c1*, K*)←KEM(pk) c2*=mb+擬似乱数(K*) C*=(c1*, c2*) b’

Game 0 チャレンジャー 敵 (pk,sk)←G m0, m1 b←{0,1} (c1*, K* )←KEM(pk) c2*=mb+擬似乱数(seed=K* ) C*=(c1*, c2*) b’

Game 1 チャレンジャー 敵 (pk,sk)←G m0, m1 b←{0,1} (c1*, K*)←KEM(pk) c2*=mb+擬似乱数(seed=乱数) C*=(c1*, c2*) b’

補題１ ハイブリッド暗号において Pr(b’=b in Game 0)～ Pr(b’=b in Game 1) 　if KEM is CPA 安全 (証明） 　　ハイブリッド暗号の敵を基に、 　　KEMの敵を以下のように構成する。

KEMの敵 KEMの チャレンジャー ハイブリッド暗号の敵 (pk,sk)←G (c1*, K0)←KEM K1←ランダム d←{0,1} c1*, Kd m0, m1 b←{0,1} c2*= mb + 擬似乱数(seed=Kd) C*=(c1*, c2*) b’ d’ =1 if b’=b

d=0のとき KEMの敵 KEMの チャレンジャー ハイブリッド暗号の敵 Game 0 d←0 (pk,sk)←G (c1*, K0)←KEM K1←ランダム d←0 c1*, K0 m0, m1 b←{0,1} c2*= mb + 擬似乱数(seed=K0) C*=(c1*, c2*) b’ d’ =1 if b’=b

d=1のとき KEMの敵 KEMの チャレンジャー ハイブリッド暗号の敵 Game 1 d←1 (pk,sk)←G (c1*, K0)←KEM K1←ランダム d←1 c1*, K1 m0, m1 b←{0,1} c2*= mb + 擬似乱数(seed=K1) C*=(c1*, c2*) b’ d’ =1 if b’=b

d’=1 if b’=b なので、 Pr(d’=1 when d=0)=Pr(b’=b in Game 0)

証明 Pr(d’=1 when d=0)=Pr(b’=b in Game 0) KEMの敵は、d=0 or 1を区別できないので、 Pr(d’=1 when d=0)～ Pr(d’=1 when d=1) よって、 Pr(b’=b in Game 0) ～ Pr(b’=b in Game 1)

補題１ ハイブリッド暗号において Pr(b’=b in Game 0)～ Pr(b’=b in Game 1) 　if KEM is CPA 安全 （証明完了）

補題２ Pr(b’=b in Game 1)～1/2

Game 1 チャレンジャー 敵 (pk,sk)←G m0, m1 b←{0,1} (c1*, K*)←KEM(pk) c2*=mb+擬似乱数(seed=乱数) C*=(c1*, c2*) b’

Game 1 チャレンジャー 敵 (pk,sk)←G m0, m1 b←{0,1} (c1*, K*)←KEM(pk) c2*=mb+擬似乱数(seed=乱数) C*=(c1*, c2*) c2*は、c1*とは独立なone-time-pad なので、 Pr(b’=b)=1/2 b’

補題２ Pr(b’=b in Game 1)～1/2 （証明完了）

ハイブリッド暗号に関する定理 CPA安全なKEM（公開鍵暗号） + One-Time-PAD = IND-CPA安全な公開鍵暗号 （証明） 　　補題１、補題２より。

公開鍵暗号系の安全性 IND-CPA安全性 Chosen Plaintext（平文）Attack IND-CCA安全性 Chosen Ciphertext（暗号文） Attack

公開鍵暗号のIND-CCA安全性 チャレンジャー 復号オラクル 敵 (pk,sk)←G m0, m1 b←{0,1} C=E(mb) pk 復号してもらえる b’

KEMのCCA安全性 チャレンジャー (pk,sk)←G 敵 C, Kb 復号オラクル (C, K0) ← E(pk) K1=ランダム 復号してもらえる 復号オラクル (C, K0) ← E(pk) K1=ランダム b←{0,1}

DEM（共通鍵暗号）のCCA安全性 復号オラクル チャレンジャー 敵 m0, m1 K←ランダム b←{0,1} C=EK(mb) 復号してもらえる b’ CCA安全 if |Pr(b’=b)-1/2|<ε

KEM-DEMフレームワーク CCA安全なKEM（公開鍵暗号） + CCA安全なDEM（共通鍵暗号） = IND-CCA安全な公開鍵暗号 公開鍵暗号の暗号文 C=KEM(共通鍵K)+DEM(共通鍵K,m)

定理 RSA仮定の下で、 RSA-KEMはCCA安全 In the RO モデル

CCA安全なDEMの構成法 K → → 暗号文 C=(E, Tag) 擬似乱数生成器 敵は、MACオラクルに１回だけ質問して偽造する

IND-ＣＣＡ安全なハイブリッド暗号 r ← ランダム 共通鍵 Ｋ＝Ｈ（ｒ） 暗号文 C=(φ, χ) χ＝（E, Tag) 公開鍵 (N,e) 　　　　　　 r ← ランダム 共通鍵 Ｋ＝Ｈ（ｒ） 暗号文 C=(φ, χ) KEMの暗号文 χ＝（E, Tag) DEMの暗号文 （鍵K) RSA仮定の下で、IND-ＣＣＡ安全 in the RO model

ROモデル IND-CPA安全な ハイブリッド暗号の 構成法 IND-CCA安全な RSA-KEM + one-time-pad + MAC

ROなしで、IND-CPAな暗号 ElGamal暗号 Paillier暗号 DDH仮定 N次剰余仮定

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

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

Paillier暗号 暗号化 x ←{1,2,…, N-1} xN=a+bN mod N2 C=(a, b+m mod N) 復号 　　 xN =a mod N　より、x=ad mod N xN=a+bN mod N2 　により、bを求める

定理 Paillier暗号は、N次剰余仮定の下で 　IND-CPA安全

N次剰余仮定 xN = a+bN mod N2 としたとき、 (a,b) と (a, 乱数）は 　　computationally indistinguishable とは、どういう意味か？

確率変数 XとY Pr(X=a) Pr(Y=a) a

Statistically distance |X-Y| Pr(X=a) Pr(Y=a) a

X and Y are statistically indistinguishable if |X-Y|<ε Pr(X=a) Pr(Y=a) a

補題 この面積＝この面積 Pr(X=a) Pr(Y=a) a

証明 Pr(X=a) C=1-A B=1-A Pr(Y=a) A a

系 |X-Y| = 2×この面積 Pr(X=a) Pr(Y=a) a

Distinguisher D X 0 or 1 Px = Pr(D=1)

例(1) PX = Pr(D=1) Pr(X=a) Pr(Y=a) a D=1 D=0

例(1) PY = Pr(D=1) Pr(X=a) Pr(Y=a) a D=1 D=0

例　(1) 2×(PX-PY) = |X-Y| Pr(X=a) Pr(Y=a) a

例(2) PY = Pr(D=1) Pr(X=a) Pr(Y=a) a D=0 D=1

例(2) Px = Pr(D=1) Pr(X=a) Pr(Y=a) a D=0 D=1

例(2) 2×(PX-PY) < |X-Y| Pr(X=a) Pr(Y=a) a D=0 D=1

定理 2×maxD |PX-PY| = |X-Y| Dは、指数時間アルゴリズムでもよい。

定義 X and Y are computationally indistinguishable if maxD |PX-PY| < ε ただし、Dは多項式時間アルゴリズム

DDH仮定 (g,ga,gb,gab)と(g,ga,gb,gc)は computationally indistinguishable ただし、 　　a,b,cはランダム

Distinguisher Px = Pr(D=1) X= (g,ga,gb,gab) PY = Pr(D=1) Y= (g,ga,gb,gc) PY = Pr(D=1) maxD |PX-PY| < ε ただし、Dは多項式時間アルゴリズム

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

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

定理 Paillier暗号は、N次剰余仮定の下で 　IND-CPA安全

証明 暗号化 x ←{1,2,…, N-1} xN=a+bN mod N2 C=(a, b+m mod N) ≒ 　　　　　　　　≒ 　　　　 (a, 乱数+m mod N) one-time pad

演習 ElGamal暗号のIND-CPA安全性を破る敵Aが存在したと仮定すると、 DDH仮定を破るdistinguisher D が存在することを示せ。 （ヒント） 　Aをサブルーチンとして使い、Dを構成せよ。

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

直感的な証明 DDH仮定より (g,y,gr,yr)と(g,y,gr,gz)は多項式時間で区別不可能 ただし、zは乱数 暗号文： E(m) = (gr, m・yr) 　　　　　 ～(gr, m・gz ) 　　 m×gz=m×乱数 → one-time pad mに関する情報は、もれていない 2018/9/17 confidential

ElGamal暗号のIND-CPA安全性 チャレンジャー 敵 g, y x←ランダム y=gx mod p m0, m1 b←{0,1} C=(gr, mbyr) C b’ Pr( b’=b )≃1/2