3 非交互式论证的构造 (Constructions of non-interactive arguments)

我们将构造一个基于配对的 NIZK 论证，用于二次算术程序，其中证明只包含 3 个群元素。 我们分两步给出构造：首先我们为二次算术程序构造一个 NILP，然后我们观察到它也是一个分裂 NILP，并使用我们之前提出的编译技术将其转换为基于配对的 NIZK 论证。

3.1 用于二次算术程序的非交互式线性证明 (Non-interactive linear proofs for quadratic arithmetic programs)

我们现在将为一个输出以下形式的关系的二次算术程序生成器构造一个 NILP:

R=(F,aux,l,{ui(X),vi(X),wi(X)}i=0m,t(X)). \mathcal{R} = (\mathbb{F}, \text{aux}, l, \{u_i(X), v_i(X), w_i(X)\}_{i=0}^{m}, t(X)). R=(F,aux,l,{ui​(X),vi​(X),wi​(X)}i=0m​,t(X)).

该关系定义了一个由陈述 $(a_1,...,a_l)\in {\mathbb{F}}^l$ 和证据 $(a_{l+1},...,a_m)\in {\mathbb{F}}^{m-l}$ 组成的语言，使得对于 $a_0=1$，有

$$\sum _{i=0}^m{a}_i{u}_i(X)\cdot \sum _{i=0}^m{a}_i{v}_i(X)=\sum _{i=0}^m{a}_i{w}_i(X)+h(X)t(X),$$

对于某个 $n-2$ 阶商多项式 $h(X)$，其中 $n$ 是 $t(X)$ 的阶。

• ($\sigma$, $\tau$) ← Setup($\mathcal{R}$): 选择 $\alpha ,\beta ,\gamma ,\delta ,x\leftarrow {\mathbb{F}}^{\ast }$。 设置 $\tau =(\alpha ,\beta ,\gamma ,\delta ,x)$ 并且

σ=(α,β,γ,δ,{xi}i=0n−1,{βui(x)+αvi(x)+wi(x)γ}i=0l,{βui(x)+αvi(x)+wi(x)δ}i=l+1m,{xit(x)δ}i=0n−2). \sigma = \left( \alpha, \beta, \gamma, \delta, \{x^i\}_{i=0}^{n-1}, \left\{ \frac{\beta u_i(x) + \alpha v_i(x) + w_i(x)}{\gamma} \right\}_{i=0}^{l}, \left\{ \frac{\beta u_i(x) + \alpha v_i(x) + w_i(x)}{\delta} \right\}_{i=l+1}^{m}, \left\{ \frac{x^i t(x)}{\delta} \right\}_{i=0}^{n-2} \right). σ=(α,β,γ,δ,{xi}i=0n−1​,{γβui​(x)+αvi​(x)+wi​(x)​}i=0l​,{δβui​(x)+αvi​(x)+wi​(x)​}i=l+1m​,{δxit(x)​}i=0n−2​).

• $\pi$ ← Prove($\mathcal{R}$, $\sigma$, $a_1,...,a_m$): 选择 $r,s\leftarrow \mathbb{F}$ 并且计算一个 $3\times (m+2n+4)$ 矩阵 $\Pi$ 使得 $\pi =\Pi \sigma =(A,B,C)$，其中

$$A=\alpha +\sum _{i=0}^m{a}_i{u}_i(x)+r\delta$$

$$B=\beta +\sum _{i=0}^m{a}_i{v}_i(x)+s\delta$$

$$C=\frac{{\sum }_{i=l+1}^m{a}_i(\beta u_i(x)+\alpha v_i(x)+w_i(x))}{\delta }+\frac{h(x)t(x)}{\delta }+As+rB-rs\delta .$$

• 0/1 ← Vfy($\mathcal{R}$, $\sigma$, $a_1,...,a_l$): 计算一个二次多元多项式 $t$，使得 $t(\sigma ,\pi )=0$ 对应于测试

$$A\cdot B=\alpha \cdot \beta +\sum _{i=0}^l{a}_i\frac{(\beta u_i(x)+\alpha v_i(x)+w_i(x))}{\gamma }\cdot \gamma +C\cdot \delta .$$

如果测试通过则接受证明。

• $\pi$ ← Sim($\mathcal{R}$, $\tau$, $a_1,...,a_l$): 选择 $A,B\leftarrow \mathbb{F}$ 并且计算

$$C=\frac{AB-\alpha \beta -{\sum }_{i=0}^l{a}_i(\beta u_i(x)+\alpha v_i(x)+w_i(x))}{\delta }.$$

返回 $\pi =(A,B,C)$。

在正式证明这是一个 NILP 之前，让我们给出关于不同组件的一些直觉。 $\alpha$ 和 $\beta$ 的作用是确保 $A$、 $B$ 和 $C$ 在 $a_0,...,a_m$ 的选择中彼此一致。 验证方程中的乘积 $A\cdot B$ 保证 $A$ 和 $B$ 涉及非平凡的 $\alpha$ 和 $\beta$ 分量。 这意味着乘积 $A\cdot B$ 涉及 $\alpha$ 和 $\beta$ 的线性依赖性，我们稍后将证明这种线性依赖性只能通过具有一致的 $a_0,...,a_m$ 的 $C$ 来平衡，在所有三个变量 $A$、 $B$ 和 $C$ 中。 $\gamma$ 和 $\delta$ 的作用是通过分别用 $\gamma$ 和 $\delta$ 分割左边的因子，使验证方程的后两个乘积与第一个乘积无关。 这可以防止验证方程中不同乘积中预期用于不同目的的元素的混合和匹配。 最后，我们使用 $r$ 和 $s$ 来随机化证明以获得零知识。

密码学概念解释：

• 商多项式 (Quotient Polynomial): 在多项式除法中，商多项式是除法的结果。 在这里，$h(X)$ 是多项式除法的结果，其中算术电路的约束多项式被目标多项式 $t(X)$ 除。

• 随机化 (Randomization): 在密码学中，随机化是指在算法中引入随机性。 随机化可以用于提高算法的安全性，防止敌手利用确定性模式。 在这里，随机数 $r$ 和 $s$ 用于随机化证明，以实现零知识性。