零知识证明

密码学中，零知识证明（英语：zero-knowledge proof）或零知识协议（zero-knowledge protocol）是一方（证明者）向另一方（检验者）证明某命题的方法，特点是过程中除“该命题为真”之事外，不泄露任何资讯。因此，可理解成“零泄密证明”。^[1]例如，欲向人证明自己拥有某情报，则直接公开该情报即可，但如此则会将该细节亦一并泄露；零知识证明的精粹在于，如何证明自己拥有该情报而不必透露情报内容。这也是零知识证明的难点。^[2]

若该命题的证明，需要知悉某秘密方能作出，则检验者单凭目睹证明，而未获悉该秘密，仍无法向第三方证明该命题（即单单转述不足以证明）。待证的命题中，必定包含证明者宣称自己知道该秘密，但过程中不能传达该秘密本身。否则，协议完结时，已给予检验者有关命题的额外的资讯。此类“知识的零知识证明”是零知识证明的特例，其中待证命题仅有“证明者知道某事”。

交互式零知识证明中，需要各方交互，靠通讯过程证明某方具备某知识，而另一方检验该证明是否成立。^[2]

也有某种非交互式零知识证明（英语：non-interactive zero-knowledge proof）^[3][4]，但证明之所以成立，依赖计算假设（典型假设是理想的密码散列函数）。

3 sources

生活示例

山洞中，小静随机选择A路或B路，阿严则在洞外等候

阿严选一个出口

小静准确出现在阿严所选的出口出现

以下有一个熟知的故事，总结零知识证明的若干重要概念。故事最早由Jean-Jacques Quisquater（英语：Jean-Jacques Quisquater）及同事发表于《如何向你的孩子解释零知识协议》。^[5]设有小静（证明者）和阿严（验证者）两人。^{[注 1]}

故事中，小静发现洞穴中某扇魔法门的开门暗号。洞穴呈环形，入口在一侧，对侧则有魔法门隔断。阿严想知小静是否已知该暗号，但小静很注重隐私，不希望泄露暗号予阿严，也不想全世界知道她有暗号之事。

两人分别将入口左右两条通道标示为A路、B路。首先，阿严在洞口外，待小静进入洞内。小静自行选择行A路或B路，但阿严不准窥视小静所选为何。然后，阿严行入洞穴，均匀随机喊出A路或B路，表明希望小静由该方向返回。假若小静确实知道暗号，则很易达成，因为即使起初所选不是同一条路，她也可以开门通过，从另一条路返回。

然而，若她其实不知道暗号，则祗有一半概率能从阿严所选的方向返回，因为阿严随机选A路和B路，恰有一半机会选中起初小静进入的方向。若两人重复以上过程，比如连续20次，则小静靠运气全部碰巧从正确方向返回的概率极小，为2²⁰分之1。

所以，若小静连续多次从阿严所选的方向返回，则阿严可以推断，小静很可能知道暗号。

以下考虑第三方的观点。即使假设阿严佩戴隐蔽的镜头，录影所见的整个过程，镜头所见亦只有阿严喊“A！”小静从A路返回；或阿严喊“B！”小静从B路返回。此种片段极易由两人共谋伪造（祗需小静与阿严事前商讨多次验证中阿严将选该串A、B的次序），从而对第三方而言，不具说服力，即阿严无法借此向第三方证明小静知道暗号。事实上，即使录影换成现场在阿严身旁监视亦同，因为两人可能一早已协调彩排好。

但是，若阿严在镜头前掷硬币，然后按该硬币喊A或B，则协议不再零知识。该段录影可能足以说服第三方，两人无法伪造，因为阿严难以准确掷出预定的AB次序。于是，虽然证明过程没有泄露暗号予阿严，但是阿严可借此说服世人，证明小静知道暗号，与小静起初的意欲完全相反。不过，数码的密码学中，“掷硬币”以伪随机数生成器实现，类似于一枚结果已预定好的硬币，但该结果（由其随机种子（英语：Random seed）决定）仅有硬币主人知道。若阿严的硬币实际是以此法运作，则协议又恢复为零知识协议，因为两人又有可能共同伪造“实验”结果，所以使用伪随机数生成器与掷真硬币不同，前者不会向世人泄露小静知道暗号。

还有另一种做法，小静以独一次实验已可向阿严证明自己知道暗号，而不泄漏。方法是，两人一同走入洞口，然后阿严目送小静沿A路走，没有原路折返，但从B路返回。如此，小静必然已向阿严证明自己知道暗号，而没有告知阿严暗号。不过此种证明亦非零知识：若第三方观察到过程，或阿严有录影，则该证明对第三方具说服力。换言之，小静无法宣称自己与阿严串通，所以无法向第三方说该证明无效。如此，小静无法控制何人得知她拥有暗号之事。

定义

零知识证明要具备下列三种性质：

完备（complete）

若所要证之事为真，则诚实（意即依协议行事）的证明者能说服诚实验证者。

健全（sound）

若命题为假，则作弊证明者仅得极小机会能说服诚实验证者该事为真。

零知识（zero-knowledge）

若命题为真，则验证者除此之外，过程中没有得悉任何其他资讯。换言之，仅知命题为真（而不知秘密本身）已足以“想像”出一个交互的情境，其中证明者的确知道该秘密。此性质能严格定义为：每个验证者皆有相应的模拟器，输入欲证事实时，无需求助于证明者，已可输出一套通讯誊本，看似诚实验证者与证明者的通讯记录。

前两种性质，更广义的交互式证明系统亦应具备。第三种性质使该交互证明称为零知识。

零知识证明不算数学证明，因为尚允许有很少（但非零）概率，令作弊证明者能向验证者“证明”假命题。该概率称为可靠度误差（soundness error）。换言之，零知识证明是概率“证明”，而非决定性。不过，也有技巧将可靠度误差压到忽略不计。

零知识的严格定义，需要抽象计算模型，如常见的图灵机。设${\displaystyle P}$、${\displaystyle V}$、${\displaystyle S}$为三部图灵机。某语言${\displaystyle L}$的交互式证明系统^{[注 2]}${\displaystyle (P,V)}$为零知识，意思是对任意概率多项式时间（PPT）验证者${\displaystyle {\widehat {V}}}$，皆有PPT模拟器${\displaystyle S}$使得：

${\displaystyle \forall x\in L,z\in \{0,1\}^{*},\operatorname {View} _{\widehat {V}}\left[P(x)\leftrightarrow {\widehat {V}}(x,z)\right]=S(x,z)}$

其中${\displaystyle \operatorname {View} _{\widehat {V}}\left[P(x)\leftrightarrow {\widehat {V}}(x,z)\right]}$是${\displaystyle P(x)}$与${\displaystyle {\widehat {V}}(x,z)}$间交互的全记录。证明者${\displaystyle P}$通常假设具无限计算能力（实践上，常为概率图灵机）。直观理解，某交互证明系${\displaystyle (P,V)}$为零知识，即对任意验证者${\displaystyle {\widehat {V}}}$，皆存在某高效模拟器${\displaystyle S}$（视乎${\displaystyle {\widehat {V}}}$而定），给定任何输入，可以重现${\displaystyle P}$与${\displaystyle {\widehat {V}}}$间的对话。定义中的辅助串${\displaystyle z}$，是用作放置任何“前备知识”（包括预知${\displaystyle {\widehat {V}}}$运行时掷得的硬币结果）。定义推出，${\displaystyle {\widehat {V}}}$不能利用预知串${\displaystyle z}$从与${\displaystyle P}$的对话中发掘出资讯，因为若给予${\displaystyle S}$该串，则也同样可以重现${\displaystyle {\widehat {V}}}$与${\displaystyle P}$间的对话。

以上为完美零知识的定义。若将定义中，验证者${\displaystyle {\widehat {V}}}$的视角（view）与模拟相等之要求，改为仅要求计算上无法分辨（英语：computational indistinguishability），则得到计算零知识的定义。

计算示例

1 sources

离散对数

前段概念适用于较实际的密码学场景。设小静欲向阿严证明，自己知道某群某指定元素的离散对数。^[6]

例如，给定数${\displaystyle y}$、素数${\displaystyle p}$、生成元${\displaystyle g}$，小静希望证明自己知道某数${\displaystyle x}$使${\displaystyle g^{x}{\bmod {p}}=y}$，而不泄漏${\displaystyle x}$。事实上，知晓${\displaystyle x}$之事，本身可用作身份证明，即小静可借此证明该${\displaystyle y}$值是由她先暗中选某随机值${\displaystyle x}$，再计算${\displaystyle y=g^{x}{\bmod {p}}}$，公诸所有潜在的验证者。如此，若某人证明自己知道${\displaystyle x}$，则相当于证明自己即小静，因为学者相信离散对数很难计算，即其他人无法从${\displaystyle y}$倒推出${\displaystyle x}$值。

证明协议如下：每轮，小静预备随机数${\displaystyle r}$，计算${\displaystyle C=g^{r}{\bmod {p}}}$，将该值传予阿严。收到${\displaystyle C}$后，阿严随机请求下列两者之一：小静公开${\displaystyle r}$值，或${\displaystyle (x+r){\bmod {(p-1)}}}$值。单独看任何一个值，其分布皆是均匀随机，所以协议每轮皆不泄露任何机密。

阿严可以验证所得回应。若问${\displaystyle r}$，则可以计算${\displaystyle g^{r}{\bmod {p}}}$，检查是否等于${\displaystyle C}$。若问${\displaystyle (x+r){\bmod {(p-1)}}}$，则可以计算${\displaystyle g^{(x+r){\bmod {(p-1)}}}{\bmod {p}}}$，而该值应当等于${\displaystyle C\cdot y{\bmod {p}}}$，所以亦验证${\displaystyle C}$值是否满足该条件。若小静确实知道${\displaystyle x}$值，理应很易回答阿严的任一条问题。

若小静预知阿严采用何种盘问，则很易作弊，在不知${\displaystyle x}$的情况下，向阿严假装自己知道${\displaystyle x}$：若她知道阿严将要问${\displaystyle r}$，则如常继续，选${\displaystyle r}$，计算${\displaystyle C=g^{r}{\bmod {p}}}$，告知阿严${\displaystyle C}$值；她可以答出${\displaystyle r}$值。另一方面，若她知道阿严将问${\displaystyle (x+r){\bmod {(p-1)}}}$，则取随机一个${\displaystyle r'}$值，计算${\displaystyle C'=g^{r'}\cdot \left(g^{x}\right)^{-1}{\bmod {p}}}$，然后发送${\displaystyle C'}$值予阿严（阿严会以为该值为${\displaystyle C}$值）。当阿严要求公开${\displaystyle (x+r){\bmod {(p-1)}}}$值时，小静公开${\displaystyle r'}$，但这足以让阿严验证结果，因为他计算的值实为${\displaystyle g^{r'}{\bmod {p}}}$，是等于${\displaystyle C'\cdot y}$，因为${\displaystyle C'}$正是小静一早乘上${\displaystyle y}$的逆元而计出。

然而，若有某轮验证中，阿严的问题与小静预估的有出入，则小静无法计算出要答的结果（假定该群的离散对数问题难解）。若她拣选${\displaystyle r}$并公开${\displaystyle C=g^{r}{\bmod {p}}}$，则无法作弊给出服众的${\displaystyle (x+r){\bmod {(p-1)}}}$值来通过阿严的检查，因为不知道${\displaystyle x}$。又若她拣选${\displaystyle r'}$值，伪装成${\displaystyle (x+r){\bmod {(p-1)}}}$，则要回答公开值的离散对数，但她无法回答，因为该值是由已知值乘出，而非某已知值以${\displaystyle g}$为底的幂，所以她不能计出其离散对数

所以，作弊的证明者仅得${\displaystyle 1/2}$概率通过某轮验证。重复足够多轮，成功作弊的概率可压到任意小。

撮要

小静要证知道${\displaystyle x}$值（如其密码）。

1. 小静与阿严约定某素数${\displaystyle p}$，及域${\displaystyle \mathbb {Z} /p\mathbb {Z} }$的乘法生成元${\displaystyle g}$。
2. 小静计算${\displaystyle y=g^{x}{\bmod {p}}}$，发送予阿严。
3. 重复以下步骤若干次：
   1. 小静选某个均匀随机数${\displaystyle r\in U[0,p-2]}$，计算${\displaystyle C=g^{r}{\bmod {p}}}$，发送${\displaystyle C}$予阿严。
   2. 阿严问小静${\displaystyle (x+r){\bmod {(p-1)}}}$或${\displaystyle r}$，二选其一。若问前者，则阿严验证${\displaystyle (C\cdot y){\bmod {p}}\equiv g^{(x+r){\bmod {(p-1)}}}{\bmod {p}}}$。若问后者，则他验证${\displaystyle C\equiv g^{r}{\bmod {p}}}$。

${\displaystyle (x+r){\bmod {(}}p-1)}$之值，可视为${\displaystyle x{\bmod {(}}p-1)}$的加密。若${\displaystyle r}$确为随机，在${\displaystyle 0}$至${\displaystyle (p-2)}$间均匀分布，则${\displaystyle (x+r){\bmod {(p-1)}}}$也同样均匀分布，所以不会泄漏任何关于${\displaystyle x}$的资讯（见一次性密码本）。

大图的哈密顿环

下列方案是曼纽尔·布卢姆提出。^[7]

此场境中，小静知道某大图${\displaystyle G}$的哈密顿环。阿严知道${\displaystyle G}$但不知该环（比如说小静将该图打印给阿严）。一般相信，找大图的哈密顿环，在计算上并不可行，因为相应的决定问题已证为NP完全。小静欲证自己知道该环，但不想泄漏出去，原因可能是阿严打算向小静买，但付款前希望先验证小静知道；也可能是全世界只得小静知道该环，所以小静向阿严证明此事，是为向阿严核实自己身份。

小静为证明自己知道哈密顿环，与阿严作若干轮验证。每轮中：

• 一开始，小静预备图${\displaystyle H}$，是与${\displaystyle G}$同构（即${\displaystyle H}$与${\displaystyle G}$一样，但顶点的标签不同）。若小静知道${\displaystyle G}$的哈密顿环，则因为${\displaystyle H}$与${\displaystyle G}$间的同构由她拣选，她很易找到${\displaystyle H}$中对应的哈密顿环。
• 小静秘诺${\displaystyle H}$。此处可选任意密码学秘诺机制（英语：commitment scheme），甚或直接将${\displaystyle H}$的顶点编号，然后对${\displaystyle H}$的每条边，将两端编号写在小纸片上，反转盖在台面。总之，秘诺目的是使小静此后无法窜改${\displaystyle H}$，但同时不让阿严提早知道${\displaystyle H}$的资讯。
• 阿严随机问小静以下两事之一：给出${\displaystyle H}$与${\displaystyle G}$间的同构（见图同构问题（英语：graph isomorphism problem））；或给出${\displaystyle H}$的哈密顿环。
• 若问两图的同构，则小静先展示${\displaystyle H}$（将台面全部纸翻开），并给出${\displaystyle G}$顶点与${\displaystyle H}$顶点的对应表。阿严可以验证该对应关系是否满足图同构的条件。
• 若问哈密顿环，则小静只翻开在${\displaystyle H}$的哈密顿环上的纸片。如此，阿严已可验证${\displaystyle H}$有哈顿顿环。

秘诺一步必须使阿严在第二种情况能验证该环确实由${\displaystyle H}$的边构成。一种做法是，逐条边分别秘诺。

1 sources

完备

若小静确知${\displaystyle G}$中的哈密顿环，则阿严询问同构时，她很易回答（该同构为她所选），而阿严问${\displaystyle H}$中的哈密顿环时，她同样很易回答（${\displaystyle G}$有哈密顿环，${\displaystyle G}$与${\displaystyle H}$间的同构为所她选，所以可以找到${\displaystyle H}$中对应的环）。

健全

若小静不知哈密顿环，则只能预先猜测阿严会问何种问题，相应准备某个与${\displaystyle G}$同构的图，或另一个不相关的哈密顿图。然而，因为她不知${\displaystyle G}$的哈密顿环，所以无法同时做两件事。于是，若以上验证重复${\displaystyle n}$次，则小静蒙混过关的概率仅得${\displaystyle 2^{-n}}$，从而实际意义上，只需合理多轮验证，已使造假者寸步难行。

零知识

小静的回答不泄漏原图${\displaystyle G}$的哈密顿环，因为每一轮，阿严只会得悉${\displaystyle H}$与${\displaystyle G}$的同构，或是${\displaystyle H}$的哈密顿环，两者之一，但他需要对同一个${\displaystyle H}$同时得知两者，才能构造出${\displaystyle G}$中的哈密顿环。如此，只要小静每轮预备一幅不同的图${\displaystyle H}$，就能保密。若小静不知${\displaystyle G}$的哈密顿环，但不知为何已事前得知阿严每轮会问的问题，则她可以作弊。例如，若小静预知阿严该轮会问${\displaystyle H}$的哈密顿图，则大可以秘诺一幅与${\displaystyle G}$无关的哈密顿图。与之类似，若小静预知阿严会问同构表，则她可以随便预备一幅与${\displaystyle G}$同构的图${\displaystyle H}$（其中她不知道任何哈密顿图）。阿严根本无需小静在场，亦可独自想像出自己将见的场面，因为他清楚自己将会问什么，将见的仅是一个环（而不显示图的其他部分）或一幅与${\displaystyle G}$同构的图，即阿严可以自行模拟该协议。因此，阿严从每一轮验证揭露之事，无法得到任何关于${\displaystyle G}$哈密顿环的资讯。

零知识条件的变式

“零知识”的定义有若干变形，分别在于如何严谨定义模拟结果“看似”真实的交互记录：

完美零知识（perfect zero-knowledge）

模拟器与真正交互产生的概率分布完全相等。离散对数示例即属此类。

统计零知识（statistical zero-knowledge）

两个分布并非完全相等，但统计上接近（英语：statistically close），即有某个可忽略函数，使该两列分布^{[注 3]}在任意集合取值的概率差，皆小于该函数。^[8]

计算零知识（computational zero-knowledge）

无高效算法分辨两个分布。

1 sources

应用

14 sources

身份验证

零知识证明的研究，是受身份验证系统启发。验证时，一方要向另一方证明自己身份，通常藉赖证明自己持有某种袐密（如通行密码），但不希望对方知悉该袐密，称为零知识知识证明（英语：proof of knowledge）。不过，通行密码一般不是太短，就是不够随机，不能用于许多零知识知识证明方案。零知识通行码证明（英语：zero-knowledge password proof）就是有考量密码长度限制的一类零知识知识证明。^{[来源请求]}

2015年4月，Sigma协议（“其中之一”证明，英语：one-out-of-many proofs）面世。^[9]2021年8月，美国网络基建、安全公司Cloudflare采用该种证明机制，以供应方硬件^{[请求校对翻译]}为私人网络提供验证服务。^[10]

1 sources

道德行为

密码学协议之中使用零知识证明，可以在不退让隐私的情况下，确保各方诚实。粗略言之，方法是迫用户零知识地证明，其所作所为是依足协议。^[11][12]由健全性，用户必先确实跟从协议，才能服众。又由于证明是零知识，此过程并无犠牲用户的隐私。

2 sources

核裁军

2016年，普林斯顿等离子物理实际室与普林斯顿大学展示一个技巧，或许适用于未来的核裁军谈判。其特点是，无需揭露某对象内部的机密构造，亦可允许督查员判断该对象是否核武器。^[13]

1 sources

区块链

零知识证明用于小零币（英语：Zerocoin protocol）与大零币协议中，最终于2016年发展成小零币（英语：Zcoin）^[14]（2020年改称飞熔币（英语：Firo (cryptocurrency)））^[15]和大零币两种加密货币。小零币内建有混币模型，以确保匿名，且该模型无需信任任何点对点用户或中央集权混币者。^[14]用户可以用另一种基准币交易，也可以将该币卖出买入小零币。^[16]:118大零币协议的模型也类似（该变式称为非交互式零知识证明（英语：Non-interactive zero-knowledge proof））^[17]，而且可以掩盖交易额，但小零币则不能。大零币的交易数据如此隐密，所以与小零币相比，较不易受到隐私计时攻击（英语：Timing attack）。不过，此层额外隐私，可能导致不能追踪假币，倘因此造成大零币供给的超通涨，可能无法侦测到。^[14][18]

2018年，防弹证明（bulletproofs）面世。其改进自非交互式零知识证明，不再需要可信的安装环境。^[19]其后，实现成“结舌”协议（Mimblewimble protocol，Grin和Beam两种加密币皆出自该协议）和门罗币。^[20]2019年，飞熔币实现Sigma协议（英语：Proof of knowledge），是对应小零币协议无可信环境的改进。^[21][9]同年，飞熔币引入莱兰托斯协议（Lelantus protocol），更自Sigma协议改进，隐去交易的源头与金额。^[22]

10 sources

沿革

零知识证明最早由莎菲·戈德瓦塞尔、希尔维奥·米卡利、查尔斯·拉克福（英语：Charles Rackoff）三人于1985年发表，论文题为《交互式证明系统的知识复杂度》。^[11]该论文引入交互式证明系统的IP复杂度类（英语：IP (complexity)），并构想出“知识复杂度”概念，衡量证明过程中，由证明者传递予验证者的知识量。三人亦给出首个具体问题的零知识证明，即零知识地证明某数不是模 m 的二次剩余。连同鲍鲍伊·拉兹洛（英语：László Babai）与什洛莫·莫兰（英语：Shlomo Moran）的另一篇论文，戈-米-拉三氏的论文发明了交互式证明系统。为此，五人同获1993年首届哥德尔奖。

引述戈-米-拉三氏：

该额外知识基本为0的情况尤其值得关注。我等证明，可以交互地证明某数非模 m 的二次剩余，而发布零额外知识。其出奇之处是，若不给定 m 的分解，则无高效算法判别某数是否模 m 的二次剩余。更甚者，任何已知的NP证明皆要表明 m 的素因数分解。这就表明，在证明过程中添加交互，可能减少证明某定理所必须交流的知识。 ^{[注 4]}

二次非剩余问题既有NP算法又有反NP算法，故位处NP与反NP两类之交集中。其后找到有零知识证明的若干个问题，亦具同样的性质，例如欧迪·戈德赖希（英语：Oded Goldreich）未经正式出版的证明系统，可以验证某数（为两个未知素数之积）不是布卢姆整数，即并非两个模4余3的素数之积。^[23]

欧迪·戈德赖希（英语：Oded Goldreich）、希尔维奥·米卡利、阿维·威格森更进一步证明，假定存在无懈可击的加密法，则可以造出三色图着色问题的零知识证明系统，而该问题本身为NP完全。又因为每个NP问题都可以高效化归成该NP完全问题，所以在前述假定下，所有NP问题皆有零知识证明。^[24]需要该假定的原因是，正如前节示例，需要有秘诺的手段。若存在单向函数，则的确有牢不可破的加密法。此为广泛引用的充分条件。另外也可能有物理方法实现。

更上一层楼，他们亦证明，图不同构问题（英语：graph nonisomorphism problem），即图同构问题（英语：graph isomorphism problem）之补（英语：complement (complexity)），有零知识证明。该问题已知属于反NP，但未知是否属于NP或其他实际可行的复杂度类。更一般地，罗素·英帕利亚佐（英语：Russell Impagliazzo）、莫迪凯·容（英语：Moti Yung）^{[译名请求]}二人，与米高·本-奥尔（Michael Ben-Or）及同事，两组证明：同样假设存在单向函数或牢不可破的加密，则任何属于IP（已证等于PSPACE）的问题，皆有零知识证明。换言之，任何命题若可藉交互系统证明，则可零知识证明。^[25][26]

许多理论家不希望假设不必要的条件，所以试图在不假定单向函数的条件之下，证明同样的结论。有种做法称为“多证明者交互式证明系统”（见交互式证明系统），即有多个独立的证明者，而非仅得一个。验证者可以将证明者逐个孤立，然后诘问，以免被作弊证明者误导。无需任何难解假设，已可证明在此系统中，任何NP问题皆有零知识证明。^[27]

后来发现，互联网等同时执行多个协议的环境中，较难构造零知识证明。研究并发零知识证明的先驱是辛西娅·德沃克（英语：Cynthia Dwork）、莫尼·纳奥尔（英语：Moni Naor）、阿米特·萨海（英语：Amit Sahai）。^[28]此类研究之中，重要成果有证据不可辨（英语：witness-indistinguishable proof）协议。与零知识相比，其性质较弱：可能有多种证据供证明者选择采用何者作证，此时仅要求验证者无法分辨证明者选择为何^{[注 5]}，但证明者可以泄漏部分资讯，如全体证据组成的集合。尽管失去零知识性质，但此类协议的好处是，并发时不会遇到此前提及的问题。^[29]

变式尚有非交互式零知识证明（英语：non-interactive zero-knowledge proof）。曼纽尔·布卢姆、保罗·费尔德曼（Paul Feldman）、米卡利证明，若证明者与验证者共有一条随机字符串，则可以达成计算零知识，而毋须交互。^[3][4]

6 sources

参见

• 配对式密码学（英语：Pairing-based cryptography）：给定${\displaystyle f(x)}$与${\displaystyle f(y)}$，无需知道${\displaystyle x}$、${\displaystyle y}$，已可计算${\displaystyle f(x\times y)}$。
• 安全多方计算：各方的输入值保密，但共同计算出该些输入对应的结果。
• 圈子签名（英语：Ring signature）：可以签署某文件，使圈外人无法得悉由圈内何人署名，只知圈内有某人署名。
• 阿罗资讯悖论（英语：Arrow information paradox）
• 密码学协议
• 费盖-菲亚特-萨莫尔身份认证（英语：Feige–Fiat–Shamir identification scheme）
• 密码学诸主题

注

1. 英文文献中，常称零知识协议中的证明者为Peggy（取prover的首字母）、验证者Victor（verifier的首字母），见爱丽丝与鲍伯。
2. 即欲证事实为某字符串${\displaystyle x\in L}$。
3. 对不同输入规模（安全参数），各有模拟器与真正交互此两个分布。
4. 原文作 "Of particular interest is the case where this additional knowledge is essentially 0 and we show that [it] is possible to interactively prove that a number is quadratic non residue mod m releasing 0 additional knowledge. This is surprising as no efficient algorithm for deciding quadratic residuosity mod m is known when m’s factorization is not given. Moreover, all known NP proofs for this problem exhibit the prime factorization of m. This indicates that adding interaction to the proving process, may decrease the amount of knowledge that must be communicated in order to prove a theorem."
5. 即无法分辨该证明者与采用另一证据的证明者。

参考文献

1. 林之晨. 區塊鏈的「零知識證明」是什麼東西？. 天下杂志. 2018-11-05, 660.
2. What is a zero-knowledge proof and why is it useful?. 16 November 2017 [2021-11-17]. （原始内容存档于2019-06-07）.
3. Blum, Manuel; Feldman, Paul; Micali, Silvio. Non-Interactive Zero-Knowledge and Its Applications. 1988: 103–112. ISBN 978-0897912648. S2CID 7282320. doi:10.1145/62212.62222. |journal=被忽略 (帮助)^{[失效链接]}
4. Wu, Huixin; Wang, Feng. A Survey of Noninteractive Zero Knowledge Proof System and Its Applications. The Scientific World Journal. 2014, 2014: 560484. PMC 4032740 . PMID 24883407. doi:10.1155/2014/560484.
5. Quisquater, Jean-Jacques; Guillou, Louis C.; Berson, Thomas A. How to Explain Zero-Knowledge Protocols to Your Children (PDF). Lecture Notes in Computer Science 435. 1990: 628–631. ISBN 978-0-387-97317-3. doi:10.1007/0-387-34805-0_60. |journal=被忽略 (帮助)
6. Chaum, David; Evertse, Jan-Hendrik; van de Graaf, Jeroen. An Improved Protocol for Demonstrating Possession of Discrete Logarithms and Some Generalizations. Lecture Notes in Computer Science 304. 1987: 127–141. ISBN 978-3-540-19102-5. doi:10.1007/3-540-39118-5_13. |journal=被忽略 (帮助)
7. Blum, Manuel. How to Prove a Theorem So No One Else Can Claim It. ICM Proceedings. 1986: 1444–1451. CiteSeerX 10.1.1.469.9048 .
8. Sahai, Amit; Vadhan, Salil. A complete problem for statistical zero knowledge (PDF). Journal of the ACM. 1 March 2003, 50 (2): 196–249. CiteSeerX 10.1.1.4.3957 . S2CID 218593855. doi:10.1145/636865.636868. （原始内容存档 (PDF)于2015-06-25）.
9. Groth, J; Kohlweiss, M. One-Out-of-Many Proofs: Or How to Leak a Secret and Spend a Coin. Annual International Conference on the Theory and Applications of Cryptographic Techniques. Lecture Notes in Computer Science (Berlin, Heidelberg: EUROCRYPT 2015). 14 April 2015, 9057: 253–280. ISBN 978-3-662-46802-9. doi:10.1007/978-3-662-46803-6_9.
10. Introducing Zero-Knowledge Proofs for Private Web attestation with Cross/Multi-Vendor Hardware. The Cloudflare Blog. 2021-08-12 [2021-08-18]. （原始内容存档于2021-12-13） （英语）.
11. Goldwasser, S.; Micali, S.; Rackoff, C., The knowledge complexity of interactive proof systems (PDF), SIAM Journal on Computing, 1989, 18 (1): 186–208 [2021-11-21], ISSN 1095-7111, doi:10.1137/0218012, （原始内容存档 (PDF)于2021-10-21）
12. Abascal, Jackson; Faghihi Sereshgi, Mohammad Hossein; Hazay, Carmit; Ishai, Yuval; Venkitasubramaniam, Muthuramakrishnan. Is the Classical GMW Paradigm Practical? The Case of Non-Interactive Actively Secure 2PC. Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security. CCS '20 (Virtual Event, USA: Association for Computing Machinery). 2020-10-30: 1591–1605. ISBN 978-1-4503-7089-9. doi:10.1145/3372297.3423366.
13. PPPL and Princeton demonstrate novel technique that may have applicability to future nuclear disarmament talks - Princeton Plasma Physics Lab. www.pppl.gov. [2022-03-22]. （原始内容存档于2021-09-21）.
14. Hellwig, Daniel; Karlic, Goran; Huchzermeier, Arnd. Privacy and Anonymity. Build your own blockchain - A practical guide to distributed ledger technology. SpringerLink. 3 May 2020: 112 [3 December 2020]. ISBN 9783030401429. doi:10.1007/978-3-030-40142-9_5. （原始内容存档于2021-11-21）.
15. Hurst, Samantha. Zcoin Announces Rebranding to New Name & Ticker "Firo". Crowdfund Insider. [4 November 2020]. （原始内容存档于30 October 2020）.
16. Bonneau, J; Miller, A; Clark, J; Narayanan, A. SoK: Research Perspectives and Challenges for Bitcoin and Cryptocurrencies. 2015 IEEE Symposium on Security and Privacy (San Jose, Carlifornia). 2015: 104–121 [2021-11-21]. （原始内容存档于2022-02-10）.
17. Ben-Sasson, Eli; Chiesa, Alessandro; Garman, Christina; Green, Matthew; Miers, Ian; Tromer, Eran; Virza, Madars. Zerocash: Decentralized Anonymous Payments from Bitcoin (PDF). IEEE. 18 May 2014 [26 January 2016]. （原始内容存档 (PDF)于2022-02-08）.
18. Orcutt, Mike. A mind-bending cryptographic trick promises to take blockchains mainstream. MIT Technology Review. [2017-12-18]. （原始内容存档于2019-08-15） （英语）.
19. Bünz, B; Bootle, D; Boneh, A. Bulletproofs: Short Proofs for Confidential Transactions and More. IEEE Symposium on Security and Privacy (San Francisco, Carlifornia). 2018: 315–334 [3 December 2020]. ISBN 978-1-5386-4353-2. S2CID 3337741. doi:10.1109/SP.2018.00020 . （原始内容存档于2022-01-21）.
20. Odendaal, Hansie; Sharrock, Cayle; Heerden, SW. Bulletproofs and Mimblewimble. Tari Labs University. [3 December 2020]. （原始内容存档于29 September 2020）.
21. Andrew, Munro. Zcoin cryptocurrency introduces zero knowledge proofs with no trusted set-up. Finder Australia. 30 July 2019 [30 July 2019]. （原始内容存档于30 July 2019）.
22. Aram, Jivanyan. Lelantus: Towards Confidentiality and Anonymity of Blockchain Transactions from Standard Assumptions. Cryptology ePrint Archive. 7 April 2019, (Report 373) [14 April 2019]. （原始内容存档于2019-04-14）.
23. Goldreich, Oded. A zero-knowledge proof that a two-prime moduli is not a Blum integer. Unpublished Manuscript. 1985.
24. Goldreich, Oded; Micali, Silvio; Wigderson, Avi. Proofs that yield nothing but their validity. Journal of the ACM. 1991, 38 (3): 690–728. CiteSeerX 10.1.1.420.1478 . S2CID 2389804. doi:10.1145/116825.116852.
25. Russell Impagliazzo, Moti Yung: Direct Minimum-Knowledge Computations. CRYPTO 1987: 40-51
26. Ben-Or, Michael; Goldreich, Oded; Goldwasser, Shafi; Hastad, Johan; Kilian, Joe; Micali, Silvio; Rogaway, Phillip. Everything provable is provable in zero-knowledge. Goldwasser, S. (编). Advances in Cryptology—CRYPTO '88. Lecture Notes in Computer Science 403. Springer-Verlag. 1990: 37–56.
27. Ben-or, M.; Goldwasser, Shafi; Kilian, J.; Wigderson, A. Multi prover interactive proofs: How to remove intractability assumptions (PDF). Proceedings of the 20th ACM Symposium on Theory of Computing. 1988: 113–121 [2021-11-27]. （原始内容存档 (PDF)于2007-04-17）.
28. Dwork, Cynthia; Naor, Moni; Sahai, Amit. Concurrent Zero Knowledge. Journal of the ACM. 2004, 51 (6): 851–898. CiteSeerX 10.1.1.43.716 . S2CID 52827731. doi:10.1145/1039488.1039489.
29. Feige, Uriel; Shamir, Adi. Witness Indistinguishable and Witness Hiding Protocols. 1990: 416–426. CiteSeerX 10.1.1.73.3911 . ISBN 978-0897913614. S2CID 11146395. doi:10.1145/100216.100272. |journal=被忽略 (帮助)