老應書齋

讀書筆記,好文摘抄,精彩轉貼,研究材料,參考文獻。
正文

阿裏巴巴的零知識證明 ZT

(2010-05-01 23:11:59) 下一個
【抄自 《科學鬆鼠會》 奧卡姆剃刀 發表於 2010-04-25 14:10 http://songshuhui.net/archives/36968.html 】

戰爭中你被俘了,敵人拷問你情報。你是這麽想的:如果我把情報都告訴他們,他們就會認為我沒有價值了,就會殺了我省糧食,但如果我死活不說,他們也會認為我沒有價值而殺了我。怎樣才能做到既讓他們確信我知道情報,但又一丁點情報也不泄露呢?

這的確是一個令人糾結的問題,但阿裏巴巴想了一個好辦法,當強盜向他拷問打開山洞石門的咒語時,他對強盜說:“你們離我一箭之地,用弓箭指著我,你們舉起右手我就念咒語打開石門,舉起左手我就念咒語關上石門,如果我做不到或逃跑,你們就用弓箭射死我。”

強盜們當然會同意,因為這個方案不僅對他們沒有任何損失,而且還能幫助他們搞清楚阿裏巴巴到底是否知道咒語這個問題。阿裏巴巴也沒損失,因為處於一箭之地的強盜聽不到他念的咒語,不必擔心泄露了秘密,而且他確信自己的咒語有效,也不會發生被射死的杯具。

強盜舉起了右手,隻見阿裏巴巴的嘴動了幾下,石門果真打開了,強盜舉起了左手,阿裏巴巴的嘴動了幾下後石門又關上了。強盜還是有點不信,說不準這是巧合呢,他們不斷地換著節奏舉右手舉左手,石門跟著他們的節奏開開關關,最後強盜們想,如果還認為這隻是巧合,自己未免是個傻瓜,那還是相信了阿裏巴巴吧。

“零知識證明”說的是示證者向驗證者表明他知道某種秘密,不僅能使驗證者完全確信他的確知道這個秘密,同時還保證一丁點秘密也不泄露給驗證者。阿裏巴巴的這個方案,就是認證理論“零知識證明”的一個重要協議。

除了被俘後如何靠情報保命這個問題,零知識證明在社會領域中還有著很多應用場合。例如你證明了一個世界級的數學難題,但在發表出來之前,總是要找個泰鬥級的數學家審稿吧,於是你將證明過程發給了他,他看懂後卻動了歪心思,他把你的稿子壓住,把你的證明用自己的名義發表,他名利雙收,你鬱悶至死,你去告他也沒用,因為學術界更相信的是這位泰鬥,而不是你這個無名之輩。

這並不是天方夜譚,而是學術界常見的難題,前些年有個博士生告他的泰鬥級導師剽竊他的成果,但除了令師生關係惡化外沒有任何效果,最後他使出了撒手鐧,稱他在給導師審閱的論文的關鍵公式中,故意標錯了一個下標,而這會導致整個推導失敗。學術委員會一查果真如此,但還是有傾向於泰鬥的聲音,有人說那是泰鬥的筆誤,隻不過讓你發現了而矣,並不能證明那公式就是你推導出來的。

這個博士生故意標錯下標,不能說他沒有心眼,但他沒有把“零知識證明”理論用好,以致於落到這種地步。“零知識證明”早在1986年就被A.Fiat和A.Shamir用數學的方法給出了解決方案,並在同年申請了美國專利,但由於該理論可能被用於軍事領域,專利局被軍方密令擱置,6個月後,軍方命令:“該申請發表後會有害於國家安全……所有美國人的研究未經許可而泄露將會被判刑罰款”。看來軍方認為作者肯定是美國人了,但作者實際上是在美國申請專利的以色列人,研究也是在以色列的大學裏做的,軍方這個命令擺了個大烏龍,雖然兩天後撤消了,但已經成為了學術界的笑柄。

這個笑柄也說明了一個問題,即“零知識證明”非常重要。基於數學的推理雖然非常複雜,但思路卻很簡單,上述的阿裏巴巴方案就是其中之一。其它的一些方案,也都是像這樣遵循著分割和選擇(Cut and Chose)協議的。

例如圖論中有個哈米爾頓回路(Hamiltonian Cyclic)問題,說的是多個頂點的全連通圖,若有一條通路通過了所有頂點,且每個頂點隻通過一次,那這就是哈米爾頓回路。如果頂點較多的話,即使用計算機窮舉計算很難找出這條回路,因為通路的可能性真在是太多了。

如果鬆鼠會貼了一張全連通圖(命名為A圖)懸賞哈米爾頓回路,而且任命我(奧卡姆剃刀)作為評審官,你幸運的找到了一條,那該怎麽辦呢,將結果直接發給我嗎?千萬不要,因為保不齊我會將你的成果讓給了我的親信。那你該怎麽辦呢?應該這麽辦:

1、你將A圖的頂點搞亂了,並生成一張新圖,隻是頂點的位置變了,而新圖頂點之間的連線關係與A圖是完全一致的。這時,新圖中每個頂點與A圖中每個頂點的對應關係你是清楚的,而且新圖中的哈米爾頓回路你也是知道的。

2、你將這張新圖發給我,沒錯,就是僅僅一張新圖,上麵並沒有畫著你發現的牛B回路。

3、我收到後,對你提出兩個問題中的一個:一是證明新圖就是從A圖變形過來的,所有頂點和連線的關係完全一致,二是畫出新圖中的哈米爾頓回路。

4、如果你真的找到了A圖的哈米爾頓回路,這兩個問題當然都能輕鬆回答。需要注意的是:你隻需要回答第3步的其中一個問題,千萬不要兩個問題一並回答,否則我就知道你關於A圖的哈米爾頓回路了,你就SB了。

5、我還是不相信你,因為有可能你隻是將A圖變了形,卻根本不知道A圖的哈米爾頓回路,而我在第3步時恰好要求你證明新圖就是從A圖變形過來的,你當然能證明。或者有可能你找了個你知道哈米爾頓回路的圖,但這張圖跟A圖一點關係都沒有,而我在第3步恰好要求你畫出這張圖的哈米爾頓回路。

6、我要求你從第1步開始重複這個驗證過程,隨著次數的增加,第5步那種巧合的可能性就越來越低,如果你多次能回答對第3步中的問題,那我還不相信你已經找到了A圖的哈米爾頓回路,那我就是一個傻瓜。

7、為了表明我不是傻瓜,我在鬆鼠會群博裏宣布你找到了A圖的哈米爾頓回路,而這時我並沒有看到你所畫的A圖的哈米爾頓回路。

回到你證明了世界級的數學難題的問題,你可以用這種分割和選擇協議來進行零知識證明,來保護你的權利。你公開聲稱你解決了這個數學難題後,驗證者會給你出一個其它的題,而能做出這道題的前提條件是已經解決了那個數學難題,否則的話無解,而且這個條件是學術界所公認的,這個題就是所謂的平行問題。不出所料,你靠著已經解開數學難題的基礎把這個平行問題做出來了,但驗證者還是不信,他又出了一道平行問題,你又做出來了,多次較量後,驗證者就確信了你已經解決了那個數學難題,雖然他並沒有看到具體的解法。

大家已經看出來了,零知識證明需要示證者和驗證者的密切配合,但如果你隻是一個數學界的無名之輩,即使你宣稱你解決了數學難題,也不會有人跟你配合著玩零知識證明,那你該怎麽辦呢?

我告訴你一個可以在法庭上都能當作有效證據的招數,你將證明打印好,選擇一個最可靠最權威的郵政公司,把它寄給自己,當你收到這個扣著郵戳的包裹後,不要打開,把它放好,然後就可以把證明寄給數學泰鬥。如果他用自己的名義發表了,不必著急,等他依靠其影響力把這個證明炒熱後再出手,你上法庭控告他,他當然不承認,在法庭上你將那個沒開封的包裹拿出來,上麵清清楚楚地蓋著時間戳,這就證明了你包裹裏的證明是發生在那個時間戳之前的,加上之後的你郵給泰鬥論文的郵件存根,和泰鬥以自己名義發表論文的時間,三者就構成了一個完整的證據鏈,泰鬥灰頭土臉名聲掃地,而你大獲全勝名利雙收。

參考文獻:《通信網的安全-理論與技術》,王育民等編著,西安電子科技大學出版社,2000.5

[ 打印 ]
閱讀 ()評論 (1)
評論
榕城老應 回複 悄悄話 “零知識證明”的精彩之處不僅在於如何去構造一個證明,而且啟發人們思路如何在推銷知識的同時加以保護。其要點是將不影響價值顯示的鑰匙與之分離藏匿。
登錄後才可評論.