完整介紹了第一個零知識證明協議的背景知識、構造以及證明。

原文標題:《第一個零知識證明協議:二次剩餘》
撰文:胡鵬,安比技術社區

人類對很多概念的認識是漫長的、不斷更新且曲折的。即使今天很多人看了零知識證明的定義,還是會一頭霧水。不用擔心,提出這個概念的圖靈獎級別論文《交互證明系統的知識複雜度》(GMR[85]),曾連續四次被業界頂級的計算理論研討會 STOC 拒絕。看來不只是我們,那個時代最聰明的頭腦們同樣難以理解這篇極爲重要的論文所蘊含的深刻意義。

一文了解首個零知識證明協議「二次剩餘」

在《不可思議的零知識證明》一文中,我們通過三個小故事介紹了零知識證明裏面的重要概念:紅綠色盲遊戲(交互和隨機性),阿里巴巴洞穴(模擬器),旅行中的數學家(非交互和公開驗證)。但從直覺到嚴格的定義、證明之間,需要一些新的工具和方法論。這些由 GMR[85] 第一次給出,並且在之後得到廣泛的研究和推廣。第一個正式的零知識證明協議是二次剩餘 (Quadratic Residue) 的判定,通過它,我們介紹零知識證明中的工具——計算不可區分(computationally indistinguable) 和模擬範式(simulation paradigm),並且給出必要的證明。

背景知識

二次剩餘是數論裏面歷史悠久的問題,起源於同餘理論的研究。高斯在《算術研究》中,第一次系統的研究了剩餘理論,總結了包括歐拉、費馬、勒讓德等前人的理論成果。

在自然數的領域裏面,餘數 (remainder) 和模數 (modulus) 指的都是公式 a = nq + r 中的 r;在高斯引入了同餘符號≡後,則這個公式可以等價的寫成 a ≡ r (mod n)。

定義:如果存在整數 x,使得 a ≡ x^k (mod n),則 x 叫做 a 模 n 的 (k 次) 原根,其中當 k = 2 時,則稱 a 是模 n 的二次剩餘。

比如 12 ≡ 25 ≡ 5^2 (mod 13)。這種冪形式顯然吸引了高斯的興趣,在他的著作中研究了包括一次同餘、二次同餘以及高次同餘等關係。在後面的文章後我們還將提到同餘與羣論的關係。

二次剩餘問題,即給定互爲質數的 a, n(否則,a ≡ 0 (mod n)),判斷 a 是否是模 n 的二次剩餘 (是否存在模平方根 x)。人們在尋找這個問題的算法時,發現它的難度等價於整數分解難題 (integer factoring)。當 n 是質數時,存在多項式時間算法,但 n 是合數時,則找不到多項式時間的算法。二次剩餘問題是一個 NP 問題

二次剩餘問題的零知識證明協議

GMR[85] 利用二次剩餘問題構造了第一個零知識證明協議,來解決以下問題:Alice 聲稱「a 是模 n 的二次剩餘」,她可以直接展示模平方根 x(或者是 n 的因數分解),但她不想泄漏除了「a 是模 n 的二次剩餘」外的任何信息;Bob 一方面想着避免被 Alice 欺騙,另外一方面,可能也想盡辦法想在和 Alice 的交流中獲得「額外的信息」。

儘管上述採用了 Alice 和 Bob 這樣的人格化比喻,但所有的計算機協議的執行者實際都是運行在計算機上的程序。在理論分析中,一般採用圖靈機模型 (Turing Machine,TM)。也就是說 Alice,Bob 是兩臺 TM。其中 Alice 作爲證明者 (prover) 被認爲有無限計算資源,所以她能夠計算出模平方根,或者說能夠解答 NP 問題;Bob 作爲驗證者 (verifier),受限於計算資源,無法破解出模平方根 x,否則他就能自己判斷 Alice 的聲稱是否爲真了。

Alice 對 Bob 說,有兩個公式 :

  1. s ≡ r^2 (mod n)
  2. as ≡ (xr)^2 (mod n)

如果 s 和 as 都是模 n 的二次剩餘,那麼 a 也是模 n 的二次剩餘。但我不會一次性全展示給你,我每次隨機生成第一個公式,然後乘以 a 得到第二個公式,並且按照你拋硬幣的結果隨機展示其中一個:如果你拋到 0,我就給你公式 1 的模平方根 r;如果你拋到 1,我就給你公式 2 的模平方根 rx。下面是協議的示意圖:

一文了解首個零知識證明協議「二次剩餘」

運行這個協議 m 次,如果 Alice 成功通過 check,則以 1-(1/2)^m 的概率說服 Bob。那麼我們看下這個協議要滿足的目的:

  1. 如果 Alice 能計算出模平方根 x,則她能夠完成任意次挑戰;
  2. 如果 Alice 不能計算出模平方根 x,則她無論採用什麼策略,也會以極大概率被 Bob 拒絕;
  3. 不管 Bob 採用什麼策略,也無法從 Alice 這裏得到「a 是模 n 的二次剩餘「外的任何信息;

其中:

  1. 顯而易見,
  2. 由於 Alice 不知道 Bob 會拋到什麼結果,則她無法通過操縱第一步中的 s 來通過測試 (如果她知道是 0,則會生成 s ≡ r^2 (mod n),如果她知道是 1,她可以通過生成 s ≡ r^2/a (mod n),這樣發送的 w 就是 r,也能通過檢查);
  3. 直覺上來看,Bob 拋到 0,返回 r;拋到 1,返回 rx,Bob 無法從 s ≡ r^2 (mod n) 中計算出 r,無法獲取 x。

分析 3 並不能叫人滿意,因爲按照定義,Bob 不僅不會得知 x,也不能獲得除命題爲真外的「任何「信息。如何證明一個協議真的做到了零知識泄漏呢?

如何證明「零知識」

Bob 作爲驗證者,在零知識證明協議運行過程中,能夠「看到」的信息包括 Alice 發過來每條記錄 (transcript) 以及自己的拋硬幣結果 (local coins),即 view = {tanscript, local coins}。如果存在某個計算資源和 Bob 一樣的圖靈機 S,能夠獨立的通過某個算法在概率多項式時間內模擬一個 view',view 和 view'無法區分。那麼 Bob 實際可以自己在家運行這個協議獲得等價的信息,那麼 Alice 在交互證明中除了說服 Bob 命題爲真外,沒有泄漏任何信息。

上面有兩個概念需要嚴格的定義,「無法區分」和「模擬」:

  • 「無法區分」是個日常表達,記住上面的 Alice, Bob, S 都是圖靈機,它們並不關心對象間是否真的相同,只關心在計算模型和算法下能否觀察到差別;即運行某個概率多項式時間的算法——叫做區分器 (Distinguisher),對 view 和 view' 的分佈判斷的概率之差可以忽略不記,這種性質叫做「計算不可區分性」(computationally indistinguishable)
    一文了解首個零知識證明協議「二次剩餘」

    P 是 Prover(即 Alice),V* 是所有的 Verifier(包括誠實和惡意的 Bob),S 是 Simulator,D 是 Distinguisher,V*, S, D 都是概率多項式時間的圖靈機,w 是 P 的私有信息 (或者說是 P 能夠計算得到的,而 V 無法計算出來),x 是共有輸入 (a, n),在這裏即「a 是模 n 的二次剩餘「這個命題,negl 表示差異可忽略不計的 (negligible)。

  • 上面的「模擬器」S 最容易讓人誤解的地方在於,view 和 view' 計算不可區分,那麼 Bob 豈不是也會被 S 說服?這種誤解來源於把 S 看作是協議中 Alice 的角色,S 產生 view' 的過程並不是 Alice 和 Bob 按照零知識證明協議交互產生 view 的過程;S 是一個獨立運行的程序,只要能證明它能夠在概率多項式時間生成這個 view' 就可以了,無須和 Bob 交互。
    同樣由於這個原因,Bob 只可能在和 Alice 交互過程中被說服,而產生的 view 無法再去說服另外一個 Bob'。即 Bob 對 Bob' 說:我確信 Alice 是知道模平方根 x,你看這是我們倆對話的 view。Bob‘無法對此採信,因爲 Bob 可以通過模擬生成 view' 來糊弄他,他必須自己去和 Alice 進行交互證明才能被說服。這種侷限導致零知識證明不具備公開驗證(publicly verifiable) 的性質,這也說明一般意義上的數字簽名(digital signature) 並不是 [完美的] 零知識證明,這在後面介紹非交互零知識證明 (NIZK) 再進一步討論。

有個上面兩個概念,我們可以來構造一個「模擬器」S(a, n):

一文了解首個零知識證明協議「二次剩餘」

首先,這個程序存在概率多項式時間算法模擬隨機變量的生成,包括拋硬幣和生成 s;程序終止 (halt) 並打印結果的概率是 1/2,儘管可能存在循環但依舊可以在多項式時間內終止。綜上,即 S(x) 可以在多項式時間內完成;

其次,要證明這個程序生成的視圖{s, b , w}與零知識證明系統生成的視圖計算不可區分:

  1. s 和交互證明中的第一條消息都是隨機生成的,不可區分;
  2. b 和交互證明中 Bob 的拋硬幣都是隨機的,不可區分;
  3. w 的構造方法保證了即使 S 並沒有關於 x 的信息,w 在 Bob 看來是合法的,w 與交互證明中 Alice 的第三條信息不可區分;

在更嚴格的證明過程中,還會引入一個輔助工具——混合模擬器 S'(a, n, x),它是一個計算能力與 Prover 相同,但執行路徑與 S(a, n) 等價的程序,感興趣的讀者可以去查閱原始論文。順序 (sequential) 重複上面的模擬器 m 次,則能夠得到一組完整的 view',可以證明以上性質仍舊適用 (即對 sequential composition 是閉合的)。

到目前爲止,我們完整的介紹了第一個零知識證明協議的背景知識、構造以及證明,終於可以得到一個嚴格的定義:交互證明系統是零知識的,當且僅當存在概率多項式時間的模擬器 S,使得:

一文了解首個零知識證明協議「二次剩餘」

其中 x 是 P 要證明的命題,L 是某類命題的集合,z 是拋硬幣的結果,w 是隻有 P 擁有 (或能計算出) 的私有信息,V*指所有的驗證者。無論 V 採用什麼拋硬幣策略 z 與 P 交互,S 都可以同樣使用 z 來複現出來一個不可區分的版本。

看到這裏的讀者,相信你已經有了從數學上準確理解零知識證明的能力了,下一篇文章我們將討論非交互和可公開驗證的零知識證明協議 (NIZK)

參考

1. Shafi Goldwasser, Silvio Micali, Charles Rackoff: The Knowledge Complexity of Interactive Proof-Systems (Extended Abstract). STOC 1985: 291-304

來源鏈接:mp.weixin.qq.com