暗号理論教室
暗号理論教室

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

攻撃者Aが構成(REACT)の暗号文 y* = (a*←Enc(pk,r*), b*=G(r*)+m*, c*=H(r*,m*,a*,b*)) を入手しても、
  • Encが一方向なので、r* はわからない。
  • r*が分からないと、G(r*)はm*と同じサイズの（r*とは独立な）ランダム文字列。
  • よって、G(r*)+m* は m* を完全に隠す。

攻撃者Aが構成(REACT)の妥当な暗号文 y = (a,b,c) を生成したとすると、
  • a は a ← Enc(pk,r) となる r を決定する。
    • ただし、Encは確率的なので、テクニカルには平文検査オラクルが必要となる。
  • このrについて、 m = b - G(r) とするとき、等式 c = H(r,m,a,b) が成り立っていなければならない。
  • よって、Aはrを知っているはずである。
  • よって、Aはyの復号文 m = b - G(r) を知っているはずである。
  • Aにとって復号オラクルは意味がない。

定理(REACT)の証明

構成(REACT)に対する任意のCCA攻撃者をAとする。Aの成功確率を 1/2 + ε(n) とおく（識別利得はε(n)）。
Aを用いてベースの公開鍵暗号(Gen,Enc,Dec) の平文検査攻撃におけるインバーターBを構成する：

インバーターB: pk, a*(← Enc(pk,r*))を入力として、
  • （REACTの公開鍵としての）pkを入力としてAを起動する。
    • AからGオラクルに対する問い合わせrを受け取ったら、
      • (a*,r)を平文検査オラクルに尋ね、返答としてtrueを受けっとたら、rを出力して終了。
      • G[r]が未定義ならば、g ← {0,1}l, G[r] = g
      • g = G[r]を返答する。
    • AからHオラクルに対する問い合わせ(r,m,a,b)を受け取ったら、
      • (a*,r)を平文検査オラクルに尋ね、返答としてtrueを受けっとたら、rを出力して終了。
      • H[r,m,a,b]が未定義ならば、h ← {0,1}k, H[r,m,a,b] = h
      • h = H[r,m,a,b]を返答する。
    • Aから復号オラクルに対する問い合わせy=(a,b,c)を受け取ったら、
      • c=H[r,m,a,b]となる r,m をH記憶から検索する。
      • みつかれば m を、みつからなければ⊥を返答する。
    • Aからチャレンジクエリ(m0,m1)を受け取ったら、
      • β← {0,1}, g* ← {0,1}l, c* ← {0,1}k, y* = (a*, b*=g*+mβ, c*)
      • /* このとき、G,Hに対し、g* = G(r*), c* = H(r*,mβ,a*,b*) というimplicitな関係を定義していることに注意。*/
      • y*を返答する。
  • Aが終了したら、終了する。

[攻撃者Bの解析]:
  • AskR： 『AがGオラクルまたはHオラクルにr*をたずねる。』
  • Fake： 『Aが復号オラクルにy=(a,b,c)を問い合わせ、a ← Enc(pk,r), m = b - G(r) について、
    • c = H(r,m,a,b)が成り立っているのに、（つまり、問い合わせyは妥当な暗号文であるのに、）
    • AはHオラクルに(r, m, a, b)を問い合わせていない。』

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

条件￢FakeのもとでのAの成功確率を 1/2 + ε'(n) とする。
条件￢Fakeのもとでの確率をPrNoFake[・]とかくことにすると、
  • 1/2+ε'(n) = PrNoFake[Aが成功する ｜ AskR] PrNoFake[AskR] + PrNoFake[Aが成功する ｜ ￢AskR] PrNoFake[￢AskR]
    • ≦ PrNoFake[AskR] + 1/2 = Pr[Bが成功する] + 1/2.
よって、仮定より(Gen,Enc,Dec)は一方向なので、ε'(n)はネグリジブルである。

さらに、
  • 1/2 +ε'(n) = Pr[Aが成功する | ￢Fake] ≧ Pr[Aが成功する] - Pr[Fake] = 1/2 + ε(n) - Pr[Fake]
より
  • ε(n) ≦ ε'(n) + Pr[Fake] .
よって、後は以下の主張を示せば、定理の証明は完了。

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

証明　復号クエリy=(a,b,c)に対して、AはHオラクルに(r,m,a,b)を問い合わせていないのに、
  • a ← Enc(pk, r), m = b - G(r), c = H(r,m,a,b)
が成り立っているとする。
  • (r,m,a,b) = (r*,mβ,a*,b*) のとき:
    • y = y* となるので、ゲームのルールより禁止。
  • (r,m,a,b) ≠ (r*,mβ,a*,b*) のとき:
    • H(r,m,a,b)は、チャレンジ暗号文y*に含まれるH(r*,m*,a*,b*)とは独立な確率変数。
    • 仮定より、H(r,m,a,b)はAにHオラクル経由でも入力されていない。
    • 以上より、AのviewはH(r,m,a,b)と独立。したがって、Aの出力したcもH(r,m,a,b)と独立。
    • よって、c = H(r,m,a,b) となる確率はネグリジブルである。
Q.E.D.

Q.E.D.












「定理(REACT)の証明」をウィキ内検索
最終更新：2009年10月10日 20:06