​

10-2交互证明系统

在计算机复杂性理论中，交互证明系统（Interactive proof system）是一种抽象机器，其将计算建模为两个参与方（证明者和验证者）之间的消息交换。通过交换信息，参与方证明某个声明成立（例如：，L为NP语言）。其中：

证明者（Prover）：拥有无穷的计算能力，且不可信；

验证者（Verifier）：拥有受限的计算能力（概率多项式时间），且诚实。

注：如果证明者能力也是受限、多项式时间的，该系统称为交互论证系统（Interactive argument system）。

交互证明系统的性质 

完备性：对于正确的声明，验证者「总是」接受。也就是说，一个诚实的验证者是能够被一个诚实的证明者用一个真声明来说服。

可靠性：对于错误的声明，验证者「总是」拒绝。也就是说，任何欺骗的证明者都不能够让诚实的验证者相信一个错误的声明。

此外，还有强调一个特性，即交互式：证明者与验证者之间采用交互的形式来完成证明过程。

交互证明系统的定义

与传统证明系统的区别

由定义可知，交互证明系统与传统数学证明最主要的区别在于交互性、参与者的随机性以及完备性和可靠性错误。数学证明系统是严谨的，要么使用不证自明的陈述，要么使用事先验证的证明。

相比而言，传统数学证明存在两个特点：

1.证明是短而简洁的。因为，验证者没有很多精力去读很长的证明。

2.验证者可能获取一些知识。譬如，证明者所采用的定理、证明的方式等等，一旦验证者获取了证明，那么它也可以向其他人证明。

交互证明系统可以改变上述两个特点，能够满足密码学的需求。

IP语言类

拥有交互证明系统的语言类，称之为IP语言类。显然，可以看出：

如果任何语言L有一个传统证明系统，那么它必然有一个交互证明系统。

因为，传统证明系统可以看成是一轮的交互证明系统，即。

NP语言类属于IP语言类。 

NP语言类是属于多项式时间内可验证的，都有一个传统证明系统。

今天的课程就到这里啦，下节课我们将继续学习零知识证明中的概念，敬请期待！

​