定理(FS変換)の証明のアイデア
キャノニカルプロトコルID = (K, P, V = (ChSet,DEC))をフィアット・シャミア変換して得られる
署名スキーム FSH(ID) について、メッセージ m の署名σ=(CMT, RSP)は
- DECpk(CMT, CH=H(CMT, m), RSP)
を満たさなければならない。
ランダムオラクルモデルのもとでは、偽造者がm（やCMT）を選べたとしても、
H(m,CMT)は（mやCMTとは独立に）ランダムに選択される。
よって、うえのようなσを生成するには、ランダムなチャレンジCHについて、
DECpk(CMT, CH, RSP)をみたすレスポンスRSPを生成するしかない。
これは（受動的に）安全なキャノニカルプロトコルIDに対しては無理。
定理(FS変換)の証明
キャノニカルプロトコルID = (K, P, V = (ChSet,DEC)) についての、
構成(FS変換)FSH(ID)に対する任意の効率的な偽造者をFとする。
Fの署名クエリ回数の上限をqS、Hオラクルへのクエリ回数の上限をqHとする。
一般性を失わず、
- FはHオラクルに同一の問い合わせを2回以上は行わない。
- Fは署名オラクルにmを問い合わせるとき、（あるCMTについて）事前に(CMT,m)をHオラクルに問い合わせている
- Fは署名の偽造(m', σ'=(CMT',RSP')) を出力するとき、事前に(CMT', m')をHオラクルに問い合わせている
としてよい。(Fにとって有利な設定)
偽造者Fを用いて、キャノニカルプロトコルIDに対する、受動的攻撃者Aを構成する。
攻撃者A: 公開鍵 pk を入力として、
- ※ Aの目的は 対応する秘密鍵skの証明者になりすますこと。
- 連想記憶H[]を初期化する。 t ← [1..qH]
- トランスクリプトオラクルからqS個のトランスクリプトを入手する：
- <tCMT1,tCH1,tRSP1>, ... , <tCMTqS,tCHqS,tRSPqS>.
- ※ DECpk(tCMTj, tCHj, tRSPj) = 1. (j=1..qS)
- vk=pkを入力としてFを起動する。
- FからHオラクルに対するk番目の問い合わせ (CMTk,mk) を受け取ったら（1≦k≦qH）、
- k = t ならば、
- CMT* = CMTt を自身のコミットとして外部の検証者Vに送る。
- 外部の検証者Vからチャレンジ CH* を受け取り、H[CMT*, m*] = CH* とし（m* = mt)、CH*をFに応答する。
- ※ H(CMT*, m*) = CH*
- k ≠ t ならば、
- H[CMTk,mk] ← ChSet とし、H[CMTk,mk]をFに応答する。
- Fから署名オラクルに対する j 番目の問い合わせmjを受け取ったら、
- H[tCMTj, mj]がすでに定義されていたら、アボートする。(アボート1)
- そうでないならば、H[tCMTj, mj] = tCHjとし、(tCMTj, tRSPj)をFに応答する。
- ※ DECpk(tCMTj, tCHj, tRSPj) = 1.
- Fが出力 (m', (CMT', RSP')) で停止したら、
- (CMT', m') = (CMTk, mk) となるkを検索する。
- k ≠ t ならば、アボートする。(アボート2)
- k = t ならば、RSP'を外部の検証者Vに送信して停止する。
- ※ Fの出力が正しければ、RSP'は DECpk(CMT'=CMT*, CH*=H(CMT*,m*), RSP') = 1 をみたす.
攻撃者Aの解析：
- アボート1が起きないとき、Aによる署名オラクルのシミュレーションは完ぺきである。
- アボート2 と Fが偽造に成功するイベントは独立。
- アボート2が起きないとき、Fが偽造に成功していれば、Aは証明者P(sk)になりすます。
以上より、
- Pr[Aがなりすましに成功] ≧ Pr[Fが偽造に成功 ∧ ￢アボート2 ∧ ￢アボート1]
- ≧ Pr[Fが偽造に成功 ∧ ￢アボート2] - Pr[アボート1]
- = Pr[Fが偽造に成功] Pr[￢アボート2] - Pr[アボート1]
- = Pr[Fが偽造に成功] 1/qH - Pr[アボート1].
IDの
コミットメント長が十分長いとの仮定より、Pr[アボート1]はネグリジブル。
IDは受動的攻撃に対し安全なので最左辺はネグリジブル。
よって、Pr[Fが偽造に成功]もネグリジブル。
Q.E.D.
最終更新：2009年11月25日 15:59
