零知识证明

零知识证明(Zero—Knowledge Proof)，是由S.Goldwasser、S.Micali及C.Rackoff在20世纪80年代初提出的。它指的是证明者能够在不向验证者提供任何有用的信息的情况下，使验证者相信某个论断是正确的。零知识证明实质上是一种涉及两方或更多方的协议，即两方或更多方完成一项任务所需采取的一系列步骤。证明者向验证者证明并使其相信自己知道或拥有某一消息，但证明过程不能向验证者泄漏任何关于被证明消息的信息。大量事实证明，零知识证明在密码学中非常有用。如果能够将零知识证明用于验证，将可以有效解决许多问题。

在有必要证明一个命题是否正确，又不需要提示与这个命题相关的任何信息时，零知识证明系统(也叫做最小泄露证明系统)是不可或缺的。零知识证明系统包括两部分：宣称某一命题为真的示证者(prover)和确认该命题确实为真的验证者(verifier)。证明是通过这两部分之间的交互来执行的。在零知识协议的结尾，验证者只有当命题为真时才会确认。但是，如果示证者宣称一个错误的命题，那么验证者完全可能发现这个错误。这种思想源自交互式证明系统。交互式系统在计算复杂度理论方面已经获得异常独立的地位。

零知识证明(Zero—Knowledge Proof)起源于最小泄露证明。设P表示掌握某些信息，并希望证实这一事实的实体，设V是证明这一事实的实体。假如某个协议向V证明P的确掌握某些信息，但V无法推断出这些信息是什么，我们称P实现了最小泄露证明。不仅如此，如果V除了知道P能够证明某一事实外，不能够得到其他任何知识，我们称P实现了零知识证明，相应的协议称作零知识协议。

性质

在最小泄露协议中零知识证明需要满足下述两个性质。 (1)正确性。P无法欺骗V。换言之，若P不知道一个定理的证明方法，则P使V相信他会证明定理的概率很低。 (2)完备性。V无法欺骗P。若P知道一个定理的证明方法，则P使V以绝对优势的概率相信他能证明。 在零知识协议中，除满足上述两个条件以外，还满足下述的第三个性质。 (3)零知识性。V无法获取任何额外的知识。 我们把性质(1)和(2)称为零知识证明的正确性和完备性，而性质(3)称为零知识性。

属性

零知识证明需要满足三个属性。
1、如果语句为真，诚实的验证者（即：正确遵循协议的验证者）将由诚实的证明者确信这一事实。
2、如果语句为假，不排除有概率欺骗者可以说服诚实的验证者它是真的。
3、如果语句为真，证明者的目的就是向验证者证明并使验证者相信自己知道或拥有某一消息，而在证明过程中不可向验证者泄漏任何有关被证明消息的内容。
零知识证明并不是数学意义上的证明，因为它存在小概率的误差，欺骗者有可能通过虚假陈述骗过证明者。换句话来说，零知识证明是概率证明而不是确定性证明。但是也存在有技术能将误差降低到可以忽略的值。
零知识的形式定义必须使用一些计算模，最常见的是图灵机的计算模。