零知识证明课件.pptVIP

零知識證明15.1互動式零知識證明系統的定義交互圖靈機作為證明者和驗證者各自的計算模型，將他們各自的交互圖靈機連接起來聯合計算就構成一問一答的交互協議。定義15.1一個交互圖靈機是一個（確定性）多帶圖靈機。它具有下列帶：1）一條只讀輸入帶；2）一條只讀隨機帶；3）一條讀寫工作帶；4）一條只寫輸出帶；5）一條只讀通信帶和一條只寫通信帶；6）一條僅有一個小方格的讀寫開關帶。定義15.2二個交互圖靈機連接在一起，若一個圖靈機的識別標記為1而另一個圖靈機的識別標記為0，它們的輸入帶合一，開關帶合一，一個圖靈機的只讀通信帶與另一圖靈機的只寫通信帶合一，反之前者的只寫通信帶與後者的只讀通信帶合一，但兩個圖靈機的隨機帶，工作帶和輸出帶是分開的。一對連接起來的交互圖靈機在初始時刻有共同的輸入，並置開關帶的內容為0。它們的聯合計算程式是一對形的有限或無限序列，其中一個形序列代表一個圖靈機的計算程式。序列中的每一對形總是有一個圖靈機（不必是同一個）工作而另一個圖靈機休息。第一對形對應於圖靈機的初始狀態，共同輸入和開關帶的內容0。若一個圖靈機停機了但開關帶的內容仍與它的識別標記相等，稱這時兩個圖靈機都已停機了，即計算在這一時刻終止。兩個圖靈機的輸出由這一時刻輸出帶的內容決定。定義15.3設A，B為連接起來的一對交互圖靈機，設對每一共同輸入，它們的聯合計算在有限步終止。記(A,B)(x)為共同輸入x聯合計算終止時B的輸出。它是在{0,1}中取值的隨機變數，即在聯合計算終止時刻圖靈機B的只寫頭在輸出帶所寫的二進數。由於A，B的隨機輸入滿足亂數約定，故(A,B)(x)為隨機變數。定義15.4一個交互圖靈機A稱為有時間複雜性（正整數集），若它與每個交互圖靈機B連接起來和對每個共同輸入x，它總是在t(|x|)步內停機（與A和B的隨機輸入無關，只要滿足亂數約定即可）。特別若存在一個正多項式p(n)，使圖靈機A有時間複雜性p(|x|)，則稱圖靈機A是多項式時間的。定義15.5一對連接起來的交互圖靈機（P，V）稱為語言L成員識別問題的交互（式省去）證明系統，若V是多項式時間的，且滿足下列兩個條件。(1)完全性：對每個x∈L， (15.1）(2)合理性：對每個x∈L和每個交互圖靈機B，B與V連接起來， 或 （15.2）其中V的輸出(P,V)(x)和(B,V)(x)表示驗證者是否接受x∈L，輸出1表示接受x∈L，輸出0表示拒絕x∈L。定理15.1語言L的成員識別問題屬於NP，當且僅當它有一個交互證明系統具有下列兩個性質。(1)交互是單向的（從證明者到驗證者）。(2)證明者和驗證者都只用確定性演算法（不出錯）。定義15.6設（P，V）為語言L的交互證明系統（參看定義15.5），稱（P，V）為語言L的一個關於不誠實驗證者的交互完全零知識證明系統，若對每個多項式時間的交互圖靈機V*，存在一個多項式時間的概率圖靈機M*，使對每個x∈L，下麵兩個條件成立。 1)當M*的輸入為x時，它以2-p(|x|)的概率輸出一個特殊符號，記作⊥，即 ，其中p(n)為任一固定的正多項式。 2）記m*(x)為一隨機變數，其分佈為M*(x)≠⊥的條件下M*(x)的條件分佈，即 再記ViewP,V’(x)為共同輸入x時在P與V*交互（聯合計算）過程中從V*的隨機帶讀出的亂數以及V*從P收到的消息，稱為V*的觀察。 於是有ViewP,V’(x)與m*(x)是相同分佈的隨機變數。 M*稱為P與V*交互的完善模擬器。定義15.7設(P，V)為語言L的交互證明系統，稱(P，V)為語言L的一個關於不誠實驗證者的交互計算零知識證明系統，若對每個多項式時間的交互圖靈機V*，存在一個多項式時間的概率圖靈機M*，使隨機變數族 與 是計算不可區分的（參看定義6.2）。 M*稱為P與V*交互的模擬器。定義15.8設（P，V）為語言L的交互證明系統，稱（P，V）為語言L的一個關於不誠實驗證者的交互統計（幾乎完全）零知識證明系統，若對每個多項式時間的交互圖靈機V*，存在一個多項式時間的概率圖靈機M*，使隨機變數族與 是統計接近的，即它們的變差距離 （15.3） 是|x|的一個可忽略函數，即對每個正多項式p(n)及一切充分大的|x|有 。定義15.9設（P，V）為語言L的交互證明系統，稱（P，V）為語言L的一個關於誠實驗證者的交互計算零知識證明系統，若存在一個多項式時間概率圖靈機M，使隨機變數族 與 是計算不可區分的（參看定義6.2）