理解分叉引理和預言機重放攻擊
許多簽名方案使用分叉引理來證明安全性，就像這裡的方案。簡而言之，它通過稱為 oracle-replay 攻擊的簡化技術來解決算法難題，需要兩輪模擬 $ \mathcal{F} $ 獲得兩個有效的簽名對 $ (m,r,e,s) $ 和 $ (m,r,e’,s’) $ ，在哪裡 $ r $ 是“承諾”， $ e = H(m||r) $ , $ s $ 和 $ s’ $ 與 $ m $ , $ r $ 和 $ e $ . 但是如何保證偽造者 $ \mathcal{F} $ 將輸出相同的消息 $ m $ 和 $ r $ ，因為他們可以在每次模擬中隨機選擇？
也可以看看 $$ PS00 $$大衛 Pointcheval 和雅克斯特恩。數字簽名和盲簽名的安全參數。密碼學雜誌，2000 年。
我們使用偽造者的事實 $ \mathcal{F} $ 只不過是帶有一些隨機磁帶的圖靈機。而且因為 $ \mathcal{F} $ 是我們擁有的，我們可以選擇磁帶。因此，我們可以重新執行 $ \mathcal{F} $ 用相同的磁帶，和行為 $ \mathcal{F} $ 將是相同的（直到預言機將返回不同的值並發生所需的“分叉”）。
偽造者 $ F $ 是機率圖靈機，即具有隨機磁帶的確定性圖靈機，但僅重用相同的隨機磁帶不能生成相同的隨機磁帶 $ (m,r) $ .
在模擬中，“外部”對手 $ A $ （針對一些難題）執行 $ F $ 以黑盒方式控制其包含公平隨機位的隨機磁帶。對於每個 $ F $ 執行， $ A $ 對隨機磁帶進行採樣 $ r_F $ 為了 $ F $ 和隨機硬幣 $ r_H $ 用於回答隨機預言 $ H $ 查詢。請注意，對於每個採樣的隨機磁帶， $ A $ 執行 $ F $ 兩次。在第二輪中， $ A $ 倒帶 $ F $ 到那個地步 $ H(m,r) $ 被查詢，然後用一個獨立的隨機值回答它 $ e’ $ . 因為 $ A $ 使用相同的隨機磁帶 $ r_F $ 和相同的前部（在回答之前 $ H(m,r) $ ） 的 $ r_H $ , $ F $ 的行為直到查詢 $ H(m,r) $ 是完全確定的，因此將產生相同的 $ (m,r) $ .