ZK证明/ Sigma协议的Fiat-Shamir变换的挑战

Question

设\Sigma是一个西格玛协议，其承诺阶段、挑战阶段和响应阶段分别为\Sigma_1, \Sigma_2, \Sigma_3。

在Fiat变换中，面临的挑战是H(\Sigma_1)，其中H是一些散列函数.

然而，在一些文献中，不是有H(\Sigma_1)，而是H(x \parallel \Sigma_1)，其中\parallel表示级联，而x是常见的输入。例如，如果\Sigma是图3着色协议，则x将是相应的图.

1. 为什么要考虑与x的连接？x是为了防止可扩展的攻击而存在的吗？
2. 考虑语言L \in NP，并假设一个证明程序P想向验证器V证明x \in L。我们使用经典的x简化为SAT实例，然后将其简化为G3C实例。将此称为减缩t。这样，x \in L当且仅当t(x)是一个3-可着色图.现在我们可以应用菲亚特-沙米尔变换，这些挑战变成了H(t(x) \parallel \Sigma_1).是否有可能使H(x \parallel \Sigma_1)而不是H(t(x) \parallel \Sigma_1)面临挑战，从而避免H投入的增加？

提前谢谢。

Answer 1

如果将挑战计算为H(\Sigma_1)，则该变换称为弱Fiat (wFS)变换。另一方面，当挑战被计算为H(x\mathbin\Vert \Sigma_1)时，转换称为强Fiath (sFS)变换。

1. 在攻击者可以自适应地选择她想要证明的语句的情况下，证明系统不再安全，即。它不再是知识的证明了。例如，这导致许多实际攻击反对Helios投票系统。让我们将Schnorr标识作为wFS转换不安全的一个例子。

在由\mathbb{G}生成的阶q群中，证明了满足已知X方程X = G^{x}的指数x的知识。将(x, X)视为签名/验证密钥对，并在哈希输入中包含一条消息，将产生一个知识签名。为了创建一个证明，验证程序选择一个随机的a\leftarrow \mathbb{Z}_q并计算A = G^a。然后，她对A进行散列，以创建一个挑战c=H(A)。最后，她计算f=a+cx；证明是对(c, f)，验证过程包括检查方程c = H\Big(\frac{G^f} {X^c}\Big)。

但是，如果对手的目标是为她选择的任何(X, c, f)建立一个有效的三重X，那么这个协议就不再是知识的证明，除非离散对数问题在\mathbb{G}中很容易解决。实际上，假设有一个提取器K，它通过与任何提供有效的三重(X, c, f)的验证程序P交互，提取x = \log_G(X)。该抽取器可用于求解离散对数问题的实例Y，具体如下:以Y作为证明承诺，计算c = H(Y )，选择f\leftarrow \mathbb{Z}_q，设置X = \Big(\frac{G^f}{Y}\Big)^{1/c} 。由于验证(Y, c, f)通过了语句X的验证过程，提取器K应该能够通过与我们的验证程序交互来计算x = \log_G(X)。我们现在观察到，通过在G定义的两边取基X中的离散对数，我们得到了对离散对数挑战的解\log_G(Y ) = f − cx。

一篇描述wFS变换缺陷的很好的文章可以找到这里。

1. 由于这是sFS转换的一个实例，您提议的更改将产生一个安全的ZKP，有关证明，请参阅上面链接的文章中的第4节。

但是，我不知道ZKP的任何实际部署都会使用这样的还原技术。在大多数应用程序场景中，用于NP-完整语言的通用ZKP过于致命和效率低下。在我看来，这些结果大多被认为是理论上的结果，以证明所有NP语言都存在ZKPs。