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

主張(RSA-HC2-2)の証明

まず、Z := | λ_t,i - W'_t,in | について

• Z ≦ εn/4

を示す。
証明

• Z = | [a_tx] + i [a_t-1x] + [bx] - (u_t + i u_t-1 + v)n |
  • = | [a_tx] - u_tn + i([a_t-1x] - u_t-1n) + [bx] - vn |

ここで、j = 1..t について、

• [a_jx] = [2^-1 a_j-1x]
  • = (1/2) [a_j-1x] (when [a_j-1x]: even)
  • = (1/2) ([a_j-1x] + n) (when [a_j-1x]: odd)
• = (1/2) ([a_j-1x] + Lsb([a_j-1x])n)

よって、

• [a_jx] - u_jn = (1/2)([a_j-1x] + Lsb([a_j-1x])n) - u_jn = (1/2)([a_j-1x] - u_j-1n).

よって、

• Z = | (1/2)(1+2i)([a_t-1x] - u_t-1n) + [bx] - vn |
  • ≦ (1/2) |1+2i| |[a_t-1x] - u_t-1n| + |[bx] - vn|
  • ≦ (1/2)^t m ε³n/8 + εn/8
  • ≦ (εn/8) (ε²m/2^t + 1)
  • ≦ εn/4.      ※ m ≦ 2^t/ε²

Q.E.D.

さて、仮定より、εn/4 < [A_t,i x] < n - εn/4 で、λ_t,i = w n + [A_t,i x] だったから、

• wn + εn/4 < λ_t,i < w(n+1) - εn/4.

よって、Z ≦ εn/4　より

• wn < W'_t,in < w(n+1)

よって、

• W_t,i = [ W'_t,in / n ] = w.

Q.E.D.

上へ

---