格密码学进阶09：基于GSW的NIZK（下）

Posted on Oct 23, 2020

格密码学进阶09：基于GSW的NIZK（下）

上期回顾

上期，我们看到了【KW17】中基于GSW的NIZK构造。大概的构造思路是基于GSW全同态加密（FHE）的变种，即全同态承诺（FHC）。

基于GSW FHC，Prover可以把要证明NP Relation的witness $ w $的承诺发送给Verifier，然后Verifier基于承诺$ c_w $同态计算证明电路$ C_x(\cdot) $。最后，Prover提供一个opening，可以让Verifier打开计算之后的结果，看到电路的输出。如果$ C_x(w) = 0 $，那么代表witness有效，证明也就通过了。

在上期的最后，我们也看到了【KW17】的NIZK的构造，虽然基于FHC的idea很有意思，但是也有两个缺陷。一个是同态承诺的opening $ \mathbf{R}_{C_x, w} $在概率分布上会暴露出和$ w $有关的信息。另一个更大的问题是，如果Prover没有遵守协议，并没有一开始诚实的发送一个GSW FHC的承诺$ c_w $的话，那么整个协议就失去了意义，毫无Soundness可言。

这期，我们就来着重的看看如何解决这两大问题，最后得到【KW17】的完全构造～

Soundness的问题

首先，我们来看看如何解决最大的问题，即Soundness的问题。

我们知道，如果Prover并不会诚实的构造GSW FHC承诺的话，那么整个协议就会失去所有的可信度。但是比较头疼的是，我们并没有一个非常好的方法来“证明”Prover发送给Verifier承诺$ c $真的是基于witness $ w $诚实构造的GSW FHC承诺。最好的证明方法就是直接把$ w $发送过去，但是这违背了我们原本零知识的要求。

我们在上期的结尾也稍微讨论过，还有一种可能性就是Prover可以事先零知识地证明他所公开的承诺是一个诚实构造的GSW FHC承诺。如果使用了别的NIZK方案，那肯定会变相的基于其他方案中的假设。但是由于我们在这里就是在尝试构造纯粹基于Lattice假设的零知识证明，所以这种方法并不可取。

从NIZK到Preprocessing NIZK

乍一看，似乎我们已经束手无策了，没有办法通过GSW FHC来构造真正的NIZK。

因为真正的NIZK要求过于苛刻，Prover没有办法说服Verifier他发送的承诺是诚实的，所以我们现在卡在了这个点上无法继续下去。既然如此，我们可不可以放松对于NIZK的要求，使得我们可以绕过这个问题呢？

一个最简单的放松（relaxation）版本，就是Preprocessing NIZK，即加入一个预处理（Preprocessing）的阶段。在Preprocessing的阶段，一个协议的双方（即Prover与Verifier）可以委托一个可信的第三方（Trusted Third Party，TTP）进行一系列诚实的参数生成操作。

在参数生成阶段完成之后，TTP会把生成的参数分为两组：属于Prover的参数$ k_p $，与属于Verifier的参数$ k_v $。最后，TTP会把这两组参数秘密的发送给Prover与Verifier。在整个初始化的阶段中，Prover和Verifier都可以完全相信TTP生成的参数是诚实生成的，不会有任何造假的部分。

对于这一类由TTP生成参数并且发送给协议双方的结构，我们称之为Trusted Setup（可信初始化）。对于zkSNARK以及隐私货币技术比较熟悉的读者们可能对于这个定义并不陌生，我们在这里就不多描述了。

我们还可以把TTP做的部分替换成一个MPC协议来完成。因为协议双方完全信赖TTP，并且TTP也不会作假，这一要求和MPC能带给我们的非常相似。这样的话，Prover与Verifier只需要在协议的一开始进行一次MPC，就可以相互得到对应的初始化参数$ k_p, k_v $了。

基于Preprocessing Model的第一次尝试

当我们relax了对于NIZK的定义，采用了Preprocessing Model之后，相比起原来的NIZK规定，我们额外的多拥有了一次可信初始化的机会。

即然我们之前遇到的问题在于Prover没法证明他生成的承诺是可信的（诚实的），那我们索性缺啥补啥：直接在可信初始化阶段生成证明所需要的承诺$ c_w $。

图上描述的就是【KW17】中基于我们的这一想法所做的第一次尝试。

我们可以看到，现在在Trusted Setup的环节，Prover悄悄地把他的witness $ w $告诉TTP，然后TTP就根据$ w $的值诚实的生成了对应的Commitment $ c_w $以及对应的opening $ \mathbf{R}_w $。随后，TTP把Commitment和Opening发送给Prover，而只把Commitment发给Verifier。

进行Trusted Setup之后，Prover和Verifier就可以和我们之前描述的步骤一样完成协议了！由于Verifier已经知道诚实构造的承诺$ c_w $了，所以Prover只需要基于$ w $的信息，通过我们上期描述的Input-dependent Evaluation计算出对应计算$ C_x $的opening $ \mathbf{R}_{C_x, w} $，随后再发送给Verifier就完成证明了。

当Verifier收到opening $ \mathbf{R} $之后，他只需要使用Input-independent Evaluation，即在承诺上同态计算$ C_x $，随后再用我们之前描述过的$ Open $算法验证Prover发过来的opening，就知道证明是否能够通过了。

我们注意到，在这里我们的NIZK体系的soundness问题已经被完全解决了，因为任何需要诚实完成的部分都被我们挪到了TTP的Trusted Setup环节，这样一来似乎可以大功告成了。

Reusable Trusted Setup

然而，我们现在得到的Preprocessing NIZK的结构仍然有不尽人意的地方。

如果我们仔细观察之前的图例，我们会发现，在Trusted Setup的过程中，Prover就需要把他的witness $ w $告诉TTP，以便完成初始化阶段。这代表着每更换一次witness都需要重新进行可信初始化！对zkSNARK的Trusted Setup环节熟悉的读者可能对这个不陌生，这基本上代表了如果Prover想要证明别的witness，或者是证明别的东西（那么witness也会相对跟着改变），协议的双方就需要重新进行一次Trusted Setup。

如果我们不依靠TTP，而是通过MPC协议来进行初始化的话，这就代表Prover和Verifier时不时的就要进行计算非常昂贵的MPC协议，以便确保双方都能拥有最新的witness的承诺。

这一点，直接就把我们的Preprocessing NIZK的构造推下了深渊。原本看起来非常简单实用的idea，现在变成一个一次性的，效率不是很高的协议。

当Kim与Wu探索到这里的时候，他们心中的疑惑和我们相同：能不能想办法使得Trusted Setup所生成的参数可以被反复使用（reusable）呢？换句话说，能不能进行一次Trusted Setup，但是生成的参数可以用与证明各种各样的问题的NIZK呢？

对于一次初始化之后，可以证明各种问题的NIZK，我们称之为Multi-theorem Preprocessing NIZK，这也就是【KW17】这一篇paper的标题了。

Adding a Layer of Indirection

为什么我们之前的Preprocessing NIZK构造只能用于一次证明呢？这是因为在Trusted Setup的过程当中，Prover必须要向TTP揭露witness $ w $的信息，这也就代表了整个协议的初始化阶段是和witness所绑定的。

如果我们想要使得这个协议可以通过一次Trusted Setup就可以证明多个问题的话，那么我们必须得从Trusted Setup中移除任何和witness有关的部分。在【KW17】中，Kim与Wu所做的，是加入了一层Indirection Layer（间接层），使得初始化生成的承诺可以用于生成多个不同的NIZK。

这是怎么实现的呢？我们来看第二次尝试的具体协议结构。

根据图中所示，Kim与Wu所做的第二次尝试，就是在Trusted Setup的阶段生成了一个和证明所需要的witness无关的一组承诺：一个用于加密用的密钥$ k $。

具体的来说，在Trusted Setup阶段，TTP会随机的生成一个对称加密用的密钥$ k $。这里使用的对称加密算法可以是任意的算法，比如AES等，具体的实现算法并不重要。随后，TTP会诚实的生成对于$ k $的一个GSW FHC承诺$ c_k $，以及对应的打开这个承诺的randomness $ \mathbf{R}_k $。最后Prover可以看到$ k, c_k, \mathbf{R}_k $，而Verifier只能看到对于密钥的承诺$ c_k $。

当我们把NIZK系统如此初始化完成之后，Prover手上就拥有了一个对称加密的密钥$ k $，而Verifier拥有了一个$ k $的承诺。

这个时候，假如说Prover想要向Verifier证明他拥有满足证明电路$ C_x(\cdot) $的witness $ w $的话，只需要做以下三步：

首先，Prover把他选择的witness $ w $用密钥$ k $在选定的对称加密系统下加密，得到$ ct \leftarrow Encrypt(k, w) $。
随后是最精髓的一步，Prover把证明所用的公共参数$ x $以及刚刚生成的密文$ ct $嵌入在电路中，构造出如下的一个新的电路$ f_{x, ct}(\cdot) $：

$$ f_{x, ct}(k) = C_x(Decrypt(k, ct)) = C_x(w) $$

这个电路的输入是密钥$ k $，而输出是我们原本证明电路的输出$ C_x(w) $！它做的事情等于就是把Prover生成的$ ct $使用$ k $对称解密，还原回原本的witness $ w $，然后再通过原本的证明电路，得到$ C_x(w) $。

得到这个新的电路之后，Prover就可以根据$ f_{x, ct} $的具体构造，再加上已知$ k $的内容，通过Input-Dependent Evaluation得到对应的同态承诺的Opening $ \mathbf{R}{f{x, ct}, k} $！

最后Prover就把$ C_x, ct, \mathbf{R}{f{x, ct}, k} $打个包全部发给Verifier，就完成NIZK啦。

当Verifier收到了Proof之后，他就需要根据$ C_x $和$ ct $的内容重新构建出电路$ f_{x, ct} $出来。随后他可以在原本得到的承诺$ c_k $上同态的计算（Input-Independent Evaluation）电路$ f_{x, ct} $，最后得到对应了证明电路输出结果的承诺$ c_{C_x(w)} $。得到了这个承诺之后，他就可以使用Prover发送过来的randomness opening $ \mathbf{R}{f{x, ct}, k} $来打开并且检查这个承诺啦。

注意这里的Trusted Setup中没有任何一点提及到$ C_x $或者$ w $的内容，所以这个协议可以反复的使用！每次只需要Prover在Proof中添加对于问题的证明电路$ C_x $的描述，Verifier就可以根据这个描述以及$ ct $来重新构建一个新的$ f_{x, ct} $出来，然后完成NIZK的验证啦。

我们通过修改最初的FHC承诺中的内容实现了重复使用初始化参数的要求，随后再基于承诺中的密钥$ k $加密/解密真正用于证明的witness，从而实现了证明电路的计算。这样一来，我们就得到了【KW17】中描述的Multi-theorem Preprocessing NIZK的大致雏形了。

安全性总结

自从添加了新的一层Indirection之后，我们整个协议的安全性发生了一些变化。因为现在Verifier额外还能看到$ ct $，即witness $ w $的密文，我们要求所选的对称加密算法是语义安全（Semantic Secure）的。这样的话，旁观者就不能从$ ct $中提取出$ w $有关的信息。

同时，我们在选择对称加密算法的时候，最好选择解密电路较为简单的算法，因为对于Verifier来说，他等同于是要在Commitment密文中同态解密其中的witness，如果解密电路较为复杂，那么整个Proof的验证计算量就会变得很大。

虽然对于选择的对称加密算法没有过多的要求，但是如果我们只想要基于Lattice的难题假设的话，要么我们就要选择不基于任何假设的算法，如AES等，或者是同样基于Lattice problem（如LWE/SIS）的加密算法，如Regev。

Opening的问题

解决了最重要的Soundness问题，接下来我们就可以来看之前提到过的Opening的问题了。

我们基于新的模型，再复述一下之前描述的问题本身：因为Prover公开的Opening $ \mathbf{R}{f{x, ct}, k} $包含了密钥$ k $本身的信息，所以如果Verifier看到了多个$ \mathbf{R} $矩阵之后，可以根据$ \mathbf{R} $矩阵的概率分布分析出和$ k $的分布有关的信息来。虽然并不能直接让Verifier知道密钥$ k $的具体值，但是这一信息的泄漏直接导致了整个协议并不是Zero Knowledge的。

解决这个问题其实并不复杂，我们和解决上一个问题一样，再增加一层Indirection：如果Prover不揭露Opening $ \mathbf{R} $的内容，而是向Verifier公开一个只有拥有了$ \mathbf{R} $才能计算的某个难题的解，那么只要Verifier验证了这个解是正确的，那么就代表Prover肯定知道正确的Opening $ \mathbf{R} $了。

在【KW17】中，Kim与Wu使用的Indirection Layer是一个和我们之前讨论的Lattice IBE/ABE相同的SIS问题。通过巧妙的把NIZK中用到的承诺嵌入在SIS问题实例中，只要Prover知道对应同态承诺的randomness $ \mathbf{R} $，他就等同于拥有了对应这个SIS实例的MP12 Trapdoor，然后就可以生成SIS问题的解了。这样我们就可以让Prover间接的“证明”他真的知道$ \mathbf{R} $而不暴露任何一点其他的信息。

接下来，我们来看看到底是怎么实现的。我们知道，在协议的一开始，Prover和Verifier手中所持有的关于密钥$ k $的承诺结构如下： $$ c_k = \mathbf{AR}k + k \mathbf{G} $$ 随后，因为Prover知道$ k $的值，所以他可以基于$ \mathbf{R}k $和证明电路$ f{x, ct} $的信息，通过Input-Dependent Evaluation计算出证明结果的承诺： $$ c{f_{x,ct}(k)} = \mathbf{AR}{f{x, ct}, k} + f_{x, ct}(k) \cdot \mathbf{G} $$ 在这里，为了更加方便的表述【KW17】中的SIS问题和MP12 Trapdoor的关系，我们修改一下证明电路$ f_{x, ct} $的定义，使得当证明电路通过（输出0）的时候，我们的$ f $电路会反向输出1： $$ \begin{align*} f_{x, ct}(k) &= 1 - C_x(Decrypt(k, ct)\ &= 1 - C_x(w)\ &= \begin{cases} 1, & C_x(w) = 0\ 0, & \text{otherwise} \end{cases} \end{align*} $$ 这样一来，如果Prover拥有正确的witness $ w $的话，那么$ f_{x, ct}(k) $就会输出1。那么我们最后得到的承诺就是： $$ c_{f_{x, ct}(k)} = \mathbf{AR}{f{x, ct}, k} + \mathbf{G} $$ 同理，当Verifier拿到密钥的承诺$ c_k $之后，他也可以通过Input-Independent Evaluation来同态计算电路$ f_{x, ct} $，得到同样的证明结果承诺$ c_{f_{x, ct}(k)} $。

引入MP12 Trapdoor

我们观察发现，承诺$ c_{f_{x, ct}(k)} $的结构，刚好符合了生成MP12 Trapdoor的结构。在详细描述之前，我们再来重新回顾一下MP12的Trapdoor的大致构造。

首先，MP12的目的就是可以构造一个Lattice Trapdoor，已知矩阵$ \mathbf{A} $的Trapdoor $ \mathbf{R} $的话，就可以任意的解开基于$ \mathbf{A} $构造的SIS与LWE问题。对于LWE问题，因为是单射的，所以我们可以还原出正确的一个解。对于SIS问题，因为解的空间到目标空间是满射的（同一个SIS问题有多个解），所以更为复杂一点，我们需要随机的在高斯分布中取出一个符合要求的解，并且这个分布不能暴露Trapdoor的信息。

我们先定义基于矩阵$ \mathbf{A} $的SIS函数为： $$ f_\mathbf{A}(\mathbf{v}) = \mathbf{A} \mathbf{v} \text{ mod }q $$ 基于矩阵$ \mathbf{A} $的LWE函数为： $$ g_\mathbf{A}(\mathbf{s, e}) = \mathbf{As + e} \text{ mod }q $$ MP12的构造方法大致分三部分：

找到基于工具矩阵（Gadget Matrix）$ \mathbf{G} $下的SIS与LWE反函数$ f_\mathbf{G}^{-1}, g_\mathbf{G}^{-1} $。这一步很简单，详细的可以参考Lattice Trapdoors的那一篇文章。
基于$ \mathbf{G} $矩阵，一个随机生成的$ \mathbf{B} $矩阵和选定的一个随机的短randomness $ \mathbf{R} $，构造出平均随机分布的$ \mathbf{A} $矩阵。这个$ \mathbf{A} $矩阵的构造可以让我们在知道了Trapdoor $ \mathbf{R} $之后，轻松的把$ \mathbf{A} $矩阵轻易的变回$ \mathbf{G} $矩阵：

$$ \mathbf{A} = [\mathbf{B \vert G - BR}]\ \mathbf{A} \cdot \begin{bmatrix} \mathbf{R}\ \mathbf{I} \end{bmatrix} = \mathbf{G} $$

给定一个基于$ \mathbf{A} $的SIS或者LWE问题，我们使用$ \mathbf{R} $的信息和之前生成的反函数$ f_\mathbf{G}^{-1}, g_\mathbf{G}^{-1} $生成真正的SIS与LWE反函数$ f_\mathbf{A}^{-1}, g_\mathbf{A}^{-1} $。

【KW17】的idea是这样的：与其让Prover直接揭露出他用于同态承诺的randomness $ \mathbf{R}{f{x, ct}, k} $，不如实现约定好一个随机分布的矩阵$ \mathbf{A} $和一个random target vector $ \mathbf{u} $，然后让Prover找到一个短的SIS解向量$ \mathbf{v} $使得$ \mathbf{Av = u} \text{ mod }q $。

不过这里设计的精髓在于，只要Prover知道了正确的$ \mathbf{R}{f{x, ct}, k} $，那么这个$ \mathbf{R} $矩阵恰巧就是$ \mathbf{A} $矩阵的MP12 Trapdoor。只要运用我们上面描述的第三步，解开这个SIS challenge就小菜一碟了。

同时，为了确保ZK的要求，我们需要巧妙的设计这个$ \mathbf{A} $矩阵，使得我们能够构造出一个simulator。这个simulator可以在不知道$ k $和对应$ k $的randomness $ \mathbf{R}k $的情况下，只需要知道同态计算所用的电路$ f{x, ct} $就可以模拟出正常协议下的所有transcript的概率分布。

为了实现这两条要求，【KW17】构造了如下结构的一个平均随机分布的SIS问题矩阵$ \mathbf{A} $： $$ \mathbf{A} = [\mathbf{A}_1 \vert \mathbf{A}_2] $$ 对于一个这样结构的$ \mathbf{A} $矩阵，可能存在两种不同的Trapdoor：

假如$ \mathbf{A}_1 $是一个使用MP12 sample的带有Trapdoor $ \mathbf{R} $的平均随机分布矩阵，而$ \mathbf{A}_2 $可以是任何结构的矩阵，那么我们可以很简单的找到$ \mathbf{A} $的Trapdoor：

$$ [\mathbf{A}_1 \vert \mathbf{A}_2] \cdot \begin{bmatrix} \mathbf{R}_1\\mathbf{0} \end{bmatrix} = \mathbf{G} $$

假如$ \mathbf{A}_1 $是一个没有Trapdoor的随机矩阵，$ \mathbf{R}_2 $是一个随机短矩阵，而$ \mathbf{A}_2 = \mathbf{A}_1 \mathbf{R}_2 \pm \mathbf{G} $，那么我们可以找到另一个Trapdoor：

$$ [\mathbf{A}_1 \vert \mathbf{A}_2] \cdot \begin{bmatrix} \mp\mathbf{R}_2\\mathbf{I} \end{bmatrix} = \mathbf{G} $$

如果我们观察这两种情况，我们会发现他们的概率分布极其相似。

在1里面，$ \mathbf{A}_1 $是MP12 sample的随机矩阵，因为Leftover Hash Lemma，所以我们无法分辨它与uniform random distribution的区别。而$ \mathbf{A}_2 $是任意sample的，自然也是随机分布的。

而在2当中，$ \mathbf{A}_1 $是一个随机sample的uniform random矩阵，而$ \mathbf{A}_2 $的构造因为Leftover Hash Lemma也是uniform random的distribution。

这也就是说，给定一个$ \mathbf{A} $矩阵，我们无法分辨它到底来自于1号平行世界，还是2号平行世界。这对于构造ZK的模拟器来说是再好不过的了。

构造SIS Challenge

简单的来说，simulator在1号平行世界中，而现实生活中的Prover则在2号平行世界中。

我们先来看现实世界。

首先，Prover和Verifier可以实现约定一个random target vector $ \mathbf{u} $，作为SIS Challenge。

当Prover通过$ k $的值使用Input-Dependent Evaluation计算出opening $ \mathbf{R}{f{x, ct}, k} $之后，他可以构造如下的矩阵$ \mathbf{A}^* $： $$ \mathbf{A}^* = [\mathbf{A} \vert \mathbf{AR}{f{x, ct}, k} + f_{x, ct}(k) \cdot \mathbf{G}] $$ Prover要做的事情，就是告诉Verifier一个短向量$ \mathbf{v} $，使得满足： $$ \mathbf{A}^* \mathbf{v} = \mathbf{u} \text{ mod }q $$ 同时，Verifier可以自己通过承诺$ c_k $和$ f_{x, ct} $的信息，通过Input-Independent Evaluation同态计算出承诺$ c_{f_{x, ct}(k)} $，然后再次创建出$ \mathbf{A}^* $矩阵出来： $$ \mathbf{A}^* = [\mathbf{A} \vert c_{f_{x, ct}(k)}] = [\mathbf{A} \vert \mathbf{AR}{f{x, ct}, k} + f_{x, ct}(k) \cdot \mathbf{G}] $$ 知道了$ \mathbf{A}^* $和$ \mathbf{v} $之后，Verifier就可以把它们相乘起来，验证结果是否等于$ \mathbf{u} $了！

Prover的Trapdoor

Prover是如何找到对应$ \mathbf{A}^, \mathbf{u} $的SIS解$ \mathbf{v} $的呢？其实很简单，这正是因为$ \mathbf{A}^ $的构造。

首先在$ \mathbf{A}^* $矩阵中，$ \mathbf{A} $就是用于最初构造承诺用的LWE矩阵（由TTP生成），而$ f_{x, ct}(k) $这部分我们讨论过，如果$ k $和witness $ w $正确的话，那么会输出1。所以在正确情况下，整个等式可以被简化为： $$ \mathbf{A}^* = [\mathbf{A} \vert \mathbf{AR}{f{x, ct}, k} + \mathbf{G}] $$ 这正是我们描述的MP12 Trapdoor的结构，所以Prover可以轻松的得到Trapdoor $ \mathbf{R} $为： $$ \mathbf{R} = \begin{bmatrix} -\mathbf{R}{f{x, ct}, k}\\mathbf{I} \end{bmatrix}\ [\mathbf{A} \vert \mathbf{AR}{f{x, ct}, k} + \mathbf{G}] \cdot \mathbf{R} = \mathbf{G} $$ 这样一来，Prover就可以轻松的利用Trapdoor把$ \mathbf{A}^* $的SIS问题变换为$ \mathbf{G} $的SIS问题，然后使用MP12中的sampling方法找到符合正态分布的SIS解$ \mathbf{v} $了。

反之，如果Prover提供了错误的witness，或者是错误的密钥$ k $的话，那么Prover自己所计算的$ \mathbf{A}^* $矩阵和Verifier同态计算的$ \mathbf{A}^* $就会有所分歧，这样Prover就算生成了一个符合自己的$ \mathbf{A}^* $要求的$ \mathbf{v} $，也无法使得Verifier接受这个SIS解。

Simulator的构造

了解完现实世界之后，接下来我们来继续探讨零知识的属性。为了确保这个协议的ZK property，我们需要构造出一个simulator可以模拟Prover和Verifier之间的所有沟通信息（包括了一开始TTP生成的公共参数）。

回到我们之前讨论的第一个平行宇宙中，我们可以构造如下的一个Simulator：

首先，我们生成一个拥有MP12 Trapdoor的uniform random矩阵$ \mathbf{A}’ $和对应的Trapdoor $ \mathbf{R}’ $。并且我们选择一个SIS的目标向量$ \mathbf{u}’ $。
随后，我们再随机的生成一个平均随机分布的代表密钥$ k $的承诺$ c_k’ $。注意这里我们只是随机生成了一个矩阵，并没有GSW FHC承诺的结构，但是这并不影响Simulator的正常运作。
因为我们要模拟一个NIZK的协议，所以我们还需要随机的生成一个NP Relation $ x’ $，和一个随机的密文$ ct’ $。基于这两项，我们就可以构造出需要同态计算的电路$ f_{x, ct}’ $。
最后，我们在$ c_k’ $上同态的计算$ f_{x, ct}’ $，得到$ c_{f_{x, ct}(k)}’ $，并且组成$ \mathbf{A’}^{} = [\mathbf{A}’ \vert c_{f_{x, ct}(k)}’] $。因为我们知道$ \mathbf{A}’ $的Trapdoor $ \mathbf{R} $，所以可以轻松的生成一个$ \mathbf{v}’ $向量使得$ \mathbf{A’}^ \mathbf{v’} = \mathbf{u’} \text{ mod }q $。

这个Simulator从头到尾生成了协议中的$ \mathbf{A} $矩阵，目标向量$ \mathbf{u} $，GSW GHC承诺$ c_k $，以及最后验证opening的$ \mathbf{v} $向量。

我们接下来，需要证明Simulator生成的这些内容和真实的协议中的内容概率分布一致，是无法分辨的（indistinguishable）。

这里的一张图上比较了真实协议与Simulator输出的三组内容，我们来看看具体是怎样的。

公共参数部分，两者唯一的区别在于构成承诺的$ \mathbf{A} $矩阵。在Simulator中$ \mathbf{A} $是uniform random的，而在真实协议中$ \mathbf{A} $是GSW FHC所用的LWE矩阵。因为DLWE假设，我们可以大致认为这两者是computationally indistinguishable的。

承诺部分，真实协议构造的是GSW FHC承诺，而在Simulator中我们则是随机的sample了一个矩阵。因为$ \mathbf{A} $是uniform random的，并且$ \mathbf{R} $矩阵也是符合正态分布的短矩阵，所以根据Leftover Hash Lemma（以及Commitment的hiding property），我们知道这两部分也是indistinguishable的。

最后，再看opening的部分。在真实协议中，Prover会构建$ \mathbf{A}^* $矩阵，然后根据$ \mathbf{R}{f{x, ct}, k} $的信息构造MP12 Trapdoor，然后找到SIS问题的解$ \mathbf{v} $。然而在Simulator中，我们同态计算随机生成的承诺，得到一个看似像承诺的$ c_f’ $，组成$ \mathbf{A’}^* $矩阵。虽然这个承诺是个假承诺，我们也不知道它对应的randomness，但是因为我们知道$ \mathbf{A}’ $的MP12 Trapdoor，所以也可以轻松的找到SIS问题的解$ \mathbf{v}’ $。这里，因为两个世界中都是使用MP12来sample SIS问题的解的，并且$ \mathbf{A}^* $矩阵的结构也是indistinguishable的，所以两个世界中sample的$ \mathbf{v} $向量的概率分布也是indistinguishable的！

Q.E.D.

当我们发现在这两个世界观中，构成NIZK的这三部分都是indistinguishable之后，我们的零知识属性证明就完成啦。

【KW17】DP-NIZK的完整形态

最后，我们来总结一下，【KW17】中所描述的Preprocessing NIZK的最终完全形态！

整个协议在一开始需要进行一次Trusted Setup，可以由可信第三方（TTP）或者是MPC完成。在初始化的阶段，我们需要生成一个密钥$ k $，以及对应这个$ k $的GSW FHC承诺$ c_k $和对应的opening $ \mathbf{R}_k $。承诺$ c_k $可以直接公开给所有人，而$ k $与$ \mathbf{R}_k $只能告诉Prover。同时，我们还需要指定好SIS问题的目标向量$ \mathbf{u} $，以及加密解密用的算法。

当初始化结束之后，Prover可以对Verifier进行任意次数的NIZK，证明任何内容（NP Relation）。其证明步骤如下：

Prover决定要证明的内容，生成公共参数$ x $，并且把witness $ w $用$ k $加密成密文$ ct $。
Prover把$ x $与$ ct $的值嵌入证明电路，得到新的证明电路$ f_{x, ct}(k) = C_x(w) $。
Prover使用$ k $的信息，通过Input-Dependent Evaluation构建出$ \mathbf{A}^* $矩阵，并且得到opening $ \mathbf{R}{f{x, ct}, k} $。这里的$ \mathbf{R} $矩阵恰好是$ \mathbf{A}^* $的MP12 Trapdoor，于是Prover找到一个SIS的解$ \mathbf{v} $，使得$ \mathbf{A}^* \mathbf{v} = \mathbf{u} \text{ mod }q $。
最后，Prover把$ x, ct, \mathbf{v} $发给Verifier，完成NIZK。

当Verifier收到这些消息之后，可以很简单的验证证明：

Verifier根据$ x, ct $重组出$ f_{x, ct} $证明电路。
Verifier使用一开始拿到的$ k $的承诺$ c_k $通过Input-Independent Evaluation同态计算$ f_{x, ct} $，得到$ c_{f_{x, ct}(k)} $，然后重组出$ \mathbf{A}^* $矩阵。
最后，Verifier检查$ \mathbf{A}^* \mathbf{v} $是否等于目标向量$ \mathbf{u} $。

这就是【KW17】基于FHE/FHC的NIZK的全貌了。

简化成DP-NIZK

我们观察发现，虽然【KW17】是Preprocessing NIZK，使用了Trusted Setup这一个步骤生成了Prover专属的$ k_p $以及Verifier专属的$ k_v $。但是其实$ k_v $中仅仅只是包含了承诺$ c_k $而已。这个部分是完全可以公开的！然而，Prover所拥有的$ k_p $中的$ k, \mathbf{R}_k $部分还是得保密的。

这也就是说，我们可以弱化一下Preprocessing NIZK的假设，把它变成一个指定证明方NIZK（Designated-Prover NIZK，DP-NIZK）。在DP-NIZK中，一次Trusted Setup只能使得一个Prover拥有证明的能力（即拥有密钥以及opening），而任何其他人只要知道$ c_k $都可以当作Verifier。这对于原本的Preprocessing（即指定证明方，指定验证方）的框架来说要好了不少。

写在最后

写到这里，关于【KW17】的NIZK构造就差不多了。

这篇文章其实是笔者半年前看到的内容，然而为了能够流畅的写出这个NIZK的具体构造以及思路，笔者在这个专栏下循序渐进，从格密码学的基础一路走来。

这几个月时间，从格的基础，到FHE，再到更进阶的Trapdoor以及ABE/IBE，最后再到把这些idea全部套用在一起的NIZK，构成了一条学习曲线。希望大家有所收获～

从下期开始，我们要开始一个新的专题，开始探索Lattice中最神奇，也是最吸引笔者的部分：Indistinguishable Obfuscation（iO）。