補題(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.
最終更新:2009年11月04日 18:42