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

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

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

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

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

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

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

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

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

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

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

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

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