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

定理(FDH)の証明のアイデア

vk = (i,H) に関する、メッセージ m のFDH署名σは

• f_i(σ) = H(m)

を満たさなければならない。

ランダムオラクルモデルのもとでは、偽造者がmを選べたとしても、
H(m)は（mとは独立に）ランダムに選択される。

よって、うえのようなσを生成するには、
f_iをランダムな値においてインバートするしかない。

定理(FDH)の証明

構成(FDH)に対する任意のPPT偽造者をFとする。Fの署名クエリ回数の上界をqとする。
一般性を失わず、

• Fは署名オラクルにmを問い合わせるとき、必ず事前にmをHオラクルに問い合わせている
• Fは(m,s)を出力するとき、事前にmをHオラクルに問い合わせている

としてよい。(Fにとって有利な設定)

偽造者Fを用いてトラップドア置換{f_i}_iのインバーターBを構成する。
インバーターB: y*(=f_i(r*))を入力として、インデックスiを補助入力として、

• ※ Bの目的は r* を求めること。
• t ← [1..q]
• vk=(i,H)を入力としてFを起動する。
  • FからHオラクルに対するk回目の問い合わせm_kを受け取ったら（1≦k≦q）、
    • k = t ならば、y* を返答する。
    • ※ H(m_t) = y* とした。
    • k ≠ t ならば、s_k ← {0,1}ⁿとし、y_k = f_i(s_k) を返答する。
    • ※ f_i(s_k) = y_k = H(m_k)、s_kはm_kの署名！
  • Fから署名オラクルに対する問い合わせmを受け取ったら、
    • m = m_k となるkを検索する。
    • k = t ならば、アボートする。(アボート1)
    • k ≠ t ならば、s_kを返答する。
• Fが出力 (m, s) で終了したら、
  • m = m_k となるkを検索する。
  • k ≠ t ならば、アボートする。(アボート2)
  • k = t ならば、sを出力して終了する。
  • ※ (m,s)が正しければ、f_i(s) = H(m_t) = y*！

インバーターBの解析：

• アボート1が起きないとき、Bによる署名オラクルのシミュレーションは完ぺきである。
• アボート2が起きないとき、Fが偽造に成功していれば、Bはy*のインバートに成功している。
• アボート2が起きず、Fが偽造に成功していれば、アボート1は起きていない。

以上より、
Pr[Bが成功] ≧ Pr[Fが成功 | ￢アボート2] Pr[￢アボート2] = Pr[Fが成功] 1/q.

f_iはトラップドア置換なのでPr[Bが成功]はネグリジブル。
よって、Pr[Fが成功]もネグリジブルである。
Q.E.D.

上へ

---