補題1(RSA-HC2)の証明 - 暗号理論教室

補題1(RSA-HC1)の証明

X := 1/t Σ_i=1..t S_i とする。

• E[X] = α = 1/2 + ε.
• Var[X] = 1/t² ΣVar[S_i] ≦ 1/t. ∴ σ ≦ 1/t^1/2.
• |X - α| < ε　ならば　X > 1/2.

よって、

• Pr[ X > 1/2 ] ≧ Pr[ |X - α| < ε]
• Pr[ |X - α| ≧ ε] ≦ Pr[ |X - α| ≧ εt^1/2 σ ] ≦　1/(t ε²) 　　（※ Chebyshevの不等式）

よって、

• Pr[ X > 1/2 ] ≧ 1 - 1/(t ε²).

Q.E.D.

---