你或许已经坐在了历史上最好的观景台上。眼下的密码算法与协议——如零知识证明与安全多方计算等——正在深刻地改变社会个体/组织之间信任的来源和它的成本。密码技术可能会远远超出一个技术的范畴，最终对社会变革产生深远的影响。或许，我们将要看到的景象要远比Michael Lewis「在金融业即将迎来变革的戏剧性时刻坐在位置最好的观景台前」所看到的更加波澜壮阔。——邓燚
起源
我开始研究密码学和零知识证明的时候当然完全想象不到它们今天所产生的影响。那时只是觉得密码概念和构造新鲜而有趣，当然还很重要，如你的基金申请书上所说的。
念博士第一年（2004）是基于pairing的IBE/signature进入井喷的前期。我也开始读一个超级腕的论文，他会在每篇论文后面留一个公开问题。那时每看到一个公开问题都会很兴奋，不管理不理解，总算有个问题可以思考了。不过只读过他三篇论文。
我刚花了两周时间拼命弄懂他第一篇论文留下的问题后，他的第二篇论文出现了，声称解决了他的第一篇文章中的问题，但是文末还是留下一个看起来有点难的公开问题；我又花了两周去弄懂这个新问题，很不幸的是他的第三篇论文如期而至，声称已经解决了第二个问题。当然，在文末他又留下了第三个公开问题。
我怀着礼貌读完了他的第三篇论文，但再没有心思去琢磨他的第三个问题了。那时开始对这个圈子和对自己都产生了失望。迷茫中拾起了Goldreich写的密码学基础。这本书对于几乎没有任何基础的我非常困难，每次重读它都会觉得上一次读的时候有点什么误会。但不知什么原因它使我平静了一点，不是那么急切地去找一个题目了。
读到最后零知识章节时，我留意了一下当时的一些主流会议这一领域的论文，通常都有但一年也只有几篇。那时便觉得自己可以尝试一下这个看起来很有趣竞争又不太激烈的领域。
第二年我读到Barak非黑盒模拟技术与分布式并发零知识时，对当时的一个重要问题——是否存在常数轮的完全并发的零知识协议——产生了很大的兴趣。读了Barak文章大概一个月后，我感觉到自己能够通过扩展Barak的技术构造这样的协议了。
当时非常兴奋，给Barak写了一封邮件，详细描述了自己的想法。第二天一大早便收到了Barak的邮件（他当时应该在IAS做博后，现在应该不会有空及时给读者回信了），他花了很长的篇幅给我解释了为什么我的想法是错误的。
这个问题也便一直困扰我至今。虽然十五年后依然没有答案，但我对密码学和安全性归约/模拟的认识几乎都来自对它的研究。密码学中许多独立于具体安全模型的安全性归约/模拟的创新都诞生于对这个（或紧密相关的）问题的研究之中。
这篇文章将描述一部分零知识证明研究所带来的模拟/归约的技术。由于时间和篇幅的原因，我们完全忽略了基于代数技巧的和各种依赖具体模型的模拟/归约技术。也由于个人的兴趣和十分有限的见识，偏见与不完整就难免了。
安全性归约，模拟，知识与知识的抽取。密码算法/协议的安全性（如可信/可靠性，隐私等）都源于底层问题（假定中的）计算困难性[1]。密码算法/协议的安全性证明通常指如下安全性「归约」: 给定一个（声称成功地攻破该算法/协议安全性的）敌手算法，我们构造一个高效的归约算法通过调用该敌手算法来打破底层困难性假设，从而在逻辑上完成了「如果底层困难性假设成立那么目标系统是安全的」这一命题。
下面我们经常会等同看待归约，模拟与知识/秘密的抽取。在归约算法调用敌手算法过程中，它需要模拟敌手在真实世界中看到的视图（view，为什么？）。因此模拟是整个归约最为关键的一环，这是为什么通常将它俩等同起来的原因。
假设给定一个涉及两方的构造（A，B）和一个扮演角色A的敌手A。在模拟A（在真实攻击中）所观察到的景象时，模拟算法（模拟器）通常需要在没有诚实方B的私有输入的情况下扮演B（以及其他可能的setup）的角色。这通常有两种途径（大多是两种途径的混合）：
1. 利用底层困难性/不可区分性假设本身模拟。这在非交互密码算法中常见，如证明ElGamal加密的CPA安全性时，模拟算法通过给敌手A输入可能无效的密文来利用它打破底层的DDH假设。这里的模拟简单而直接，底层DDH的不可区分性本身就假定了无论密文是否正常，A的表现几乎都一样。
2. 通过从A身上抽取（extract）到某些秘密/知识，或在有setup的场景下，模拟器自身扮演其他可信/诚实方来生成对模拟有利的（公共）输入，进而模拟诚实的B。这在交互密码协议的安全性证明中非常普遍，如下面将提到的经典Feige-Shamir零知识协议。
第二种模拟方法中的关键就是秘密/知识的抽取。我们很多时候在谈论安全性归约时，它的核心就是模拟，或者知识的抽取。事实上，第二种模拟方法给一般性的密码协议设计提供了一个原则：我们设计一个诚实方B的算法时，要使得在拥有诚实方的私有输入或对方和/或公共输入的某些秘密的前提下，我们均能顺利执行诚实方算法。
什么是「知识」？或者，怎么定义一个算法「知道」某个秘密/知识呢？Goldwasser他们在其开创性论文[GMR,STOC 85]中对知识的定义就是「the output of anunfeasible computation」。即：我们自己无法计算出来的东西。「output」在这里极为关键：敌手如果「知道」某个秘密，那么它（或者一个调用它的新算法）能够输出这个秘密。
这一概念在算法的世界里非常清晰，但它也是严谨安全性证明的噩梦：有时候一个算法「明明」应该知道某个秘密才能成功，可我们无法通过它或改编后的新算法来输出这个秘密。这里一个经典的例子就是Damgard的指数知识(knowledge of exponent)猜测，我们目前还无法将它建立在更为牢固的标准困难性假设上。
零知识证明与重置模拟(rewinding)：为什么简单的策略会失败
先回顾图同构的零知识证明。如果两个图 (G0,G1 ) 的顶点之间存在着边保持的置换映射 N，我们则称俩图是同构的。对图同构的一个传统的数学证明就是同构映射N本身，我们有时也称它为一个证据。
和传统的数学证明一样，这一交互证明也满足完备性，即如果断言为真那么V最终会接受；以及某种程度的可靠性：如果给定的俩图不同构，那么无论证明者使用什么策略有多强的计算能力，它无法以高于1/2的概率使得V接受。
观察到P发送的消息在外界看起来都无关它所拥有的关键证据n，这也是交互证明与传统数学证明相比它的威力所在：交互能实现零知识地证明，即P在整个过程中无需泄露关键证据（传统的数学证明）也能够使得验证者接受该断言。
GMR通过引入模范式给出了零知识严格的定义。粗略地讲，如果对于任意的多项式验证者策略V*, 如果存在一个多项式时间的模拟器S，它在没有证明者所拥有的关键证据（如上面提到的n）前提下也能够产生一个与真实交互不可区分的副本（transcript或验证者的视图，包括验证者的随机带和它所接收到的所有消息），那么我们说一个协议（P,V）是零知识的。给定一个任意的 V*，上述图同构证明协议的零知识可以由下面的模拟器S来证明（它扮演证明者的角色与V*交互，与真实世界的证明者不同的是，S拥有V*的代码）：
否则，将V*重置到最开始的状态，重新回到步骤1直到猜中i为止。容易证明，S运行的loop期望次数为2（故为期望多项式时间），并且它最终输出的副本与真实的交互服从同一分布。
一些观察
代码，随机带与黑盒模拟。上述模拟器S为V*选择随机带（我们假定知道V*随机带分布）仅仅是为了让V*运行起来，有时候我们也省略这一步。注意到在大多数情况下，尽管模拟器知道 V*的完整代码（包括它的随机带），它仍然很难直接利用这些信息来模拟。注意到 V*是一个任意的函数，我们不知道它将怎么利用自身的随机带和S发送的图H来生成一比特的挑战i。如上面所描述的S，它直接忽略了 V*的代码本身而将它看成一个黑盒，采用随机猜测i的策略进行模拟。
模拟器的输出分布。注意到上面提到的三个算法P，V，V*和S均为随机算法。我们说模拟器的输出与真实世界中P与V*之间的交互不可区分，是指模拟器的输出分布[2] (由模拟器所使用的随机数决定）和P与V*之间交互所产生的分布（由P和V*所使用的随机决定）对于任意的多项式时间算法而言是不可区分的。
重置：人与代码。上述模拟器S所采用的重置策略有两种方式来实现。一种是将V*的状态重置/回复（如将当前的 memory 擦掉等）到初始状态，另一种是想象模拟初始时我们拥有V*多个克隆，当模拟器猜错时就换一个copy重头开始。对于后者，读者可以想象同一代码的不同 copy 活在「平行世界」中，但他们计算的是同一个函数：给定相同的输入，它们的输出相同。这或许是人跟代码之间的根本区别：人能被重置吗？
为什么简单的重置策略会失败
我们希望图同构证明系统的可靠性错误非常小，而不是上面的1/2。上述协议可以通过顺序执行多次（验证者接受当且仅当所有的完整执行都接受）来降低这一可靠性错误（同时保持零知识性），但这会大幅增加交互的次数（轮复杂性，我们通常称发送一次消息为一轮）。
另一种方式就是并行执行多次协议来降低可靠性错误，这样可以保持交互轮数（3轮）不变。但它导致的一个问题就是上述简单的重置策略无法使得我们能够在多项式时间内完成模拟：假设进行n次并行，这时V的挑战问题变成了n个（可有一个n长的比特串表示），模拟器S同时猜中这n个问题的概率此时就变成 1/2n , 这会导致S的猜中为止的期望循环次数为2n，进而需要指数时间来完成模拟。3轮零知识的存在性目前仍是一个巨大的公开问题。
最近Canetti和Chen等人在Fiat-Shamir启发式（将公开掷币的交互协议转化为非交互协议的一种方法）方面的突破性工作[CCH+, STOC 19]中，给出了这一问题的强有力负面证据。
信任、隐私针对NP断言与一般性计算的零知识证明
零知识证明的可靠性让诚实验证者信任被证明断言的正确性，同时，它的零知识性最大程度地保护了诚实证明者的隐私，即它所知道的传统数学证明/证据。
我们接下来将针对一般NP断言构造零知识证明。所谓一般性NP断言指的是那些在给定数学证明/证据的条件下我们能够快速验证（虽然找到证明/证据可能非常困难）的断言，这包括有关一般性（高效算法）计算正确性的断言，比如，给定公开的多项式时间算法M，和一个y值，断言「存在x，使得输入x时M将输出y，M(x)=y」。
当给定这一断言的证据x时，任何人都可以快速验证它（这说明它也构成一个NP断言）：输入x然后自己运行算法M，检查M是否输出y。在许多密码场景下，M通常代表某实体的诚实算法，x代表这一方的私有输入，在不知x的情况下他人无法判断是否存在x使得M(x)=y。
这样，针对此类断言的零知识证明就发挥了不可思议的功能：这一证明既保护M所代表实体的隐私（证明结束时他人仍然不知道有关x的信息），又能使得其他相关方能确认M所代表的实体诚实地执行了算法M并输出y。我们能够对一般性高效算法的正确性构造零知识证明是它能够被广泛应用的根本原因。
参考
[1] 或许人们会怀疑随着计算技术（量子计算？）的进步，所有密码系统所依赖的数学难题在计算上都会变得容易。我觉得这是不可能的，因为实在无法想象一个没有密码的恐怖世界。
[2] 更准确一点应该是分布簇。