问Wesolowski和Pietrzak可验证延迟函数(VDF)的平方和非任意幂的原因

EN

使用重复的平方而不是任意的指数是否有密码意义？只是简单点吗？

更重要的是，它使描述更简单。

验证者和验证者共同计算g^{2^t} \bmod G，但是他们并没有以平衡的方式完成它。

证明器完成大部分工作，计算除指数的\ell因子(其中\ell是适度素数)的所有因子；也就是说，它计算g^{\lfloor 2^t / \ell \rfloor}；验证器以其馀的方式(将\ell的最终指数应用于它)，并验证最终乘积(在乘以g^{2^t \bmod \ell}的最终因子之后)是期望值。

现在，我们可以重写它来使用一个大的随机T值，而不是2^t，但是它更复杂(因为T / \ell和T \bmod \ell的计算必然更复杂)，而且还不清楚额外的复杂性会带来什么好处。

先前的错误答案

2^T方法确实降低了执行验证步骤的成本；考虑到这是我们期望的廉价步骤，降低成本是非常重要的。

使用2^T，验证器将需要计算2^T \bmod p-1和2^T \bmod q-1 (其中p, q是G的主要因素)；这可以使用O(\log T)模块乘法来完成。

相反，如果我们使用CSRNG生成的T位数字，验证器将需要生成T位号(这显然需要O(t)时间)。

我不知道这是否是他们用来选择平方方法的理由；然而，这似乎是一个合理的决定。

为了补充其他答案，让我补充一下，Wesolowski关于重复平方的证明已经扩展到任意指数(证实了Sam的猜测是可以做到的)。例如，这样的扩展可以在这篇最近的论文中找到。泛化并没有真正导致更好的VDF，因为重复的平方非常好，但是它还有许多其他的应用。从本质上讲，它可以给出任意大指数知识的简洁证明，这是在先前引用的工作中用来建立累加器和位置向量承诺的有效方法。甚至最近，这些结果被用来给出鼻梁的新构造。