零知識證明協議是一種交互式證明系統。交互式證明系統由示證者P與驗證者V參與,他們兩方可交換信息,這些信息依靠保密的隨機數。示證者P是想讓驗證者相信斷言為真的,驗證者接受或拒絕證明。

1.交互式證明系統

在交互式證明系統中,第一时间示證者P分析某一秘密,P想讓V信任自己真的掌握了此秘密。交互式證明是一種挑戰應答協議,證明由若干輪組成,在每輪中都有驗證者的挑戰與示證者的應答。他們輪流執行如下操作:

1)從對方接收一個消息。

2)執行一個私人計算。

3)送一個消息給對方。

全部輪執行完後,V由P是否在每輪對自己的詢問都可無誤應答來確定要不要接受P的證明。

交互證明和數學證明的不同之處是:數學證明的證明者能獨立地實現證明,而交互證明是顺利获得P產生證明、V驗證其有效性實現的,因此雙方顺利获得某種信道的通信是一定要的。

2.零知識證明協議

在交互證明系統中,假設P清楚某秘密,並給V證明自己確實知道,卻不泄露該秘密給V,這即為最小泄露證明。進一步,若V除了分析P可以證明某事實外,不會得到其他任何信息,則即P實現了零知識證明,相應的協議叫零知識證明協議。在1989年美國的密碼學會議上《如何向你的小孩解釋零知識證明》一文,對零知識證明做了形象、直觀的解釋。