多项式

多项式（polynomial）是由一个或多个项（terms）组成的代数表达式，通常以变量（如 $x$）和常数的幂次形式表示。每一项的形式是常数与变量的幂的乘积。一个标准的多项式通常写作：

$$P(x) = a_n x^n + a_{n-1} x^{n-1} + \cdots + a_1 x + a_0$$

其中：

• $a_n, a_{n-1}, \dots, a_1, a_0$ 是常数，称为系数（coefficient），
• $x$ 是变量，
• $n$ 是多项式的最高次数，称为该多项式的次数（degree）。

多项式的基本特征

1. 次数：多项式中变量 $x$ 的最高幂次称为该多项式的次数。例如，$3x^4 + 2x^3 - x + 5$ 是一个次数为 4 的多项式。
2. 系数：多项式中各个项前的常数叫做系数，系数可以是任何实数或复数。
3. 项数：多项式中项的个数，像 $3x^4 + 2x^3 - x + 5$ 有 4 项。

多项式的分类

• 常数多项式：如果多项式的次数为 0（即没有 $x$ 的项），它是一个常数，例如 $P(x) = 7$。
• 线性多项式：次数为 1 的多项式，例如 $P(x) = 2x + 3$。
• 二次多项式：次数为 2 的多项式，例如 $P(x) = x^2 - 4x + 4$。
• 三次多项式：次数为 3 的多项式，例如 $P(x) = x^3 + 2x^2 - 3x + 1$。

多项式承诺

多项式承诺（Polynomial Commitment）是一种加密学技术，它允许用户在不泄露多项式的具体形式或系数的情况下，证明某个给定的多项式在某些点上的值。这类技术通常用于零知识证明（ZKP）和其他密码学协议中，用于确保多项式的正确性而不需要直接暴露其内容。

Pedersen

Pedersen 多项式承诺（Pedersen Commitment for Polynomials）是密码学中的一种承诺方案，用于生成对多项式的承诺，并且该承诺具有零知识证明的性质。Pedersen 承诺本身是基于离散对数难题，具有绑定性和隐藏性，而多项式承诺则扩展了这一概念，使其适用于多项式的承诺。

1. Pedersen承诺的基础回顾

Pedersen承诺的数学基础在于离散对数问题。具体地，假设我们有一个群 $G$，其中生成元为 $g$ 和 $h$，并且 $g$ 和 $h$ 是彼此独立的。Pedersen承诺用于承诺某个值 $v$，其形式为：

$$C(v) = g^v h^r$$

其中，$v$ 是我们希望承诺的值，$r$ 是一个随机值（通常称为“开销”），该值用于确保承诺的隐私性。

2. 多项式承诺的扩展

Pedersen 承诺扩展到多项式时，我们需要承诺一个多项式的系数。假设我们有一个多项式 $P(x) = a_0 + a_1 x + a_2 x^2 + \dots + a_n x^n$，我们希望承诺该多项式的所有系数。

3. 基本的Pedersen多项式承诺方案

假设我们有一个多项式 $P(x) = \sum_{i=0}^{n} a_i x^i$，我们可以通过以下步骤进行承诺：

3.1 选择承诺参数

我们选择一个生成元 $g$ 和一个独立的生成元 $h$，以及一个群 $G$（通常是一个椭圆曲线群）。

3.2 计算多项式承诺

我们为每个系数 $a_i$ 计算一个单独的 Pedersen 承诺。具体来说，对于每个系数 $a_i$，我们选择一个随机数 $r_i$，并且承诺为：

$$C(a_i) = g^{a_i} h^{r_i}$$

然后，将所有的承诺结合起来，形成一个多项式的承诺：

$$C(P(x)) = \prod_{i=0}^{n} C(a_i)^{x^i} = \prod_{i=0}^{n} (g^{a_i} h^{r_i})^{x^i}$$

这意味着：

$$C(P(x)) = \prod_{i=0}^{n} g^{a_i x^i} h^{r_i x^i}$$

3.3 隐藏性和绑定性

• 隐藏性：由于 $r_i$ 是随机选择的，承诺 $C(P(x))$ 不透露任何关于 $P(x)$ 中系数的信息，只有在知道 $r_i$ 时才能揭示具体系数。
• 绑定性：一旦承诺计算出 $C(P(x))$，除非知道 $r_i$ 和 $a_i$，否则无法更改多项式的系数或伪造承诺。