Fiat-Shamir 啟發式的磨削
假設 Fiat-Shamir 啟發式算法將來自驗證者的公共硬幣消息替換為證明者消息的雜湊值，直到這一點，即：$$ H(\alpha_1) = \beta_1, \ H(\alpha_1, \alpha_2) = \beta_2,\H(\alpha_1, \alpha_2, \alpha_3) = \beta_3,\\vdots $$在哪裡 $ \alpha_i $ 是證明者的消息。
我理解為什麼 Fiat-Shamir 啟發式在 ROM 中被證明是安全的，但是，在實踐中，雜湊函式 $ H $ 不是預言機，那麼是什麼避免證明者為了能夠偽造假證明而研究他的資訊呢？
例如，在一個 $ \Sigma $ -protocol 只有一條來自驗證者的消息 $ \beta_1 = H(\alpha_1) $ . 如果證明者在一些問題上苦苦掙扎怎麼辦 $ \alpha_1’ $ 直到他找到雜湊函式的一些輸入，使得 $ \beta_1 $ 讓他獲得一些優勢？
為什麼我們要對所有前一個證明者的消息進行雜湊處理以獲得下一個非互動式驗證者消息？例如，這是執行的問題， $ H(\alpha_i) = \beta_i $ ? 更糟糕的是，如果證明者可以散列任何他想要的東西怎麼辦？
是什麼避免了證明者為了能夠偽造假證明而研究他的資訊？
我們也可以針對隨機預言提出完全相同的問題！是什麼阻止了證明者對他的資訊進行仔細研究，直到他可以偽造一個假證明？你的建議完全可以用 RO 完成。
答案是：應該有非常少的消息 $ \alpha_1 $ 這樣 $ \beta_1 = H(\alpha_1) $ 讓證明者有優勢。在一個典型的 $ \Sigma $ -協議，例如，當陳述不是語言時（因此證明者在作弊），平均有一個 $ \alpha_1 $ 這允許證明者作弊。（練習：證明這是 $ \Sigma $ -DDH 元組的協議，其中單詞是 $ (X,Y) $ 證人是 $ x\in\mathbb{Z}_p $ 這樣 $ X = g^x $ 和 $ Y = h^x $ ）。因此，如果有 $ 2^c $ 可能的值 $ \beta_1 $ （這是挑戰空間），惡意證明者必須計算 $ O(2^c) $ 散列來偽造一個假證明。現在做 $ c $ 足夠大，並且您獲得計算安全性。
請注意，研磨攻擊仍然是一個重要的考慮因素： $ \Sigma $ - 協議具有無條件的安全性，但是一旦您使用 Fiat-Shamir 在 ROM 中編譯它們，它們就只有計算上的健全性。這意味著必須相應調整穩健性的安全參數（挑戰空間）：40 位挑戰空間適用於 $ \Sigma $ -protocol（因為它給惡意證明者一個 $ 2^{-40} $ 成功打破健全性的統計機率，這在實踐中是可以接受的），但對於 Fiat-Shamir 來說是失敗的（因為打破編譯的協議需要 $ 2^{40} $ 操作，執行起來很簡單）。通常，我們將使用一個挑戰空間 $ 2^{128} $ 使用 Fiat-Shamir 時。