零知識證明(Zero—Knowledge Proof)，是由S.Goldwasser、S.Micali及C.Rackoff在20世紀80年代初提出的。它指的是證明者能夠在不向驗證者提供任何有用的信息的情況下，使驗證者相信某個論斷是正確的。零知識證明實質上是一種涉及兩方或更多方的協定，即兩方或更多方完成一項任務所需採取的一系列步驟。證明者向驗證者證明並使其相信自己知道或擁有某一訊息，但證明過程不能向驗證者泄漏任何關於被證明訊息的信息。大量事實證明，零知識證明在密碼學中非常有用。如果能夠將零知識證明用於驗證，將可以有效解決許多問題。
基本介紹
- 中文名：零知識證明
- 外文名：Zero-Knowledge Proof
- 所屬學科：密碼學
- 提出時間：20世紀80年代初
- 起源：最小泄露證明
引入,簡介,性質,屬性,證明舉例,
引入
顧名思義，零知識證明就是既能充分證明自己是某種權益的合法擁有者，又不把有關的信息泄露出去——即給外界的“知識”為“零”。其實，零知識證明並不是什麼新東西，早在16世紀的文藝復興時期，義大利有兩位數學家為競爭一元三次方程求根公式發現者的桂冠，就採用了零知識證明的方法。當時，數學家塔爾塔里雅和菲奧都宣稱自己掌握了這個求根公式，為了證明自己沒有說謊，又不把公式的具體內容公布出來(可能在當時數學公式也是一種技術秘密)，他們擺開了擂台：雙方各出30個一元三次方程給對方解，誰能全部解出，就說明誰掌握了這個公式。比賽結果顯示，塔爾塔里雅解出了菲奧出的全部30個方程，而菲奧一個也解不出。於是人們相信塔爾塔里雅是一元三次方程求根公式的真正發現者，雖然當時除了塔爾塔里雅外，誰也不知道這個公式到底是個什麼樣子。從這個故事，我們可以初步了解零知識證明的概念。
簡介
在有必要證明一個命題是否正確，又不需要提示與這個命題相關的任何信息時，零知識證明系統(也叫做最小泄露證明系統)是不可或缺的。零知識證明系統包括兩部分：宣稱某一命題為真的示證者(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、如果語句為真，證明者的目的就是向驗證者證明並使驗證者相信自己知道或擁有某一訊息，而在證明過程中不可向驗證者泄漏任何有關被證明訊息的內容。
零知識證明並不是數學意義上的證明，因為它存在小機率的誤差，欺騙者有可能通過虛假陳述騙過證明者。換句話來說，零知識證明是機率證明而不是確定性證明。但是也存在有技術能將誤差降低到可以忽略的值。
零知識的形式定義必須使用一些計算模型，最常見的是圖靈機的計算模型。
證明舉例
1、A要向B證明自己擁有某個房間的鑰匙，假設該房間只能用鑰匙打開鎖，而其他任何方法都打不開。這時有2個方法：
①A把鑰匙出示給B，B用這把鑰匙打開該房間的鎖，從而證明A擁有該房間的正確的鑰匙。
②B確定該房間內有某一物體，A用自己擁有的鑰匙打開該房間的門，然後把物體拿出來出示給B，從而證明自己確實擁有該房間的鑰匙。
後面的②方法屬於零知識證明。它的好處在於，在整個證明的過程中，B始終不能看到鑰匙的樣子，從而避免了鑰匙的泄露。
2、A擁有B的公鑰，A沒有見過B，而B見過A的照片，偶然一天兩個人見面了，B認出了A，但A不能確定面前的人是否是B，這時B要向A證明自己是B，也有2個方法。
① B把自己的私鑰給A，A用公鑰對某個數據加密，然後用B的私鑰解密，如果正確，則證明對方確實是B。
② A給出一個隨機值，並使用B的公鑰對其加密，然後將加密後的數據交給B，B用自己的私鑰解密並展示給A，如果與A給出的隨機值相同，則證明對方是B。
後面的方法屬於零知識證明。
3、有一個缺口環形的長廊，出口和入口距離非常近（在目距之內），但走廊中間某處有一道只能用鑰匙打開的門，A要向B證明自己擁有該門的鑰匙。採用零知識證明，則B看著A從入口進入走廊，然後又從出口走出走廊，這時B沒有得到任何關於這個鑰匙的信息，但是完全可以證明A擁有鑰匙。
