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

定理(CCAinRO)の証明のアイデア

攻撃者Aが構成(CCAinRO)の暗号文 c* = (f_i(r*), G(r*)+m*, H(r*,m*)) を入手しても、

• f_i が一方向置換なので、r* はわからない。
• r*が分からないと、G(r*)はm*と同じサイズの（r*とは独立な）ランダム文字列。
• よって、G(r*)+m* は m* を完全に隠す。

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

• a は a = f_i(r) となる r を数学的に決定する。
• このrについて、等式 b = H(r, w-G(r)) が成り立っていなければならない。
• よって、Aはrを知っているはずである。
• よって、Aはcの復号文 m = w - G(r) を知っているはずである。
• Aにとって復号オラクルは意味がない。

定理(CCAinRO)の証明

構成(CCAinRO)に対する任意のCCA攻撃者をAとする。Aの成功確率を 1/2 + ε(n) とおく（識別利得はε(n)）。
Aを用いてトラップドア置換 f_i のインバーターBを構成する：

インバーターB: a*(=f_i(r*))を入力として、インデックスiを補助入力として、

• pk=(i,G,H)を入力としてAを起動する。
  • AからGオラクルに対する問い合わせrを受け取ったら、
    • a* = f(r)ならば、rを出力して終了。
    • G[r]が未定義ならば、g ← {0,1}^l, G[r] = g
    • g = G[r]を返答する。
  • AからHオラクルに対する問い合わせ(r,m)を受け取ったら、
    • a* = f(r)ならば、rを出力して終了。
    • H[r,m]が未定義ならば、b ← {0,1}ⁿ, H[r,m] = b
    • b = H[r,m]を返答する。
  • Aから復号オラクルに対する問い合わせc=(a,w,b)を受け取ったら、
    • b=H[r,m] かつ f_i(r)=a かつ w=G(r)+m となる r,m をH記憶から検索する。
    • みつかれば m を、みからなければ⊥を返答する。
  • Aからチャレンジクエリ(m₀,m₁)を受け取ったら、
    • w* ← {0,1}^l, b* ← {0,1}ⁿ, c* = (a*, w*, b*)
    • /* このとき、G,Hに対し、b* = H(r*, w*+G(r*)) というimplicitな関係を定義していることに注意。*/
    • c*を返答する。
• Aが終了したら、終了する。

[攻撃者Bの解析]:

• AskR： 『AがGオラクルまたはHオラクルにr*をたずねる。』
• Fake： 『Aが復号オラクルにc=(a,w,b)を問い合わせ、a = f_i(r), b = H(r, w+G(r))が成り立っているのに、
  • （つまり、問い合わせ c は妥当な暗号文であるのに、）
  • AはHオラクルに(r, w+G(r))を問い合わせていない。』

• Fakeが起きない限り、復号オラクルのシミュレーションは正しい。
  • シミュレートされた復号オラクルの返答は復号アルゴリズムの返答に等しい。
• さらに、Fakeが起きない限り、
  • AskRがおきないうちは、BのAに対するシミュレーションは完全である。（b*がテキトウであることがバレナイ）
  • AskRがおきれば、Bは直ちに成功する。
  • AskRが最後までおきなかったら、Aの成功確率は高々1/2である。

条件￢FakeのもとでのAの成功確率を 1/2 + ε'(n) とする。
条件￢Fakeのもとでの確率をPr_NoFake[・]とかくことにすると、

• 1/2+ε'(n) = Pr_NoFake[Aが成功する ｜ AskR] Pr_NoFake[AskR] + Pr_NoFake[Aが成功する ｜ ￢AskR] Pr_NoFake[￢AskR]
  • ≦ Pr_NoFake[AskR] + 1/2 = Pr[Bが成功する] + 1/2.

よって、仮定よりf_iは一方向置換なので、ε'(n)はネグリジブルである。

さらに、

• 1/2 +ε'(n) = Pr[Aが成功する | ￢Fake] ≧ Pr[Aが成功する] - Pr[Fake] = 1/2 + ε(n) - Pr[Fake]

より

• ε(n) ≦ ε'(n) + Pr[Fake] .

よって、後は以下の主張を示せば、定理の証明は完了。

主張 Pr[Fake]はネグリジブルである。

証明　復号クエリc=(a,w,b)に対して、AはHオラクルに(r, w+G(r))を問い合わせていないのに、

• a = f_i(r), b = H(r, w+G(r))

が成り立っているとする。

• r = r* かつ w+G(r) = w*+G(r*)のとき:
  • (a,w,b) = (a*,w*,b*)となるので、ゲームのルールより、このケースは起こらない（としてよい）。
• r ≠r* または w+G(r) ≠ w*+G(r*)のとき：
  • H(r, w+G(r))は、チャレンジ暗号文c*に含まれるb*=H(r*, w*+G(r*))とは独立な確率変数。
  • 仮定より、H(r,w+G(r))はAにHオラクル経由でも入力されていない。
  • 以上より、AのviewはH(r,w+G(r))と独立。したがって、Aの出力したbもH(r,w+G(r))と独立。
  • よって、b = H(r, w+G(r)) となる確率はネグリジブルである。

Q.E.D.

Q.E.D.

上へ

---