定理(CS暗号)の証明 - 暗号理論教室

定理(CS暗号)の証明のアイデア

攻撃者Aが構成(CS暗号)の公開鍵と暗号文

• pk = (g₁, g₂, h=g₁^xg₂^y, c=g₁^a g₂^b, d=g₁^a' g₂^b'),
• C* = (g₁^r*, g₂^r*, h^r*m*=(g₁^r*)^x(g₂^r*)^ym*, (cd^α*)^r*=(g₁^a+α*a'g₂^b+α*b')^r*)

を入手したとする。
まず、DDH仮定を用いて、(g₁, g₂, g₁^r*, g₂^r*)を(g₁, g₂,g₃, g₄)に置き換えると、

• pk = (g₁, g₂, g₁^xg₂^y, g₁^a g₂^b, g₁^a' g₂^b'),
• C* = (g₃, g₄, g₃^xg₄^ym*, g₃^a+α*a'g₄^b+α*b').

x,yはランダムなので、(g₁^xg₂^y, g₃^xg₄^y)をランダムな2要素(γ,δ)に置き換えてよい：

• pk = (g₁, g₂, γ, g₁^a g₂^b, g₁^a' g₂^b'),
• C* = (g₃, g₄, δm*, g₃^a+α*a'g₄^b+α*b')

δはm*にしか掛っていないので、m*は完全に隠される。

攻撃者Aが構成(CS暗号)の妥当な暗号文 c = (u,v,w,e) を生成したとすると、

• α=H(u,v,w)に対し、e = u^a+αa'v^b+αb'

を満たさなければならない。
これを成り立たせるには、αはハッシュ値でその値を自由にコントロールすることができないので、Aはu, vを

• u = g₁^s, v = g₂^s

という形で生成しなければならず、このとき、Aが復号オラクルから受け取る返答は、

• u^xv^y = (g₁^x g₂^y)^s = h^s

となり、x, y に関する新しい情報は全く含まない。よって、m*は隠されたまま。

定理(CS暗号)の証明

構成(CS暗号)に対する任意のCCA攻撃者をAとする。Aを用いて判定DH仮定における識別者Dを構成する：

識別者D: par=(q,g₁), (g₂,g₃,g₄)を入力として、

• pkを入力としてAを起動する。ただし、
  • x, y, a, b, a', b' ← Z_q
  • h = g₁^x g₂^y, c = g₁^a g₂^b, d = g₁^a' g₂^b'
  • pk = (g₁,g₂,h,c,d,H), sk = (x,y,a,b,a',b').
• Aからチャレンジクエリ(m₀,m₁)を受け取ったら、
  • 0または1をランダムに選択し、βとする。
  • C* = (u*=g₃, v*=g₄, w*=g₃^xg₄^ym_β, e*=g₃^a+α*a'g₄^b+α*b')を応答する。(α* := H(u*, v*, w* )）
• Aから復号オラクルに対する問い合わせを受け取ったら、skを用いて復号し、結果を応答する。
• Aが出力β'で終了したら、β =^? β' の１ビットを出力とする。

識別者Dの解析：

• 入力(g₁, g₂, g₃, g₄)がDH組であるとき:
  • あるランダムなrについて、g₃ = g₁^r, g₄ = g₂^r. このとき、
    • g₃^xg₄^ym_β = (g₁^xg₂^y)^r m_β = h^r m_β,
    • g₃^a+α*a'g₄^b+α*b' = (g₁^ag₂^b (g₁^a'g₂^b')^α*)^r = (cd^α*)^r.
  • よって、C* = Enc(pk, m_β; r). すなわち、DのAに対するシミュレーションは完ぺき。
  • 以上より、Pr[D = 1 | DH] = Pr[Aが成功].

入力(g₁, g₂, g₃, g₄)はランダムな組であるとする。
Aが復号クエリをまったく用いなかったとすると、Aが受け取る秘密鍵x,yに関する情報は、公開鍵h経由の、

• h=g₁^xg₂^y と w*=g₃^xg₄^ym_βのみ。

x,yは独立にそれぞれランダムなので、hとg₃^xg₄^yも独立にそれぞれランダム。
よって、このときg₃^xg₄^yはm_βを完全に隠し、Pr[Aが成功] = 1/2.

あとは、Aの復号クエリがx,yについて追加情報を与えないことを示せばよい。
復号クエリ(u,v,w,e)がbadであるとは、『(g₁,g₂,u,v)がDH組でない』ことと定義する。
（badでない復号クエリをgoodと呼ぶ。）

主張1 goodな復号クエリに対する応答は、Aに秘密鍵x,y,a,b,a',b' に関する追加情報を全く漏らさない。

証明 (u=g₁^s,v=g₂^s,w,e)をgoodな復号クエリとする。
このとき、Aが返答として受け取る情報は高々m = w/(u^xv^y).
ここで、u^xv^y = (g₁^x g₂^y)^s = h^s.
これは、秘密鍵x,y,a,b,a',b' に関する追加情報を全く与えない。（x,yを知らなくてもsを知っていたら生成できるから。）Q.E.D.

主張2 Aがbadで（ありながら復号アルゴリズムの検証式をパスする）妥当な復号クエリを発する確率はネグリジブルηである。

証明 Aがbadで妥当な復号クエリC=(u=g₁^r1,v=g₂^r2,w,e)を初めて発したとする。

• (u,v,w) = (u*,v*,w*)のとき：
  • Cの妥当性より、α=α*となり、C=C*となる。これはゲームのルールとして禁止されている。
• (u,v,w)≠(u*,v*,w*) かつ H(u,v,w) = H(u*,v*,w*)のとき：
  • Hの衝突が得られ、Hの衝突困難性に反する。O.K.
• H(u,v,w)≠H(u*,v*,w*)のとき：
  • α = H(u,v,w), α* = H(u*,v*,w*), γ = log_g1(g₂)とする。
  • Aが復号クエリCを発する前に知っていた、秘密鍵a,b,a',b'についての情報は、公開鍵とチャレンジ暗号文を経由して、以下の高々3次元分である:
    • log_g1(c) = a + bγ, log_g1(d) = a' + b'γ, log_g1(e*) = (a+α*a')r₁* + (b+α*b')r₂*γ
    • （ r₁* := log_g1(g₃), r₂* := log_g2(g₄) ）
  • 一方、復号クエリCの妥当性より、 log_g1(e) = (a+αa')r₁ + (b+αb')r₂γ.
  • 以上4次元分の情報はa,b,a',b'を一意的に決定する（r₁*≠r₂*,α≠α*,r₁≠r₂）。
  • すなわち、Aがbadで妥当な復号クエリを発するとすると、Aは高々3次元分の情報で、秘密鍵a,b,a',b'を一意に数学的に特定することとなる。
  • よって、Pr[Aがbadで妥当な復号クエリを発する] ≦ 1/q. Q.E.D.

主張1、主張2より、

• Pr[D=1 | Random] = 1/2 + η.

よって、Dの識別利得は

• | Pr[Aが成功] - (1/2 + η) | ≧ (Aの識別利得) - η.

判定DDH仮定より、Dの識別利得はネグリジブル。よって、Aの識別利得もネグリジブルである。
Q.E.D.

上へ

---