零知識證明及承諾協(xié)議的不可延展性研究.pdf

1、上世紀七、八十年代，現(xiàn)代密碼學迎來了蓬勃發(fā)展的新時期，產(chǎn)生了諸如公鑰密碼學、交互證明系統(tǒng)、偽隨機發(fā)生器等一系列具有里程碑式意義的成果，并開啟了現(xiàn)代密碼學與計算復雜性理論相結合的道路。Goldwasser在1997年FOCS會議上曾發(fā)表了題為“Cryptography and Complexity Theory：A Match Made inHeaven”的特邀報告，她指出：現(xiàn)代密碼學最重大的進展是將密碼學建立在計算復雜性的基礎之上，并且

2、正是計算復雜性理論將密碼學從一門藝術發(fā)展成為一門嚴謹?shù)目茖W。而零知識證明則是密碼學和復雜性理論相互交織、相互促進的最好見證。
　　 簡言之，零知識證明系統(tǒng)是一個兩方交互協(xié)議，其中證明者通過交互來向驗證者證明某一個斷言，并且確保不向驗證者泄露任何額外的信息。零知識證明自提出以來一直處于密碼學的中心位置，對密碼學的發(fā)展起到關鍵作用。首先，零知識證明為密碼協(xié)議安全性的形式化分析奠定了基礎，其基于模擬不可區(qū)分性的證明思想已成為可證明安全

3、理論的核心。更重要的是，零知識證明看似矛盾的獨特性質(zhì)令其集“保密性”和“認證性”于一身，因此廣泛應用于各類密碼算法和密碼協(xié)議的構造，例如身份認證協(xié)議、抗選擇密文攻擊安全的加密方案、以及抵抗惡意敵手的安全多方計算協(xié)議。
　　 作為構造零知識證明系統(tǒng)以及其他安全計算協(xié)議的一個基本組件，承諾的思想先于零知識證明而被學者們用于設計電話投幣、虛擬撲克等協(xié)議，并最終由Brassard等人給出了形式化的定義以及“承諾(commitment)”

4、這個形象的名稱。簡言之，承諾協(xié)議是一類兩方參與的兩階段交互協(xié)議。首先在承諾階段，承諾者對一個字符串v承諾，發(fā)送給接收者，并且確保接受者得不到關于v的任何信息；隨后在打開階段，承諾者公開v，并證明其與第一階段的一致性。承諾協(xié)議的兩個基本性質(zhì)分別稱為隱藏性和綁定性。所謂隱藏性，是指在承諾階段任意惡意的接收者都不能獲取承諾字符串的信息；而綁定性是指在打開階段，任意惡意的承諾者都不能將承諾打開為另外一個值，并且通過驗證。
　　 在密碼協(xié)

5、議的設計中，承諾協(xié)議通常作為子協(xié)議來構造更為復雜的安全計算協(xié)議，其主要作用是固定參與者的輸入，同時保證其隱私性。它通常與零知識證明系統(tǒng)配合來實現(xiàn)抵抗惡意敵手的安全多方計算協(xié)議。另外，承諾協(xié)議與零知識證明系統(tǒng)存在著內(nèi)在的聯(lián)系，并且兩者的研究總是相互促進，共同發(fā)展的。
　　 近年來，隨著互聯(lián)網(wǎng)的興起，密碼協(xié)議在并發(fā)、異步的網(wǎng)絡環(huán)境下的面臨著更多的安全性沖擊，協(xié)議基本的安全屬性已經(jīng)不足以應對復雜的網(wǎng)絡環(huán)境和應用。如何建立合理的協(xié)議安全

6、模型，以及設計滿足更高安全性需求、適用于互聯(lián)網(wǎng)應用的密碼協(xié)議逐漸成為了密碼學界關注的熱點問題。
　　 其中，并發(fā)不可延展性定義了零知識證明及承諾協(xié)議在多次并發(fā)執(zhí)行的過程中抵抗中間人攻擊的能力。以零知識證明為例，考慮如下情景：一個中間人敵手并發(fā)的參與多個會話，執(zhí)行同一個零知識證明協(xié)議，在其中一部分會話中，敵手作為驗證者接收并驗證誠實證明者對某些斷言的證明，而在另一部分會話中，敵手作為證明者與誠實的驗證者交互，試圖構造對相關斷言的證

7、明。能夠抵抗上述并發(fā)中間人攻擊的零知識證明或者承諾協(xié)議稱為并發(fā)不可延展的。研究者普遍認為，并發(fā)不可延展性在最大程度上反映了協(xié)議在開放網(wǎng)絡環(huán)境下所要達到的安全性要求。
　　 本文的研究主要圍繞并發(fā)不可延展的零知識證明系統(tǒng)以及承諾方案而展開，重點在與協(xié)議魯棒性研究，具體包括以下方面：
　　 ·關于并發(fā)不可延展的零知識
　　 近期，Lin等人將承諾協(xié)議的不可延展性擴展到更一般化的形式，稱為對任意k-輪協(xié)議的不可延展性，

8、討論承諾協(xié)議在以下場景中的安全性：敵手在左側會話中參與任意一個k-輪協(xié)議，而在右側與多個接收者交互，執(zhí)行某個承諾協(xié)議。k-不可延展性反應了一個承諾協(xié)議與其他協(xié)議組合執(zhí)行時的魯棒性，即一個k-不可延展的承諾可以與任意輪數(shù)不超過k的協(xié)議組合執(zhí)行，而不影響其安全性。因此，當與其他協(xié)議組合執(zhí)行時，此類承諾協(xié)議的不可延展性更易于分析。
　　 本文受上述文獻所啟發(fā)，研究并發(fā)不可延展零知識的魯棒性。在已有的不可延展零知識協(xié)議中，一部分使用了非

9、黑盒的模擬機制，而缺乏魯棒性正是非黑盒模擬機制自身的限制，尤其在并發(fā)環(huán)境下；另一部分雖然采用的黑盒模擬，但都是基于Goldreich-Kahan結構而構造，包含一個零知識子協(xié)議。由于零知識在并發(fā)組合下并不封閉，因此這些協(xié)議的魯棒性難于分析。為此，本文提出了第一個具有魯棒性并發(fā)不可延展零知識論證系統(tǒng)，具有如下特點：
　　 a)基于Feige-Shamir結構而構造，以具有魯棒性的不可延展承諾協(xié)議以及巧妙設計的證據(jù)不可區(qū)分證明系統(tǒng)來

10、實現(xiàn)零知識，并確保整個協(xié)議的魯棒性。
　　 b)采用“茫然模擬(oblivious simulation)”的策略來模擬敵手的視圖。
　　 c)在單向函數(shù)假設下，擁有最優(yōu)的輪復雜度，即超對數(shù)。
　　 d)通過適當調(diào)整子協(xié)議的輪數(shù)，可以實現(xiàn)與任意協(xié)議的組合。
　　 ●關于并發(fā)不可延展的承諾
　　 承諾協(xié)議的不可延展性針對其兩個階段分別定義，即關于承諾階段的不可延展性以及關于打開階段的不可延展性，分別

11、描述了兩個階段相對于自身的獨立性。近期，在TCC’09的一項工作中，Ostrovsky等人研究了這兩類不可延展性之間的關系，并指出，在基于模擬的不可延展性定義下，承諾階段的不可延展性并不一定蘊含打開階段的不可延展性，因此設計同時滿足這兩種性質(zhì)的承諾協(xié)議具有重要的理論意義。文中同時構造了一個計算隱藏且計算綁定的承諾方案，同時滿足承諾階段和打開階段的并發(fā)不可延展性。此后，在PKC’10中，Cao等人將該方案擴展并得到一個統(tǒng)計綁定的版本。然而

12、，上述兩方案(以及幾乎所有已知的不可延展承諾方案)都存在一個共同的限制：承諾階段和打開階段在時間上不可重疊。因此，如何構造一個兩階段可重疊的完全并發(fā)不可延展的承諾方案仍然是一個公開問題。
　　 為此，本文作了如下工作：
　　 a)分析并指出在目前的不可延展性定義下，上述問題無法解決。同時，本文給出了一個新的并發(fā)不可延展性定義，它與原定義在本質(zhì)上相同，但適用于兩階段可重疊的承諾協(xié)議。
　　 b)分析了上述問題存在的