點(diǎn)擊上方藍(lán)字談思實(shí)驗(yàn)室

獲取更多汽車網(wǎng)絡(luò)安全資訊

構(gòu)造多方安全計(jì)算協(xié)議和零知識(shí)證明系統(tǒng)的核心挑戰(zhàn)之一在于：如何證明所設(shè)計(jì)的協(xié)議或系統(tǒng)是安全的？ 要回答這一問題，首先需要明確什么是“安全”。

對(duì)于多方安全計(jì)算，“安全” 至少意味著：各方的私有輸入不會(huì)被泄露。對(duì)于零知識(shí)證明，“安全” 至少要求：證明方（Prover）的私有信息不會(huì)被泄露。更嚴(yán)格地，密碼學(xué)中定義的“安全”是指：協(xié)議或系統(tǒng)在理論上不會(huì)泄露任何關(guān)于私有輸入的信息（信息泄露量為零）。

然而，如何精確定義“不會(huì)泄露任何信息”是一個(gè)極具挑戰(zhàn)的問題。在密碼學(xué)中，這一難題通過引入“模擬器”（Simulator）的概念得以解決。

模擬器的直覺來源于以下想法：如果參與協(xié)議或系統(tǒng)的任何一方，在不知曉其他方的私有輸入的前提下，可以完全模擬整個(gè)交互過程的行為，那么可以認(rèn)定該協(xié)議或系統(tǒng)是安全的。因?yàn)樵谶@種情況下，交互過程中產(chǎn)生的信息對(duì)任何方都是無效的——任何方僅憑自己的輸入和公開信息就可以生成這些交互，完全不需要依賴其他方的私有信息。

為了更形象地解釋模擬器的概念，可以借助一個(gè)課堂教學(xué)的類比：假設(shè)我們要驗(yàn)證一位學(xué)生是否從某位老師的課堂中真正學(xué)到了新知識(shí)。我們讓這位學(xué)生扮演老師的角色，站上講臺(tái)授課，板書內(nèi)容，與臺(tái)下的學(xué)生進(jìn)行問答交互。如果這位扮演老師的學(xué)生講得非常好，以至于臺(tái)下的其他學(xué)生無法分辨講課的人究竟是老師還是學(xué)生，那么可以得出結(jié)論：這位學(xué)生并沒有從老師那里學(xué)到任何新知識(shí)。因?yàn)樗軌颡?dú)立模擬整個(gè)課堂教學(xué)過程，且模擬得如此逼真，讓其他人無法分辨出真正的講課者是誰。

同樣的邏輯可以應(yīng)用于多方安全計(jì)算和零知識(shí)證明。如果模擬器能夠在不訪問他人私有信息的情況下，完美重現(xiàn)協(xié)議或證明過程中的所有交互細(xì)節(jié)，那么說明交互過程本身并未泄露任何有價(jià)值的信息，因而系統(tǒng)可以被認(rèn)定為“安全”。

統(tǒng)計(jì)不可區(qū)分 (statistically indistinguishable/close)

計(jì)算不可區(qū)分 (computationally indistinguishable)

hard-core predicate

證明多方安全計(jì)算協(xié)議抵御半誠(chéng)實(shí)敵手

現(xiàn)在討論如何在半誠(chéng)實(shí)安全模型下 (against semi-honest adversaries, semi-honest security, passive security)證明多方安全計(jì)算協(xié)議是安全的。具體地，選取多方安全計(jì)算協(xié)議為不經(jīng)意傳輸 (oblivious transfer, OT)[6]。OT可以說是最基本的多方安全機(jī)選協(xié)議之一。它的重要性體現(xiàn)在它的完備性[7]：任意的多項(xiàng)式時(shí)間可計(jì)算函數(shù) (polynomial time computable function)的多方安全計(jì)算協(xié)議都可以僅僅借助OT構(gòu)造出來。

OT協(xié)議細(xì)節(jié)如下圖所示：

不經(jīng)意傳輸協(xié)議

證明（非確定輪次的）交互式零知識(shí)證明系統(tǒng)抵御惡意敵手

這里討論如何在惡意安全模型下，論證一個(gè)圖三著色問題(3-coloring problem[8])的零知識(shí)證明是安全的。

之所以選擇3-coloring問題，是因?yàn)樗荖P完全的(NP-complete)[9]。如果我們可以構(gòu)造它的零知識(shí)證明，也意味著我們可以構(gòu)造任意NP問題的零知識(shí)證明(Any language in NP can be proved in zero knowledge[10])。

選擇惡意安全（malicious security, active security）模型的原因在于，在半誠(chéng)實(shí)安全（semi-honest security）模型下，零知識(shí)安全證明幾乎是平凡成立的，因?yàn)樵撃Ｐ图僭O(shè)證明者（Prover）不會(huì)偽造或欺騙，只要提交了證明，就一定是正確的，不存在作假的可能。然而，零知識(shí)證明系統(tǒng)真正需要防范的風(fēng)險(xiǎn)在于，證明者實(shí)際上并不知道正確的證明，卻仍能偽造一個(gè)錯(cuò)誤證明，使驗(yàn)證者（Verifier）誤以為其掌握了有效證明。

零知識(shí)證明可用下圖進(jìn)行描述：

三著色問題的零知識(shí)證明

對(duì)該零知識(shí)證明做一些解釋：

若以上條件均滿足，則驗(yàn)證者確信證明者確實(shí)掌握了一個(gè)正確的三著色方案，而無需得知完整的著色信息，從而實(shí)現(xiàn)零知識(shí)證明。

從模擬器（Simulator）輸出的視角來看，很容易證明其輸出與真實(shí)交互視角在計(jì)算上不可區(qū)分，這里不再贅述。

特別需要注意的是步驟 5 中，如果邊猜錯(cuò)，則跳回步驟 2 的行為，這一過程通常稱為重繞（rewinding）。模擬器面臨的最大挑戰(zhàn)在于，它事先并不知道驗(yàn)證者（Verifier）隨機(jī)選擇的是哪條邊，因此必須引入 rewinding 技術(shù)，以確保它最終能夠“猜中”Verifier 選擇的邊。

可以將 Verifier 理解為一臺(tái)圖靈機(jī)（Turing Machine），而 Simulator 則是在這臺(tái)圖靈機(jī)上運(yùn)行的小程序。在這個(gè)框架下，Simulator 能夠緩存 Verifier 初始化后的原始狀態(tài)（即隨機(jī)選邊之前的狀態(tài)），并在需要時(shí)將 Verifier 恢復(fù)到這一狀態(tài)。這個(gè)特殊的狀態(tài)重置功能就是 rewinding。

類似于現(xiàn)代操作系統(tǒng)中的虛擬機(jī)（VM），我們可以在某個(gè)時(shí)刻保存虛擬機(jī)的快照（snapshot），并在需要時(shí)恢復(fù)至這一狀態(tài)，而虛擬機(jī)本身并不察覺時(shí)間已經(jīng)被“回溯”。然而，需要注意的是，真正試圖欺騙 Verifier 的作弊證明者（Cheating Prover）并不具備 rewinding 能力，因?yàn)樗举|(zhì)上是 Verifier 外部的另一臺(tái)圖靈機(jī)，無法對(duì) Verifier 內(nèi)部的狀態(tài)進(jìn)行操控。這也是simulator和cheating prover的本質(zhì)區(qū)別: simulator可以在不知道證明的前提下成功“欺騙”verifier，而prover在不知道證明的前提下一定無法成功欺騙verifier (soundness)。

證明多方安全計(jì)算協(xié)議抵御惡意敵手

Coin Tossing協(xié)議過程如圖所示：

來源：知乎@hujwei

https://zhuanlan.zhihu.com/p/588114150