2.4 线性非交互式证明 (Linear non-interactive proofs)

Bitansky 等人 [BCI⁺13] 给出了对近期 SNARK 构造的信息论基础的有用表征，他们称之为 2-move 代数输入-不经意的线性交互式证明。 为了阐明与我们在 2.2 节中定义的非交互式论证的联系，我们将把这个概念重命名为非交互式线性证明 (non-interactive linear proofs, NILP)。 NILP 是相对于关系生成器 $\mathcal{R}$ 定义的，我们假设关系指定了一个有限域 $\mathbb{F}$，并且工作方式如下。

• ($\sigma$, $\tau$) ← Setup($\mathcal{R}$): Setup 是一个概率多项式时间算法，它返回向量 $\sigma \in {\mathbb{F}}^m$ 和 $\tau \in {\mathbb{F}}^n$。 为了符号简洁，我们假设 $\sigma$ 总是包含 1 作为一个条目，这样在 $\sigma$ 的仿射和线性函数之间没有区别。

• $\pi$ ← Prove($\mathcal{R}$, $\sigma$, $\varphi$, $w$): Prover 分两个阶段操作：

  • 首先，它运行 $\Pi$ ← ProofMatrix($\mathcal{R}$, $\varphi$, $w$)，其中 ProofMatrix 是一个概率多项式时间算法，它生成一个矩阵 $\Pi \in {\mathbb{F}}^{k\times m}$。
  • 然后它计算证明为 $\pi =\Pi \sigma$。

• 0/1 ← Vfy($\mathcal{R}$, $\sigma$, $\varphi$, $\pi$): Verifier 分两个阶段运行：

  • 首先，它运行一个确定性的多项式时间算法 $t$ ← Test($\mathcal{R}$, $\varphi$)，以获得一个算术电路 $t:{\mathbb{F}}^{m+k}\to {\mathbb{F}}^{\eta }$，对应于计算总阶数为 $d$ 的多元多项式向量。
  • 然后它接受证明当且仅当 $t(\sigma ,\pi )=0$。

度数 $d$ 和维度 $\mu ,m,n,k,\eta$ 可能是安全参数 $\lambda$ 中的常量或多项式。

定义 3 (线性非交互式证明)。 元组 (Setup, Prove, Vfy) 是 $\mathcal{R}$ 的一个线性非交互式证明 (linear non-interactive proof)，如果它具有完美完备性 (perfect completeness) 和针对仿射 Prover 策略的统计知识可靠性 (statistical knowledge soundness against affine prover strategies)，定义如下。

针对仿射 Prover 策略的统计知识可靠性 (Statistical Knowledge Soundness against Affine Prover Strategies)

如果可以从一个成功的证明矩阵 $\Pi$ 中提取一个证据，则 NILP 具有针对仿射 Prover 策略的知识可靠性 (knowledge soundness against affine prover strategies)。 更准确地说，存在一个多项式时间提取器 (extractor) $\mathcal{X}$，使得对于所有敌手 $\mathcal{A}$：

$$\mathrm{Pr}\left[(R,z)\leftarrow \mathcal{R}(1^{\lambda });(\sigma ,\tau )\leftarrow \text{Setup}(\mathcal{R});(\varphi ,\Pi )\leftarrow \mathcal{A}(R,z);w\leftarrow \mathcal{X}(R,\varphi ,\Pi ):\Pi \in {\mathbb{F}}^{k\times m}\wedge \text{Vfy}(\mathcal{R},\sigma ,\varphi ,\Pi \sigma )=0\wedge (\varphi ,w)\notin R\right]\approx 0.$$

第 2.2 节中的零知识概念也适用于 NILP，并且对应于 2-move LIP 的诚实验证者零知识。 另一个潜在的扩展是将公共参考字符串 $\sigma$ 分成两个部分，${\sigma }_P$ 由 Prover 使用，${\sigma }_V$ 由 Verifier 使用，从而得到指定验证者的 NILP。

---

密码学概念解释：

• 线性非交互式证明 (Linear Non-interactive Proof, NILP): 是一种特殊的非交互式证明，Prover 通过对公共参数（CRS）进行线性运算来生成证明。 这种结构在某些情况下可以提高效率。

• 2-move 代数输入-不经意的线性交互式证明: 这里的 “2-move” 指的是证明协议需要 Prover 和 Verifier 之间进行两轮交互。 “代数” 指的是协议基于代数运算。 “输入-不经意” 指的是 Prover 的输入对 Verifier 来说是隐藏的。

• 仿射函数 (Affine Function): 一个线性函数加上一个常数项。 在这里，仿射 Prover 策略指的是 Prover 使用仿射函数来生成证明。

• 证明矩阵 (Proof Matrix): Prover 使用的一个矩阵，用于将公共参数转换为证明。

• 统计知识可靠性 (Statistical Knowledge Soundness): 一种比计算知识可靠性更强的可靠性概念。 统计知识可靠性意味着即使攻击者拥有无限的计算能力，它也无法在不知道证据的情况下生成有效的证明。

• 提取器 (Extractor): 一种算法，可以从成功生成证明的 Prover 中提取出证据。

• 诚实验证者零知识 (Honest-Verifier Zero-Knowledge): 一种比完美零知识性弱的零知识概念。 诚实验证者零知识意味着，只有当 Verifier 遵循协议时，Prover 才不会泄露任何关于证据的信息。

2.5 来自线性非交互式证明的非交互式论证 (Non-interactive arguments from linear non-interactive proofs)

NILP 是有用的，因为它们可以被编译成公开可验证的非交互式论证，使用配对和指定验证者的非交互式论证，以及 Paillier 加密变体 [BCI⁺13]。 如果我们在配对设置中工作，直觉是具有 Verifier 度 $d=2$ 的 NILP 可以被执行“在编码离散对数中”。 公共参考字符串包含字段元素的编码。 Prover 计算以公共参考字符串中的群元素为系数的群元素的线性组合来计算证明。 Verifier 通过验证多个配对乘积方程 (由将配对结果相乘形成的方程) 来检查论证，这对应于检查编码字段元素中的二次方程。 我们现在将正式化这种方法。

当使用 Type III 配对时，执行 NILP 需要我们为每个元素指定进行运算的组。

我们可以定义一个分裂 NILP (split NILP)，这是一个 NILP，其中公共参考字符串可以分成两个部分 $\sigma =({\sigma }_1,{\sigma }_2)$，Prover 的证明可以分成两个部分 $\pi =({\pi }_1,{\pi }_2)$。 证明的每个部分都是根据公共参考字符串的相应部分计算的。 最后，在验证证明时，我们希望 Verifier 的测试成为一个二次方程，其中每个变量的度为 1。 编写出来，一个分裂 NILP 是以下形式的 NILP：

• ($\sigma$, $\tau$) ← Setup($\mathcal{R}$): Setup 算法生成向量 $\sigma =({\sigma }_1,{\sigma }_2)\in {\mathbb{F}}^{m_1}\times {\mathbb{F}}^{m_2}$ 和 $\tau \in {\mathbb{F}}^n$。 为了符号简洁，我们假设 ${\sigma }_1$ 和 ${\sigma }_2$ 都包含 1 作为条目，这样在 $\sigma$ 的仿射和线性函数之间没有区别。

• $\pi$ ← Prove($\mathcal{R}$, $\sigma$, $\varphi$, $w$): Prover 分两个阶段操作：

  • 首先，它运行 $\Pi$ ← ProofMatrix($\mathcal{R}$, $\varphi$, $w$)，其中我们要求 ProofMatrix 生成一个形式为 $\Pi =\left(\begin{array}{cc}{\Pi }_1& 0\\ 0& {\Pi }_2\end{array}\right)$ 的矩阵，其中 ${\Pi }_1\in {\mathbb{F}}^{k_1\times m_1}$ 且 ${\Pi }_2\in {\mathbb{F}}^{k_2\times m_2}$。
  • 然后它计算 ${\pi }_1={\Pi }_1{\sigma }_1$ 和 ${\pi }_2={\Pi }_2{\sigma }_2$，并返回 $\pi =({\pi }_1,{\pi }_2)$。

• 0/1 ← Vfy($\mathcal{R}$, $\sigma$, $\varphi$, $\pi$): Verifier 分两个阶段运行：

  • 首先，它运行 $t$ ← Test($\mathcal{R}$, $\varphi$) 以获得一个算术电路 $t:{\mathbb{F}}^{m_1+k_1+m_2+k_2}\to {\mathbb{F}}^{\eta }$，对应于矩阵 $T_1,...,T_{\eta }\in {\mathbb{F}}^{(m_1+k_1)\times (m_2+k_2)}$。
  • 然后它接受证明当且仅当对于所有矩阵 $T_1,...,T_{\eta }$，有 $\left(\begin{array}{c}{\sigma }_1\\ {\pi }_1\end{array}\right)\cdot T_i\cdot \left(\begin{array}{c}{\sigma }_2\\ {\pi }_2\end{array}\right)=0$。

直观地说，在编译分裂 NILP 之后，我们想要论证，使用通用群操作的作弊 Prover 不能偏离 NILP。 然而，当 Prover 看到公共参考字符串时，她可能会从中学习有用的信息，并以依赖于它的方式选择她的矩阵 $\Pi$。 为了对抗这种类型的敌手，我们将定义一个无泄露公共参考字符串 (disclosure-free common reference string)，Prover 不会获得可以帮助她选择一个特殊矩阵 $\Pi$ 的有用信息。

定义 4 (无泄露 NILP)。 我们说一个分裂 NILP 是无泄露的 (disclosure-free)，如果对于所有敌手 $\mathcal{A}$：

$$\mathrm{Pr}\left[(R,z)\leftarrow \mathcal{R}(1^{\lambda });T\leftarrow \mathcal{A}(R,z);({\sigma }_1,{\sigma }_2,\tau ),({\sigma }_1^{\prime },{\sigma }_2^{\prime },{\tau }^{\prime })\leftarrow \text{Setup}(\mathcal{R}):{\sigma }_1\cdot T{\sigma }_2=0\text{ if and only if }{\sigma }_1^{\prime }\cdot T{\sigma }_2^{\prime }=0\right]\approx 1.$$

解释无泄露公共参考字符串的方式是，任何敌手在 ${\sigma }_1,{\sigma }_2$ 上运行的测试的结果可以被预测，通过在独立生成的 ${\sigma }_1^{\prime },{\sigma }_2^{\prime }$ 上运行它。

我们现在准备好描述一个编译器，它使用一个分裂 NILP (Setup, Prove, Vfy, Sim) 和无泄露的公共参考字符串来给我们一个基于配对的非交互式论证 (Setup’, Prove’, Vfy’, Sim’)。

• ($\sigma$, $\tau$) ← Setup’($\mathcal{R}$): 运行 (${\sigma }_1$, ${\sigma }_2$, $\tau$) ← Setup($\mathcal{R}$)。 返回 $\sigma =([{\sigma }_1{]}_1,[{\sigma }_2{]}_2)$ 和 $\tau =\tau$。

• $\pi$ ← Prove’($\mathcal{R}$, $\sigma$, $\varphi$, $w$): 生成 $({\Pi }_1,{\Pi }_2)$ ← ProofMatrix($\mathcal{R}$, $\varphi$, $w$) 并返回 $\pi =([{\pi }_1{]}_1,[{\pi }_2{]}_2)$，其中 $[{\pi }_1{]}_1={\Pi }_1[{\sigma }_1{]}_1$ 且 $[{\pi }_2{]}_2={\Pi }_2[{\sigma }_2{]}_2$。

• 0/1 ← Vfy’($\mathcal{R}$, $\sigma$, $\varphi$, $\pi$): 生成算术电路 $(T_1,...,T_{\eta })$ ← Test($\mathcal{R}$, $\varphi$)。 解析 $\pi =([{\pi }_1{]}_1,[{\pi }_2{]}_2)\in {\mathbb{G}}_1^{k_1}\times {\mathbb{G}}_2^{k_2}$。 接受证明当且仅当对于所有 $T_1,...,T_{\eta }$，有 $\left(\begin{array}{c}[{\sigma }_1{]}_1\\ [{\pi }_1{]}_1\end{array}\right)\cdot T_i\cdot \left(\begin{array}{c}[{\sigma }_2{]}_2\\ [{\pi }_2{]}_2\end{array}\right)=[0{]}_T$。

• $\pi$ ← Sim’($\mathcal{R}$, $\tau$, $\varphi$): 模拟 (${\pi }_1$, ${\pi }_2$) ← Sim($\mathcal{R}$, $\tau$, $\varphi$) 并返回 $\pi =([{\pi }_1{]}_1,[{\pi }_2{]}_2)$。

---

密码学概念解释：

• 分裂 NILP (Split NILP): 这种 NILP 的变体将公共参考字符串和证明分成两部分。 这种分裂结构便于在基于配对的密码学方案中实现。

• 无泄露公共参考字符串 (Disclosure-Free Common Reference String): 这种 CRS 不会向 Prover 泄露任何关于证据的信息。 形式上，这意味着即使 Prover 知道 CRS，它也无法利用这些信息来生成一个虚假的证明。

• 编译器 (Compiler): 在密码学中，编译器指的是将一个密码学方案转换为另一个密码学方案的算法。 在这里，编译器将分裂 NILP 转换为基于配对的非交互式论证。

• 基于配对的密码学 (Pairing-Based Cryptography): 一种利用双线性配对来构建密码学方案的方法。 基于配对的密码学可以实现许多有趣的功能，例如基于身份的加密、属性加密和简洁证明。

• 引理 1. 上述协议是一个具有完美完备性和针对通用敌手的统计知识可靠性的非交互式论证，该通用敌手只进行多项式数量的通用群操作。 如果底层分裂 NILP 是完美零知识的，则它是完美零知识的。

证明。 完美完备性源于 NILP 的完美完备性，并且事实上它是一个分裂 NILP，这使得敌手可以使用相关群 ${\mathbb{G}}_1$ 和 ${\mathbb{G}}_2$ 中的通用群操作来计算 $[{\pi }_1{]}_1$ 和 $[{\pi }_2{]}_2$ 的两个部分。 完美零知识性源于 NILP 的完美零知识性。

仍然需要论证针对通用敌手的统计可靠性。 一个通用敌手可以使用通用群操作来乘以 ${\mathbb{G}}_1$、${\mathbb{G}}_2$ 和 ${\mathbb{G}}_T$ 中的元素，测试群成员资格，评估配对，以及测试元素是否相等。

我们首先论证，无泄露性意味着关于公共参考字符串的非平凡信息的学习概率可以忽略不计。 每当敌手测试一个使用通用群操作计算的元素是否为 0 时，它可以被写成一个配对乘积相等性测试的形式 $[{\sigma }_1{]}_1\cdot T[{\sigma }_2{]}_2=[0{]}_T$，其中矩阵 $T$ 可以从敌手进行的通用群操作查询中推导出来。 我们可以不进行这些查询，而是运行一个修改后的敌手，该敌手选择一个备选的公共参考字符串 $({\sigma }_1^{\prime },{\sigma }_2^{\prime },{\tau }^{\prime })$，并通过测试 ${\sigma }_1^{\prime }\cdot T{\sigma }_2^{\prime }=0$ 自己回答查询。 通过无泄露性，以压倒性的概率，这些方式做出的答案与敌手在真实公共参考字符串上看到的相同，所以我们可以从现在开始假设通用敌手不对涉及公共参考字符串的元素进行任何零测试。

一个不对公共参考字符串进行任何零测试并且只使用通用群操作的敌手，等价于一个独立地选择矩阵 ${\Pi }_1$ 和 ${\Pi }_2$，然后计算证明为 $[{\pi }_1{]}_1={\Pi }_1[{\sigma }_1{]}_1$ 和 $[{\pi }_2{]}_2={\Pi }_2[{\sigma }_2{]}_2$ 的敌手。 采用离散对数，这对应于运行一个分裂 NILP 知识可靠性敌手来获得矩阵 ${\Pi }_1,{\Pi }_2$ 和证明 ${\pi }_1={\Pi }_1{\sigma }_1$, ${\pi }_2={\Pi }_2{\sigma }_2$。

采用验证方程的离散对数，我们看到如果敌手成功找到 $\varphi$ 和一个有效的证明 ${\pi }_1,{\pi }_2$，这对应于找到 $\varphi$ 和 ${\Pi }_1,{\Pi }_2$ 使得对于测试矩阵 $T_1,...,T_{\eta }\leftarrow \text{Test}(\mathcal{R},\varphi )$，有

$$\left(\begin{array}{c}{\sigma }_1\\ {\Pi }_1{\sigma }_1\end{array}\right)\cdot T_i\cdot \left(\begin{array}{c}{\sigma }_2\\ {\Pi }_2{\sigma }_2\end{array}\right)=0.$$

通过分裂 NILP 的统计可靠性，这种情况发生的概率可以忽略不计，除非知道 ${\Pi }_1,{\Pi }_2$ 使得可以提取一个证据 $w$，使得 $(\varphi ,w)\in R$。

$\Pi$ 的优势在于抵御密码分析，即使敌手发现了一个 ${\mathbb{G}}_1$ 和 ${\mathbb{G}}_2$ 之间的高效可计算的同构，甚至可以将 $g$ 映射到 $h$，我们仍然会在通用群模型中具有安全性。 另一个优点是，该构造也适用于对称双线性群，只有很小的改动。

引理 1 的证明也适用于我们使用一个只具有针对分裂仿射敌手的可靠性的分裂 NILP 的情况，该分裂仿射敌手被限制为输出一个矩阵 $\Pi =\left(\begin{array}{cc}{\Pi }_1& 0\\ 0& {\Pi }_2\end{array}\right)$。

然而，我们稍后构建的分裂 NILP 实际上将可以抵御任何 $\Pi$ 的选择。