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

定理(RSA-HC2)の証明 [Neuenschwander 04, 2.4]

主張
l = |n| 、ε= 1/ξ(l) とし、これらについて定理(RSA-HC2)のアルゴリズムA₁が存在するとする。
a, b, x ∈ Z_n* について、有理数u = u(a,x) と 有理数v = v(b,x)を以下のようにとる：

• | [a x]_n - u n | ≦ ε³ n / 8
• | [b x]_n - v n | ≦ εn / 8.

さらに、α = Lsb([a x]_n), β = Lsb([b x]_n)　とする。
このとき、あるPPTアルゴリズムLがあって、

• a, b, x ← Z_n*, y = [x^e]_n, (α₀, ... , α_l) ← L(n,e,y,a,b,u,v,α,β) について、
• Pr[ α_t = Lsb([a_t x]_n) | α_j = Lsb([a_j x]_n) for j = 0..(t-1) ] ≧ 1 - 1/(2 l)　for t = 0..l.
  • ただし、a₀ = a, a_t = [2^-1 a_t-1]_n.

証明

主張のアルゴリズムLを用いて、目標のアルゴリズムA₂を構成する。
アルゴリズムA₂: n, e, y を入力として、

• l = |n| 、ε= 1/ξ(l)
• a, b ← Z_n*
• Guess u, v ∈ Q s.t.
  • | [a x]_n - u n | ≦ ε³ n / 8
  • | [b x]_n - v n | ≦ εn / 8.
    • ※ u, v はそれぞれ (ε³/8)刻み, (ε/8)刻みの[0,1]範囲の有理数からのguess.
• Guess α = Lsb([a x]_n), β = Lsb([b x]_n)
• (α₀, ... , α_l) ← L(n, e, y, a, b, u, v, α, β)
• ※ 以下は定理(RSA-HC1)の証明のA₂と（本質的に）同じ。精度をn倍に精密化する。
• a₀ = a, u₀ = u
• t ∈ [1..l] : u_t = (u_t-1 + α_t-1) / 2, a_t = [2^-1 a_t-1]_n
• return [a_l^-1 floor(u_l n + 1/2)]_n.

[アルゴリズムA₂の解析]:

• j ∈ [1..t] について、α_j-1 = Lsb([a_j-1 x]_n)との仮定のもとで
  • | [a_t x] - u_t n | = (1/2) | [a_t-1 x] - u_t-1 n |.　（※ 定理(RSA-HC1)の証明のときと同様）
  • よって、
  • | [a_l x] - u_l n | ≦ ε³/8 < 1/2
  • よって、
  • x = a_l^-1 floor(u_l n + 1/2) mod n.
• ゆえに、主張より
• Pr[ A₂(n, e, y) = x ] ≧ (1 - 1/(2l))^l+1 ≧ (1 - 1/(2l))^2l-1 ≧ 1/e.

Q.E.D.
上へ

---