如何将Fiat-Shamir变换随机预言应用于协议的备选方案

Question

菲亚特-沙米尔变换通常是通过对验证者的消息进行散列来替代(公共)硬币，直到这一点，即：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's是验证者的消息。

我知道这在随机oracle模型中被证明是安全的(至少对于不断循环的协议来说是这样)，但是我正在寻找这个范例的一些替代方案。也就是说，我想知道如果我用输入\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将i-th维一致分布映射到j-th维空间，将会发生什么。

例子:如果我们把所有的f_i作为j=i的恒等函数(即f_i(\alpha_1, \dots, \alpha_i) = (\alpha_1,\dots,\alpha_i) )，那么我们得到了执行Fiat变换的原始方法。另一个(不知道是安全的)示例是f_i(\alpha_1, \dots, \alpha_i) = \alpha_1 + 2\cdot\alpha_2 + \dots +i\cdot\alpha_i。

我问自己的一个更普遍的问题是:为了确保Fiat转换协议在随机预言模型中是安全的，f_i应该满足哪些条件。

为什么这是有用的:嗯，我还没有想出一个合适的动机；但是我认为它在证明合成的场景中可能是有用的。也就是说，如果我试图计算一个非交互证明的非交互式证明，那么我必须在我的计算模型(例如算术电路)中表示每个验证者对第一个证明的消息的计算。如果has函数有较少的输入，则得到的结果将更短。

事实上，我已经看到一些人实现Fiat如下：H(x,\alpha_1) = \beta_1, \\ H(\beta_1, \alpha_2) = \beta_2,\\H(\beta_2, \alpha_3) = \beta_3,\\\vdots，这与最初的定义略有不同。这证明是安全的吗？

Answer 1

有几点：

1. 你的最后一个菲亚特-沙米尔方案可以被看作是H(x, \alpha_1)，H(H(x, \alpha_1), \alpha_2)，H(H(H(x, \alpha_1), \alpha_2), \alpha_3), ....如果H是一个随机的预言，这应该有类似的分析，第一个菲亚特-沙米尔变换你提出。
2. 根据协议的不同，对于菲亚特-沙米尔变换来说，随机预言可能不是必需的.例如，最近一项名为菲亚特-沙米尔需要密码哈希函数吗？的工作表明，即使使用非加密哈希函数(例如和-mod-p或位分解)实例化，菲亚特-沙米尔变换仍然是健全的。重要的是:这是为了某些协议！
3. 考虑到第1和第2点，对于某些协议，如果函数f(\cdot)不是随机预言，菲亚特-沙米尔可能仍然是健全的。然而，这需要相当的谨慎和证明。

希望这能给你一个开始！