理解分叉引理
每次我讀到一篇有數字簽名的論文，在證明一個數字簽名方案的安全性時，作者都會有很多機會使用分叉引理。
分叉引理如下：
讓 $ \mathcal A $ 是一個機率多項式時間圖靈機，只給定公共數據作為輸入。如果 $ \mathcal A $ 可以以不可忽略的機率找到一個有效的簽名 $ (m,\sigma_1,h,\sigma_2) $ ，然後以不可忽略的機率，用相同的隨機磁帶和不同的預言機重放這台機器，輸出兩個簽名 $ (m, \sigma_1,h,\sigma_2) $ 和 $ (m, \sigma_1,h’,\sigma_2’) $ 這樣 $ h $ 不等於 $ h’ $ .
這個措辭來自 David Pointcheval 和 Jacques Stern 關於“簽名方案的安全證明”的論文。他們也證明了這個引理，但我很難閱讀。
為了理解我在說什麼，您可以在本文第 8-9 頁的“A Secure and Efficient Authenticated Diffie–Hellman Protocol”中看到一個範例。這是關於 FXCR 的安全證明。您可以從http://eprint.iacr.org/2009/408.pdf下載。
分叉引理確實讓我困惑了很長時間；誰能給出一個簡單的方法來理解它？
對於許多簽名方案，對於兩個不同的雜湊值使用相同隨機性的兩個簽名允許恢復私鑰。這在許多安全證明中被使用，表明偽造有效簽名的對手可以通過重播來強制生成這種形式的兩個簽名。結果，偽造者可能被扭曲成密鑰恢復攻擊。
技術問題是如何確保偽造者符合我們的期望並真正為相同的隨機性偽造兩個簽名。事實上，一般來說，沒有什麼能迫使對手以簡單的方式使用其隨機性。特別是，給他相同的硬幣並強制更改消息不會達到預期的目標，因為對手被允許將消息本身混合到用於簽名的隨機性中。
關鍵思想是以相同的隨機性重新啟動對手，讓它在沒有變化的情況下執行，直到它生成消息 $ M_0 $ 這是在第一次執行中與它的 rzndomness 一起簽署的，然後在其餘執行中強制進行更改。此時，在實際設置中，您可以想像對雜湊函式使用故障攻擊。然而，在一個理論模型中，改變是通過改變隨機預言機的響應來實現的，該隨機預言機對第一個查詢的雜湊函式建模，涉及 $ M_0 $ 以及所有後續查詢。
當你這樣做時，你已經知道對手的行為，直到 $ M_0 $ 已生成，並希望它會再次鍛造 $ M_0 $ 具有相同的隨機性但不同的雜湊值。這就是分叉引理髮揮作用的地方（對於一般版本，請參閱普通公鑰模型中的多重簽名和Bellare 和 Neven的一般分叉引理http://cseweb.ucsd.edu/~mihir/papers/多重簽名-ccs.pdf）。在這個通用版本中，它是一個技術引理，用於分析對手的行為，該對手接收一些隨機值（每個隨機值均取自 $ h $ 元素）並輸出一對值 $ (J,\sigma) $ 和 $ 0\leq J\leq q $ 當執行多個輸入共享公共前綴的執行時。請注意，當 $ J=0 $ ，則認為對手失敗。分叉引理的結果是獲得兩個具有相同值的相關執行的機率 $ J $ 和一個共同的長度前綴 $ J-1 $ 是不是太小了。更準確地說，如果 $ acc $ 表示對手在隨機輸入上的成功機率，並且 $ frk $ 如上所述獲得兩個相關執行的機率：
$$ frk\geq acc\cdot \left(\frac{acc}{q}-\frac{1}{h}\right). $$ Bellare 和 Neven 給出的證明並不難理解，我建議您閱讀它。