補題(Reset)の証明のアイデア

ACC = 『 VはQを受理 』
RES = 『 Vは2回続けてQを受理 』∧ 『 CH1 ≠ CH2 』.
示したい不等式は、
  • Pr[ACC] ≦ |ChSetpk|-1 + Pr[RES]1/2.

補題(Reset)の証明

acc =def Pr[ ACC(pk, sk) ], res =def Pr[ RES(pk, sk) ] とする。
ランダムテープR が定まればCMTは決まり、RとCHが決まればRSPも決まる:
  • CMTR := Q(ε; (sk,R))のCMT
  • RSPR,CH := Q(CH; (sk,R,CMT))のRSP

そこで、
  • accR =def Pr[ CH←ChSet: DEC(CMTR, CH, RSPR,CH) = 1 ]
  • resR =def Pr[ CH1←ChSet, CH2←ChSet:
    • DEC(CMTR, CH1, RSPR,CH1) = 1 ∧ DEC(CMTR, CH2, RSPR,CH2) = 1 ∧ CH1 ≠ CH2 ]
とおく。acc = ER[accR], res = ER[resR] である。

このとき、
主張
  • resR ≧ accR (accR - |ChSet|-1).
証明
di = DEC(CMTR, CHi, RSPR,CHi) とおくと、
  • accR2 = Pr[d1 = 1 ∧ d2 = 1]
    • = Pr[CH1≠CH2] Pr[d1=1 ∧ d2=1 | CH1≠CH2] + Pr[CH1=CH2] Pr[d1=1 ∧ d2=1 | CH1=CH2]
    • ≦ resR + |ChSet|-1 accR.
q.e.d.

p := |ChSet|-1 とおく。主張より、
  • res = ER[resR] ≧ ER[accR (accR - p)]
    • ≧ ER[accR]2 - p ER[accR] = acc2 - p acc.
よって、
  • (acc - p/2)2 ≦ res + p2/4.
ゆえに、
  • acc ≦ (res + p2/4)1/2 + p/2 ≦ res1/2 + (p2/4)1/2 + p/2 ≦ res1/2 + p.

Q.E.D.
上へ


















最終更新:2009年11月04日 18:42