编辑“零知识证明（ZKP）”（章节）

== 计算示例 ==

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

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

证明协议如下：每轮，小静预备随机数，计算，将该值传予阿严。收到后，阿严随机请求下列两者之一：小静公开值，或值。单独看任何一个值，其分布皆是均匀随机，所以协议每轮皆不泄露任何机密。

阿严可以验证所得回应。若问，则可以计算，检查是否等于。若问，则可以计算，而该值应当等于，所以亦验证值是否满足该条件。若小静确实知道值，理应很易回答阿严的任一条问题。

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

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

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

==== 撮要 ====
小静要证知道值（如其密码）。

# 小静与阿严约定某素数，及域的乘法生成元。
# 小静计算，发送予阿严。
# 重复以下步骤若干次：
## 小静选某个均匀随机数，计算，发送予阿严。
## 阿严问小静或，二选其一。若问前者，则阿严验证。若问后者，则他验证。

之值，可视为的加密。若确为随机，在至间均匀分布，则也同样均匀分布，所以不会泄漏任何关于的信息（见一次性密码本）。

=== 大图的哈密顿环 ===
下列方案是曼纽尔·布卢姆提出。

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

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

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

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

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

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

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