主張(RSA-HC2)の証明 - 暗号理論教室

主張(RSA-HC2)の証明

補題1
t個の、組ごとに独立なバイナリ確率変数S₁,...,S_tが平均値 E[S_i] = α = 1/2 + εを共有するならば（ε>0）、

• Pr[ Σ_i=1..t S_i > t/2 ] ≧ 1 - 1/(tε²).

証明

主張(RSA-HC2)の証明
l = |n| について、m = 2l/ε² とする。（※lについて多項式）
注意： このとき、m ≦ 2^t/ε² が成り立つとしてよい。
実際、t > log(l) としてよい（log(l)個までならLsb([a_jx]) (j=1..log(l))を直接geussできる）ので、m ≦ 2^t/ε²。

アルゴリズムL: n, e, y, a, b, u, v, α, β を入力として、（※α=Lsb([ax]_n), β= Lsb([bx]_n)）

• a₀ = a, u₀ = u, α₀ = α
• t ∈ [1..l] :
  • c₀ = 0, c₁ = 0
  • a_t = [2^-1 a_t-1]_n, u_t = (u_t-1 + α_t-1) / 2
  • i ∈ [(-m/2)..(m/2-1)] :    ※ A₁を何度か実行して多数決で正しい値を判断する
    • A = a_t + i a_t-1 + b    ※ a_t を中心に2次元分のランダムネスをa, bから引き継ぐ
    • W = floor( u_t + i u_t-1 + v )　※ w のguess
    • B = (i α + β + W) mod 2
    • A₁(n,e,[A^e y]_n) + B ≡^? 0　(mod 2) ：　
      • c₀ = c₀ + 1 else c₁ = c₁ + 1
  • c₀ > c₁ ： α_t = 0 else α_t = 1
• return (α₀, α₁, ... , α_l).

[アルゴリズムLの解析]:
j ∈ [0..(t-1)] について α_j = Lsb([a_jx]) と仮定する。

i ∈ [(-m/2)..(m/2-1)] :

• A_t,i := a_t + i a_t-1 + b
• W'_t,i := u_t + i u_t-1 + v
• W_t,i := floor(W'_t,i)
• B_t,i := i Lsb([a_t-1x]_n) + Lsb([bx]_n) + Lsb(W_t,i) mod 2
• λ_t,i := [a_tx]_n + i [a_t-1x]_n + [bx]_n
• w := floor(λ_t,i/n)　※ λ_t,i = wn + [A_t,i x]_n

主張1 W_t,i = w ならば　Lsb([a_tx]_n) ≡ Lsb([A_t,ix]_n) + B_t,i　(mod 2).
証明

主張2 εn/4 < [A_t,i x]_n < n - εn/4 ならば W_t,i = w.
証明

主張3 i ≠ j ならば、確率変数 [A_t,i]_n と [A_t,j]_n は独立。
証明

i∈[(-m/2)..(m/2-1)]について、

• イベント E_1,i : 『 A₁(n,e,[A_t,i^e y]_n) = Lsb([A_t,i x]_n) 』
• イベント E_2,i : 『 εn/4 < [A_t,i x]_n < n - εn/4 』
• イベント I_i := E_1,i ∩ E_2,i

とおくと、

• Pr[E_1,i] ≧ 1/2 + ε　※ 主張の仮定
• Pr[E_2,i] = 1 - ε/2

よって、

• Pr[I_i = 1] ≧ Pr[E_2,i] - (1-Pr[E_1,i]) ≧ (1 - ε/2) - (1/2 - ε) = 1/2 + ε/2.

主張3より、i≠jならばI_iとI_jは独立なので、{I_i : i∈[(-m/2)..(m/2-1)]}に補題1を適用でき、

• Pr[ Σ_{i=(-m/2)..(m/2-1)}I_i > m/2 ] ≧ 1 - 1/(mε²) ≧ 1 - 1/(2l).

一方、主張1、主張2より、

• I_iが成り立つならば、Lsb([a_tx]) ≡ Lsb([A_t,ix]) + B_t,i (mod 2).

よって、

• Lsb([a_tx]) = 0 ⇒ C₀ ≧ Σ_iI_i ⇒ Pr[C₀ > C₁] ≧ 1 - 1/(2l).
• Lsb([a_tx]) = 1 ⇒ C₁ ≧ Σ_iI_i ⇒ Pr[C₁ > C₀] ≧ 1 - 1/(2l).

したがって、

• Pr[ α_t = Lsb([a_tx]) ] ≧ 1 - 1/(2l).

Q.E.D.

上へ

---