GS 零知识证明（Groth–Sahai）

GS证明是 Groth 与 Sahai 提出的高效非交互式证明（NIZK）/见证不可区分证明（NIWI）框架，专门用于在双线性群环境中直接证明代数关系的成立。与将语句规约到电路可满足性再做证明的传统做法不同，GS证明能够“就地”处理群上的等式，从而显著降低证明规模与计算开销。由于它既能达到零知识性（不泄露见证），又能实现见证不可区分（在多见证时不暴露哪一个被使用），GS证明已被广泛用于基于双线性群的现代密码学协议中（如基于身份/属性的加密、群签名等）。

GS证明能做什么

GS证明可以在不泄露秘密信息的前提下，证明多种与双线性群有关的代数语句成立，例如：
可以使用它证明某群元素是一个Pederson承诺。也就是说：给定群元素 $C\in G$ 与公共基 $g,h$，它可以证明 存在消息 $m$ 与随机数 $r$ 使得 $C=g^m h^r$ 成立，而不泄露 $m,r$。
也可以用它证明两个群元素是ElGamal加密的密文。即给定密文 $c=(c_1,c_2)=(g^r,\; m\cdot h^r)$ 和 公共密钥 $pk=h$，GS证明可证明存在 $m,r$ 使得 $c$ 的确是 $m$ 的 ElGamal 加密”，而不泄露 $m$。
当然，它也可以是用它证明给定的群元素向量/结构是一份有效签名，同时隐藏签名者身份或签名见证等等。这是因为，这些语句在GS框架中被统一表述为双线性群上的方程（如配对乘积方程、多标量相乘方程、模数上的二次方程等），因此可以统一而高效地给出非交互式证明。

一般的，该证明可以在不暴露 variables 的情况下证明它们满足下面四个等式： Variables:

$$X_1, \ldots, X_m \in G_1,\quad Y_1, \ldots, Y_n \in G_2,\quad x_1, \ldots, x_{m'} , y_1, \ldots, y_{n'} \in \mathbb{Z}_n$$

Pairing product equation:

$$\prod_{i=1}^{n} e(A_i, Y_i) \cdot \prod_{i=1}^{m} e(X_i, B_i) \cdot \prod_{i=1}^{m} \prod_{j=1}^{n} e(X_i, Y_j)^{\gamma_{ij}} = t_T \tag{1}$$

for constants $A_i \in G_1, B_i \in G_2, t_T \in G_T, \gamma_{ij} \in \mathbb{Z}_n$. Multi-scalar multiplication equation in $G_1$:

$$\sum_{i=1}^{n'} y_i A_i + \sum_{i=1}^{m} b_i X_i + \sum_{i=1}^{m} \sum_{j=1}^{n'} \gamma_{ij} y_j X_i = \mathcal{T}_1 \tag{2}$$

for constants $A_i, T_1 \in G_1$ and $b_i, \gamma_{ij} \in \mathbb{Z}_n$. Multi-scalar multiplication equation in $G_2$:

$$\sum_{i=1}^{n} a_i Y_i + \sum_{i=1}^{m'} x_i B_i + \sum_{i=1}^{m'} \sum_{j=1}^{n} \gamma_{ij} x_i Y_j = \mathcal{T}_2 \tag{3}$$

for constants $B_i, T_2 \in G_2$ and $a_i, \gamma_{ij} \in \mathbb{Z}_n$. Quadratic equation in $\mathbb{Z}_n$:

$$\sum_{i=1}^{n'} a_i y_i + \sum_{i=1}^{m'} x_i b_i + \sum_{i=1}^{m'} \sum_{j=1}^{n'} \gamma_{ij} x_i y_j \equiv t \pmod{n} \tag{4}$$

for constants $a_i, b_i, \gamma_{ij}, t \in \mathbb{Z}_n$.

说明：

为了说明GS证明系统的通用性，这里简单举 2 个常见的例子。

Pederson承诺：
使用GS证明，可以证明某个元素是一个合法消息 $m$ 的 Pederson 承诺，并且不暴露 $m$ 的信息。具体来说，只需要令公式 $(2)$ 中的 $b_i,\gamma_{ij}$ 全为 0，且 $n'=2$ 即可得到:

$$\sum_{i=1}^{n'} y_i\cdot A_i = \mathcal{T}_1 = g^m\cdot h^r = C; \ [\ y_1=m , y_2 = r , A_1 = g, A_2 = h, \mathcal{T}_1 = C \ ]$$

容易看出，上述式子是 GS证明 的一个特殊形式，证明了 $C=g^mh^r$ 成立，并且不暴露 $m$ 和 $r$ 。也就是证明了 $C$ 是某个消息的 Pederson 承诺。 相似的，通过合适的设置参数值，使用 $(3)$ 式也可以证明 $G_2$ 上的某元素是某个消息的 Pederson 承诺。

ElGamal加密：
我们还可以使用 GS 证明，声称给定的两个群元素 $(c_1, c_2)$ 是某个消息 $m$ 的合法 ElGamal 密文。即证明陈述 \{\ \exists m,r: (c_1, c_2) = (g^r,\; m\cdot y^r)\ \\} 为真。

具体来说，只需要令公式 $(2)$ 中的 $b_i,\gamma_{ij}$ 全为 0，分别取 $n'=1$ 与 $n'=2$，即可得到：

$$\sum_{i=1}^{n'} y_i\cdot A_i = \mathcal{T}_1 = g^r = c_1; \quad [\ y_1=r,\ A_1=g,\ \mathcal{T}_1=c_1\ ]$$

$$\sum_{i=1}^{n'} y_i\cdot A_i = \mathcal{T}_1 = m\cdot 1 + y^r = c_2; \quad [\ y_1=m,\ y_2=r,\ A_1=1,\ A_2=y,\ \mathcal{T}_1=c_2\ ]$$

容易看出上式是 GS证明 的一个特殊形式，证明了 $(c_1, c_2) = (g^r,\; m\cdot y^r)$ 成立，并且不暴露 $m$ 和 $r$。也就是证明了 $(c_1, c_2)$ 是某个消息 $m$ 的合法 ElGamal 密文。其中$A_1=1$ 是群的生成元。

GS证明如何构造

一、记号说明

为了能够更好的理解论文中的内容，我们首先需要介绍一些必要的预备知识，并且为了便于理解，在预备知识的介绍中，我们还加上了一些例子。具体如下：

---

1.1 环、模及双线性映射简介

• 数论相关概念：环（Ring）
  一个有限交换环 $(\mathcal{R}, +, \cdot, 0, 1)$ 是一个带加法和乘法的代数结构，其中：

  1. $(\mathcal{R}, +, 0)$ 构成一个交换群（类似整数的加法）；
  2. $(\mathcal{R}, \cdot, 1)$ 构成一个幺半群（类似整数的乘法，有乘法单位元 $1$）；
  3. 乘法对加法满足分配律：$r(s+t) = rs + rt$，$(r+s)t = rt + st$。

• 数论相关概念：模（Module）
  模可以看作是 向量空间的推广，但标量不一定来自域，而是来自环 $\mathcal{R}$。 一个 $\mathcal{R}$-模 $A$ 表示一个阿贝尔群 $(A, +, 0)$，配合一个 标量乘法 $ \mathcal{R} \times A \to A : \ (r, x) \mapsto rx $ 满足以下四条公理：

  $$(r+s)x = rx + sx, \quad r(x+y) = rx + ry, \quad r(sx) = (rs)x, \quad 1\cdot x = x \tag{5}$$

  前两条保证加法的分配律；第三条保证标量乘法的结合性；第四条保证单位元的作用。
  注意：

  • 模 $A$ 是一个阿贝尔群 $(A, +, 0)$，这个群中的二元关系[+]并不一定是环 $\mathcal{R}$ 中的 二元关系[+]，而模中引入的标量乘法<$\cdot$>也不一定是环 $\mathcal{R}$ 中的二元关系[$\cdot$]。听起来有点抽象，我们将在后面通过举例子的方式来辅助理解。
  • 模可以与向量空间进行类比，在向量空间中，我们把实数作为标量，向量作为元素。向量与向量之间有自己的运算，标量也可以与向量相乘。
    在模中，标量来自一个更一般的环$\mathcal{R}$，模 $A$ 中的元素则可类比成向量空间中的向量，模中的元素自带一个二元运算[+]，且模中的元素可以与环中元素进行一个新的二元运算[$\cdot$]

  下面举几个例子说明一下什么是模，以及模中的二元关系和环中的区别。

  1. 整数模
     给定一个整数环$\mathcal{R}$（所有整数的集合，则 $A=\mathbb{Z}_n=\\{0,1,\cdots,n-1\\}$ 是一个 $\mathcal{R}\text{-}$模。

     • 模的加法[+]： 模 $A$ 的自带二元运算是加法[+]，定义为模 $n$ 的加法：
       $$(x,y) \mapsto (x+y) \bmod n, \quad \forall x,y \in A$$
       这个运算显然满足封闭性和结合律并存在单位元，显而易见的是：$A$ 中的每个元素都存在逆元，并且"加法"满足可交换性，因此是一个 模 $A$ 阿贝尔群。
     • 与环的标量乘法[$\cdot$]： 模 $A$ 还定义了一个来自环 $\mathcal{R}$ 的 标量乘法：
       $$a \cdot x = (a \cdot x) \bmod n, \quad \forall a \in \mathbb{Z},\ x \in \mathbb{Z}_n$$
       这个标量乘法显然满足 式$(5)$ 中的四个性质。通过这个例子我们可以看出，整数模中的加法运算和标量乘法运算和环 $\mathcal{R}$ 中的并不相同。【环中的加法和乘法都不是不带模的】

  2. 循环群作为模
     给定整数环 $\mathcal{R} = \mathbb{Z}_n$，则阶为 $n$ 的循环群 $ A = G = \langle g \rangle = \{ g^0, g^1, \dots, g^{n-1} \} $ 是 $\mathcal{R}$-模。

     • 模的加法[+]： 模 $A$ 的自带二元运算是群运算，记作加法[$\cdot$]：
       $$(x=g^a,y=g^b) \mapsto (x \cdot y = g^{a+b}) \ , \quad \forall x,y \in G$$
       其中[$\cdot$]表示群运算，该运算满足显然满足阿贝尔群的性质，因此 $(G,\cdot)$ 构成阿贝尔群。
     • 与环的标量乘法[$\cdot$]： 模 $A$ 中还定义了一个来自 $\mathbb{Z}_n$ 的标量乘法：
       $$a \cdot g := g^a, \quad a \in \mathbb{Z}_n,\ g \in G$$
       这个运算显然满足模的四个公理。可以看到：模 $G$ 的加法[$\cdot$]对应于指数的相加（群运算）。标量乘法则是环 $\mathbb{Z}_n$ 中的乘法作用在指数上。 因此，循环群作为 $\mathbb{Z}_n$-模时，模的加法和标量乘法与环中的运算保持兼容，但并不是相同的运算。

  3. 椭圆曲线群作为模（密码学中的常见情况）
     给定整数环 $\mathcal{R} = \mathbb{Z}_n$，则阶为 $n$ 的椭圆曲线循环群 $G=\langle P \rangle$ 是一个 $\mathcal{R}\text{-}$模。 其中标量乘法定义为：$k \cdot P = P + P + \cdots + P$ ($k$ 次)。椭圆曲线的运算定义这里不再赘述。

• 双线性映射及其实例化：
  给定三个有限的 $\mathcal{R}$-模 $A_1, A_2, A_T$，一个映射 $f : A_1 \times A_2 \to A_T$ 满足以下条件时，说它是双线性映射。即， 对任意 $x,x' \in A_1,\ y,y' \in A_2,\ r \in \mathcal{R}$：（对 $y$ 同理）。

  $$f(x+x', y) = f(x,y) + f(x',y), \quad f(rx, y) = r f(x,y)$$
  1. 一个典型例子的例子是密码学中的配对函数 $e : G_1 \times G_2 \to G_T$, 它通常基于椭圆曲线循环群构造，满足对任意 $X,X' \in G_1,\ Y,Y' \in G_2,\ r \in \mathbb{F}_q$，以下双线性性质成立：
     $$\begin{aligned} e(X+X', Y) &= e(X,Y)\cdot e(X',Y), \quad e(rX, Y) = e(X,Y)^r \\ e(X, Y+Y') &= e(X,Y)\cdot e(X,Y'), \quad e(X, rY) = e(X,Y)^r \end{aligned}$$
     使用这个配对函数 $e$ 来实例化双线性映射 $f$ 之后，可以据此构造出配对积方程 $(1)$ 用于证明，为了直观理解其他三个方程 $(2)(3)(4)$，我们给出 $f$ 对应的其他三种实例化方式。
  2. 另一种例子是 $G_1$ 上的标量乘法映射 $f: G_1 \times \mathbb{Z}_q \to G_1$，定义为 $f(X,r)=r \cdot X$，下面证明了它对 $X$ 与 $r$ 满足双线性性质，故 $f$ 可以实例化 $G_1$ 上的多标量乘法方程 $(2)$。
     
     $$\begin{aligned} f(X+X', y) &= f(X,y)+f(X',y), \quad f(rX, y) = r\cdot f(X,y) \\ f(X, y+y') &= f(X,y)+f(X,y'), \quad f(X, r y) = r\cdot f(X,y) \end{aligned}$$
  3. 对称地，$G_2$ 上的标量乘法映射取 $f:\mathbb{Z}_q \times G_2 \to G_2$，定义为 $f(x,Y)=x\cdot Y$。下面证明它对 $x$ 与 $Y$ 满足双线性性质，故 $f$ 可以实例化 $G_2$ 上的多标量乘法方程 $(3)$。
     
     $$\begin{aligned} f(x+x',Y) &= f(x,Y)+f(x',Y), \quad & f(r x,Y) &= r\cdot f(x,Y) \\ f(x,Y+Y') &= f(x,Y)+f(x,Y'), \quad & f(x,r Y) &= r\cdot f(x,Y) \end{aligned}$$
  4. 第三种是标量环上的乘法映射取 $f:\mathbb{Z}_q\times \mathbb{Z}_q\to \mathbb{Z}_q$，定义为 $f(x,y)=x\cdot y$。下面证明它对 $x$ 与 $y$ 满足双线性性质，故 $f$ 可以实例化标量域上的线性/二次约束方程 $(4)$。
  $$\begin{aligned} f(x+x',y) &= f(x,y)+f(x',y), \quad & f(r x,y) &= r\cdot f(x,y) \\ f(x,y+y') &= f(x,y)+f(x,y'), \quad & f(x,r y) &= r\cdot f(x,y) \end{aligned}$$

---

1.2 变量与记号定义

在前面的介绍中，我们可以发现GS证明要证明的四个方程 $(1-4)$ 写起来非常复杂，为了方便后面的叙述，我们引入一些符号，以简化方程的表达形式。

1. 定义证明中需对验证者隐藏的变量(也叫见证)为： $ x_1,\ldots,x_m \in A_1, \quad y_1,\ldots,y_n \in A_2 $

2. 双线性映射可形式定义为： $ \vec{x} \cdot \vec{y} = \sum_{i=1}^{n} f(x_i, y_i) = \prod_{i=1}^n e(x_i,y_i) $ 【这里的 $\vec{x},\vec{y}$ 维数都为 $n$】

3. 定义广义二次方程形式为，其中 $f(x,y)$ 表示一个映射：

$$\sum_{j=1}^n f(a_j, y_j) + \sum_{i=1}^m f(x_i, b_i) + \sum_{i=1}^m \sum_{j=1}^n \gamma_{ij} f(x_i, y_j) = t \tag{\#}$$

使用上面定义的符号，可以将上述方程简化为：

$$\underline{ \vec{a} \cdot \vec{y} + \vec{x} \cdot \vec{b} + \vec{x} \cdot \Gamma \vec{y} = t\ }; \quad \vec{a} \in A_1^n, \ \vec{b} \in A_2^m, \ \Gamma \in \text{Mat}_{m \times n}(\mathcal{R}), \ t \in A_T$$

上述广义二次方程可以作为 GS证明 的四个关系式的统一表达形式。在证明不同的关系时，令向量来自相应的 $\mathcal{R}\text{-}$模 并设置合适的映射 $f(x,y)$ 即可。我们在下面给出如何通过设置不同的$\mathcal{R}\text{-}$模 和映射 $f(x,y)$ 来将上述一般方程转换为 GS证明 中要证明的关系。

---

1.3 GS证明能证明的四个等式关系的简写

事实上，通过上述符号的定义我们可以看出：GS证明要证明的四个方程 $(1)(2)(3)(4)$都是广义二次方程 (\\#) 的特殊形式。通过对模、群和映射取不同取值，可以分别得到配对积方程，群 $G_1$ 或 $G_2$ 中的多标量乘法方程以及 $\mathbb{Z}_n$ 中的二次方程。通过使用上述引入的记号，可以将他们简写为：

1. 配对积方程
   定义 $\mathcal{R} = \mathbb{Z}_n,\ A_1 = G_1,\ A_2 = G_2,\ A_T = G_T,\ f(x,y) = e(x,y)$ 并重写方程为：

   $$(\vec{A} \cdot \vec{Y})(\vec{X} \cdot \vec{B})(\vec{X} \cdot \Gamma \vec{Y}) = t_T$$

2. 群 $G_1$ 中的多标量乘法
   定义 $ \mathcal{R} = \mathbb{Z}_n,\ A_1 = G_1,\ A_2 = \mathbb{Z}_n,\ A_T = G_1,\ f(X,y) = yX $ 并重写方程为：

   $$\vec{a} \cdot \vec{y} + \vec{x} \cdot \vec{b} + \vec{x} \cdot \Gamma \vec{y} = T_1$$

3. 群 $G_2$ 中的多标量乘法
   定义： $ \mathcal{R} = \mathbb{Z}_n,\ A_1 = \mathbb{Z}_n,\ A_2 = G_2,\ A_T = G_2,\ f(x,Y) = xY $ 并重写方程为：

   $$\vec{a} \cdot \vec{y} + \vec{x} \cdot \vec{b} + \vec{x} \cdot \Gamma \vec{y} = T_2$$

4. 群 $\mathbb{Z}_n$ 中的二次方程
   定义 $ \mathcal{R} = \mathbb{Z}_n,\ A_1 = \mathbb{Z}_n,\ A_2 = \mathbb{Z}_n,\ A_T = \mathbb{Z}_n,\ f(x,y) = xy \bmod n $ 并重写方程为：

   $$\vec{a} \cdot \vec{y} + \vec{x} \cdot \vec{b} + \vec{x} \cdot \Gamma \vec{y} \equiv t \pmod{n}$$

---

二、预备知识

2.1 非交互式证明系统简介
非交互式证明系统是指：证明者想要证明一个陈述 $st$ 为真，而整个证明过程中，证明者只发送一个证明 $\pi$ 给验证者，验证者通过该证明即可判断陈述 $st$ 是否为真，而无需进一步的交互。

1. 非交互式证明系统的基本算法
   一个通用的非交互式证明系统通常由以下算法组成：
   $\text{Setup}(1^\lambda) \to \mathsf{crs}$: 系统初始化算法，输入安全参数 $\lambda$，生成公共参考字符串（crs）。
   $\text{Prove}(\mathsf{crs}, st, w) \to \pi$: 证明算法，输入 crs、语句 $st$ 及其对应的证人 $w$，输出证明 $\pi$。 $\text{Verify}(\mathsf{crs}, st, \pi) \to \\{0,1\\}$: 验证算法，输入公共参考字符串 crs、要验证的语句 $st$ 和相应的证据 $\pi$，如果验证者接受语句 $st$ 的证据 $\pi$, 输出 1 ,否则输出 0 。
   注意：有些扩展模型中还会引入 Simulate（模拟算法）或 Extract（提取算法）以满足零知识性或知识可提取性等性质。这里不再详细介绍。

2. 常见的三种非交互式证明系统
   (1) 非交互式零知识证明:（NIZK, Non-Interactive Zero-Knowledge Proof）
   NIZK 要求证明者在单轮消息传递中，既能够让验证者确信给定语句的正确性，又不泄露关于见证的任何附加信息。其安全性最强，在匿名凭证、数字签名、可验证计算、区块链隐私保护等密码协议中被广泛应用。 一个 NIZK 系统需满足以下三个性质：

   • 完备性(Completeness)：拥有见证的证明者总能使用见证生成可被验证者接受的证明。
   • 可靠性(Soundness)：任何没有见证的多项式时间敌手无法生成被验证者接受的证明。
     通俗的讲，不使用见证生成的证明无法通过验证者的验证。换句话说，他的逆否命题是，能够通过验证者验证的证明是由某个见证生成的。这个逆否命题的表述在三、3 中会有用到。
   • 零知识性(Zero-Knowledge)：整个证明不会暴露见证的任何信息。通常意味着存在一个模拟器能在不知道见证的情况下生成与真实证明不可区分的模拟证明。

   (2) 非交互式证人不可区分证明:（NIWI, Non-Interactive Witness Indistinguishable Proof）
   NIWI 系统保证，当同一语句存在多个合法见证时，验证者无法区分证明者在生成证明时使用了哪一个见证。与 NIZK 相比，NIWI 对隐私的要求更弱，不保证零知识性，但仍能防止验证者从证明中推断出具体证人，从而保护一定程度的隐私和匿名性。一个 NIWI 系统需满足以下性质：

   • 完备性(Completeness): 同上；
   • 可靠性(Soundness): 同上。
   • 见证不可区分性(Witness Indistinguishability)：设陈述 $st$ 存在两个不同的合法见证 $w_0$ 和 $w_1$。对于任意PPT时间验证者 $\mathcal{V}$，当其与诚实证明者 $\mathcal{P}$ 交互时，若 $\mathcal{P}$ 分别基于 $w_0$ 与 $w_1$ 生成证明，则 $\mathcal{V}$ 在 PPT 时间内无法以不可忽略的优势判断证明所使用的见证是哪一个。

   (3)非交互式知识论证:（NIAoK, Non-Interactive Argument of Knowledge）
   本文不涉及这种证明，这里不再介绍，感兴趣的可以自己去查相关内容。

3. 举例帮助理解上述几个性质
   (1) 非交互式零知识证明例子：
   我们知道，Schnorr 签名实际上是一个 NIZK 证明，回忆一下 Schnorr 签名的过程如下：
   签名者选择一个随机数 $r \in \mathbb{Z}_q$ 并计算承诺值 $t = g^r \pmod{p}$ 和挑战值 $c = H(m , t)$；最后计算响应值 $s = r + c \cdot x \pmod{q}$ 并生成最终的签名 $\sigma = (t, s)$ 。
   验证者在验证时通过 $g^s = t \cdot y^{H(m,t)}$ 是否成立来决定是否接受签名。

   上述签名实际上是：签名者向验证者证明自己知道公钥 $y = g^x \pmod{p}$ 对应的私钥 $x$，而不泄露 $x$ 的任何信息。在该证明系统中，陈述 $st$ 为：存在一个 $x$ 使得 $y = g^x \pmod{p}$；见证为私钥 $x$；证明即为根据上述过程生成的 Schnorr 签名 $(c, s)$。

   • 完备性（Completeness）:
     如果证明者知道私钥 $x$，那么他按照 Schnorr 协议生成的签名总会被验证者接受。这是因为验证者通过检查 $g^s = t \cdot y^{H(m , t)}$ 是否成立来决定是否接受这个证明，而当 $y = g^x$ 成立时，该等式恒成立，因此验证必然成功。

   • 可靠性（Soundness）
     在随机预言机模型下，若存在任意多项式时间算法能以非忽略概率生成通过验证的 Schnorr 证明 $(t,s)$，则存在一个多项式时间提取器可以从该算法中提取见证 $x$。提取方法基于分叉引理：用相同的随机性两次运行证明生成算法，并在它两次查询 $H(m\parallel T)$ 时返回两个不同的挑战 $c \neq c'$。这样可以得到两份有效的证明 $g^s = t\cdot y^{c},\quad g^{s'} = t\cdot y^{c'}$ 我们将上述两个式子左右分别相除可得 $g^{s-s'} = g^{x(c-c')}$，进而计算出 $x = \frac{s-s'}{c-c'}^{-1} \pmod{q}$。随机预言机和分叉引理可以保证能提取上述 $x$ 的概率是不可忽略的【证明略】。 因此，能生成有效证明等价于知道见证 $x$，保证了协议的知识可靠性。 知识可靠性是一个比可靠性更强的安全属性。简而言之，可靠性保证没有见证的人无法生成假证明以通过验证，而知识可靠性确保能生成真证明的人一定知道见证，并且这个见证可以被提取器恢复出来。

   • 零知识性（Zero-Knowledge）
     该签名方案满足零知识性，即签名不会泄露私钥 $x$ 的任何信息。具体来说，存在一个模拟器在不知 $x$ 的情况下即可生成与真实签名分布完全相同的结果：模拟器随机选择 $c, s$，计算 $t = g^s \cdot y^{-c}$，得到签名 $(t, s)$。由于模拟生成的签名与真实签名在分布上不可区分，验证者无法判断签名是由模拟器生成还是由真实算法生成，因此无法从签名中提取任何关于 $x$ 的信息。若验证者能够从 $(t, s)$ 中获得 $x$，那么同样可以从模拟器生成的签名中获得 $x$，但模拟器本身并不掌握 $x$，这与假设矛盾，因此签名不可能泄露私钥。

   (2) 非交互式证人不可区分证明的例子:
   我们知道，Schnorr 签名的 OR 证明是一个经典的 NIWI 证明。在该证明中，证明者希望证明自己知道 $y_0 = g^{x_0}$ 或 $y_1 = g^{x_1}$ 中的某一个的离散对数，即证明自己知道 $x_0$ 或 $x_1$。过程如下：

   证明者仅知道一个私钥 $x_b$，其中 $b\in\\{0,1\\}$。基本思路是：分别针对 $y_0 = g^{x_0}$ 和 $y_1 = g^{x_1}$ 构造两个 Schnorr 签名，其中对已知私钥的一侧按真实 Schnorr 协议生成，对另一侧使用模拟器生成，最后组合成完整证明。具体步骤如下：

   1. 真实分支 $y_b = g^{x_b}$：随机选择 $r_b \in \mathbb{Z}_q$，计算承诺 $t_b = g^{r_b}$。
   2. 模拟分支 $y_{1-b} = g^{x_{1-b}}$：随机选择挑战 $c_{1-b}$ 与响应 $s_{1-b}$，计算承诺 $t_{1-b} = g^{s_{1-b}} \cdot y_{1-b}^{-c_{1-b}}$。
   3. 计算全局挑战 $c = H(m, t_0, t_1)$，令真实分支挑战 $c_b = (c - c_{1-b}) \bmod q$。
   4. 计算真实分支响应 $s_b = r_b + c_b \cdot x_b \pmod{q}$。
   5. 输出证明 $\pi = (t_0, t_1, c_0, s_0, c_1, s_1)$。

   验证者计算 $c' = H(m, t_0, t_1)$，并检查下列等式是否成立，若全部成立，则接受证明。

   $$c' \overset{?}{=} (c_0 + c_1) \bmod q , \quad g^{s_0} \overset{?}{=} t_0 \cdot y_0^{c_0}, \quad g^{s_1} \overset{?}{=} t_1 \cdot y_1^{c_1}$$
   • 完备性（Completeness）
     如果证明者知道某一支的私钥 $x_b$，则真实支的响应方程恒成立，模拟支由构造确保恒成立，且全局挑战的拆分保证 $c = c_0 + c_1$，因此验证总能通过。
   • 可靠性（Soundness）
     在 OR 协议中，如果一个 PPT 证明者能够生成一个通过验证的 OR 证明，则存在一个 PPT 提取器可以从其生成过程提取出至少一个合法见证 $x_0$ 或 $x_1$。提取器的工作方式如下：
     1. 在第一次执行中，证明者发送承诺对 $(t_0, t_1)$，提取器给出全局挑战 $c$，证明者返回 $(c_0, s_0, c_1, s_1)$，且验证通过： $ g^{s_i} = t_i \cdot y_i^{c_i},\quad c = (c_0 + c_1) \bmod q. $
     2. 提取器回滚到承诺阶段，保持 $(t_0, t_1)$ 不变，发送一个新的全局挑战 $c' \neq c$。由于模拟分支 $(c_{1-b}, s_{1-b})$ 被承诺 $t_{1-b}$ 绑定，无法在不知 $x_{1-b}$ 的情况下更改，因此它的挑战值在两次执行中保持不变；真实分支的挑战值则会随全局挑战变化为 $c_b' = (c' - c_{1-b}) \neq c_b$。
     3. 在真实分支 $b$ 上，提取器得到两组等式： $ g^{s_b} = t_b \cdot y_b^{c_b},\quad g^{s’_b} = t_b \cdot y_b^{c’_b}. $ 两式相除得到： $ g^{s_b - s’_b} = y_b^{c_b - c’_b} = g^{x_b (c_b - c’_b)}. $ 因此可计算出见证： $ x_b = \frac{s_b - s’_b}{c_b - c’_b} \pmod{q} $。 在离散对数问题困难性假设下，如果证明者不知道任意一个见证，则无法在同一承诺下生成两个不同挑战值且满足验证方程的响应。因此，该协议满足知识可靠性。
   • 证人不可区分性（Witness Indistinguishability）
     若证明者同时知道 $x_0$ 和 $x_1$，则他可以任选一支作为真实支来生成证明。由于另一支是通过模拟生成的，且最终证明的分布在统计上对称，验证者无法在多项式时间内以非可忽略优势判断证明者究竟使用了哪一个证人。因此，证明在计算上对所选证人保持不可区分性。

---

2.2 密码学中的 承诺 简介

承诺是密码学中的一种基本原语，用于在不公开消息内容的前提下，将消息的值"锁定"，之后可以选择性地揭示该消息并让验证者验证其正确性。直观上，它就像是把一条消息封进一个信封：承诺阶段封好信封并交给验证者，揭示阶段再当众打开信封，验证里面的内容是否一致。

1. 承诺方案的基本算法
   一个通用的承诺方案通常由以下算法组成：
   $\text{Setup}(1^\lambda) \to \mathsf{crs}$: 系统初始化算法，输入安全参数 $\lambda$，生成公共参考字符串（crs）。
   $\text{Commit}(crs,m; r) \to (c, d)$：承诺算法，输入消息 $m$ 与随机性 $r$，输出承诺值 $c$。
   $\text{Open}(crs,c,m,d) \to \\{0,1\\}$：打开算法，在公共参考字符串 $\mathsf{crs}$ 下，输入承诺值 $c$、消息 $m$ 及揭示信息 $d$，若承诺与消息匹配则输出 $1$（接受），否则输出 $0$（拒绝）。

2. 承诺方案的两个基本性质

• 隐藏性（Hiding）：通俗地说，隐藏性意味着在承诺揭示之前，任何人都无法从承诺值中获取被承诺消息的内容信息。也就是说验证者无法从承诺值 $c$ 中获得消息 $m$ 的任何信息。
  • 完美隐藏：承诺值在信息论意义上与 $m$ 无关。
  • 计算隐藏：在计算上难以区分承诺的是哪一个消息。
• 绑定性（Binding）：通俗地说，绑定性意味着承诺值与被承诺的消息是牢牢绑定的，承诺者在生成承诺后就不能再更改其中的消息。换句话说，一旦生成了承诺值 $c$，承诺者就无法找到两个不同的 $(m, d)$ 和 $(m', d')$ 使得 $\text{Open}(crs,c,m,d) = 1$ 并且 $\text{Open}(crs,c,m',d') = 1$。
  • 完美绑定：即使计算能力无限也无法改变承诺内容。
  • 计算绑定：除非解决某个困难问题，否则无法改变承诺内容。

2. 举例分析

   (1) 基于哈希的承诺

   $\text{Setup}(1^\lambda)$：选择抗碰撞且输出均匀的哈希函数 $H: \\{0,1\\}^* \to \\{0,1\\}^\lambda$ 作为公共参数。
   $\text{Commit}(crs, m)$：输入消息 $m$，选择随机值 $r$，计算它的承诺值为 $c = H(m||r)$。
   $\text{Open}(\mathsf{crs}, c, m, d=r)$：验证是否有 $c = H(m||d)$，若成立则输出 1，否则输出 0。

   • 绑定性分析：
     假设存在攻击者能对同一个承诺 $c$ 给出两组不同的消息-随机对 $(m,r)\neq (m',r')$ 使得他们的承诺都为 $c$，即 $H(m,r) = H(m',r')=c$，则相当于找到了 $H$ 的碰撞，那么攻击者就找到了哈希函数 $H$ 的一个碰撞，这与 $H$ 的抗碰撞性假设矛盾。因此方案满足计算绑定性。

   • 隐藏性分析：
     消息 $m$ 的承诺值为 $c=H(m,r)$，其中 r 是长度为 $\lambda$ 的均匀随机串。由于攻击者在看到 $c$ 时并不知道 $r$，即便它能够枚举所有可能的消息 $m$，仍需要同时猜测一个指数大的随机串 $r$，这在计算上不可行。因此，只要 $H$ 满足单向性，则给定 $c$ 无法在多项式时间内区分它是由哪一个消息 $m$ 生成的。因此该方案满足计算隐藏性。

   (2) Pedersen 承诺
   $\text{Setup}(1^\lambda)$： 选择一个阶为 $q$ 的循环群 $G$ 及它的两个不同的生成元 $g, h \in G$，并确保 $\log_g h$ 对任何人都是未知的，输出公共参考字符串 $crs = (G, q, g, h)$。
   $\text{Commit}(\mathsf{crs}, m; r)$：输入消息 $m \in \mathbb{Z}_q$ 和随机数 $r \in_R \mathbb{Z}_q$，计算承诺值 $c = g^m h^r$。 $\text{Open}(\mathsf{crs}, c, m, d=r)$：验证是否有 $c = g^m h^d$，若成立则输出 1，否则输出 0。

   • 绑定性分析：
     若承诺方能够打破绑定性，即找到 $(m, r) \neq (m', r')$ 使得 $g^m h^r = g^{m'} h^{r'}$，则可以推出

     $$g^{m - m'} = h^{r' - r} \quad \Rightarrow \quad \log_g h = \frac{m - m'}{r' - r} \pmod q$$
     即通过承诺方打破绑定性的方法求出了 $h$ 的离散对数 $\log_g h$ [这不可能]，满足计算绑定性。

   • 隐藏性分析：
     当 $r$ 在 $\mathbb{Z}_q$ 上均匀分布时，$h^r$ 在 $G$ 中也是均匀分布的，因此 $c = g^m h^r$ 的分布与 $m$ 无关。即使具有无限计算能力，攻击者也无法从 $c$ 推断 $m$，因此方案满足完美隐藏性。

---

三、GS证明如何对见证进行承诺

在 GS 证明中，证明者需要向验证者证明：自己掌握的某些见证能够满足特定的等式关系，同时不向验证者泄露这些见证的任何信息。为此，作者首先引入了承诺空间，并将原等式关系的证明转化为在承诺空间中验证新的等式关系。在这一转化过程中，承诺的构造至关重要。作者提出了一种针对见证的承诺方法，能够在两种不同的公共参考字符串下分别保证承诺的隐藏性与绑定性，并且这两种公共参考字符串在计算上是不可区分的。下面将对这种承诺方式进行介绍。

3.1 提出承诺的一般形式

GS承诺的两种公共参考字符串可分别实现完美绑定性或完美隐藏性，这两种模式在计算上不可区分，使得在安全性证明中可以根据不同需求同时兼顾可靠性与隐私性。 承诺的具体过程如下：

1. 引入新的 $R$-模：设 $(R,+,\cdot,0,1)$ 是有限交换环。假设我们要承诺一个 $R$-模 $A$ 中的元素。 为了实现承诺机制，我们首先引入一个更大的 $R$-模 $B$。【具体实例化后面会讲】

2. 定义两类映射： 线性嵌入映射 $\iota: A \to B$，可高效计算。 投影映射 $p: B \to A$。难以计算。

3. 生成随机向量： 将随机向量 $u_1, \ldots, u_{\hat{m}} \in B$ 作为公共参数的一部分用于对参数的随机化。

4. 假设要对 $x \in A$ 进行承诺，先随机选择 $r_1, \ldots, r_{\hat{m}} \in R$，并结合公开向量 $\\{u_i\\}$ 计算承诺：

   $$c := \iota(x) + \sum_{i=1}^{\hat{m}} r_i u_i \tag{6}$$
   直观上，$\iota(x)$ 记录了与 $x$ 相关的部分；随机噪声 $\sum r_i u_i$ 混淆了外部观察者。
   直接构造一个绑定又隐藏的承诺存在困难，作者通过分别构造两种承诺(一种隐藏，一种绑定)，并证明这两种承诺不可区分来实现类似的效果。

5. 更一般的，可以对多个元素组成的向量 $\vec{x} = (x_1,\ldots,x_m) \in A^m$ 进行承诺如下：

   $$\vec{c}=(c_1,\cdots,c_m) := \iota(\vec{x}) + R \vec{u}, \quad R \in Mat_{m \times \hat{m}}(R), \quad c_i = \iota(x_i) + \sum_{j=1}^{\hat{m}} r_{ij} u_j$$

   • 绑定性设置（论文称这种设置下的参数取值为 绑定密钥Binding Key）：
     要使承诺具备绑定性，参数需满足 $\forall i: p(u_i) = 0$ 且 $p \circ \iota$ 为非平凡映射。此时对承诺 $c$ 应用 $p$ 可得 $p(c) = p(\iota(x))$，噪声项 $\sum_{i=1}^{\hat{m}} r_i u_i$ 在 $p$ 下被完全消去，从而 $c$ 与消息 $x$ 一一对应，即唯一绑定。换言之，存在映射 $p$ 使得 $p(c)$ 仅依赖于 $x$ 而与随机性无关，因此每个承诺值都唯一对应一个消息。进一步的，若映射 $p \circ \iota$ 是恒等映射【即 $p \circ \iota(x) = x$】，则 $p$ 不仅能消去随机性，还可直接恢复消息本身，实现完美绑定。

   • 隐藏性设置（论文称这种设置下的参数取值为 隐藏密钥Hiding Key）
     要使承诺具备隐藏性，参数需满足 $\iota(A) \subseteq \langle u_1, \ldots, u_{\hat{m}} \rangle$，即 $x$ 在 $\iota$ 映射下的像空间完全包含在由 $u_1, \ldots, u_{\hat{m}}$ 张成的子空间中，此时，承诺 $c = \iota(x) + \sum_{i=1}^{\hat{m}} r_i u_i$ 中，$\iota(x)$ 会被随机噪声项 $\sum_{i=1}^{\hat{m}} r_i u_i$ 完全覆盖。换言之，给定一条承诺 $c$，消息 $x$ 在信息论意义下被完美隐藏，任何敌手都无法从 $c$ 中获得关于 $x$ 的任何信息。

   • 两种设置的计算不可区分性: 如果能够保证绑定性的设置和隐藏性的设置是不可区分的，那么在安全性分析的时候就可以根据自己的需要证明承诺满足绑定性和隐藏性。论文给出了 3 个承诺的实例化，它们基于不同的困难问题，并且作者证明了绑定密钥和隐藏密钥在计算上是不可区分的。这是作者给出的 见证不可区分证明 和 GS零知识证明 的关键安全假设。

---

3.2 系统初始化以公共参数生成

我们刚才在 2.1 中介绍承诺时已经知道，上述承诺要想实现绑定性和隐藏性，需要不同的参数设置，2.1 中已经简单的分析了参数设置的问题，这一节则会详细分析关于参数设置，也就是公共参考字符串生成的问题，这部分对于GS证明的安全性至关重要。

1. GS证明关系的结构定义：
   GS证明关系的结构 $gk$ 定义为代数结构 $gk \Rightarrow (\mathcal{R}, A_1, A_2, A_T, f)$，其中 $\mathcal{R}$ 表示有限交换环，$A_1, A_2, A_T$ 则是三个 $\mathcal{R}$-模，$f : A_1 \times A_2 \to A_T$ 表示一个双线性映射。
   我们在 1.4 中已经介绍过，通过不同方式实例化这个结构 $gk$, 可以得到要证明的四种关系。

2. 公共参考串 $\sigma$ 的定义：
   前面对承诺的介绍中我们知道，对要证明的秘密信息进行承诺需要引入映射，随机性等。我们将这些东西以公共参考字符串 $\sigma$ 的形式定义，并作为公开参数允许任何人访问。$\sigma$ 具体包含：

   $$\sigma \Rightarrow (B_1, B_2, B_T, F, \iota_1, p_1, \iota_2, p_2, \iota_T, p_T, \vec{u}, \vec{v}, H_1, \ldots, H_\eta)$$
   其中，$\underline{B_1, B_2, B_T}$ 表示承诺空间（新的 $R$-模），$\underline{F : B_1 \times B_2 \to B_T}$ 表示双线性映射。
   并且，$\underline{\iota_1, \iota_2, \iota_T}$ 表示高效可计算的线性嵌入映射，$\underline{p_1, p_2, p_T}$ 表示难以计算的投影映射。
   接着，$\underline{\vec{u}, \vec{v}}$ 表示生成承诺的公开随机向量。$\vec{u}=(u_1,\cdots,u_{\hat{m}})$ 是 (6) 式中的 $u_i$ 集合，$\vec{v}$ 同理
   最后，$\underline{H_1, \ldots, H_\eta}$ 表示辅助矩阵，满足 $\vec{u} \bullet H_i \vec{v} = 0$，用于保证零知识性，后续可以看出。

3. 承诺密钥
   如果要对 $A_1$ 上的元素进行承诺，那么用到的参数(也可叫密钥)是： $(B_1, \iota_1, p_1, u_1, \ldots, u_{\hat{m}})$
   同理，对 $A_2$ 上的元素进行承诺，那么用到的参数(也可叫密钥)是： $(B_2, \iota_2, p_2, v_1, \ldots, v_{\hat{n}})$
   注意：通过改变承诺密钥的取值，使其满足特定的条件，可以使承诺满足绑定性或隐藏性。

4. GS证明要求公共参考串 $\sigma$ 中的映射【 $\iota_1, \iota_2, \iota_T,p_1, p_2, p_T,F$ 】满足下图中的关系。这样才能把证明原等式关系成立转化为证明承诺后的等式关系成立。【具体过程后面会详细讲解】
   为简化表示，与双线性映射 $f(x,y)$ 类似的可定义符号： $\vec{x} \bullet \vec{y} := \sum_{i=1}^n F(x_i, y_i)$； 利用双线性性质，若 $\Gamma$ 为合适维度的矩阵则有： $\vec{x} \bullet \Gamma \vec{y} = \Gamma^\top \vec{x} \bullet \vec{y}$
   (1) 可靠性设置： 在可靠性设置中，首先要求投影映射对生成承诺所用的随机向量具有抹除性，即 $p_1(\vec{u}) = 0, p_2(\vec{v}) = 0$，并且要求组合映射 $p_1 \circ \iota_1, p_2 \circ \iota_2, p_T \circ \iota_T$ 都是非平凡的（即不是恒为零或常数的映射），那么所生成的承诺就是绑定的。原因在于，随机性在投影后被完全清除，而非平凡映射又确保了承诺中包含与消息本身相关的信息，从而保证了承诺值只能对应唯一的被承诺消息，实现绑定性。下文还会介绍：该绑定性还能保证 NIWI 证明的可靠性。
   (2) 证据不可区分性设置：在该设置中，首先要求嵌入映射满足 $\iota_1(A_1) \subseteq \langle u_1, \ldots, u_{\hat{m}} \rangle$，以及 $\iota_2(A_2) \subseteq \langle v_1, \ldots, v_{\hat{n}} \rangle$，即嵌入后的元素可以由承诺生成向量线性表示。此时承诺值被随机噪声 $\sum_{i=1}^{\hat{m}} r_i u_i$ 完全覆盖，从而保证了承诺的隐藏性。此外，还要求辅助矩阵 $H_1, \ldots, H_\eta$ 生成所有满足 $\vec{u} \bullet H \vec{v} = 0$ 的矩阵空间，用于在后续的 NIWI 证明中实现随机化。这些条件确保了即使使用不同的见证生成证明，生成的承诺在语义上也是不可区分的，从而实现承诺的隐藏性。下文还会介绍：隐藏性还能保证 NIWI 证明的见证不可区分性。
   (3) 计算不可区分性：虽然上面两种设置在构造上存在本质区别（前者确保承诺绑定性，后者确保零知识性），但如果这两种设置在分布上对于多项式时间的敌手而言是计算上不可区分的，那么我们就说系统满足计算不可区分性。这意味着敌手无法通过计算判断公共参考字符串（CRS）是在哪种设置下生成的。因此，在安全性证明中，我们可以在两个设置之间切换，而不会被敌手察觉。该属性是 GS 证明系统成立的关键基础，下文会展示如何实现这样的不可区分设置。

---

四、如何证明知道满足指定方程的见证

在上面的章节中已经讨论过：作者并不是直接证明见证满足原等式关系，而是首先引入了承诺空间，并将原等式关系的证明转化为在承诺空间中验证新的等式关系。这一节试图解释作者最初的想法，以及如何根据此想法构造出一个 NIWI 证明。

---

4.1 待证明关系的重申

通过上面的叙述我们知道，GS证明的四个关系实际上可以写成一个通用的二次方程形式：

$$\vec{a} \cdot \vec{y} + \vec{x} \cdot \vec{b} + \vec{x} \cdot \Gamma \vec{y} = t \tag{7}$$

其中常量 $\vec{a}, \vec{b}, \Gamma, t$ 已知，我们的目标是证明知道 $\vec{x}, \vec{y}$ 满足上式而不暴露 $\vec{x}, \vec{y}$. 使用零知识证明的常见表示符号可将这个证明表示为 $(8)$ 式。意思是以 $gk,\sigma,\vec{a}, \vec{b}, \Gamma, t$ 为公共输入，在不暴露 $\vec{x}, \vec{y}$ 的情况下证明自己知道满足等式 $\vec{a} \cdot \vec{y} + \vec{x} \cdot \vec{b} + \vec{x} \cdot \Gamma \vec{y} = t$ 的秘密向量 $\vec{x}, \vec{y}$ 。

$$\\{ (gk,\sigma,\vec{a}, \vec{b}, \Gamma, t\ ;\ \vec{x}, \vec{y}): \vec{a} \cdot \vec{y} + \vec{x} \cdot \vec{b} + \vec{x} \cdot \Gamma \vec{y} = t \\} \tag{8}$$

在本文中，作者并没有直接介绍如何构造一个非交互式的零知识证明(NIZK)，而是首先给出了非交互式的证据不可区分证明(NIWI)，最后再给出转化为NIZK的方法。我们在本节首先介绍 NIWI证明的构造思路，在【第七节】中再介绍如何将其转化为NIZK证明。NIWI的具体的证明过程如下：

---

4.2 如何构造 NIWI 证明

1. 对变量 $\vec{x}, \vec{y}$ 进行承诺：
   首先选择两个随机矩阵 $R,S$,然后通过下式计算得到他俩的承诺分别为：

   $$\vec{c} = \iota_1(\vec{x}) + R \vec{u}, \quad \vec{d} = \iota_2(\vec{y}) + S \vec{v}, \quad R,S \in \mathrm{Mat}_{m \times \hat{m}}(\mathbb{R}),$$
   值得说明的是，由于映射 $\iota_1,\iota_2,...,F$ 满足 Fig. 1 中的关系，因此我们可以将原方程的验证转化为对映射之后的模上的关系的验证。即，证明 $(7)$ 成立相当于证明下面的 $(9)$ 成立。
   $$\begin{array}{c} \vec{a} \cdot \vec{y} + \vec{x} \cdot \vec{b} + \vec{x} \cdot \Gamma \vec{y} = t \\ \Downarrow \quad \Downarrow \quad \Downarrow \\ \iota_1(\vec{a}) \bullet \iota_2(\vec{y}) + \iota_1(\vec{x}) \bullet \iota_2(\vec{b}) + \iota_1(\vec{x}) \bullet \Gamma \iota_2(\vec{y}) = \iota_T(t) \tag{9} \end{array}$$
   上式给出了GS证明的一个思路，即先对秘密向量进行承诺，并通过证明承诺后的向量满足上述 $(9)$ 式来完成对原始等式 $(7)$ 的证明，当然，为了实现零知识等特性，还需做一些额外处理。在进行下一步的介绍之前，我们首先证明 $(9)$ 中的两个式子是等价的。【证明见附录1】

2. 展开验证等式
   使用上述对向量 $\vec{x},\vec{y}$ 的承诺可以构造以下等式，也就是对原式左边分别做 $\iota$ 映射后得到：

   $$\begin{array}{c} \iota_1(\vec{a}) \bullet \vec{d} + \vec{c} \bullet \iota_2(\vec{b}) + \vec{c} \bullet \Gamma \vec{d} \\ \Downarrow \quad \Downarrow \quad \Downarrow \\ \iota_1(\vec{a}) \bullet (\iota_2(\vec{y}) + S \vec{v}) + (\iota_1(\vec{x}) + R \vec{u}) \bullet \iota_2(\vec{b}) + (\iota_1(\vec{x}) + R \vec{u}) \bullet \Gamma (\iota_2(\vec{y}) + S \vec{v}) \\ \Downarrow \quad \Downarrow \quad \Downarrow \\ \underbrace{\iota_1(\vec{a}) \bullet \iota_2(\vec{y}) + \iota_1(\vec{x}) \bullet \iota_2(\vec{b}) + \iota_1(\vec{x}) \bullet \Gamma \iota_2(\vec{y})}_{= \iota_T(t)} + \\ \underbrace{\iota_1(\vec{a}) \bullet S \vec{v} + R \vec{u} \bullet \iota_2(\vec{b}) + \iota_1(\vec{x}) \bullet \Gamma S \vec{v} + R \vec{u} \bullet \Gamma \iota_2(\vec{y}) + R \vec{u} \bullet \Gamma S \vec{v}}_I \\ \Downarrow \quad \Downarrow \quad \Downarrow \\ \iota_T(t) + \vec{u} \bullet \left( R^\top \iota_2(\vec{b}) + R^\top \Gamma \iota_2(\vec{y}) + R^\top \Gamma S \vec{v} \right) + \left( S^\top \iota_1(\vec{a}) + S^\top \Gamma^\top \iota_1(\vec{x}) \right) \bullet \vec{v} \\ \end{array}$$
   接下来，我们引入证明向量 $\vec{\pi}, \vec{\theta}$，并将 $\vec{\pi}, \vec{\theta}$ 代入到上述化简结果中可得：
   $$\begin{array}{c} \vec{\pi} := R^\top \iota_2(\vec{b}) + R^\top \Gamma \iota_2(\vec{y}) + R^\top \Gamma S \vec{v} \\ \vec{\theta} := S^\top \iota_1(\vec{a}) + S^\top \Gamma^\top \iota_1(\vec{x}) \\ \end{array}$$
   $$\iota_1(\vec{a}) \bullet \vec{d} + \vec{c} \bullet \iota_2(\vec{b}) + \vec{c} \bullet \Gamma \vec{d} = \iota_T(t) + \vec{u} \bullet \vec{\pi} + \vec{\theta} \bullet \vec{v} \tag{10}$$
   这意味着，若给定证明 $(\ \vec{c},\vec{d},\vec{\pi}, \vec{\theta} \ )$，验证者只需检查 (10) $式成立即验证了原始等式 $(7) 也成立。直观上，整个过程验证者不需知道 $\vec{x}, \vec{y}$ 的值，也即是证明者不需要向验证者暴露 $\vec{x}, \vec{y}$ 。我们似乎已经可以用上述方法构造 $\vec{\pi},\vec{\theta}$ 来实现一个非交互式的证明系统，但实际上，我们还需要证明上述系统满足非交互式证明系统中的两个核心安全属性： 可靠性 和 见证不可区分性，它们分别从"安全性"和"隐私性"两个角度保证了整个证明系统的可信性与实用性。

3. 对称情形解析
   在对称情形下（即 $A_1=A_2,B_1=B_2,\vec{u}=\vec{v}$，且 $F$ 是对称的），方程 $(10)$ 的右边等于下式，证明者将承诺 $\vec{c},\vec{d}$ 和 证明 $\vec{\pi}$ 一起发给验证者。

   $$\iota_T(t) + \vec{u} \bullet \underbrace{\left( R^\top \iota_2(\vec{b}) + R^\top \Gamma \iota_2(\vec{y}) + R^\top \Gamma S \vec{v} + S^\top \iota_1(\vec{a}) + S^\top \Gamma^\top \iota_1(\vec{x}) \right)}_{\vec{\pi}}$$

   验证者检查以下 $(11)$ 式的对称形式是否成立，成立则接受证明者的证明，否则不接受该证明。

   $$\iota_1(\vec{a}) \bullet \vec{d} + \vec{c} \bullet \iota_2(\vec{b}) + \vec{c} \bullet \Gamma \vec{d} = \iota_T(t) + \vec{u} \bullet \vec{\pi} \tag{11}$$
   我们在预备知识中已经介绍过，一个非交互式的 NIWI 证明系统需要满足三个关键的安全属性，完备性、可靠性和见证不可区分性。通过上述公式推导可以看出，完备性显然成立，下面我们证明如何实现可靠性和见证不可区分性。

   • 可靠性（Soundness）
     在可靠性设置下有 $p_1(\vec{u}) = 0$，并且 $p_1 \circ \iota_1, p_2 \circ \iota_2, p_T \circ \iota_T$ 是恒等映射，此时如果证明者给出的证明通过了验证方程 $(11)$，则理论上(映射 $p$ 是计算不可行的没关系)可以直接从承诺中唯一恢复出被承诺的值： $ \vec{x} = p_1(\vec{c}), \ \vec{y} = p_2(\vec{d}) $。 该设置下承诺的绑定性保证了承诺值与消息一一对应，则 $\vec{x}$ 和 $\vec{y}$ 就是唯一对应于 $(\vec{c}, \vec{d})$ 的见证。将其代入原始的二次方程可得：
     

     $$\vec{a} \bullet \vec{y} + \vec{x} \bullet \vec{b} + \vec{x} \bullet \Gamma \vec{y} = t,$$
     这说明提取出的 $(\vec{x}, \vec{y})$ 必然满足需要证明的关系。 因此，在绑定性模式下，任何能够通过验证的证明都隐含一个真实的、满足等式的见证 $(\vec{x}, \vec{y})$，从而排除了敌手在没有见证的情况下伪造出可接受证明的可能性，这就保证了知识可靠性【knowledge soundness】。

   • 证人不可区分性（Witness Indistinguishability, WI）
     在见证不可区分设置下，承诺具有完美隐藏性，因此证明中除了 $\vec{\pi}$ 外，不会泄露关于 $\vec{x}, \vec{y}$ 的任何额外信息。因此，验证者想区分不同见证，唯一能依赖的就是 $\vec{\pi}$。作者将见证不可区分性的分析分为两种情况：

     1. 唯一解的情况：如果验证等式成立的 $\vec{\pi}$ 是唯一的，则无论选择哪个见证生成证明，得到的 $\vec{\pi}$ 都相同，因此验证者无法区分所用的见证，WI 性质显然成立。
     2. 非唯一解的情况：若存在两个不同的证明 $\vec{\pi}$ 与 $\vec{\pi}'$ 都满足验证等式 (11)，则将两式相减后，右边相同的部分抵消，得到 $\vec{u} \bullet (\vec{\pi} - \vec{\pi}') = 0$，这说明 $\vec{\pi} - \vec{\pi}'$ 落在 $\vec{u}$ 的正交空间中，而该正交空间的方向恰好是所有保持验证等式成立的“自由方向”。
        由于已知矩阵族 $H_1, \dots, H_n$ 生成了所有满足 $\vec{u} \cdot H \vec{u} = 0$ 的 $H$，我们可以随机选择系数 $r_1, \dots, r_n$，构造 $\vec{\pi}'' = \vec{\pi} + \sum_{i=1}^n r_i H_i \vec{u}$ 得到新的合法证明 $\vec{\pi}''$。无论从 $\vec{\pi}$ 还是从 $\vec{\pi}'$ 出发生成的 $\vec{\pi}''$分布都是均匀且一致的，也就是说，使用不同的见证生成的证明 $\vec{\pi}$ 都是同分布的，因此验证者无法根据最终证明 $\vec{\pi}$ 区分证明者最初使用了哪个见证。

4. 非对称情形解析
   在对称情形下，只需针对 $\vec{u}$ 部分构造一个证明 $\vec{\pi}$，即可获得满足证人不可区分性的证明系统。但在非对称情形中，除了 $\vec{\pi}$（对应 $\vec{u}$ 部分）之外，还需要额外构造一个 $\vec{\theta}$（对应 $\vec{v}$ 部分），并且必须确保这两个部分在验证等式中相互独立且不泄露任何见证信息。为此，作者引入一个随机矩阵 $T \leftarrow Mat_{\hat{n} \times \hat{m}}(\mathcal{R})$ 对 $(\vec{\pi}, \vec{\theta})$ 进行随机化处理。利用该矩阵可以将验证等式改写为：

   $$\iota_T(t) + \vec{u} \bullet \vec{\pi} + \vec{\theta} \bullet \vec{v} = \iota_T(t) + \vec{u} \bullet (\vec{\pi} - T^\top \vec{v}) + (\vec{\theta} + T\vec{u}) \bullet \vec{v}.$$
   这样可以将 $\vec{\pi}$ 与 $\vec{\theta}$ 的耦合项分离，使它们能够分别进行随机化，从而消除二者之间的相关性。为了进一步打破可能的依赖关系，对 $\vec{\pi}$ 加入额外的随机项$\sum_{i=1}^\eta r_i H_i \vec{v}$， 其中 $H_i$ 来自生成所有满足 $\vec{u} \cdot H \vec{u} = 0$ 的矩阵族，$r_i$ 是随机系数。这些随机化操作不会影响验证等式的成立，但能保证 $(\vec{\pi}, \vec{\theta})$ 在满足验证等式的解空间中均匀分布，以保护见证信息。

   非对称情况下的完整证明过程如下：
   证明者随机选择 $T \leftarrow Mat_{\hat{n} \times \hat{m}}(\mathcal{R})$，$r_1, \dots, r_\eta \leftarrow \mathcal{R}$，并计算 $(\vec{\theta}, \vec{\pi})$ 发送给验证者。

   $$\begin{array}{c} \vec{\pi} := R^\top \iota_2(\vec{b}) + R^\top \Gamma \iota_2(\vec{y}) + R^\top \Gamma S \vec{v} - T^\top \vec{v} + \sum_{i=1}^\eta r_i H_i \vec{v} \\ \vec{\theta} := S^\top \iota_1(\vec{a}) + S^\top \Gamma^\top \iota_1(\vec{x}) + T\vec{u}. \end{array}$$
   验证者接收到证明 $(\vec{\theta}, \vec{\pi})$ 后，验证下面的方程是否成立，若成立，则接受该证明。
   $$\iota_1(\vec{a}) \bullet \vec{d} + \vec{c} \bullet \iota_2(\vec{b}) + \vec{c} \bullet \Gamma \vec{d} = \iota_T(t) + \vec{u} \bullet \vec{\pi} + \vec{\theta} \bullet \vec{v}.$$

   接着，我们证明上述非交互式证明系统满足完备性、可靠性和见证不可区分性。

   • 完备性 Completeness：
     若 $\vec{x} \in A_1^m, \vec{y} \in A_2^n, R, S \in Mat_{m \times \hat{m}}(\mathcal{R})$ 满足下列等式：

     $$\vec{c} = \iota_1(\vec{x}) + R\vec{u}, \quad \vec{d} = \iota_2(\vec{y}) + S\vec{v}, \quad \vec{a} \cdot \vec{y} + \vec{x} \cdot \vec{b} + \vec{x} \cdot \Gamma \vec{y} = t,$$
     则对所有 $T, r_1, \dots, r_\eta$，由上述方法构造的 $(\vec{\pi}, \vec{\theta})$ 均能通过验证。
     证明：由线性映射与双线性映射的交换性，可得：
     $$\begin{array}{c} \iota_1(\vec{a}) \bullet \vec{d} + \vec{c} \bullet \iota_2(\vec{b}) + \vec{c} \bullet \Gamma \vec{d} \\ \Downarrow \quad \Downarrow \quad \Downarrow \\ \iota_1(\vec{a}) \bullet \left( \iota_2(\vec{y}) + S \vec{v} \right) + \left( \iota_1(\vec{x}) + R \vec{u} \right) \bullet \iota_2(\vec{b}) + \left( \iota_1(\vec{x}) + R \vec{u} \right) \bullet \Gamma \left( \iota_2(\vec{y}) + S \vec{v} \right) \\ \Downarrow \quad \Downarrow \quad \Downarrow \\ \iota_1(\vec{a}) \bullet \iota_2(\vec{y}) + \iota_1(\vec{x}) \bullet \iota_2(\vec{b}) + \iota_1(\vec{x}) \bullet \Gamma \iota_2(\vec{y}) + \\ R\vec{u} \bullet \iota_2(\vec{b}) + R\vec{u} \bullet \Gamma \iota_2(\vec{y}) + R\vec{u} \bullet \Gamma S\vec{v} + \iota_1(\vec{a}) \bullet S\vec{v} + \iota_1(\vec{x}) \bullet \Gamma S\vec{v} \\ \Downarrow \quad \Downarrow \quad \Downarrow \\ \iota_T(t) + \vec{u} \bullet \left( R^\top \iota_2(\vec{b}) + R^\top \Gamma \iota_2(\vec{y}) + R^\top \Gamma S \vec{v} \right) + \left( S^\top \iota_1(\vec{a}) + S^\top \Gamma^\top \iota_1(\vec{x}) \right) \bullet \vec{v} \\ \Downarrow \quad \Downarrow \quad \Downarrow \\ \iota_T(t) + \vec{u} \bullet \left( R^\top \iota_2(\vec{b}) + R^\top \Gamma \iota_2(\vec{y}) + R^\top \Gamma S \vec{v} \right) + \underbrace{\sum_{i=1}^\eta r_i \left( \vec{u} \bullet H_i \vec{v} \right)}_{Always \ equal \ to \ 0} \\ \underbrace{- \vec{u} \bullet T^\top \vec{v} + T \vec{u} \bullet \vec{v}}_0 + \left( S^\top \iota_1(\vec{a}) + S^\top \Gamma^\top \iota_1(\vec{x}) \right) \bullet \vec{v} \\ \Downarrow \quad \Downarrow \quad \Downarrow \\ \iota_T(t) + \vec{u} \bullet \vec{\pi} + \vec{\theta} \bullet \vec{v} \end{array}$$
     上述推导表明，如果证明者正确生成证明 $(\vec{\pi}, \vec{\theta})$，则验证者的验证总是通过，满足完备性。

   • 可靠性 Soundness：
     在 $\vec{p}_1(\vec{u}) = \vec{0}$ 且 $\vec{p}_2(\vec{v}) = \vec{0}$ 的情况下，任何有效证明 $(\vec{\pi}, \vec{\theta})$ 必须满足：

     $$p_1(\iota_1(\vec{a})) \cdot p_2(\vec{d}) + p_1(\vec{c}) \cdot p_2(\iota_2(\vec{b})) + p_1(\vec{c}) \cdot \Gamma p_2(\vec{d}) = p_T(\iota_T(t)).$$
     证明： 一个可接受的证明 $(\vec{\pi}, \vec{\theta})$ 满足下式，对两边分别取相应的投影映射可得：
     $$\begin{array}{c} \iota_1(\vec{a}) \bullet \vec{d} + \vec{c} \bullet \iota_2(\vec{b}) + \vec{c} \bullet \Gamma \vec{d} = \iota_T(t) + \vec{u} \bullet \vec{\pi} + \vec{\theta} \bullet \vec{v} \\ \Downarrow \quad \Downarrow \quad \Downarrow \\ p_1(\iota_1(\vec{a})) \bullet p_2(\vec{d}) + p_1(\vec{c}) \bullet p_2(\iota_2(\vec{b})) + p_1(\vec{c}) \bullet \Gamma p_2(\vec{d}) \\ = p_T(\iota_T(t)) + p_1(\vec{u}) \bullet p_2(\vec{\pi}) + p_1(\vec{\theta}) \bullet p_2(\vec{v}) \end{array}$$
     在可靠性设置中 $p_1(\vec{u}) = \vec{0}$ 且 $p_2(\vec{v}) = \vec{0}$，因此 $p_2(\vec{d}) = p_2(\iota_2(\vec{y}))$，$p_1(\vec{c}) = p_1(\iota_1(\vec{x}))$,参考【附录1】中的证明方法，将 $p_2(\vec{d})$，$p_1(\vec{c})$ 代入上式后化简得：
     $$p_1(\iota_1(\vec{a})) \bullet p_2(\vec{d}) + p_1(\vec{c}) \bullet p_2(\iota_2(\vec{b})) + p_1(\vec{c}) \bullet \Gamma p_2(\vec{d}) = p_T(\iota_T(t))$$
     特别的，当 $p_1 \circ \iota_1, p_2 \circ \iota_2, p_T \circ \iota_T$ 均为恒等映射时，有 $\vec{x} := p_1(\vec{c}), \vec{y} := p_2(\vec{d})$, 这给出了方程 $\vec{a} \cdot \vec{y} + \vec{x} \cdot \vec{b} + \vec{x} \cdot \Gamma \vec{y} = t$ 的一个解。因此此证明在可靠性设置下满足知识可靠性。

   • 见证不可区分性 WI：
     在不可区分设置下 $\iota_1(A_1) \subseteq \langle u_1, \dots, u_{\hat{n}} \rangle$, $\iota_2(A_2) \subseteq \langle v_1, \dots, v_{\hat{n}} \rangle$，并且 $H_1, \dots, H_n$ 生成了所有满足 $\vec{u} \bullet H \vec{v} = 0$ 的矩阵 $H$，则所有满足验证方程的见证，其对应 $(\vec{\pi}, \vec{\theta})$ 在条件分布下服从均匀分布，从而实现见证不可区分性。
     证明：由于 $\iota_1(A_1) \subseteq \langle u_1, \dots, u_{\hat{n}} \rangle, \quad \iota_2(A_2) \subseteq \langle v_1, \dots, v_{\hat{n}} \rangle$ 则存在矩阵 $A, B, X, Y$ 使得： $ \iota_1(\vec{a}) = A \vec{u}, \quad \iota_1(\vec{x}) = X \vec{u}, \quad \iota_2(\vec{b}) = B \vec{v}, \quad \iota_2(\vec{y}) = Y \vec{v} $， 将它们带入承诺中可得： $ \vec{c} = (X + R) \vec{u}, \quad \vec{d} = (Y + S) \vec{v} $。 我们知道，证明者给出的证明为 $(\vec{\pi}, \vec{\theta})$，其中：

     $$\begin{array}{c} \vec{\pi} = R^\top \iota_2(\vec{b}) + R^\top \Gamma \iota_2(\vec{y}) + R^\top \Gamma S \vec{v} - T^\top \vec{v} + \sum_{i=1}^\eta r_i H_i \vec{v} \\ = \left( R^\top B + R^\top \Gamma Y + R^\top \Gamma S - T^\top \right) \vec{v} + \left( \sum_{i=1}^\eta r_i H_i \right) \vec{v} \\ \vec{\theta} = S^\top \iota_1(\vec{a}) + S^\top \Gamma^\top \iota_1(\vec{x}) + T \vec{u} = \left( S^\top A + S^\top \Gamma^\top X + T \right) \vec{u} \end{array}$$
     由于 $T$ 是随机选择的，可将 $\vec{\theta}$ 看作由 $\vec{\theta} = \Theta \vec{v}$ 给出的均匀随机变量，其中 $\Theta$ 为随机的方阵。同理，$\vec{\pi}$ 可写为 $\vec{\pi} = \Pi \vec{v}$，其中 $\Pi$ 依赖于 $\Theta$。
     由完备性可知，所有满足条件的见证生成的证明均满足： $ \iota_T(t) - \vec{\theta} \bullet \vec{v} = \vec{u} \bullet \vec{\pi} $
     令 $\Pi = \Pi' + \sum_{i=1}^\eta r_i' H_i$，并利用 $\vec{u} \bullet H_i \vec{v} = 0$ 的性质，构造 $\vec{\pi}$ 时：
     $$\vec{\pi} = \left( R^\top B + R^\top \Gamma Y + R^\top \Gamma S - T^\top \right) \vec{v} + \left( \sum_{i=1}^\eta r_i H_i \right) \vec{v}$$
     其中 $r_1, \dots, r_\eta$ 是随机选取的。因此，$\vec{\theta}$ 在条件 $\iota_T(t) - \vec{\theta} \bullet \vec{v} = \vec{u} \bullet \vec{\pi}$ 下均匀分布，$\vec{\pi}$ 在最后一个随机项的混淆下也是均匀分布的，从而证明了见证不可区分性。

5. 线性方程的特例
   在特殊情形下，考虑当 $\vec{a} = 0$ 且 $\Gamma = 0$ 时的证明系统。此时验证方程简化为：$\vec{x} \bullet \vec{b} = t$。在该情况下，可以通过在证明中选择 $T = 0$ 来简化方案，此时有：

   $$\vec{\theta} := \vec{0}, \quad \vec{\pi} := R^\top \iota_2(\vec{b}) + \sum_{i=1}^\eta r_i H_i \vec{v}$$
   当 $T = 0$ 时，4.中证明的完备性依然成立，因此完备性依然保持。并且4.中证明的可靠性表明等式 $ p_1(\vec{c}) \cdot p_2(\iota_2(\vec{b})) = p_T(\iota_T(t)) $ 成立，这将保证可靠性。

   见证不可区分性：
   在见证不可区分性设置下 $ \iota_1(A_1) \subseteq \langle u_1, \dots, u_{\hat{n}} \rangle, \iota_2(A_2) \subseteq \langle v_1, \dots, v_{\hat{n}} \rangle $ 且 $H_1, \dots, H_\eta$ 生成所有满足 $\vec{u} \bullet H \vec{v} = 0$ 的矩阵 $H$，则使用任意一个满足待证明方程的见证 $\vec{x}, \vec{y}, R, S$ 生成的证明 $\vec{\pi} \in \langle v_1, \dots, v_{\hat{n}} \rangle^{\hat{m}}$ 服从均匀分布。即验证者不能从 $\vec{\pi}$ 中区分出证明使用了哪一个见证。
   证明：与上述证明类似，可以将 $\vec{\pi}$ 写为 $\vec{\pi} = \Pi \vec{v}$ ，则任意见证给出的证明满足：

   $$\vec{c} \bullet \iota_1(\vec{b}) - \iota_T(t) = \vec{u} \bullet \vec{\pi} = \vec{u} \bullet \Pi \vec{v}$$
   由于 $H_1, \dots, H_\eta$ 生成了所有满足 $\vec{u} \bullet H \vec{v} = 0$ 的矩阵 $H$，矩阵 $\Pi$ 在满足验证方程的所有矩阵集合上均匀分布，从而证明了见证不可区分性。

---

五、基于 SXDH 假设的 NIWI 构造

上一节介绍了NIWI证明的通用构造方法，只需要公共参数中的群结构和使用的映射满足特定的关系即可实现NIWI证明。这一节，我们将给出具体的$\mathcal{R}$-模和映射如何选取，论文中分别基于三个困难假设给出了三个不同的实例化方法，我们在这里只介绍一个基于 SXDH 困难假设的实例化。

5.1 SXDH假设介绍

SXDH 假设认为 DDH（Decisional Diffie-Hellman）问题在 $G_1$ 和 $G_2$ 中都是困难的。设生成算法 $G_{\mathrm{SXDH}}$ 输出群参数 $gk = (p, G_1, G_2, G_T, e, P_1, P_2)$，其中 $P_1 \in G_1$，$P_2 \in G_2$ 是生成元。SXDH 假设表述为：对于任意多项式时间算法 $\mathcal{A}$ 和任意 $b \in \\{1,2\\}$ 有:

$$\Pr \left[ \begin{aligned} &gk \leftarrow G_{SXDH}(1^k); \ \alpha, t \leftarrow Z_p^* : \\ &\mathcal{A}(gk, \alpha P_b, t P_b, \alpha t P_b) = 1 \end{aligned} \right] \approx \Pr \left[ \begin{aligned} &gk \leftarrow G_{SXDH}(1^k); \ \alpha, t, r \leftarrow Z_p^* : \\ &\mathcal{A}(gk, \alpha P_b, t P_b, r P_b) = 1 \end{aligned} \right]$$

通俗来讲，SXDH假设认为任何概率多项式的敌手不能高效的区分两个元组 $(\alpha P_b, t P_b, \alpha t P_b)$ 和 $(\alpha P_b, t P_b, r P_b)$。也可以描述为，给敌手有一个元组 $(\alpha P_b, t P_b, r P_b)$，敌手无法判断最后一个元素的离散对数 $r$ 是否等于前两个元素的离散对数 $\alpha,t$ 的乘积 $\alpha t$。

---

5.2 如何实例化对见证的承诺

我们的目标是在不暴露见证的情况下证明他们满足 $(1)(2)(3)(4)$ 式，我们在上述证明思路中已经介绍了如何构造承诺 $\vec{c},\vec{d}$ 和 证明 $\vec{\pi},\vec{\theta}$ 来实现 NIWI 证明。其中为了实现至关重要的可靠性和见证不可区分性 ，需要使用的公共参考字符串满足特定的要求，即映射 $\iota_1,\iota_2,p_1,p_2$ 和 随机向量 $\vec{u},\vec{v}$ 满足特定的要求。下面我们给出满足这些条件的实例化构造。

上文介绍道，GS证明中通过两种不同的设置分别实现可靠性和见证不可区分性，并且通过让这两种设置不可区分使得安全性证明中可以根据需要让方案既满足可靠性，又满足见证不可区分性。 可靠性设置要求 $\vec{p_1}(\vec{u}) = \vec{0}$ 且 $\vec{p_2}(\vec{v}) = \vec{0}$ 且 $p_1 \circ \iota_1, p_2 \circ \iota_2, p_T \circ \iota_T$ 均为恒等映射。 见证不可区分设置则要求 $\iota_1(A_1) \subseteq \langle u_1, \dots, u_{\hat{n}} \rangle$，$\iota_2(A_2) \subseteq \langle v_1, \dots, v_{\hat{n}} \rangle$， 并且 $H_1, \dots, H_n$ 生成了所有满足 $\vec{u} \bullet H \vec{v} = 0$ 的矩阵 $H$。下文使用可靠性设置和见证不可区分性设置来代指这些要求。

1. 对群 $G$ 上的元素 $X$ 进行承诺
   对群元素 $X \in G_1$ 进行承诺的方式是使用最开始 $(6)$ 式定义的承诺方法如下。(对 $G_2$，$Z_p$ 等群里的元素承诺同理，只是用到的随机向量和映射使用不同的实例化)，即： $$ c = \iota(X) + \sum_{i=1}^2r_i u_i \quad = \iota(X) + r_1 u_1 + r_2 u_2,\quad r_1, r_2 \overset{$}{\leftarrow} \mathbb{Z}_p $$ 当群元素 $X \in G_1$ 时，我们相应的取实例化公共参考字符串如下：

   • 定义承诺空间为： $B = G_1^2$
   • 定义承诺密钥为： $u_1 = (P, Q) = (P, \alpha P)$，$u_2 := t u_1$ 或 $u_2 = t u_1 - (\mathcal{O}, P)$。
   • 定义嵌入映射为： $\iota(Z) = (O, Z)$
   • 定义投影映射为： $p(Z_1, Z_2) = Z_2 - \alpha Z_1$

   对于上述定义，我们分析可得下面的性质：

   • 映射满足 $p \circ \iota(X) = p(\iota(X)) = p(\mathcal{O},X) = X - \alpha \mathcal{O} = X$，故 $p \circ \iota$ 是一个恒等映射。
   • 随机向量 $u_2 = tu_1$ 时，显然有 $p(u_1) = Q- \alpha P = p(u_2) = tQ - t \alpha P = \mathcal{O}$ 成立。
   • 随机向量 $u_2 = t u_1 - (O, P)$ 时，显然 $u_1, u_2$ 性无关，故它们构成二维空间 $B = G^2$ 的一组基。由于 $\iota(G)$ 是 $B$ 上的元素，因此 $\iota(G)$ 可被 $u_1,u_2$ 线性表示，即 $\iota(G) \subseteq \langle u_1, u_2 \rangle$。

   至此，可以发现当 $u_2 = t u_1 - (O, P)$ 时，上述公共参考字符串满足见证不可区分性设置。而当 $u_2 := tu_1$ 时，上述公共参考字符串满足可靠性设置。在前面介绍承诺时已经证明，两种参数设置分别可以保证承诺的绑定性和隐藏性。下面从另一个角度分析承诺的这两个性质。

   完美绑定（Perfectly Binding）
   在可靠性设置下 $p(c) = p(\iota(X)) + r_1 p(u_1) + r_2 p(u_2) = X$， 这意味着，给定承诺 $c$，通过公开的 $p$ 就能唯一恢复被承诺的消息 $X$，不同的 $X$ 不可能生成相同的承诺值。因此实现了完美绑定，即不存在 $X \neq X'$ 使它们对应同一个 $c$。值得注意的是，该设置下有：

   $$c = ((r_1 + r_2 t) P,\ (r_1 + r_2 t) Q + X)$$
   该分布与明文为 $X$ 的 ElGamal 加密相同，从另一个角度说明了承诺只能对应唯一的 $X$。

   完美隐藏（Perfectly Hiding）
   在见证不可区分性设置下，我们将 $X$ 表示为 $X = xP$ 并代入承诺公式得：

   $$c = \iota(X) + r_1 u_1 + r_2 u_2 = (r_1 + x t) u_1 + (r_2 - x) u_2$$
   由于 $(r_1, r_2)$ 在 $\mathbb{Z}_p^2$ 上均匀分布，$(r_1 + x t, r_2 - x)$ 仍为均匀分布，且与 $x$（即 $X$）无关，因此 $c$ 的分布与 $X$ 完全独立。这正是“完美隐藏”性质。 直观地看，$\iota(X)$ 位于随机子空间 $\langle u_1, u_2 \rangle$ 内，可被随机性完全淹没，从而在信息论意义下实现对 $X$ 的完全隐藏。

---

2. 对 $\mathbb{Z}_p$ 群上的标量 $x$ 进行承诺
   对 $\mathbb{Z}_p$ 群上的标量 $x$ 的承诺为： $ c := \iota’(x) + r u_1 $ 我们相应的取实例化公共参考字符串如下：

   • 定义承诺空间为： $B = \mathbb{Z}_p^2$
   • 定义承诺密钥为： $u := u_2 + (O, P)$。
   • 定义嵌入映射为： $\iota'(z) := z u$
   • 定义投影映射为： $p'(z_1 P, z_2 P) := z_2 - \alpha z_1$

   对于上述定义，我们分析可得下面的性质：

   • 映射满足 $p' \circ \iota'(z) = p'(\iota'(z)) = p'(zu) = z$，故 $p \circ \iota$ 是一个恒等映射。【$u$ 在 $u_2$ 的两种取值下，也会有两种取值，直接代入上述映射的计算公式容易证明 $p' \circ \iota'$ 确实是恒等映射 】
   • 映射满足 $p'(u_1) = \alpha - \alpha\cdot 1 = 0$ 成立。
   • 随机向量 $u_2 = t u_1 - (O, P)$ 时，此时 $u=tu_1$，即 $\iota'(z) = zu = ztu_1 \subseteq \langle u_1 \rangle$。

   完美绑定（Perfectly Binding）
   在可靠性设置下，$p' \circ \iota'$ 为恒等映射，且 $p'(u_1) = 0$，因此有：

   $$c = ((r + x t) P,\ (r + x t) Q + x P)$$
   该形式与明文为 $x P$ 的 ElGamal 加密同分布，进一步说明了承诺只能对应唯一的 $x$。

   完美隐藏（Perfectly Hiding）
   当使用隐藏密钥时，有 $u = t u_1$，因此 $u \in \langle u_1 \rangle$，从而可得：$\iota'(\mathbb{Z}_p) \subseteq \langle u_1 \rangle.$ 在此情况下，随机性可以完全掩盖消息 $x$，从而得到一个完美隐藏的承诺方案。

---

3. 公共参考字符串（CRS）
   现在我们可以将上面给出的基于 SXDH 假设构造的公共参考字符串通用的写成以下形式：

   $$\sigma \Rightarrow (B_1, B_2, B_T, F, \iota_1, p_1, \iota_2, p_2,\iota_1', p_1', \iota_2', p_2', \iota_T, p_T, \vec{u}, \vec{v})$$
   其中映射即为上面描述的映射，$G_2$ 群上的映射定义和 $G_1$ 类似：
   • $(u_1, u_2) \in B_1^2 = G_1^2 \times G_1^2$ 是针对群 $G_1$ 的承诺密钥，对应隐式定义的映射 $\iota_1, p_1, \iota'_1, p'_1$
   • $(v_1, v_2) \in B_2^2 = G_2^2 \times G_2^2$ 是针对群 $G_2$ 的承诺密钥，对应隐式定义的映射 $\iota_2, p_2, \iota'_2, p'_2$
   • 定义承诺空间分别为 $B_1 = G_1^2,\ B_2 = G_2^2,\ B_T = G_T^4$，其中 $B_T$ 上的加法为逐坐标相加。
   • 定义双线性映射如下:
     $$F: G_1^2 \times G_2^2 \to G_T^4,\quad \big( (X_1, X_2), (Y_1, Y_2) \big) \mapsto \begin{pmatrix} e(X_1, Y_1) & e(X_1, Y_2) \\ e(X_2, Y_1) & e(X_2, Y_2) \end{pmatrix}$$
     通过上述实例化中的分析，我们可以发现，通过设置 $u_2$ 取不同的值可以分别保证可靠性和见证不可区分性成立。上面的讨论中，一直没有提到矩阵 $H$, 在这里将证明 $H=0$ 恒成立。也就是该实例化中的 crs 不需要含有 $H_i$。

   在上述的见证不可区分设置下，选择的 $u_1, u_2$ 在 $B_1$ 中线性无关，选择的 $v_1, v_2$ 则在 $B_2$ 中线性无关。此时，四个元素： $ F(u_1, v_1),\ F(u_1, v_2),\ F(u_2, v_1),\ F(u_2, v_2) $ 在 $B_T$ 中也是线性无关的。因此由线性无关的定义可得，对于任意 $2 \times 2$ 矩阵 $H = (H_{ij})$，若：

   $$\tilde{u} \bullet H \tilde{v} = \sum_{i,j \in \{1,2\}} H_{ij} \, F(u_i, v_j) = 0,$$
   唯一的解是 $H = 0$（即全零矩阵）。这意味着 $H$ 的核空间是平凡的。因此，在构造配对积方程时，CRS 中无需包含任何 $H$ 矩阵（如 $H_1, \dots, H_\eta$）。 这一结论在 SXDH 小节中被明确指出，并且在一般框架下的性质 $\tilde{x} \bullet \Gamma \tilde{y} = (\Gamma^\mathsf{T} \tilde{x}) \bullet \tilde{y}$ 上同样成立。 换句话说，在 WI 模式的 CRS 中，我们只需包含承诺密钥 $(u_1, u_2, v_1, v_2)$，而不必附加额外的 $H$ 矩阵即可满足所需的性质。

---

5.3. 配对积方程、多标量乘法方程与二次方程的统一表示

在本节中，我们将展示如何通过实例化不同的公共参考字符串来将不同类型的方程（配对积方程、多标量乘法方程、二次方程）统一嵌入到同一套 NIWI 证明框架中。

1. 对于配对积方程，公共参考字符串（CRS）被实例化为：
   • 群结构：$R = \mathbb{Z}_p,\ A_1 = G_1,\ A_2 = G_2,\ A_T = G_T$。
   • 辅助群：$B_1 = G_1^2,\ B_2 = G_2^2,\ B_T = G_T^4$。
   • 定义承诺密钥为： $u_1 = (P, Q) = (P, \alpha P)$，$u_2 := t u_1$ 或 $u_2 = t u_1 - (\mathcal{O}, P)$。
   • 定义两个群 $G_1,G_2$ 上的嵌入映射为： $\iota_i(Z) = (O, Z),\ Z \in G_i, \ i=\\{1,2\\}$
   • 定义投影映射为： $p_i(Z_1, Z_2) = Z_2 - \alpha Z_1$ 【也是两个群上的】
   • 定义映射 $\iota_T,p_T$ 如下：【$p_T$ 的定义是正确的且能保证 $p_T \circ \iota$ 是恒等映射。证明见附录2】
     $$\begin{aligned} \iota_T: \quad & e(X,Y) \mapsto \begin{pmatrix} 1 & 1\\ 1 & e(X,Y) \end{pmatrix}, \\ p_T: \quad & \left( \begin{pmatrix} a & b\\ c & d \end{pmatrix} \right) = d\cdot a^{\alpha_1\alpha_2}\cdot b^{-\alpha_1}\cdot c^{-\alpha_2} \end{aligned}$$
   • 双线性映射实例化为：
     $$f : (X, Y) \mapsto e(X, Y), \quad F : \left( \begin{pmatrix} \mathcal O \\ X \end{pmatrix}, \begin{pmatrix} \mathcal O \\ Y \end{pmatrix} \right) \mapsto \begin{pmatrix} e(\mathcal{O},\mathcal{O}) & e(\mathcal{O},Y)\\ e(X,\mathcal{O}) & e(X,Y) \end{pmatrix}$$
     
     下图展示了映射之间的关系，我们在【5.2节】中已经证明了在可靠性设置下 $p_i(u_i) = 0,\ i=1,2$，并且证明了 $\iota_i \circ p_i$ 都是恒等映射。为了保证能够使用第四节中介绍的方法进行 NIWI证明，需要上述定义的公共参考字符串满足 Fig. 1 中的关系。即：
     • 映射 $f,F$ 满足 $F(\iota_1(x),\iota_2(y)) = \iota_T(f(x,y))$ 【该该等式通过瞪眼法可知：显然成立】
     • 映射 $p_T \circ \iota_T$ 是恒等映射，具体证明如下所示：【详细证明见附录2】
       $$\begin{aligned} (p_T\circ \iota_T)(Z) &= p_T \left( \begin{pmatrix} 1 & 1\\ 1 & Z \end{pmatrix} \right) = Z \cdot 1^{\alpha_1\alpha_2}\cdot 1^{-\alpha_1}\cdot 1^{-\alpha_2} = Z \end{aligned}$$

综上所述，使用上述实例化的公共参考字符串，可直接套用第四节介绍的方法进行 NIWI 证明。

除了配对积方程，GS证明还能证明知道见证满足 $(2)(3)(4)$ 三个方程成立，关于这几种情况下，公共参考字符串中各个元素的取值，放在附录3

通过上述映射构造和交换图可知，GS证明要证明的四个等式等可以归结为一个广义二次方程的验证。这使得它们能够在同一套 NIWI 证明体系下处理，复用相同的 CRS 和安全性证明结构。

---

5.3 NIWI证明的具体步骤

在开始证明之前，首先要生成证明所需要的各种参数，这个步骤在系统初始化阶段完成：

0. 系统初始化
   下面给出完整 NIWI 证明过程。生成证明的第一步是生成参数：
   $$gk := (p, G_1, G_2, G_T, e, P_1, P_2) \leftarrow \mathsf{G}_{\mathsf{SXDH}}(1^k)$$
   在输入 $gk$ 的情况下，返回可靠性设置下的字符串如下： $$ \sigma := (u_1, u_2, v_1, v_2), \ u_2 = t_1 u_1, \quad v_2 = t_2 v_1,\quad t_1, t_2 \overset{$}{\leftarrow} \mathbb{Z}_p $$ 在输入 $gk$ 的情况下，返回见证不可区分设置下的字符串如下： $$ \sigma := (u_1, u_2, v_1, v_2), \ u_2 = t_1 u_1 - (O, P_1), \quad v_2 = t_2 v_1 - (O, P_2),\quad t_1, t_2 \overset{$}{\leftarrow} \mathbb{Z}_p $$

NIWI证明的具体步骤

输入：公共参数 $gk$，公共参考字符串 $\sigma$，一组方程与见证 $\vec{X}, \vec{Y}, \vec{x}, \vec{y}$。

证明者 $\mathcal{P}$ 执行：

1. 对群元素与标量进行承诺
   为了对群 $G_1$ 上的元素 $\vec{X} \in G_1^m$ 与标量 $\vec{x} \in Z_p^m$ 进行承诺，我们按照下面的式子计算：

   $$\vec{c} := \iota_1(\vec{X}) + R \vec{u},\quad \vec{c}' := \iota_1'(\vec{x}) + \vec{r} u_1,\quad R \leftarrow \mathsf{Mat}_{m \times 2}(\mathbb{Z}_p),\ \vec{r} \leftarrow \mathbb{Z}_p^m$$

   同样的道理，为了对群 $G_2$ 上的元素 $\vec{Y} \in G_2^n$ 与 $\vec{y} \in Z_p^n$进行承诺，我们按照下式计算：

   $$\vec{d} := \iota_2(\vec{Y}) + S \vec{v},\quad \vec{d}' := \iota_2'(\vec{y}) + \vec{s} v_2,\quad S \leftarrow \mathsf{Mat}_{n \times 2}(\mathbb{Z}_p),\ \vec{s} \leftarrow \mathbb{Z}_p^n$$

2. 对广义二次方程中的四种情况进行证明
   我们在开始就已经介绍，GS证明实际上是对 式$(1-4)$ 四种广义二次方程的特殊形式进行证明，对于不同的情形，给出的具体证明分别如下：【 $H_i$ 全为 0，故 $\vec{\pi}$ 中的 $\sum_{i=1}^{\eta} r_i H_i \vec{v} = 0$ 】
   2.1 配对积方程 $(\vec{A} \cdot \vec{Y})(\vec{X} \cdot \vec{B})(\vec{X} \cdot \vec{\Gamma} \vec{Y}) = t_T$ 的证明

   生成随机矩阵 $T \leftarrow \mathsf{Mat}_{2 \times 2}(\mathbb{Z}_p)$，并计算证明为：

   $$\vec{\pi} := R^\mathsf{T} \iota_2(\vec{B}) + R^\mathsf{T} \Gamma \iota_2(\vec{Y}) + (R^\mathsf{T} \Gamma S - T^{\mathsf{T}}) \vec{v}$$
   $$\vec{\theta} := S^\mathsf{T} \iota_1(\vec{A}) + S^\mathsf{T} \Gamma^\mathsf{T} \iota_1(\vec{X}) + T \vec{u}$$
   对线性方程 $\vec{A} \cdot \vec{Y} = t_T$：取 $\vec{\pi} := \vec{0}$，$\vec{\theta} := S^\mathsf{T} \iota_1(\vec{A})$，通信时发送 $S^\mathsf{T} \vec{A}$。
   对线性方程 $\vec{X} \cdot \vec{B} = t_T$：取 $\vec{\pi} := R^\mathsf{T} \iota_2(\vec{B})$，$\vec{\theta} := \vec{0}$，通信时发送 $R^\mathsf{T} \vec{B}$。
   2.2. $G_1$ 中多标量乘法方程 $\vec{A} \cdot \vec{y} + \vec{x}' \cdot \vec{b} + \vec{X}' \cdot \Gamma \vec{y} = \mathcal{T}_1$ 的证明

   生成随机矩阵 $T \leftarrow \mathsf{Mat}_{1 \times 2}(\mathbb{Z}_p)$，并计算证明向量：

   $$\vec{\pi} := R^\top \iota_2'(\vec{b}) + R^\top \Gamma \iota_2'(\vec{y}) + \left(R^\top \Gamma \vec{s} - T^\top\right) v_1$$
   $$\theta := \vec{s}^\top \iota_1(\vec{A}) + \vec{s}^\top \Gamma^\top \iota_1(\vec{X}) + T \vec{u}$$
   对线性方程 $\vec{A} \cdot \vec{y} = T_1$：取 $\vec{\pi} := \vec{0}$，$\vec{\theta} := \vec{s}^\mathsf{T} \iota_1(\vec{A})$，通信时发送 $\vec{s}^\mathsf{T} \vec{A}$。
   对线性方程 $\vec{X}' \cdot \vec{b} = T_1$：取 $\vec{\pi} := R^\mathsf{T} \iota'_2(\vec{b})$，$\vec{\theta} := \vec{0}$，通信时发送 $R^\mathsf{T} \vec{b}$。
   2.3. $G_2$ 中多标量乘法方程 $\vec{a} \cdot \vec{Y} + \vec{x}' \cdot \vec{B} + \vec{x} \cdot \Gamma \vec{Y} = \mathcal{T}_2$ 的证明

   生成随机矩阵 $T \leftarrow \mathsf{Mat}_{2 \times 1}(\mathbb{Z}_p)$，并计算证明向量为：

   $$\pi := \vec{r}^\mathsf{T} \iota_2(\vec{B}) + \vec{r}^\mathsf{T} \Gamma \iota_2(\vec{Y}) + (\vec{r}^\mathsf{T} \Gamma S - T^\mathsf{T}) \vec{v}$$
   $$\theta := S^\mathsf{T} \iota'_1(\vec{a}) + S^\mathsf{T} \Gamma^\mathsf{T} \iota'_1(\vec{x}) + T u_1$$
   对线性方程 $\vec{a} \cdot \vec{Y} = T_2$：取 $\pi := 0$，$\theta := S^\mathsf{T} \iota'_1(\vec{a})$，通信时发送 $S^\mathsf{T} \vec{a}$。
   对线性方程 $\vec{x} \cdot \vec{B} = T_2$：取 $\pi := \vec{r}^\mathsf{T} \iota_2(\vec{B})$，$\theta := 0$，通信时发送 $\vec{r}^\mathsf{T} \vec{B}$。
   2.4. $\mathbb{Z}_p$ 上二次方程 $\vec{a} \cdot \vec{y} + \vec{x}' \cdot \vec{b} + \vec{x} \cdot \Gamma \vec{y} = t$ 的证明

   生成随机矩阵 $T \leftarrow \mathbb{Z}_p$，并计算证明向量为：

   $$\pi := \vec{r}^\mathsf{T} \iota'_2(\vec{b}) + \vec{r}^\mathsf{T} \Gamma \iota'_2(\vec{y}) + (\vec{r}^\mathsf{T} \Gamma S - T) v_1$$
   $$\theta := \vec{s}^\mathsf{T} \iota'_1(\vec{a}) + \vec{s}^\mathsf{T} \Gamma^\mathsf{T} \iota'_1(\vec{x}) + T u_1$$
   对线性方程 $\vec{a} \cdot \vec{y} = t$：取 $\pi := 0$，$\theta := \vec{s}^\mathsf{T} \iota'_1(\vec{a})$，通信时发送 $\vec{s}^\mathsf{T} \vec{a}$。
   对线性方程 $\vec{x} \cdot \vec{b} = t$：取 $\pi := \vec{r}^\mathsf{T} \iota'_2(\vec{b})$，$\theta := 0$，通信时发送 $\vec{r}^\mathsf{T} \vec{b}$。

验证者 $\mathcal{V}$ 执行：

输入：$(gk, \sigma)$，一组方程以及证明 $[\ \vec{c}, \vec{d}, \vec{c}', \vec{d}', \\{\vec{\pi_i}, \vec{\theta_i}\\}_{i=1}^n \ ]$。

1. 为验证证明者知道满足配对积方程 $(\vec{A} \cdot \vec{Y})(\vec{X} \cdot \vec{B})(\vec{X} \cdot \vec{\Gamma} \vec{Y}) = t_T$ 的见证
   检查下面的等式是否成立，如果成立，则相信证明者的证明：

   $$\iota_1(\vec{A}) \cdot \vec{d} + \vec{c} \cdot \iota_2(\vec{B}) + \vec{c} \cdot \Gamma \vec{d} = \iota_T(t_T) + \vec{u} \cdot \vec{\pi} + \vec{\theta} \cdot \vec{v}$$

2. 为了验证证明者知道 $G_1$ 中多标量乘法方程 $\vec{A} \cdot \vec{y} + \vec{x}' \cdot \vec{b} + \vec{X}' \cdot \Gamma \vec{y} = \mathcal{T}_1$ 的见证
   检查下面的等式是否成立，如果成立，则相信证明者的证明：

   $$\iota_1(\vec{A}) \cdot \vec{d}' + \vec{c} \cdot \iota'_2(\vec{b}) + \vec{c} \cdot \Gamma \vec{d}' = \tilde{\iota_T}(\mathcal{T}_1) + \vec{u} \cdot \vec{\pi} + F(\theta, v_1)$$

3. 为了验证证明者知道 $G_2$ 中多标量乘法方程 $\vec{a} \cdot \vec{Y} + \vec{x}' \cdot \vec{B} + \vec{x} \cdot \Gamma \vec{Y} = \mathcal{T}_2$ 的见证
   检查下面的等式是否成立，如果成立，则相信证明者的证明：

   $$\iota'_1(\vec{a}) \cdot \vec{d} + \vec{c} \cdot \iota_2(\vec{B}) + \vec{c}' \cdot \Gamma \vec{d} = \hat{\iota_T}(\mathcal{T}_2) + F(u_1, \pi) + \vec{\theta} \cdot \vec{v}$$

4. 为了验证证明者知道 $\mathbb{Z}_p$ 上二次方程 $\vec{a} \cdot \vec{y} + \vec{x}' \cdot \vec{b} + \vec{x} \cdot \Gamma \vec{y} = t$ 的见证
   检查下面的等式是否成立，如果成立，则相信证明者的证明：

   $$\iota'_1(\vec{a}) \cdot \vec{d}' + \vec{c}' \cdot \iota'_2(\vec{b}) + \vec{c} \cdot \Gamma \vec{d}' = \iota_T'(t) + F(u_1, \pi) + F(\theta, v_1)$$

---

六、一簇二次方程可满足性的NIWI证明

前文中，我们介绍的都是证明自己知道一个见证满足某广义二次方程，这一节我们证明知道某一个见证使得一簇广义二次方程都成立。我们在这一节对这一类证明进行介绍。在开始证明之前，首先要生成证明所需要的各种参数，这个步骤在系统初始化阶段完成：

我们现在给出一个针对带双线性映射的模上的二次方程组可满足性的可组合 NIWI 证，即语言

L = \left\\{ \\{(\vec{a_i}, \vec{b_i}, \Gamma_i, t_i)\\}_{i=1}^N \ \middle| \ \exists \vec{x}, \vec{y},\ \forall i: \ \vec{a_i} \cdot \vec{y} + \vec{x} \cdot \vec{b_i} + \vec{x} \cdot \Gamma_i \vec{y} = t_i \right\\}

该证明对下列语言 $L_{\text{guilt}}$ 具有完美的 $L_{\text{guilt}}$-可靠性：

L_{\text{guilt}} = \left\\{ \quad \begin{array} \\{(\vec{a_i}, \vec{b_i}, \Gamma_i, t_i)\\}_{i=1}^N \ |\ \forall \vec{x}, \vec{y}, \ \exists i: \\ p_1(\iota_1(\vec{a_i})) \cdot \vec{y} + \vec{x} \cdot p_2(\iota_2(\vec{b_i})) + \vec{x} \cdot \Gamma_i \vec{y} \neq p_T(\iota_T(t_i)) \end{array} \quad \right\\}

注意：如果 $p_1 \circ \iota_1$、$p_2 \circ \iota_2$、$p_T \circ \iota_T$ 在 $A_1, A_2, A_T$ 上都是恒等映射，那么 $L_{\text{guilt}} = \overline{L}$，此时的 $L_{\text{guilt}}$-可靠性就是标准的可靠性。假设公共参考串由算法 $K$ 或算法 $S$ 生成，并且它们的输出在计算上不可区分。$K$ 输出的 CRS 对应可靠性设定，$S$ 输出的 CRS 对应见证不可区分设定。

1. 系统初始化
   下面给出完整 NIWI 证明过程。生成证明的第一步是生成参数：
   $$gk := (R, A_1, A_2, A_T, f) \leftarrow G(1^k)$$
   在输入 $gk$ 的情况下，返回可靠性设置下的字符串如下：
   $$\sigma := (B_1,B_2,B_T,F,\iota_1,p_1,\iota_2,p_2,\iota_T,p_T,\vec{u},\vec{v},H_1,\dots,H_\eta) \ \leftarrow\ K(gk,sk)$$
   在输入 $gk$ 的情况下，返回见证不可区分设置下的字符串如下：
   $$\sigma := (B_1,B_2,B_T,F,\iota_1,p_1,\iota_2,p_2,\iota_T,p_T,\vec{u},\vec{v},H_1,\dots,H_\eta) \ \leftarrow\ S(gk,sk)$$
   其中 $K$ 输出可靠性设置字符串，$S$ 输出见证不区分性设置字符串。

输入：公共参数 $gk$ 和 $\sigma$，二次方程组 $\\{(\vec{a_i}, \vec{b_i}, \Gamma_i, t_i)\\}_{i=1}^N$ 与见证 $\vec{x} \in A_1^m,\ \vec{y} \in A_2^n$。

证明者 $\mathcal{P}$ 执行：

1. 对变量进行承诺
   随机取： $ R \leftarrow Mat_{m \times \hat{m}}®, \quad S \leftarrow Mat_{n \times \hat{n}}® $ 并计算承诺：

   $$\vec{c} := \iota_1(\vec{x}) + R\vec{u}, \quad \vec{d} := \iota_2(\vec{y}) + S\vec{v}$$

2. 针对每个方程生成证明向量
   对每个 $(\vec{a_i}, \vec{b_i}, \Gamma_i, t_i)$：
   随机选取： $ T_i \leftarrow Mat_{\hat{n} \times \hat{m}}®, \quad r_{ij} \leftarrow R \ (j=1,\dots,\eta) $ 并计算：

   $$\vec{\pi_i} := R^\mathsf{T} \iota_2(\vec{b_i}) + R^\mathsf{T} \Gamma_i \iota_2(\vec{y}) + R^\mathsf{T} \Gamma_i S\vec{v} - T_i^\mathsf{T} \vec{v} + \sum_{j=1}^\eta r_{ij} H_j \vec{v}$$
   $$\vec{\theta}_i := S^\mathsf{T} \iota_1(\vec{a}_i) + S^\mathsf{T} \Gamma_i^\mathsf{T} \iota_1(\vec{x}) + T_i \vec{u}$$

3. 输出证明： $ \Pi := \big(\vec{c},\ \vec{d},\ {(\vec{\pi_i},\vec{\theta_i})}_{i=1}^N\big) $

验证者 $\mathcal{V}$ 执行：

输入：$(gk, \sigma)$，方程组 $\\{(\vec{a_i}, \vec{b_i}, \Gamma_i, t_i)\\}_{i=1}^N$ 以及证明 $\Pi$

1. 逐方程验证
   对每个 $i=1,\dots,N$ 检查：
   $$\iota_1(\vec{a}_i) \bullet \vec{d} + \vec{c} \bullet \iota_2(\vec{b}_i) + \vec{c} \bullet \Gamma_i \vec{d} \ =\ \iota_T(t_i) + \vec{u} \bullet \vec{\pi}_i + \vec{\theta}_i \bullet \vec{v}$$
   若全部成立，则接受证明，否则拒绝。

七、由 NIWI 扩展到 NIZK 的零知识改造

一个证明要满足零知识性，一般的可以证明存在一个模拟器可以在不知道见证的情况下模拟出一个合法的证明，此时称该证明系统满足零知识性。通俗地说：若任何看到证明的人都无法分辨这份证明到底是有见证的人做的，还是没见证的模拟器做的，那么这份证明就没有泄露见证的任何信息。

在 GS 证明中，前面构造的 NIWI（非交互式证人不可区分）证明系统已经能够在公共参考字符串下证明给定的二次方程系统成立，并保证见证不可区分性。但若直接将 NIWI 当作 NIZK 使用，模拟器在没有真实见证的情况下可能无法生成有效证明，因为方程组可能在无见证时无解。

7.1 转化为NIZK的思路解析

作者给出了一种从 NIWI 转化为NIZK 的方法，该方法的核心思路是通过引入陷门参数与额外变量，将原方程组改写为一个等价但一定有解的新系统，使得在零知识模拟时，即使没有原始见证，模拟器也能构造出“假见证”，并且使用假见证生成的证明与真实的证明分布完全一致。

1. 引入额外变量 $\delta$ 并改写方程
   在 NIWI 证明中，需证明的【原方程】为 \vec{a} \cdot \vec{y} + \vec{x} \cdot \vec{b} + \vec{x} \cdot \Gamma \vec{y} = t $，其中 $(\vec{x}, \vec{y}) 为见证。我们考虑在方程中引入一个新变量 $\delta$，并利用双线性映射 $f$ 对 $t$ 做扰动，改写为：

   $$\vec{a} \cdot \vec{y} + f(-\delta, t) + \vec{x} \cdot \vec{b} + \vec{x} \cdot \Gamma \vec{y} = 0 \tag{12}$$
   首先声明的是，上述方程针对群 $G_1,G_2$ 上的多标量乘法方程和 $\mathbb{Z}_n$ 上的二次方程，不包括配对积方程，关于配对积方程如何实现零知识性，我们在后面单独介绍。在这种情况下, 当 $\delta = 1$ 时根据定义可得 $f(-\delta,t) = -\delta t = -t$，移项后易知上述 $(12)$ 式与【原方程】等价。当 $\delta = 0$ 时 $f(-\delta,t) = 0$，此时 $\vec{x} = 0,\vec{y} = 0$ 永远满足 $(12)$ 式，模拟器的构造可基于此原理。

2. 如何在承诺空间构造与(12)式等价的证明
   由Fig. 1中映射之间的关系可知, $\iota_T(f(\delta,t)) = F(\iota_1(\delta),\iota_2(t))$。在附录一中已经说明了如何把对广义二次方程的证明转化为承诺空间中的证明。同理可将对 $(12)$ 式的证明转化为：

   $$\begin{array}{c} \vec{a} \cdot \vec{y} + f(-\delta, t) + \vec{x} \cdot \vec{b} + \vec{x} \cdot \Gamma \vec{y} = 0 \\ \Downarrow \quad \Downarrow \quad \Downarrow \\ \iota_1(\vec{a}) \bullet \iota_2(\vec{y}) + \iota_1(\vec{x}) \bullet \iota_2(\vec{b}) + \iota_1(\vec{x}) \bullet \Gamma \iota_2(\vec{y}) + F(\iota_1(-\delta),\iota_2(t)) = \iota_T(0) \tag{13} \end{array}$$
   同理，我们使用 $\vec{x},\vec{y}$ 的承诺 $\vec{c},\vec{d}$ 构造下面的等式,并使用NIWI证明中的方法设置 $\vec{\pi},\vec{\theta}$ 可得：
   $$\begin{array}{c} \iota_1(\vec{a}) \bullet \vec{d} + \vec{c} \bullet \iota_2(\vec{b}) + \vec{c} \bullet \Gamma \vec{d} + F(\iota_1(-\delta),\iota_2(t)) = \iota_T(0) \\ \Downarrow \quad \Downarrow \quad \Downarrow \\ \iota_1(\vec{a}) \bullet \vec{d} + \vec{c} \bullet \iota_2(\vec{b}) + \vec{c} \bullet \Gamma \vec{d} = F(\iota_1(\delta),\iota_2(t)) + \vec{u} \bullet \vec{\pi} + \vec{\theta} \bullet \vec{v} \end{array}$$
   如果模拟器能够随意控制 $\delta$ 的取值，那么它可以让 $(12)$ 式在真实方案与模拟方案直接自由切换，在有见证时，令 $\delta = 1$,此时直接按照真实方案的方法生成证明。在没见证时，令 $\delta = 0$ 并使用 $\vec{x} = 0,\vec{y} = 0$ 生成证明，同样可以通过验证，并且该证明与真实方案的证明不可区分。

3. 如何让模拟器能够控制 $\delta$ 的取值
   作者通过引入一个带陷门的承诺 $c$ 来实现对 $\delta$ 的控制，令 $c = \iota_1(1) + \vec{0}\ \vec{u} = \iota_1(0) + \tau \vec{u}$。容易看出，$c$ 既可以被看成使用随机性 $\vec{0}$ 对消息 1 的承诺，也可以看成使用随机性 $\vec{\tau}$ 对消息 0 的承诺。因此，只要将陷门 $\tau$ 给模拟器，他就可以自由控制 $\delta$ 的取值。
   下面考虑如何把对 $\delta$ 的承诺 $c$ 融合到验证等式 $(13)$ 中。通过定义我们容易知道，可以将 $\delta$ 作为 $\vec{x}$ 的一部分，并将 c 作为 $\vec{c}$ 的一部分。为了保证向量维度的一样，还需要对 $\vec{b},\Gamma$ 进行修改。
   首先回顾原方程相关的参数细节

   • 变量和承诺：$\vec{x} \in A_1^{m}$, $\vec{y} \in A_2^{n}$ ，$\vec{c} = \iota_1(\vec{x}) + R \vec{u} \in B_1^{m}$，$\vec{d} = \iota_2(\vec{y}) + S \vec{v} \in B_2^{n}$
   • 原方程：$\vec{a} \cdot \vec{y} + \vec{x} \cdot \vec{b} + \vec{x}^\top \Gamma \vec{y} = t$

   1. 将 $\delta$ 视为新增的 $A_1$ 变量追加到 $\vec{x}$ 末尾，并将其承诺 $c_{\delta}$ 追加到 $\vec{c}$ 的末尾，结果如下：

      $$\tilde{\vec{x}} := (\vec{x}, \delta)\ \in A_1^{m+1}, \quad c_{\delta} := \iota_1(\delta) + r_{\delta}^{\top}\vec{u}, \quad \tilde{\vec{c}} := \begin{pmatrix} \vec{c}\\ c_{\delta} \end{pmatrix} = \begin{pmatrix} \iota_1(\vec{x}) + R\vec{u} \\ \iota_1(\delta) + r_δ^{\top}\vec{u} \end{pmatrix} \in B_1^{m+1}$$
      为保证承诺能正常计算，需要同时把 $R$ 扩成增加一行的 $ \tilde{R} := \begin{pmatrix} R \ r_δ^{\top} \end{pmatrix}. $

   2. 对 $\vec{b}$ 与 $\Gamma$ 做零填充(维度对齐)以保持 $\tilde{\vec{c}} \bullet \iota_2(\cdot)$ 与 $\tilde{\vec{c}} \bullet \tilde{\Gamma} \vec{d}$ 的维度匹配，可以正常计算。

      $$\tilde{\vec{b}} := \begin{pmatrix} \vec{b}\\ 0 \end{pmatrix} \in A_2^{m+1}, \qquad \tilde{\Gamma} := \begin{pmatrix} \Gamma \\ 0_{1\times n} \end{pmatrix} \in Mat_{(m+1)\times n}(R).$$

   3. 把常数项单独写成公开双线性项 $F(c_{\delta}, -\iota_2(t))$，并验证增广后的等式为：

      $$\iota_1(\vec{a}) \bullet \vec{d} + \tilde{\vec{c}} \bullet \iota_2(\tilde{\vec{b}}) + \tilde{\vec{c}} \bullet \tilde{\Gamma} \vec{d} + F\big(c_{\delta},\ -\iota_2(t)\big) = \iota_T(0) + \vec{u} \bullet \tilde{\vec{\pi}} + \tilde{\vec{\theta}} \bullet \vec{v}$$
      则证明者的 $\tilde{\pi}, \tilde{\theta}$ 计算方式为（将 GS 单方程模板中的对象替换为维度自洽版）：

   \begin{array} \tilde{\vec{\pi}} := \tilde{R}^{\top} \iota_2(\tilde{\vec{b}}) + \tilde{R}^{\top} \tilde{\Gamma} \iota_2(\vec{y}) + \tilde{R}^{\top} \tilde{\Gamma} S \vec{v} - T_i^{\top}\vec{v} + \sum_{j=1}^{\eta} r_{ij} H_j \vec{v} \\ \tilde{\vec{\theta}} := S^{\top} \iota_1(\vec{a}) + S^{\top}\,\tilde{\Gamma}^{\top} \iota_1(\tilde{\vec{x}}) + T_i \vec{u} \end{array}

4. 模拟器如何不使用见证去模拟出一个合法的证明

   • 真实方案的证明：取 $\delta = 1$ 时表示真实方案，此时 $r_{\delta}^{\top} = \vec{0}^{\top}$，用 $r_{\delta}^{\top}$ 生成对应的证明即可。
   • 模拟器通过陷门生成的证明：由于模拟器知道陷门 $\tau$ 满足 $c_{\delta} = \iota_1(1) = \iota_1(0) + \tau^{\top}\vec{u}$。因此模拟器可以取平凡见证 $\tilde{\vec{x}}=(\vec{0}, \delta=0)$, $\vec{y}=\vec{0}$，并把 $r_{\delta}^{\top} := \tau^{\top}$，于是
     $$c_{\delta} = \iota_1(0) + r_{\delta}^{\top}\vec{u} = \iota_1(0) + \tau^{\top}\vec{u} = \iota_1(1)$$
     可以看出，只有拥有陷门的人才能令 $\delta = 0$，并使用陷门生成 $\vec{\pi},\vec{\theta}$。并且无论是 $\delta = 0$ 还是 $\delta = 1$，承诺值本身 $c_{\delta}$ 都是一样的，并且最终生成的证明都是随机化之后的，即模拟器模拟的证明和真实证明的分布不可区分。

7.2 具体的非交互式零知识证明步骤

实际上，上面的分析表明，我们可以通过引入一个新的变量 $\delta$ 对原方程进行变形，得到一个等价形式的方程，并且已经证明了，在等价形式下，可以模拟证明，且模拟出的证明与真实证明不可区分。因此在上述讨论的情况下(不包含配对积方程)，NIZK 证明实际上可以和原 NIWI 证明相同。

1. 生成系统参数： 下面给出完整的 NIZK证明，在零知识模式下，运行生成算法 $G(1^\lambda)$ 得到公共参考字符串 $gk$ 和陷门密钥 $sk$，其中： $ (gk, sk) \leftarrow G(1^\lambda), \quad sk = \tau = \vec{s}^\top \vec{u} $
   在输入 $gk$ 的情况下，返回可靠性设置下的字符串如下：
   $$\sigma = (B_1, B_2, B_T, F, \iota_1, p_1, \iota_2, p_2, \iota_T, p_T, \vec{u}, \vec{v}, \vec{\tilde{u}}, \vec{\tilde{v}}, H_1, \dots, H_\eta)$$

证明步骤如下

输入：公共参数 $gk$、可靠性设置 $\sigma$、方程集合 $\\{(\vec{a_i}, \vec{b_i}, \Gamma_i, t_i)\\}_{i=1}^N$ 及满足方程的见证 $(\vec{x}, \vec{y})$。

证明者 $\mathcal{P}$ 执行：

1. 随机选择矩阵 $R,S$ 并生成见证 $\vec{x}, \vec{y}$ 的承诺为：

   $$\vec{c} := \iota_1(\vec{x}) + R \vec{u}, \quad \vec{d} := \iota_2(\vec{y}) + S \vec{v},\ R \leftarrow Mat_{m \times \hat{m}}(\mathcal{R}), \quad S \leftarrow Mat_{n \times \hat{n}}(\mathcal{R})$$

2. 生成每个方程的证明: 对每个 $(\vec{a}_i, \vec{b}_i, \Gamma_i, t_i)$：

   • 随机选择 $T_i \leftarrow Mat_{\hat{n} \times \hat{m}}(\mathcal{R})$ 和系数 $r_{i1}, \dots, r_{i\eta} \leftarrow \mathcal{R}$。并计算：
     $$\vec{\pi_i} := R^\top \iota_2'(\vec{b_i}) + R^\top \Gamma_i \iota_2'(\vec{y}) + R^\top \Gamma_i S \vec{v} - T_i^\top \vec{v} + \sum_{j=1}^\eta r_{ij} H_j \vec{v}$$
     $$\vec{\theta}_i := S^\top \iota_1(\vec{a}_i) + S^\top \Gamma_i^\top \iota_1(\vec{x}) + T_i \vec{u}$$

3. 输出证明：$(\vec{c}, \vec{d}, \\{(\vec{\pi_i}, \vec{\theta_i})\\}_{i=1}^N)$

验证者 $\mathcal{V}$ 执行：

输入：公共参考字符串 $gk$、方程集合 $\{(\vec{a_i}, \vec{b_i}, \Gamma_i, t_i)\}_{i=1}^N$ 和证明 $(\vec{c}, \vec{d}, \\{(\vec{\pi}_i, \vec{\theta}_i)\\})$

对每个 $i$ 检查下面的式子，若全部成立，输出 1；否则输出 0。

$$\iota_1(\vec{a}_i) \bullet \vec{d} + \vec{c} \bullet \iota_2(\vec{b}_i) + \vec{c} \bullet \Gamma_i \vec{d} \overset{?}{=} \iota_T(t_i) + \vec{u} \bullet \vec{\pi}_i + \vec{\theta}_i \bullet \vec{v}$$

---

模拟器工作过程

输入：公共参考字符串 $gk$、陷门 $\tau$、方程集合 $\{(\vec{a}_i, \vec{b}_i, \Gamma_i, t_i)\}$。

1. 对每个方程引入 $\delta$ 并改写下式，并取 $\vec{x} = \vec{0}, \vec{y} = \vec{0}, \delta = 0$ 作为假见证生成证明。

   $$\vec{a}_i \cdot \vec{y} + f(\delta, -t_i) + \vec{x} \cdot \vec{b}_i + \vec{x} \cdot \Gamma_i \vec{y} = 0$$

2. 由于模拟器持有 $\tau$，因此它能使用模拟器构造证明 $\vec{\pi_i},\vec{\theta_i}$，在不知道见证的情况下模拟证明。

Appendix 1

这部分将证明验证 $(9)$ 式中的两个等式是等价的，
从 Fig. 1 中可知，本文构造的嵌入映射和投影映射以及双线性映射之间满足可交换性。 即对任意标量/群元 $X,Y$ 有 $ F(\iota_1(X),\iota_2(Y)) = \iota_T(f(X,Y)), \ f(p_1(X),p_2(Y)) = p_T(F(X,Y)) $， 即先在原空间计算双线性 $f(X,Y)$ 再嵌入，与先将 $X,Y$ 嵌入承诺空间再计算 $F$ 是等价的。
还容易证明 $ \iota_2(\Gamma\vec{y}) = \Gamma\iota_2(\vec{y}) $ 成立，即在原空间先进行矩阵–向量乘法，再嵌入承诺空间，等价于先嵌入每个坐标再做矩阵–向量乘法。这一性质成立的原因是 $\iota_2$ 是逐坐标的线性嵌入： 若 $\vec{y} = (y_1, \dots, y_m)$，$\iota_2(\vec{y}) = (\iota_2(y_1), \dots, \iota_2(y_m))$，而矩阵 $\Gamma$ 对 $\vec{y}$ 的作用是按标量加权求和。由于 $\iota_2$ 是线性映射，矩阵乘法中的标量乘与加法在嵌入后保持不变，因此满足上述交换关系。
上述映射之间存在的特殊关系保证了原空间和承诺空间的双线性运算完全对齐。

1. 引理（逐项恒等）
   首先我们证明，对任意向量与矩阵，有以下关系成立：
   

   $$\iota_1(\vec{a})\bullet \iota_2(\vec{y}) = \iota_T(\vec{a}\cdot \vec{y}),\quad \iota_1(\vec{x})\bullet \iota_2(\vec{b}) = \iota_T(\vec{x}\cdot \vec{b}), \quad \iota_1(\vec{x})\bullet \Gamma \iota_2(\vec{y}) = \iota_T(\vec{x}\cdot \Gamma \vec{y})$$
   以第一式为例证明，第二式同理，第三式利用线性相容性 $\iota_2(\Gamma\vec{y}) = \Gamma \iota_2(\vec{y})$ 即可推出。
   
   $$\iota_1(\vec{a})\bullet \iota_2(\vec{y}) = \sum_i F(\iota_1(a_i), \iota_2(y_i)) = \sum_i \iota_T(f(a_i,y_i)) = \iota_T \Big(\sum_i f(a_i,y_i)\Big) = \iota_T(\vec{a}\cdot \vec{y})$$

2. 首先证明原式成立暗含着承诺式成立
   若原式 $(7)$ 式成立，也就是 $ \vec{a} \cdot \vec{y} + \vec{x} \cdot \vec{b} + \vec{x} \cdot \Gamma \vec{y} = t, $ 成立，则由上面介绍的引理、结合线性嵌入映射 $\iota_i$ 的线性性质可得: 承诺空间中的式 $(9)$ 也成立，推导过程如下：
   

   $$\begin{aligned} &\iota_1(\vec{a})\bullet \iota_2(\vec{y}) +\iota_1(\vec{x})\bullet \iota_2(\vec{b}) +\iota_1(\vec{x})\bullet \Gamma\,\iota_2(\vec{y}) \\ &= \iota_T(\vec{a}\cdot \vec{y}) + \iota_T(\vec{x}\cdot \vec{b}) + \iota_T(\vec{x}\cdot \Gamma \vec{y}) \\ &= \iota_T \big(\vec{a}\cdot \vec{y} + \vec{x}\cdot \vec{b} + \vec{x}\cdot \Gamma \vec{y}\big) \\ &= \iota_T(t) \end{aligned}$$

3. 然后证明承诺式成立暗含着原式成立
   若承诺空间中的式 $(9)$ 式 $ \iota_1(\vec{a})\bullet \iota_2(\vec{y}) +\iota_1(\vec{x})\bullet \iota_2(\vec{b}) +\iota_1(\vec{x})\bullet \Gamma \iota_2(\vec{y}) = \iota_T(t) $ 成立，且存在投影 $p_T$ 使 $p_T\circ\iota_T = \mathrm{id}$ 是恒等映射【通过合适的实例化可以实现】，则承诺空间的值可以通过 $p_T$ 去掉噪声恢复到原空间的结果。此时对两边施加 $p_T$ 可得原式 $(7)$ 成立：

   $$\vec{a}\cdot \vec{y} + \vec{x}\cdot \vec{b} + \vec{x}\cdot \Gamma \vec{y} = p_T(\iota_T(t)) = t,$$

Appdendix 2

下面说明为什么 $p_T$ 取下面的值时，可以把承诺里的噪声完全消去并恢复出真正的配对值。

$$p_T \left( \begin{pmatrix} a & b\\ c & d \end{pmatrix} \right)=d\cdot a^{\alpha_1\alpha_2}\cdot b^{-\alpha_1}\cdot c^{-\alpha_2}$$

在可靠性设置下，$u_1=(P_1,\alpha_1 P_1)\in B_1,\ v_1=(P_2,\alpha_2 P_2)\in B_2$，并且 $\iota_1(X)=(\mathcal O,X)$，$\iota_2(Y)=(\mathcal O,Y)$；我们容易算出 $r_1u_1 + r_2u_2 = (r_1 + r_2t)u_1$，如果令 $r = r_1 + r_2 t$，则对见证 $X\in G_1,\ Y\in G_2$的承诺可写为:

$$\vec c=\iota_1(X)+r u_1=(rP_1,\ X+\alpha_1 rP_1), \vec d=\iota_2(Y)+s v_1=(sP_2,\ Y+\alpha_2 sP_2).$$

此时，

$$F(\vec{c},\vec{d}) = \begin{pmatrix}a & b\\ c & d \end{pmatrix} = \begin{pmatrix} e(rP_1,sP_2) & e(rP_1,\,Y+\alpha_2 sP_2) \\ e(X+\alpha_1 rP_1,\,sP_2) & e(X+\alpha_1 rP_1,\,Y+\alpha_2 sP_2) \end{pmatrix}.$$

利用双线性展开：

$$\begin{aligned} a &=e(P_1,P_2)^{rs},\\ b &=e(P_1,Y)^r\ \cdot\ e(P_1,P_2)^{\alpha_2 rs},\\ c &=e(X,P_2)^s\ \cdot\ e(P_1,P_2)^{\alpha_1 rs},\\ d &=e(X,Y)\ \cdot\ e(X,P_2)^{\alpha_2 s}\ \cdot\ e(P_1,Y)^{\alpha_1 r}\ \cdot\ e(P_1,P_2)^{\alpha_1\alpha_2 rs}. \end{aligned}$$

计算

$$\begin{aligned} d\cdot a^{\alpha_1\alpha_2}\cdot b^{-\alpha_1}\cdot c^{-\alpha_2} &=\Big[e(X,Y)\, e(X,P_2)^{\alpha_2 s}\, e(P_1,Y)^{\alpha_1 r}\, e(P_1,P_2)^{\alpha_1\alpha_2 rs}\Big]\\ &\quad\cdot\Big[e(P_1,P_2)^{rs}\Big]^{\alpha_1\alpha_2}\\ &\quad\cdot\Big[e(P_1,Y)^r\, e(P_1,P_2)^{\alpha_2 rs}\Big]^{-\alpha_1}\\ &\quad\cdot\Big[e(X,P_2)^s\, e(P_1,P_2)^{\alpha_1 rs}\Big]^{-\alpha_2}. \end{aligned}$$

逐底数归并指数：

• 对 $e(X,P_2)$：指数为 $\alpha_2 s - \alpha_2 s = 0$；
• 对 $e(P_1,Y)$：指数为 $\alpha_1 r - \alpha_1 r = 0$；
• 对 $e(P_1,P_2)$：指数为 $ \alpha_1\alpha_2 rs + \alpha_1\alpha_2 rs - \alpha_1\alpha_2 rs - \alpha_2\alpha_1 rs = 0. $

于是只剩 $ p_T(B_T) = d\cdot a^{\alpha_1\alpha_2}\cdot b^{-\alpha_1}\cdot c^{-\alpha_2}=e(X,Y). $

1. 对嵌入映射 $\iota_T(Z)=\begin{pmatrix}1&1\\1&Z\end{pmatrix}$ 有： $ p_T(\iota_T(Z))=Z\cdot 1^{\alpha_1\alpha_2}\cdot 1^{-\alpha_1}\cdot 1^{-\alpha_2}=Z. $
2. 对任意 $X,Y$ 有 $ p_T \Big(F(\iota_1(X),\iota_2(Y))\Big) = p_T \left(\begin{pmatrix}1&1\1&e(X,Y)\end{pmatrix}\right) = e(X,Y) $$

因此，这个 $p_T$ 的定义正是利用 $u_1,v_1$ 引入噪声的结构，选择恰当幂次使噪声在四个条目间相互抵消，最终恢复出真实的配对值。可以看出，这种定义使得 $p_T \circ \iota_T$ 是恒等映射。

Appendix 3

这里给出 GS证明 中，证明见证满足 $(2)(3)(4)$ 时的公共惨开字符串设置。

2. 对于群 $G_1$ 或 $G_2$ 上的多标量乘法方程，公共参考字符串被实例化为：
   接下来，我们实例化用于 $G_2$ 中多标量乘法方程的公共参考字符串；$G_1$ 情形完全对称。

   • $R=\mathbb{Z}_p,\quad A_1=\mathbb{Z}_p,\quad A_2=G_2,\quad A_T=G_T$。
   • 辅助空间：$B_1=G_1^2,\ B_2=G_2^2,\ B_T=G_T^4$。
   • 记 $u=(P_1,\alpha_1 P_1)\in B_1,\ \ v=(P_2,\alpha_2 P_2)\in B_2$。
   • 标量嵌入映射：$\iota'_1(x):=x u\in B_1$。
   • 群元嵌入映射：$\iota_2(Z):=(\mathcal O,Z)\in B_2$。
   • 标量投影映射： $p_1'(z_1 P, z_2 P) := z_2 - \alpha z_1$
   • 群元投影映射： $p_2(P, Q) := Q - \alpha P$
   • 双线性映射 $f: f(x,Y) := xY $
   • 由 $F:B_1\times B_2\to B_T$（按坐标配对）定义 $\hat{\iota}_T$ 和 $\hat p_T$
     $$\hat{\iota}_T(Z)\ :=\ F(\iota'_1(1),\ \iota_2(Z))\ =\ F(u,\ (\mathcal O,Z))\in B_T$$
     $$\hat p_T\ :=\ e^{-1} (p_T(z)),\ where: e^{-1}(e(P_1,Z)):=Z$$

   在可靠性设置下，$\hat p_T\circ \iota_T=\mathrm{id}_{G_2}$ 成立。由线性与双线性，任意 $x\in\mathbb Z_p,\ Y\in G_2$ 有

   $$F(\iota'_1(x),\ \iota_2(Y))\ =\ F(xu,\ (\mathcal O,Y)) \ =\ x\cdot F(u,\ (\mathcal O,Y)) \ =\ x\cdot \iota_T(Y) \ =\ \iota_T(xY)$$

   因而 Fig.1 的可交换性 $F(\iota_1'(x),\iota_2(Y))=\iota_T(f(x,Y))$ 成立。【其他需要的性质易证】
   综上所述，用上述公共字符串的实例化，多标量乘法方程 $f(x,Y)=xY$ 可嵌入到与配对积方程相同的 NIWI 骨架中；$G_1$ 中的多标量乘法完全对称（交换 $G_1,G_2$ 的角色并相应替换映射）。

3. 对于 $\mathbb{Z}_p$ 上的二次方程，公共参考字符串被实例化为：
   接下来，我们实例化用于 $\mathbb{Z}_p$ 上的二次方程的公共参考字符串如下：

   • $R=\mathbb{Z}_p,\quad A_1=\mathbb{Z}_p,\quad A_2=\mathbb{Z}_p,\quad A_T=\mathbb{Z}_p$。
   • 辅助空间仍取 $B_1=G_1^2,\ B_2=G_2^2,\ B_T=G_T^4$。
   • 仍记 $u=(P_1,\alpha_1 P_1)\in B_1,\ v=(P_2,\alpha_2 P_2)\in B_2$。
   • 标量嵌入：$\iota'_1(x):=x\,u\in B_1,\quad \iota'_2(y):=y\,v\in B_2$。
   • 投影映射： $ p’_1(x_1P_1,\ x_2P_1)\ :=\ x_2-\alpha_1 x_1, p’_2(y_1P_2,\ y_2P_2)\ :=\ y_2-\alpha_2 y_1 $
   • 定义
     $$\iota'_T(t)\ :=\ F(\iota'_1(1),\ \iota'_2(t))\ =\ F(u,\ t v)\in B_T$$
   $$p_T'(z)\ :=\ \log_{\,e(P_1,P_2)} \big(p_T(z)\big)\ \in\ \mathbb Z_p$$

   其中 $p_T: B_T\to G_T$ 为配对积方程部分定义的消噪投影。于是 $p_T'\circ \iota_T'=\mathrm{id}_{\mathbb Z_p}$。
   由线性与双线性：

   $$F(\iota_1'(x),\ \iota_2'(y))\ =\ F(xu,\ yv)\ =\ xy\cdot F(u,v)\ =\ \iota_T'(xy).$$
   • 与 $p'_1,p'_2,p'_T$ 的一致性（对任意 $x_1,x_2,y_1,y_2\in\mathbb Z_p$）：
     $$\begin{array}{c} p_1'(x_1P_1,x_2P_1)\ \cdot\ p_2'(y_1P_2,y_2P_2) = (x_2-\alpha_1 x_1)(y_2-\alpha_2 y_1) \\ = p_T' \Big(F\big((x_1P_1,x_2P_1),\ (y_1P_2,y_2P_2)\big)\Big) \end{array}$$

   综上所述：用上述 $\iota'_1,\iota'_2,\iota'_T$ 与 $p'_1,p'_2,p'_T$ 的实例化，标量二次约束 $xy=t$（或更一般的二次式）可嵌入与配对积方程相同的 NIWI 框架中，且满足 Fig.1 的可交换与投影恢复性质。