零知识证明课件.pptVIP

零知识证明课件.ppt

此“教育”领域文档为创作者个人分享资料,不作为权威性指导和指引,仅供参考
  1. 1、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。。
  2. 2、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载
  3. 3、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
  4. 4、该文档为VIP文档,如果想要下载,成为VIP会员后,下载免费。
  5. 5、成为VIP后,下载本文档将扣除1次下载权益。下载后,不支持退款、换文档。如有疑问请联系我们
  6. 6、成为VIP后,您将拥有八大权益,权益包括:VIP文档下载权益、阅读免打扰、文档格式转换、高级专利检索、专属身份标志、高级客服、多端互通、版权登记。
  7. 7、VIP文档为合作方或网友上传,每下载1次, 网站将根据用户上传文档的质量评分、类型等,对文档贡献者给予高额补贴、流量扶持。如果你也想贡献VIP文档。上传文档
查看更多

零知識證明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)

文档评论(0)

子不语 + 关注
官方认证
服务提供商

平安喜乐网络服务,专业制作各类课件,总结,范文等文档,在能力范围内尽量做到有求必应,感谢

认证主体 菏泽喜乐网络科技有限公司
IP属地未知
统一社会信用代码/组织机构代码
91371726MA7HJ4DL48

1亿VIP精品文档

相关文档