奧卡姆剃刀

戰(zhàn)爭(zhēng)中你被俘了，敵人拷問(wèn)你情報(bào). 你是這么想的：如果我把情報(bào)都告訴他們，他們就會(huì)認(rèn)為我沒(méi)有價(jià)值了，就會(huì)殺了我省糧食;但如果我死活不說(shuō)，他們也會(huì)認(rèn)為我沒(méi)有價(jià)值而殺了我. 怎樣才能做到既讓他們確信我知道情報(bào)，但又一丁點(diǎn)兒情報(bào)也不泄露給他們呢？

這的確是一個(gè)令人糾結(jié)的問(wèn)題，但阿里巴巴想到了一個(gè)好辦法，當(dāng)強(qiáng)盜向他拷問(wèn)打開(kāi)山洞石門(mén)的咒語(yǔ)時(shí)，他對(duì)強(qiáng)盜說(shuō)：“你們離我一箭之地，用弓箭指著我，你們舉起右手我就念咒語(yǔ)打開(kāi)石門(mén)，舉起左手我就念咒語(yǔ)關(guān)上石門(mén)，如果我做不到或逃跑，你們就用弓箭射死我. ”

強(qiáng)盜們當(dāng)然會(huì)同意，因?yàn)檫@個(gè)方案不僅對(duì)他們沒(méi)有任何損失，而且還能幫助他們搞清楚阿里巴巴到底是否知道咒語(yǔ)這個(gè)問(wèn)題. 阿里巴巴也沒(méi)有損失，因?yàn)樘幱谝患氐膹?qiáng)盜們聽(tīng)不到他念的咒語(yǔ)，不必?fù)?dān)心泄露了秘密，而且他確信自己的咒語(yǔ)有效，也不會(huì)發(fā)生被射死的悲劇.

強(qiáng)盜舉起了右手，只見(jiàn)阿里巴巴的嘴動(dòng)了幾下，石門(mén)果真打開(kāi)了;強(qiáng)盜舉起了左手，阿里巴巴的嘴動(dòng)了幾下后石門(mén)又關(guān)上了. 強(qiáng)盜還是有點(diǎn)不信，說(shuō)不準(zhǔn)這是巧合呢，他們不斷地變換著節(jié)奏舉右手、舉左手，石門(mén)跟著他們的節(jié)奏開(kāi)開(kāi)關(guān)關(guān)，最后強(qiáng)盜們想，如果還認(rèn)為這只是巧合，自己未免是一個(gè)傻瓜，那還是相信阿里巴巴吧！

“零知識(shí)證明”說(shuō)的是示證者向驗(yàn)證者表明他知道某種秘密，不僅能使驗(yàn)證者完全確信他的確知道這個(gè)秘密，同時(shí)還保證一丁點(diǎn)兒秘密也不泄露給驗(yàn)證者. 阿里巴巴的這個(gè)方案，就是認(rèn)證理論“零知識(shí)證明”的一個(gè)重要協(xié)議.

除了被俘后如何靠情報(bào)保命這個(gè)問(wèn)題，零知識(shí)證明在社會(huì)領(lǐng)域中還有著很多應(yīng)用場(chǎng)合. 例如你證明了一個(gè)世界級(jí)的數(shù)學(xué)難題，但在發(fā)表出來(lái)之前，總得找個(gè)泰斗級(jí)的數(shù)學(xué)家審稿吧？于是你將證明過(guò)程發(fā)給了他. 他看懂后卻動(dòng)了歪心思，他把你的稿子壓住，把你的證明用自己的名義發(fā)表，他名利雙收，你郁悶至死. 你去告他也沒(méi)用，因?yàn)閷W(xué)術(shù)界更相信的是這位泰斗，而不是你這個(gè)無(wú)名之輩.

這并不是天方夜譚，而是學(xué)術(shù)界常見(jiàn)的難題，前些年有個(gè)博士生狀告他的泰斗級(jí)導(dǎo)師剽竊他的成果，但除了令師生關(guān)系惡化外沒(méi)有任何效果，最后他使出了撒手锏，稱他在給導(dǎo)師審閱的論文的關(guān)鍵公式中，故意標(biāo)錯(cuò)了一個(gè)下標(biāo)，而這會(huì)導(dǎo)致整個(gè)推導(dǎo)失敗. 學(xué)術(shù)委員會(huì)一查果真如此，但還是有傾向于泰斗的聲音，有人說(shuō)那是泰斗的筆誤，只不過(guò)讓你發(fā)現(xiàn)了而已，并不能證明那公式就是你推導(dǎo)出來(lái)的.

這個(gè)博士生故意標(biāo)錯(cuò)下標(biāo)，不能說(shuō)他沒(méi)有心眼，但他沒(méi)有把“零知識(shí)證明”理論用好，以至于落到這種地步. “零知識(shí)證明”早在1986年就被A. Fiat和A. Shamir用數(shù)學(xué)的方法給出了解決方案，并在同年申請(qǐng)了美國(guó)專利，但由于該理論可能被用于軍事領(lǐng)域，專利局被軍方密令擱置，6個(gè)月后，軍方命令“該申請(qǐng)發(fā)表后會(huì)有害于國(guó)家安全……所有美國(guó)人的研究未經(jīng)許可而泄露將會(huì)被判刑罰款”. 看來(lái)軍方認(rèn)為作者肯定是美國(guó)人了，但作者實(shí)際上是在美國(guó)申請(qǐng)專利的以色列人，研究也是在以色列的大學(xué)里做的，軍方這個(gè)命令擺了個(gè)大烏龍，雖然兩天后撤銷了，但已經(jīng)成為了學(xué)術(shù)界的笑柄.

這個(gè)笑柄也說(shuō)明了一個(gè)問(wèn)題，即“零知識(shí)證明”非常重要. 基于數(shù)學(xué)的推理雖然非常復(fù)雜，但思路卻很簡(jiǎn)單，上述的阿里巴巴方案就是其中之一. 其他的一些方案，也都是像這樣遵循著“分割和選擇協(xié)議“的.

例如數(shù)學(xué)中有個(gè)“哈密爾頓回路問(wèn)題”， 其大意是在任意給定的一個(gè)圖中，能不能找到這樣的路徑，即從一點(diǎn)出發(fā)，不重復(fù)地走過(guò)所有的結(jié)點(diǎn)（不必通過(guò)圖中每一條邊），最后又回到原出發(fā)點(diǎn). 如果“科學(xué)松鼠會(huì)”（一個(gè)科學(xué)傳播公益團(tuán)體，試圖通過(guò)自己的努力使科學(xué)傳播并流行開(kāi)來(lái)）貼了一張全連通圖（命名為A圖）懸賞哈密爾頓回路，而且任命我作為評(píng)審官，你幸運(yùn)地找到了一條這樣的回路，那該怎么辦呢？將結(jié)果直接發(fā)給我嗎？千萬(wàn)不要！因?yàn)檎f(shuō)不準(zhǔn)我會(huì)將你的成果讓給我的親信. 那你該怎么辦呢？應(yīng)該這么做：

1. 你將A圖的頂點(diǎn)弄亂，并生成一張新圖，只是頂點(diǎn)的位置變了，而新圖頂點(diǎn)之間的連線關(guān)系與A圖是完全一致的. 這時(shí)，你清楚新圖中每個(gè)頂點(diǎn)與A圖中每個(gè)頂點(diǎn)的對(duì)應(yīng)關(guān)系，而且你也知道新圖中的哈密爾頓回路.

2. 你將這張新圖發(fā)給我（沒(méi)錯(cuò)，就是僅僅一張新圖），上面并沒(méi)有畫(huà)著你發(fā)現(xiàn)的精彩回路.

3. 我收到后，對(duì)你提出兩個(gè)問(wèn)題中的一個(gè)：一是證明新圖就是從A圖變形過(guò)來(lái)的，所有頂點(diǎn)和連線的關(guān)系完全一致;二是畫(huà)出新圖中的哈密爾頓回路.

4. 如果你真的找到了A圖的哈密爾頓回路，這兩個(gè)問(wèn)題當(dāng)然都能輕松回答. 需要注意的是，你只需要回答第3步的其中一個(gè)問(wèn)題，千萬(wàn)不要兩個(gè)問(wèn)題一并回答，否則我就知道你關(guān)于A圖的哈密爾頓回路了.

5. 我還是不相信你，因?yàn)橛锌赡苣阒皇菍圖變了形，卻根本不知道A圖的哈密爾頓回路，而我在第3步時(shí)恰好要求你證明新圖就是從A圖變形過(guò)來(lái)的，你當(dāng)然能證明. 或者有可能你找了個(gè)你知道哈密爾頓回路的圖，但這張圖跟A圖一點(diǎn)關(guān)系都沒(méi)有，而我在第3步恰好要求你畫(huà)出這張圖的哈密爾頓回路.

6. 我要求你從第1步開(kāi)始重復(fù)這個(gè)驗(yàn)證過(guò)程，隨著次數(shù)的增加，第5步那種巧合的可能性就越來(lái)越低，如果你多次能回答對(duì)第3步中的問(wèn)題，那我還不相信你已經(jīng)找到了A圖的哈密爾頓回路，那我就是一個(gè)傻瓜.

7. 為了表明我不是傻瓜，我會(huì)在“科學(xué)松鼠會(huì)”群博里宣布你找到了A圖的哈密爾頓回路，而這時(shí)我并沒(méi)有看到你所畫(huà)的A圖的哈密爾頓回路.

現(xiàn)在，我們回到你證明了世界級(jí)的數(shù)學(xué)難題這個(gè)問(wèn)題上來(lái)，你可以用這種分割和選擇協(xié)議來(lái)進(jìn)行零知識(shí)證明，從而保護(hù)你的權(quán)利. 你公開(kāi)聲稱你解決了這個(gè)數(shù)學(xué)難題后，驗(yàn)證者會(huì)給你出一個(gè)其他的題，而能做出這道題的前提條件是已經(jīng)解決了那個(gè)數(shù)學(xué)難題，否則的話無(wú)解，而且這個(gè)條件是學(xué)術(shù)界所公認(rèn)的，這個(gè)題就是所謂的平行問(wèn)題. 不出所料，你靠著已經(jīng)解開(kāi)數(shù)學(xué)難題的基礎(chǔ)把這個(gè)平行問(wèn)題做出來(lái)了，但驗(yàn)證者還是不相信，他又出了一道平行問(wèn)題，你又做出來(lái)了，多次較量后，驗(yàn)證者就確信了你已經(jīng)解決了那個(gè)數(shù)學(xué)難題，雖然他并沒(méi)有看到具體的解法.

大家已經(jīng)看出來(lái)了，零知識(shí)證明需要示證者和驗(yàn)證者的密切配合，但如果你只是一個(gè)數(shù)學(xué)界的無(wú)名之輩，即使你宣稱解決了數(shù)學(xué)難題，也不會(huì)有人跟你配合著玩零知識(shí)證明，那你該怎么辦呢？

我告訴你一個(gè)可以在法庭上都能當(dāng)作有效證據(jù)的招數(shù). 你將證明打印好，選擇一個(gè)最可靠、最權(quán)威的郵政公司，把它寄給自己，當(dāng)你收到這個(gè)蓋著郵戳的包裹后，不要打開(kāi)，把它放好，然后就可以把證明寄給數(shù)學(xué)泰斗了. 如果他用自己的名義發(fā)表了，不必著急，等他依靠其影響力把這個(gè)證明炒熱后再出手. 你上法庭控告他，他當(dāng)然不承認(rèn)，在法庭上你就將那個(gè)沒(méi)開(kāi)封的包裹拿出來(lái)，上面清清楚楚地蓋著時(shí)間戳，這就證明了包裹里的證明是發(fā)生在那個(gè)時(shí)間戳之前的，加上之后的你郵給泰斗論文的郵件存根，和泰斗以自己名義發(fā)表論文的時(shí)間，三者就構(gòu)成了一個(gè)完整的證據(jù)鏈，泰斗灰頭土臉名聲掃地，而你則會(huì)大獲全勝名利雙收.endprint