Delegable zk-SNARKs with Proxies

多代理人的可代理简洁的非交互零知识证明协议

Jinrui Sha, Shengli Liu*

研究目标

在基于双线性配对群设计的简洁的非交互零知识证明协议中，Groth在Crypto16中的工作实现了证明长度短（3个群元素）、验证复杂度低（3次双线性映射）等诸多优势，但缺陷是方案依然有着较高的证明复杂度。为了降低证明复杂度，我们考虑将证明者的证明工作委托给代理方来代理计算的场景。在传统的简洁的非交互式零知识证明方案中，证明者需要使用陈述x和证据w来为验证者生成证明。在证明者的计算能力受限的场景下，证明者希望将自己的证明工作量委托给其他代理方。一种直观的方法是，证明者将证据w分享给代理方。通过这种方式，任何获得证据w的代理方都可以利用陈述x和代理w生成证明。然而这种做法显然是不安全的，因为证明代理带来证据w的滥用。基于这样的原因，我们希望可以设计一个安全且可以代理证明计算的zk-SNARK方案 。

关键问题

是否可以设计一个新的zk-SNARK方案，其中证明者可以在不泄露证据w的情况下委托证明工作？

研究内容

本工作中，我们致力于通过设计多代理方的场景来规避上述关键问题。我们提出了可代理简洁的非交互式零知识证明的概念，允许证明者将其证明能力代理给多个代理方，每个代理方获得证据w的一部分，这部分本身不泄露证据w的信息，但多个代理方可以合作完成证明的生成。同时本工作希望基于算术电路可满足性问题，来给出多代理方的可代理简洁的非交互式零知识证明的具体构造，并在通用群模型下保障方案的安全性。

技术路线

在多代理方的可代理简洁的非交互式零知识证明的具体构造中，我们使用了基于拉格朗日插值多项式的秘密共享方案，利用秘密共享方案的安全性保障了秘密证据w的安全性，利用秘密共享方案的加法性和乘法性保障了验证者对代理证明的聚合验证，进而保障了方案的完备性；在通用群模型下，实现了方案的可靠性；并利用双线性映射群中群元素的不可区分性保障了方案的零知识性。

研究意义

本工作中，我们提出了首个可代理简洁的非交互式零知识证明的概念，可代理简洁的非交互式零知识证明的性质由参数$(\mu ,k,k^{\prime },k^{″})$$(\mu,\ k,\ k',\ k'')$来定义。可代理简洁的非交互式零知识证明的可代理性允许证明者将其证明能力委托给$\mu$$\mu$个代理方，任何$k$$k$个好的代理都能够为某个命题生成正确的证明，但少于$k$$k$个代理的合谋不会获得命题见证的任何信息。我们还定义了基于多代理的$k^{\prime }$$k'$-可靠性和$k^{″}$$k''$零知识性。

我们也构造了一种针对算术电路可满足性问题（C-SAT）的多代理方的$(\mu ,2t+1,t,t)$$(\mu,2t+1,t,t)$-zk-SNARK方案。我们使用了基于拉格朗日插值多项式的秘密共享方案，利用秘密共享方案的安全性保障了秘密证据w的安全性（对代理方的不可获取性），利用秘密共享方案的加法性和乘法性保障了验证者对代理证明的聚合验证，进而保障了方案的2t+1-完备性；在通用群模型下，实现了方案的t-可靠性；并利用双线性映射群中群元素的不可区分性保障了方案的t-零知识性。 ​ 我们的多代理方的$(\mu ,2t+1,t,t)$$(\mu,2t+1,t,t)$-zk-SNARK方案可用于两种场景。第一种场景是计算外包场景，一旦证明者的计算资源受限，可以将证明过程外包给不同的服务器（代理方），证明者只需要向服务器（代理方）发送证明片段，由代理方计算代理证明后发送给验证者验证；第二种场景是证明能力代理场景，该场景下存在正常模式和代理模式两种方式，在代理模式下，证明者将证明能力委托给代理方，每个代理方生成代理证明后发送给验证者。整个过程中，即使大部分代理方恶意同谋的情况下，也不会泄露完整的证据，同时代理方也无法伪造代理证明通过验证。在这些场景下，成功解决了证明者资源受限的问题。