这篇博客结合了ZKP Community Reference$[1]$和密码学报今年的一篇ZKP的综述$[2]$，主要是翻译学习文档和论文中的主要理论内容

对于ZPK Comm. Ref.的学习不涉及与开发和标准制定相关内容（相关内容可以看原文档$[1]$）

Part 1 Background and Preliminary

Abstract

零知识证明能够证明数学陈述，同时保持支持数据的机密性，这一特性可以作为增强隐私保护的密码学工具，在许多应用中广泛使用，但其可用性取决于安全、实用和可交互操作的部署

ZKP Comm. Ref.是ZKProof社区参考，同时作为ZKProof标准化的成果之一，旨在作为ZKP技术的开发参考

该文档来源于社区内的贡献，涵盖了定义和理论方面的知识、实施和应用相关方面的内容

1 Background and Introduction

1.1 A brief introduction to ZKP

ZKP可以证明一个陈述（statement）为真，同时不泄露任何机密信息$[GMR89]$，当陈述的真实性不明显，但是只有Prover知道相关的秘密信息时（或有能力计算该秘密），ZKP可以产生一个有意义的证明

这里保密的概念是为了不泄露秘密信息，但是即便是Verifier事先知道了秘密（或者其中的个一部分），ZKP也是有意义的

ZKP的用途十分广泛，可以用于证明许多关于机密数据的陈述，比如下列一些场景

  1. 证明我成年了，但是不透露我的实际年龄
  2. 证明我的偿付能力（证明我尚未破产），同时不揭示投资结构
  3. 证明资产的所有权，同时不暴露历史交易
  4. 定理的正确性（可证明性），同时不透露实际的数学证明

ZKP的应用场景包括但不限于上面这些，部分声明（claim）要求其拥有一个实例（instance），该实例是Prover和Verifier都已知的，目的是支持与秘密信息的关联性（秘密信息称为证据，witness，只有Prover知道）

比如证明偿付能力（statement）可能需要依赖于加密并经过认证的银行记录（instance），但是加密密钥和对应的明文（witness）是Vierifer不能知道的

表1.1给出了statement、instance和witness三者之间的几个例子

一个ZKP系统需要阐述Prover与Verifier之间如何交互，同时Prover使得Verifier信服某个陈述为真，一个ZKP系统必须满足下列三个性质

  • 完备性（Completeness）：若statement为真，且Prover和Verifier均依照协议执行，则Verifier总是接受Prover
  • 合理性/可靠性（Soundness）：若statement为假，且Verifier依照协议执行，Prover无论如何背离协议都无法使得Verifier接受
  • 零知识性（Zero-Knoeledge）：若statement为真，且Prover依照协议执行，则Verifier无法获得statement为真以外的任何信息

简单来说，完备性就是真的假不了，合理性就是假的真不了，零知识性就是除了我说的话是真的意外，其他的你不知道

这里有一个点，也是所有ZKP的paper都会提到的，就是proof和argument的关系

Proof vs. Argument：这两者的区别在于Prover和Verifier计算能力，若在对抗计算无界的Prover时，系统的合理性仍然成立，则称系统为Zero-Knowledge Proof，若合理性仅需在对抗计算有界的Prover成立（通常限制Prover为一PPT算法），则此时称为Zero-Knowledge Argument

为了简单起见，下文采用证明来泛指Proof和Argument，但是实际上两者是有本质区别的

1.2 Current Research

目前关于ZKP的主流研究方向为简洁非交互式零知识论证（zero-knowledge Succinct Non-interactive Argument of Knowledge，zk-SNARK），这项技术虽然在多个领域具有热门和广泛的应用前景，但一方面零知识证明种类繁多，各类协议基于的原理驳杂，性能侧重点也各不相同，目前在一定程度上存在技术壁垒

自$[GMR85]$提出ZKP的概念以来，ZKP的理论与实践已经取得较大的突破，目前学术界对于ZKP的研究大致上可以总结为$[2]$中的这个表格

说明：

  • 上述表格均为知识论证（Knowledge of Argument）
  • $\mathbb F$表示域元素，$\mathbb F_o$表示域操作，$\mathbb G$表示群元素，$\mathbb G_o$表示群操作（群幂运算$E$和群乘法），一般而言群运算（尤其是群幂）比域运算开销大得多
  • $P$表示双线性配对
  • $|C|$表示电路规模，$|C_M|$表示电路中乘法门数量
  • $d$表示电路深度，$g$表示电路宽度
  • $|io|$表示$C-SAT$的公共输入输出规模，$n$表示R1CS可满足问题的规模，$T$表示对数空间可计算电路的时间上线
  • data-parallel circuit（数据并行电路）：该电路可以分为$N$份宽度为$g$，深度为$d$的子电路，满足$|C|=Ngd$
  • Public：表示初始化阶段的参数可公开生成，意味着系统可通过基于ROM的FS变换转换为非交互的
  • Private：Prover和Verifier需要拥有CRS
  • /：未查明具体的参数
  • ?：未有明确的ITPS分类
  • 表格仅表示单轮的开销，实际运行的轮数，各种开销和通信量，可靠性误差取决于安全参数
  • 基于DEIP的ZKP开销省略了部分因子

2 Preliminary

简要介绍一下ZKP中的一些（亿些）常用术语

符号表示

  • $\boldsymbol a\in \mathbb F^{1\times n}$：小写粗体字母，表示域$\mathbb F$上长度为$n$的向量
  • $\boldsymbol A \in \mathbb F^{m\times n}$：表示$m$行$n$列的矩阵
  • $f(\cdot )$：多项式
  • $\boldsymbol f(\cdot )$：粗体，表示向量多项式
  • $\boldsymbol A \boldsymbol a$：矩阵与向量的乘积
  • $\boldsymbol a\cdot \boldsymbol b=\sum_i^na_i\cdot b_i$：向量内积
  • $\odot$：哈达玛积
  • $y\larr A(x,r)$：算法$A$，输入为$x$，随机性为$r$，输出$y$
  • $y \stackrel{\$}{leftarrow} S$：从集合$S$中随机均匀挑选元素$y$
  • $\rarr$：函数映射关系
  • $a?=b$：判断是否相等
  • $[n]$：表示$\{1,2,...,n\}$
  • $\lambda$：安全参数
  • $negl(\lambda)$：对于$\lambda$的可忽略函数
  • $f(\lambda)\approx g(\lambda)$：表示$|f(\lambda)-g(\lambda)|\leq negl(\lambda)$
  • PPT：概率多项式时间
  • $O_\lambda(\cdot )$：表示省略安全参数的记法

信息论证明系统

  • IP：Interactive Proof$[GMR85]$
  • LIP：Linear Interactive Proof$[BCIPO13]$
  • PCP：Probabilistic Checkable Proof$[BFLS91,AS98,ALMSS98]$
  • DEIP：Doubly Efficient Interactive Proof$[CMT12,GKR15]$
  • LPCP：Linear PCP$[BCIPO13,SBVBPW13]$
  • Sum-Check：和校验协议$[LFKN92]$
  • IPCP：Interactive PCP$[KR08]$
  • R1CS：Rank-1 Constraint System$[WSRBW15]$
  • IOP：Interactive Oracle Proof$[BBCGGH17,RRR21]$
  • IPA：Inner Product Argument$[BN20]$
  • CRS：Common Reference String$[BFM88]$
  • DLOG：Discrete Logarithm Assumption
  • ROM：Random Oracle Model$[BR93,CGH98]$
  • MPC：(Secure) Multi-Party Computation$[Yao82]$
  • C-SAT：Circuit Satisfiability Problem
  • RS：Reed-Solomon Code$[RS60]$
  • CRHF：Collision-Resistant Hash Function
  • NIZKAoK：Non-INteractive Zero-Knowledge Argument of Knowledge
  • QAP：Quadratic Arithmetic Program$[GGPO13]$
  • zk-SNARK：Zero-Knowledge Succinct Non-Interactive Argument of Knowledge$[BCCT12]$

电路定义

ZKP主要讨论扇入为2的电路（fan-in 2gate，门的输入为2），记电路大小为$|C|$，深度为$d$，宽度为$g$

  • Arithmetic Circuit：记为$C:\mathbb F^{|x|+|w|}\rarr \mathbb F^{|y|}$，由域上若干乘法门和加法门组成，变量为域上元素
  • Boolean Circuit：属于算术电路的子类，仅包含AND、OR、XOR等布尔逻辑门，变量为布尔值

通过增加常数级别的门的数量和电路的深度，可以将任意布尔电路转换为算术电路

  • Layered Arithmetic Circuit：可以分为$d$层的电路，任意层的电路们的输入导线均来自上一层

通过增加电路深度级别的门的数量，任意算术电路可转换为LAC

  • Circuit Satisfiability Problem（C-SAT）：给定电路$C$、部分输入$\boldsymbol x$（可为空）、电路输出$\boldsymbol y$，判断是否存在witness $\boldsymbol w$（电路的秘密输入）满足$C(\boldsymbol x,\boldsymbol w)=\boldsymbol y$

针对布尔电路可满足问题的零知识证明可通过调用针对算术电路可满足问题的零知识证明高效构造（扩大域并约束变量为0和1即可），反之不然（尚未清楚是否存在高效的转化方式）

  • R1CS：为一个七元组$(\mathbb F,\boldsymbol A,\boldsymbol B,\boldsymbol C,io,m,n)$，$io$表示公共输入向量，$\boldsymbol A,\boldsymbol B,\boldsymbol C$为三个$m$行方阵，$m\geq |io|+1$，$n$为所有矩阵中非零元素的最大数目

令$\boldsymbol z=(io,1,\boldsymbol w)^T$，当且仅当存在$\boldsymbol w\in \mathbb F^{m-|io|-1}$，满足$(\boldsymbol A\cdot z)\odot (\boldsymbol B\cdot z)=(\boldsymbol C\cdot z)$时，R1CS可满足

记R1CS的规模为$n$，任意C-SAT可用R1CS表示，其中$n=O(|C|)$

R1CS为高级语言编译器常见的目标程序，形式简单，结构清晰，部分ZKP方案先将C-SAT转化为R1CS，再针对R1CS构建ZKP方案，也有直接针对R1CS构建ZKP

证明系统定义

  • $R:\{0,1\}^*\times \{0,1\}^*\rarr \{0,1\}$：表示二元关系
  • $L(R)$：表示集合$\{x:\exist w,s.t. R(x,w)=1\}$

当且仅当下列两个条件成立时，语言$L$为NP语言

  1. $|w|=poly(|x|)$
  2. $\forall x,w$，存在多项式算法判定$R(x,w)?=1$

下面是一些证明系统中常用的术语

  • Instance：P和V均可知，用于辅助statement的证明
    instance可以通过P和V本地交互获得，也可以公开（其他参与方也可见）

instance通常用$x$表示（有些paper通常交错使用instance和statement）

  • Witness：P的私密输入，其他参与方可能或可能不了解witness
    witness以$w$表示
  • Relation：关系用于明确instance和witness之间联系，关系可以被视为一组合理的$(instance,witness)$对
    relation以$R$表示
  • Language：$R$中所有合理的instance组成的集合
    language以$L$表示
  • Statement：由instance和relation定义，statement用于声明一个instance有一个对应的witness
    statement以$x\in L$表示
  • Security Parameter：安全参数为一个正整数（通常为128或256），越大表示系统越安全
    大部分构造中将安全参数区分计算安全参数（以$k$表示）和统计安全参数（以$s$表示）
  • Setup：除了$x$和$w$，初始设置也会作为P和V的输入的一部分
    各个参与方的初始设置可以被拆分为私有部分（只有其自己知道）和公共部分（所有参与方公开可知，比如CRS）

setup通常记为$Setup$

这里几个点需要注意

为了简单起见，部分系统中的setup和安全参数是隐式的（比如包含在CRS中），包括定义语言和关系的辅助信息也是隐式的

witness和instance可被视为具体的ZKP执行的setup元素（需要明确的区分这两个概念）

实践中，setup通常用于证明系统的设置，随后系统可以被实例化为具有不同instance和witness的多次执行

ZKP定义

关于$R$的证明系统$(Setup,Prove,Verify)$必须满足完备性和合理性，根据额外的要求还可以满足知识证明和零知识性，前面简单介绍了ZKP的三个性质，这里给出比较详细的定义

  • Completeness：
    完备性表明，若诚实的P用一个合法的witness证明statement，则其总是可以说服诚实的V，使其输出true

证明系统必须包含完备性的明确定义，下面举一个例子，说明从Prover角度来定义完备性

考虑一个攻击完备性的敌手$A$，其攻击方式如下

  1. $(setup_R,setup_P,setup_V,auxi)\larr Setup(params)$
  2. $A$选择最坏的instance和witness：$(x,w)\larr A(params,setup_R,setup_P,setup_V,auxi)$
  3. 运行$Prover,Verify$，直到$Prove$返回error或$Verify$返回accept或reject，此时记$result$为结果，则根据定义，$result=error$意味着协议尚未终止

$<Prove(setup_P,x,w,start);Verify(setup_V,x)>\rarr result$

  1. 若$(setup_R,x,w)\in R$且$result\ne accept$，则敌手赢

定义敌手的优势为$Advantage(params)= Pr[Adv-wins]$，若没有任何人可以构造一个以显著的优势获胜的高效敌手，则表示证明系统满足完备性
这里所谓的高效取决于实际应用中（计算设备，运行时间，内存消耗，使用寿命等等），同时还取决于可接受的最大的优势为多少，比较强的设定是统计完备性（无条件完备性），其要求任意敌手获胜的概率都很小，更强的设定是完美完备性（任意敌手获胜的概率为0）

  • Soundness：
    若一个作弊的P只能以很小的概率或0概率使得诚实的V相信一个错误的statement，则系统满足合理性（有的资料写为可靠性）

考虑一个攻击合理性的敌手$A$，攻击方式如下

  1. $(setup_R,setup_P,setup_V,auxi)\larr Setup(params)$
  2. 敌手选择一个instance，$x\larr A(params,setup_R,setup_P,setup_V,auxi)$
  3. 让敌手与V交互，记V的输出为$result$（若协议未终止则令$result=reject$）

$<A;Verify(setup_V,x)>\rarr result$

  1. 若$(setup_R,x)\notin L$且$result = accept$，则敌手赢

若没有任何人可以构造一个以显著的优势获胜的高效敌手，则表示证明系统满足合理性
高效与前述相同，取决于实际应用，同时区分统计合理性和完美合理性

  • Zero Knowledge：
    若一个证明系统没有泄露P的witness的任何信息（敌手从外界已知的除外），则该系统为零知识的

零知识性由一个有效的模拟器来定义，模拟器可以在不知道witness的情况下生成符合协议的证明
若一个系统为零知识的，则其安全性分析中必须包含零知识性的精确定义
若证明系统为零知识的，则其设计者必须给出两个高效的算法$SimSetup,SimProve$，使得敌手在下面的游戏中以很小的（可忽略的）优势取胜

  1. 均匀随机选择一个比特$\{0,1\}\rarr b$
  2. 若$b=0$，则运行$(setup_R,setup_P,setup_V,auxi)\larr Setup(params)$，否则运行$(setup_R,setup_P,setup_V,auxi,trapdoor)\larr SimSetup(params)$
  3. 敌手选择一个instance和witness：$(x,w)$
  4. 若$(setup_R,x,w)\notin R$，则令$guess = 0$
  5. 若$b=0$，则敌手与真实的P交互，并输出$guess$（$guess=0$表示协议未终止）
  6. 若$b=1$，则敌手与模拟的P交互，并输出$guess$（$guess=0$表示协议未终止）
  7. 若$guess= b$则敌手赢

定义敌手获胜的优势为$Advantage[params] = |Pr[Adv-wins]-\frac{1}{2}|$，与完备性和合理性相同，零知识性区分统计性和完备性
若没有高效的敌手以显著优势赢得上述游戏，则证明系统满足零知识性（高效取决于实际应用）

  • Proof of Knowledge：
    若一个系统不仅满足合理性，还可以说服一个诚实的V，使其相信P知道某个witness，则该系统称为知识证明（Proof of knowledge）

这里P关于witness的知识可以定义为在某一理想世界里的能力，该能力可以使得在理想世界中从一个成功的P那里抽取出witness
若一个系统为知识证明，则其安全分析必须包含知识合理性

对于上述性质，有下面几个分类

  • Independence of verifier's knowledge：ZK性质不取决于V是否对witness有了解，不过特定的证明可以被设计为V知道（某些合法的）witness，但是可以通过更有效的证明生成和验证（？）
  • Multi-theorem zero knowledge：ZK定义中，敌手在单个instance中与P和S交互，可以扩展ZK的性质，使敌手在看到多个instance后也满足ZK性
  • Honest Verifier zero knowledge：一个较弱的安全属性，其要求敌手总是诚实的执行协议，实际上设计协议的时候可以先设计HVZK的系统，之后用标准转换来确保其完全满足ZK性
  • Witness indsitinguishability and witness hiding：若一个statement有多个证据，则证据不可区分性要求敌手无法区分P到底用的哪个witness来完成的证明，证据隐藏则确保诚实的P不会给敌手提供计算witness的帮助

下面是ZKP方案中可能具备的一些特点或额外性质

  • Interactive Proof System：给定二元关系$R$及其对应语言$L(R)$，其交互式证明系统记为$<P(y),V(z)>$，其中$P/P^*$为Prover（可为计算无界），V为Verifier（PPT），交互式证明系统满足下列性质

    • Completeness：$\forall x\in L(R),\exist y,s.t. \forall z\in \{0,1\}^*,Pr[<P(y),V(z)>(x)=1]\ge 1-negl(|x|)$
    • Soundness：$\forall \notin L(R),\forall P^*,\forall y,z\in\{0,1\}^*,Pr[<P^*(y),V(z)>(x)=1]=negl(|x|)$
  • Interactive Argument：限制交互式证明系统中Prover的算力为PPT，其余定义相同
  • Zero-Knowledge：考虑V在交互过程中的视角，记为$view^P_V(x,z)$，表示V在交互过程中获得的所有信息（包括公共输入、随机性、辅助输入，来自P的消息，V自行计算的消息等等）

对于任意PPT的$V^*$，均存在一个期望PPT的模拟器$S$，使得分布$\{view^P_V(x,z)\}_{x\in L(R)}$与分布$\{S(x,z)\}_{x\in L(R)}$不可区分（两个随机变量族不可区分），则称该证明系统（论证）满足零知识性

计算ZK表示限制概率算法的运行时间为$poly(|x|)$

  • Honest Verifier ZK：表示模拟过程中Verifier一定会按照协议步骤执行，也就是上面提到的那个较弱的安全属性
  • Argument of Knowledge：表示满足知识可靠性的论证系统

给定一个多项式时间内可判定的关系$R$及其对应的NP语言$L(R)$，若对于任意PPT敌手$P^*$，均存在一个PPT抽取器$E$，使得对于$L(R)$和任意statement $x$，witness $w'$，若有$Pr[w'\larr P^*(x):<P^*(w'),V(z)>(x)=1]\ge 1/p(|x|)$，则有$Pr[w'\larr E^{P^*}(x):R(x,w')=1]\ge 1/p(|x|)-negl(|x|)$，其中$p$为某一多项式

  • Public Coin：Verifier在交互过程中的掷币结果公开可见
  • Succint：Prover和Verifer之间的通信复杂度不超过$poly(\lambda)(|x|+|w|)^{O(1)}$
    基于标准假设（仅限制敌手的可用时间和算力），无法实现统计级别可靠性的证明系统
  • Non-Interactive：Prover只需要向Verifier发送一条消息即可完成证明
    标准假设下已证明无法构造平凡语言的NIZK，必须引入新的假设

目前主流的NIZK有两种：基于CRS模型和基于ROM-FS

  • Common Reference String：$[BFM12]$假设Prover和Verifier都可以访问一个由可信第三方声称得串（可以MPC方式生成），此类方案中通信量为常数个群元素，Verifier复杂度可优化至常数次双线性配对，此类方案通常又称为zk-SNARK
    但此类方案存在两个较为严重问题：(1)需要可信设置预处理，(2)基于不可证伪假设（Gentry共和wichs从理论上证明了基于可证伪假设无法构造zk-SNARK）
  • Random Oracle Model：此类模型下，Verifier的随机挑战由Hash函数的输出代替，因此任何公开掷币的交互式方案（包括Sigma Protocol）均可转换为非交互式
    大部分基于PCP、IPCP、IOP、DEIP、IPA、MPC-in-the-head的ZKP方案均基于ROM下的FS变换实现非交互性
  • No Setup/Trustless Setup：无需可信的场景，比如setup只需要简单的复制安全参数，此类场景中所有人都可以直接验证setup的正确性
  • Uniform Random String：所有参与方均可访问URS，可以区分较轻的信任情况和较强的信任情况，在较轻的情况下，当事方只需要获得一个均匀选择的串即可，而零知识性依赖于URS的模拟和模拟陷门
  • Designated verifier setup：若setup中的$setup_V$由指定的V生成，则意味着setup算法需要信任，比如Cramer-Shoup的公钥加密方案中，指定Verifier的NIZK用于确保在选择密文攻击下的安全性
  • Universal Composability：UC框架表示，若一个协议在任意环境下均实现了一个理想的函数，则其为安全的
    可以考虑一个理想的ZK函数，其以P的$(x,w)$作为输入，当且仅当$(x,w)\in R$时向V发送消息$(x,accept)$

上述这个函数为完美合理的，因为其不会接受一个没有合法witness的statement，同时其也是完美零知识的，因为其只发送了$x$被接受这一消息
若真实执行与理想执行是等价安全的，则表明该系统为UC安全的，通常证明一个系统为UC安全的需要更多的工作，但是这一安全概念会在证明系统由其他密码协议组成时提供更强的安全性

  • Threshold secure and/or subversion resistant：有很多种方式来减少对信任的以来，比如安全多方计算来生成CRS，或者抗颠覆的CRS（subversion-resistant CRS）

密码学编译器

Cryptographic Compiler，目的是将ITPS转化为实际可用的ZKP系统

CC的目的有很多，主要是下列几个

  • 实现（Random）Oracle：ITPS通常包含一个理想预言（Ideal Oracle），现实世界不存在此类理想预言，因此需要借助承诺方案、抗碰撞Hash等密码学工具实现，这些密码学工具大部分基于标准假设，因此得到的ZKP系统通常也只是论证系统
  • 实现非交互性：根据ITPS模型，实现CRS模型的非交互性（QAP）或基于ROM-FS模型的非交互性（DEIP、IPA、MPC-in-the-head）
    部分ROM模型仍然需要CRS（ZKvSQL，Libra等）
  • 实现ZK：ITPS本身不具备零知识性，需要利用CC实现
    比如基于DEIP的IPA的零知识性基于承诺方案的隐藏性和盲化多项式，基于MPC-in-the-head的零知识性基于MPC协议的隐私性
  • 降低通信复杂度：比如基于DEIP的ZKP可通过多项式承诺降低，基于MPC-in-the-head的ZKP可通过选取合适的MPC协议降低

其他定义

  • Commitment Scheme：承诺方案
    承诺方案需要满足隐藏性和绑定性
  • Additive Homomorphic Commiement）：加性承诺方案
  • Pedersen Commitment：
  • Pedersen Vector Commitment：
  • Schwartz-Zoppel Lemma：
  • Falsifiable：基于敌手和高效挑战者之间的游戏模型描述的假设，游戏结束时挑战者可高效判断敌手是否攻击成功，常见的标准可证伪假设有单向函数存在、DLOG等

关系种类

主要分为两种：特定目的的关系和取决于Setup的关系

  • Special Purpose Relations：电路可满足性为NP完备问题（NP-C），但是其关系不一定需要是NP完备的
    比如密码学中常用的一些statement：一个承诺值位于区间$[A,B]$中或位于某个集合$S$中，一个密文对应的明文为$0$，两个不同的密文对应相同的明文，P有一个公钥所对应的私钥，等等
  • Setup-dependent Relations：部分场景下可以让关系$R$取一些额外的输入，比如让关系$R$包含三元组$(setup_R,x,w)$，此时输入$setup_R$可用于指定持久信息
    比如算术电路可满足性中，有限域$\mathbb F$和电路$C$将使用很多次，则可以令$setup_R=(\mathbb F,C)$和$x=(v_1,...)$

此外，$setup_R$还可用于捕获关系中未检查的可信输入（比如RSA的模数）

知识与成员关系

ZKP理论根据statement的类型，将证明分为两种类型

  • ZKP of Knowledge（ZKPoK）：证明statement的准确性，比如证明一个符合statement的隐私数据而不揭示之
  • ZKP of membership：证明statement的成员属性，比如证明与statemen相关的实例属于某个语言，同时不向（计算有界的）V暴露相关信息

表1.1的前三个属于ZKPoK，后两个属于ZKP of membership

这两种类型分别举一个例子

  • ZKPoK：

ZKPoK的经典例子为$[Sch90]$的离散对数问题，记$p$为大素数（4096 bit），且满足$p=2q+1$，其中$q$也为素数

记$g$为群$\Z^*_p=\{1,...,p-1\}=\{g^i:i=1,...,p-1\}$的生成元，模数为$p$，假设该群上的离散对数在计算上不可行，且$p,q$均由P和V验证有效，令$w$为witness，instance为$x=g^w \ mod \ p$，此时statement为：P知道$x$在模$p$下的底数为$g$的离散对数（P知道一个$w$，满足$x=g^w \ mod \ p$）

上述例子对应的语言为$L:\{x:\exist w:(x,w)\in R\}$，且上述例子属于ZKPoK，因为证明成员归属并不合理（显然存在某个$w$满足等式），但是P证明其知道这个$w$就很重要，因为已知的公开信息$p,q$无法在多项式时间内计算离散对数（量算除外）

  • ZKP of membership：

在具有超多项式算力的情况下（比如算力无界），P可以在没有witness概念的情况下构造一个成员证明，此类情况中ZKPoK不再适用

一个典型的例子为图的非同构问题$[GMW91]$，证明用于向说服V两个图不同构

这一例子不依赖于某个witness，而是依赖于P的能力——P可以判断两个图之间的同构性

此时，V向P发起挑战，V通过向P发送两个图中其中一个的置换来检查两个图的同构性，若P正确判断的次数足够多，则V相信P

困难性假设

证明系统的完整规范必须说明其满足安全定义的假设，并证明这些假设意味着证明系统具有声称的安全特性

安全分析可以采用数学证明的形式，通过简化证明，若现实敌手获得了对安全属性的显著优势，则可以构建出一个现实敌手，使其获得了对其中一个潜在假设的显著优势

举个例子，系统以SHA256作为参数的一部分，若我们假设预算为100万刀的敌手在五年内找到SHA256碰撞的概率小于$2^{-128}$，则通过归约，可以知道相似敌手攻破合理性的概率小于$2^{-125}$

下面是几个假设的分类

  • Cryptographic assumptions：比如一些难以处理的假设，规定了证明系统设计者认为真实攻击者无法计算的内容
    有时候安全属性可能完全不依赖于密码假设，在这种情况下称之为无条件安全，但是通常情况下合理性和ZK性依赖于一个难处理的假设

假设的选择通常依赖于设计者的风险偏好和其期望要抵抗的攻击类型

  • Plausibility：不应使用已被攻破的假设，本文档建议设计灵活和模块化的证明系统，以便在基础密码假设被证伪的情况下更轻松地更新密码系统
    可以通过建立假设的合理顺序：比如可以攻破群上的离散对数问题则意味着可以攻破基于该群的DH假设，但反之不一定成立，这意味着离散对数假设比DH假设更合理，因此从安全角度而言更合理
  • Post-quantum resistance：量算可能在未来几十年发展起来，利用量算可以攻破许多密码假设（比如DLOG假设）
    若证明系统的预期寿命超过了量算的出现时间，则有必要依赖于可以抵抗量算的假设

不同的安全属性可能需要不同的生命周期，如果是需要立即验证的证明，则可以不需要后量子合理性
若敌手可能收集和存储证明副本，并尝试从中获取信息，则此时就需要后量子零知识性

  • Concrete parameters：许多密码学文献中，在描述证明系统背后的理论时会使用诸如“多项式时间敌手的优势可忽略不计”等模糊的说法，但是真实世界的部署需要精确且具体的安全性定义，因此证明系统应当附带具体的参数和安全性水平
  • System assumptions：除了密码学假设以外，证明系统还可以依赖于关于工作设备或工作环境的假设
    如果证明系统依赖于可信的设置，则应明确说明信任的类型
  • Setup：若P或V为概率性的，则需要一个熵源来生成其随机性，错误的伪随机性生成在其它类型的密码系统中会导致漏洞，因此证明系统的完整规范需要明确其熵源的性质或质量所依赖的假设

Reference

$[1]$ ZKProof Community Reference

$[2]$ GitHub Repo

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