Fiat-Shamir 變換隨機預言如何應用於協議的替代方案
Fiat-Shamir 轉換通常通過將驗證者的（公共）投幣替換為證明者消息的雜湊值直到這一點來工作，即：$$ H(x,\alpha_1) = \beta_1, \ H(x,\alpha_1, \alpha_2) = \beta_2,\H(x,\alpha_1, \alpha_2, \alpha_3) = \beta_3,\\vdots $$在哪裡 $ x $ 是協議的公共輸入和 $ \alpha_i $ 是證明者的消息。
我知道這在隨機預言模型中被證明是安全的（至少對於常量輪協議），但我正在尋找這種範式的一些替代方案。也就是說，我想知道如果我替換輸入會發生什麼 $ \alpha_1, \alpha_2, \alpha_3, … $ 具有它們的功能。更具體地說，如果不執行會發生什麼 $ H(x,\alpha_1,\alpha_2,\dots,\alpha_i) $ 我表演 $ H(x,f_i(\alpha_1,\alpha_2,\dots,\alpha_i)) $ ， 在哪裡 $ f_i $ 是一個 $ i $ -th 變數函式映射 $ i $ -th 維均勻分佈到 a $ j $ -th 維空間，對於每個 $ i $ .
例子：如果我們把所有的 $ f_i $ 成為恆等函式 $ j=i $ （IE， $ f_i(\alpha_1, \dots, \alpha_i) = (\alpha_1,\dots,\alpha_i) $ 然後我們得到執行 Fiat-Shamir 變換的原始方式。另一個（不知道是安全的）範例是 $ f_i(\alpha_1, \dots, \alpha_i) = \alpha_1 + 2\cdot\alpha_2 + \dots +i\cdot\alpha_i $ .
我問自己的一個更普遍的問題是：哪些條件應該 $ f_i $ 滿足以確保 Fiat-Shamir 轉換後的協議在隨機預言機模型中是安全的。
為什麼這可能有用：嗯，我還沒有想出一個合適的動機；但我認為它在證明組合場景中可能很有用。也就是說，如果我嘗試計算非互動式證明的非互動式證明，那麼我必須在我的計算模型（比如算術電路）中表示每個驗證者的第一個證明的消息的計算。如果 has 函式的輸入更少，結果會更短。
事實上，我看到有些人實現 Fiat-Shamir 如下：$$ H(x,\alpha_1) = \beta_1, \ H(\beta_1, \alpha_2) = \beta_2,\H(\beta_2, \alpha_3) = \beta_3,\\vdots $$這與原始定義略有不同。這是否被證明是安全的？
有幾點：
- 您的上一個 Fiat-Shamir 計劃可以被視為 $ H(x, \alpha_1) $ , $ H(H(x, \alpha_1), \alpha_2) $ , $ H(H(H(x, \alpha_1), \alpha_2), \alpha_3), … $ . 如果 $ H $ 是一個隨機預言機，這應該與您提供的第一個 Fiat-Shamir 變換有類似的分析。
- 根據協議，Fiat-Shamir 轉換可能不需要隨機預言機。例如，最近的一項工作，Fiat-Shamir 是否需要加密雜湊函式？, 表明 Fiat-Shamir 變換即使在使用非加密雜湊函式（例如 sum-mod-p 或 bit-decomposition）實例化時也保持正確。重要提示：這是針對某些協議的！
- 考慮到第 1) 點和第 2) 點，對於某些協議，Fiat-Shamir 可能仍然是健全的，如果你的功能 $ f(\cdot) $ 不是隨機預言機。但是，這需要相當多的注意和證明。
希望這能讓你開始！