Lattice-Crypto
對於基於格的 GPV 雜湊和簽名算法產生的數字簽名，分叉引理如何工作？
我正在努力理解基於格的數字簽名背後的概念和方法，特別是 GPV 算法。
在這種方法的安全性降低過程中，使用分叉引理來證明攻擊者可以生成正確的偽造消息。
我讀到了分叉 lemme，但在這裡我無法完全理解它及其應用。這主要是因為我不是主要來自數學背景。
我正在尋找一個關於分叉引理如何在該方案中偽造簽名的簡單解釋。
雖然，正如 Chris 所說，GPV 不依賴於分叉引理，但這裡有一個可愛的隱喻。
想像一個有 n 級的影片遊戲。遊戲很艱難，在每一關，你有 1/2 的機率死亡。如果你死了，你必須從頭開始。它在一個非常舊的遊戲機上執行，您無法保存遊戲。所以，你需要平均 $ 2^n $ 在贏得整場比賽之前進行試驗。
儘管如此，遊戲仍然是完全確定的，唯一的隨機來源是您在遊戲搖桿上重現完全相同的擊鍵序列的有限技能。
分叉引理可以被認為是你的遊戲搖桿和控制台之間的一個小設備，它可以記錄你的擊鍵並重播它們。因此，如果您有幸成功通過了第 1 級，但未能通過第 2 級，您可以準確重播第 1 級的獲勝擊鍵序列，因此直接重播第 2 級，以嘗試那裡的擊鍵序列。有了這樣的策略，你可以平均贏得比賽 $ 2n $ 水平。
回到加密世界，確定性控制台是攻擊者，每一級的擊鍵序列是隨機預言機對每個雜湊查詢的響應。使用分叉引理策略，您可以針對給定請求嘗試多個響應，而無需重新隨機化所有先前的響應。這樣，您可以以某種方式欺騙您的攻擊者，使其更有效地到達特定情況，而不是希望隨機設置一組 $ n $ 回應會讓他到達那裡。