《简洁非交互零知识证明》介绍

Original 李威翰隐私计算研习社 2022-09-24

收录于合集 #零知识证明 1个

本次介绍由北航网络空间安全学院张宗洋副教授，博士生李威翰、周子博，和中国科学院信息工程研究所邓燚研究员发表于《密码学报》2022年第9期的《简洁非交互零知识证明综述》一文，作者从通用构造方法、底层技术原理、协议性能表现、安全性等角度深入研究了现有的简洁非交互零知识证明。该论文篇幅达69页，结构清晰，内容详实，文献引用全面，可为该领域的理论研究和应用实现提供重要的参考。

原文链接：[http://www.jcr.cacrnet.org.cn/CN/Y2022/V9/I3/379]

0. 简介零知识证明是运行在证明者和验证者之间的一种两方密码协议，可用于进行成员归属命题证明或知识证明。零知识证明具有完备性、可靠性和零知识性。零知识性是指证明者能向验证者证明某个命题的正确性而不泄露除正确性以外的其他任何额外信息。零知识证明的三个性质使其具备了信任建立和隐私保护的功能，具有良好的应用前景。它不仅可以用于公钥加密、签名、身份认证等经典密码学领域，也可应用于区块链、隐私计算等新兴热门领域。

零知识证明尤其是简洁非交互零知识证明，虽然在多个领域具有热门和广泛的应用前景，但其种类繁多，且各类协议底层原理驳杂，性能侧重点也各不相同，目前在很大程度上存在技术壁垒。

该论文首先总结了简洁非交互零知识证明的通用构造方法。其次，分别基于信息论安全证明和底层关键技术对现有的简洁非交互零知识证明进行分类并提炼了核心思路，深入分析了典型协议的实现原理。再次，辨析了各类协议的性能表现，探讨其安全性并指出其适用场景。最后，总结了简洁非交互零知识证明的研究热点和发展方向。

1. 通用构造方法

如图1所示，简洁非交互证明的通用构造方法分为四步，分别是将待证明陈述转换为电路可满足问题（C-SAT问题）、将电路可满足问题转换为易证明的语言（如一阶约束系统，此步可省略，用虚线表示）、针对易证明的语言构造信息论安全证明和利用密码编译器将信息论安全证明转换为简洁非交互零知识证明。

2. 分类方法

目前的简洁非交互零知识证明，大致可从信息论安全证明和关键技术两个角度进行分类。根据信息论安全证明的种类，主要分为基于概率可验证证明（probabilistic checkable proof，PCP）、线性概率可验证证明（Linear-PCP）、交互式概率可验证证明（interacitve PCP，IPCP）、交互式谕示证明（interactive oracle proof，IOP）等的零知识证明。根据密码编译器应用的底层关键技术，主要分为基于二次算术程序（quadratic arithmetic program，QAP）、双向高效的交互式证明（doubly efficient interactive proof，DEIP）、基于离散对数内积论证（inner product argument，IPA）和MPC-in-the-Head的零知识证明，表1分别从信息论安全证明和密码编译器应用的底层关键技术两个角度，总结了零知识证明，涵盖了待证明陈述表示形式、协议性能、启动阶段参数能否公开生成等相关信息。

3. 性能表现

如表3所示，性能评价标准主要分为效率及安全性两个层面。

在效率层面，主要分为证明复杂度、验证复杂度、通信复杂度和是否需要公钥密码操作。

（1）证明复杂度。证明复杂度是指在协议中证明者生成证明所需计算步数的渐近复杂度。几乎所有的简洁非交互零知识证明协议都具有线性或准线性级别的证明复杂度。

（2）验证复杂度。验证复杂度是指协议验证者验证证明有效性所需计算步数的渐近复杂度。需要指出的是，一般而言由于验证者起码要读取整个陈述，因此验证复杂度起码为线性。但是，可通过CRS和预处理降低验证者参与协议后的计算开销至对数级别甚至为常数级别的运算。

（3）通信复杂度。通信复杂度是指协议证明规模的渐近复杂度。常见的亚线性通信复杂度为常数级别元素（zk-SNARK）、根号级别（包括Ligero、BooLigero )、对数级别（包括Aurora等基于IOP的零知识证明、Bulletproofs 等基于IPA的零知识证明和Ligero++等基于MPC-in-the-Head的零知识证明）。

（4）是否需要公钥密码操作。对称密码操作是指移位、异或、域上多项式运算等对称密码中常出现的运算操作，公钥密码操作包括椭圆曲线上运算等公钥密码中常出现的运算操作。一般而言,公钥密码操作尤其是群幂运算的实际开销较高。

在安全性层面，主要分为底层难题假设、系统参数生成方式和是否抗量子。

（1）底层难题假设：不同简洁非交互零知识证明协议的底层难题假设通用性有一定的差距。目前主流协议的底层难题假设包括zk-SNARK等所基于的q-PKE、q-SDH等不可证伪假设，离散对数难题假设，抗碰撞哈希函数存在假设，LPN假设（learning parity with noise）等。

（2）系统参数生成方式：基于公共字符参考串（Common Reference String，CRS）的简洁非交互零知识证明（如Pinocchio、Groth16、Plonk、Libra）的系统参数必须由可信第三方生成，这在去中心化的区块链应用中会带来安全性问题。而一些基于随机谕言模型（Random Oracle Model）实现非交互的简洁非交互零知识证明可利用某些哈希函数由证明者自行生成随机数，在某种程度上具有更高的安全性。

（3）是否抗量子：基于MPC-in-the-Head的零知识证明和部分基于IOP的零知识证明（如Aurora、Virgo）只需假设单向函数存在, 且仅有对称密钥操作, 被认为是抗量子的。

4. 一些典型零知识证明协议

（1）ZK-SNARK/基于QAP的零知识证明

优点：通信复杂度为常数个群元素、验证复杂度可通过适当预处理达到常数级别配对运算。

缺点：需要可信建立、假设为不可证伪假设。

应用：隐私密码货币（如Zcash，基于Groth16、Plonk等），区块链扩容。

描述：zk-snark，是指zero knowledge succinct non-interactive argument of knowledge，即零知识的简洁非交互知识论证。从信息论安全证明的角度，zk-SNARK是基于Linear-PCP及LIP实现的；从密码编译器应用的底层关键技术角度, 其大多利用二次算术程序及变种将电路可满足问题归约为一组多项式的约束并利用双线性配对验证上述约束进而实现。部分zk-snark总结如表4，其典型协议的优化思路见图5.

（2）基于内积论证/离散对数假设的零知识证明

优点：不需可信设置、实际通信量很小

缺点：需要公钥密码操作，不抗量子；相比于其他不需可信设置的零知识证明，实际证明和验证速率较低

应用：门罗币（基于Bulletproofs）

描述：基于内积论证（inner product argument）的零知识证明底层难题假设均基于离散对数假设，且以内积论证为底层核心技术。通过内积论证，证明者通过可利用循环递归的方式证明他拥有两个公开向量承诺的消息，且这两个消息的内积等于某个公开值。该类简洁非交互零知识证明总结见表8，优化思路见图10。

（3）基于MPC-in-the-Head的零知识证明

优点：不需可信建立、底层假设仅为抗碰撞哈希函数存在、抗量子攻击、实际证明速率较快。

缺点：相比于其他不许可信建立的零知识证明，实际通信量较高。

应用：抗量子签名（Picnic，基于ZKB++、Ligero等）。

描述：基于MPC-in-the-Head的零知识证明的构造思路是证明者在脑海中模拟运行一个针对零知识函数的安全多方计算协议，然后将协议运行过程中的视图视为谕示发送给验证者，验证者验证视图正确性，而协议的零知识性由MPC 协议的隐私性保障。该类简洁非交互零知识证明总结见表9，优化思路见图13。

论文信息

李威翰, 张宗洋, 周子博, 邓燚. 简洁非交互零知识证明综述[J]. 密码学报, 2022, 9(3): 379-447.

论文作者信息：

李威翰（1997–），山东烟台人，现为北京航空航天大学网络空间安全学院博士生。主要研究领域为零知识证明和区块链。

张宗洋（1984–），山东菏泽人，现为北京航空航天大学网络空间安全学院副教授，主要研究领域为密码学和区块链。

周子博（1999–），山东菏泽人，博士生。主要研究领域为零知识证明和区块链。

邓燚（1977–），湖南望城人，现为中国科学院信息工程研究所研究员。主要研究领域为零知识证明及其在金融科技中的应用。