Schwartz-Zippel 引理及其在零知识证明中的应用
- RareSkills
- 发布于 2024-08-28 23:21
- 阅读 1051
文章详细介绍了Schwartz-Zippel Lemma在零知识证明（ZK-Proof）中的应用，通过多项式例子和Python代码展示了如何利用该引理进行多项式相等性测试和向量相等性测试。
几乎所有 ZK-Proof 算法都依赖于 Schwartz-Zippel 引理来实现简洁性。
Schwartz-Zippel 引理指出，如果我们有两个多项式 $p(x)$ 和 $q(x)$，它们的次数分别为 $d_p$ 和 $d_q$，并且 $p(x) \neq q(x)$，那么 $p(x)$ 和 $q(x)$ 的交点数量小于或等于 $\mathsf{max}(d_p, d_q)$。
让我们来看几个例子。
多项式示例与 Schwartz-Zippel 引理
一条直线与抛物线的交点
考虑多项式 $p(x) = x$ 和 $q(x) = x^2$。它们在 $x = 0$ 和 $x = 1$ 处相交。
它们在两点相交，这是多项式 $y = x$ 和 $y = x^2$ 之间的最大次数。
三次多项式与一次多项式
考虑多项式 $p(x) = x^3$ 和 $q(x) = x$。这些多项式在 $x = -1$、$x = 0$ 和 $x = 1$ 处相交，其余地方不相交。交点的数量受多项式最大次数的限制，本例中为 3。
有限域中的多项式与 Schwartz-Zippel 引理
Schwartz-Zippel 引理适用于有限域中的多项式（即所有计算都是对一个质数 $p$ 取模）。
多项式相等性测试
我们可以通过检查它们的所有系数是否相等来测试两个多项式是否相等，但这需要 $\mathcal{O}(d)$ 的时间，其中 $d$ 是多项式的次数。
如果我们能在一个随机点 $u$ 处评估多项式并在 $\mathcal{O}(1)$ 的时间内比较评估值，则会更快。
也就是说，在有限域 $\math...
- 学分: 0
- 分类: 密码学
- 标签: Schwartz-Zippel Lemma 零知识证明 多项式 有限域 Python Lagrange插值
本文参与登链社区写作激励计划 ，好文好收益，欢迎正在阅读的你也加入。
