定理(ランポート署名)の証明 - 暗号理論教室

定理(ランポート署名)の証明のアイデア

メッセージ m = m₁ ・・・m_l の、vk = (y_1,0, y_2,0, ・・・, y_l,0 : y_1,1, y_2,1, ・・・, y_l,1)に関するランポート署名は

• σ = (x_1,m1, x_2,m2, ・・・, x_l,ml).

攻撃者Fが署名オラクルから入手した、メッセージ m' = m'₁ ・・・m'_l の署名は

• σ' = (x_1,m'1, x_2,m'2, ・・・, x_l,m'l).

ゲームのルールより、ある i* があって、

• m_i* ≠ m'_i*.

よって、攻撃者Fは、あるi*とm_i*について、
y_i*,mi*に関する f の逆像 x_i*,mi* を自力で計算できていなければならない。

定理(ランポート署名)の証明

ランポート署名Ωに対する任意の効率的な偽造者をFとする。
偽造者Fを用いて一方向関数 f のインバーターBを構成する。

インバーターB: y (= f(x))を入力として、

• i* ← [1..l], b* ← {0,1}, y_i*,b* = y
• i ∈ [1..l], b ∈ {0,1} with (i,b) ≠ (i*,b*) :
  • x_i,b ← {0,1}ⁿ, y_i,b = f(x_i,b)
• vk = (y_1,0, y_2,0, ・・・, y_l,0 : y_1,1, y_2,1, ・・・, y_l,1) を入力としてFを起動：
  • Fから署名オラクルに対する問い合わせ m' を受け取ったら、
    • その i* 番目のビット m'_i* が b* だったら、諦めてアボートする。
    • そうでなければ、σ = (x_1,m'1, ・・・, x_l,m'l) を m の署名として応答する。
• Fが出力(m, σ = (x₁,...,x_l))で終了したら、
  • σが妥当な署名で、かつ m'_i* = 1-b* かつ m_i* = b* ならば（すなわち、(i*,b*)において偽造に成功していたら）、
    • x_i*を出力して停止。
  • そうでなければアボートする。

インバーターBの解析：

• m≠m'より、Fが偽造に成功するならば、Fはある(i,b)において偽造に成功する。
• よって、偽造に成功するという条件のもとで、Fが(i*,b*)において偽造に成功する確率は 1/(2l)。
• Fが(i*,b*)において偽造するならば、m'_i* ≠ b*なので、署名オラクルのシュミレーションは完ぺきで、
• その出力 x_i* は必ず y の逆像となっている。

以上より、

• Pr[Bが成功] ≧ Pr[Fが(i*,b*)において偽造に成功] ≧ 1/(2l) Pr[Fが偽造に成功].

よって、

• Pr[Fが偽造に成功] ≦ 2l Pr[Bが成功].

仮定より f は一方向関数なので、右辺はネグリジブル。よって、Pr[Fが偽造に成功]もネグリジブル。

Q.E.D.
上へ

---