1. 引言

本文將探討構建零知識證明（ZKP）的一種非常有趣的方法：

• MPC-in-the-Head Transformation（轉換）。
  • 該方法最早由 2007 年的論文 Zero-knowledge from secure multiparty computation 提出，通常被稱為 IKOS 轉換，該名稱來源于論文作者的首字母縮寫。
  • 該轉換允許從任意的 MPC 協議（將其視為黑盒）構建零知識證明系統。

本文將介紹 MPC 協議背后的直覺、最初的轉換技術，并探討該構造如何應用于開發后量子簽名方案。

2. 何為MPC？

安全多方計算（MPC） 是一種密碼學技術：

• 允許多個參與方共同計算一個函數的結果，同時各自保留輸入的私密性。
• 每個參與方都持有自己的私有輸入，目標是對所有私有輸入執行某個預定的函數。
• 協議結束時，每個參與方只應學習到該函數的輸出，而不能得知其他參與方的輸入信息。
  

3. 一個簡單的MPC協議

MPC 協議中常用的示例是如下場景：

• 假設一家公司的一群員工想要知道全體員工的平均工資，但又不想暴露自己的工資。
  • 在這個設定中，每個員工持有一個私有輸入 $S_i$，表示自己的工資。

假設所有計算都在某個素域 ${\mathbb{F}}_p$ 上進行，希望構建一個協議，用于計算所有員工私有輸入（工資）的總和 $\sum S_i\in {\mathbb{F}}_p$。隨后，平均工資可以在明文中通過總和除以員工數量來計算。

該協議分為三個步驟：

• 1）輸入共享（input sharing）
• 2）本地累加（local accumulation）
• 3）重構（reconstruction）。

3.1 輸入共享

設想1號員工持有自己的工資 $S_1$。其首先會對 $S_1$ 進行加法秘密共享（additive secret sharing），也就是說將該值“分割”為 $n$ 個份額：
$$[S_1{]}_1,[S_1{]}_2,\dots ,[S_1{]}_n$$

這些份額都是域中的元素，滿足它們的總和等于原始值 $S_1$：
$$S_1=[S_1{]}_1+[S_1{]}_2+\dots +[S_1{]}_n$$

在實踐中，計算方式如下：首先從 ${\mathbb{F}}_p$ 中均勻隨機采樣前 $n?1$ 個份額，然后計算最后一個份額為：
$$[S_1{]}_n=S_1?\sum _{i=1}^{n?1}[S_1{]}_i$$

顯然，如果前 $n?1$ 個份額是從 ${\mathbb{F}}_p$ 中均勻隨機選擇的，那么最后一個份額也在 ${\mathbb{F}}_p$ 中是均勻分布的（即使只有其中一個是均勻隨機的也同樣成立）。這是一種實現完美隱私（perfect privacy）的簡單方式：

• 即使攻擊者看到最多 $n?1$ 個份額，也無法得知原始值 $S_1$ 的任何信息。

3.2 本地累加（Local accumulation）

在這一步中，每位員工將自己生成的第 $i$ 個份額發送給第 $i$ 個參與方。以1號員工為例，他們會將 $[S_1{]}_2$ 發送給2號員工，$[S_1{]}_3$ 發送給3號員工，依此類推。1號員工最終會從其他員工那里接收到以下份額：
$$[S_2{]}_1,[S_3{]}_1\dots ,[S_n{]}_1$$

同時他們還持有自己生成的份額 $[S_1{]}_1$。

接下來，每位員工可以將所有收到的份額進行本地累加（Local accumulation）：
$$[S{]}_1=[S_1{]}_1+[S_2{]}_1+\dots +[S_n{]}_1$$

然后將這個累加結果 $[S{]}_1$ 發送給其他所有員工。

3.3 重構（Reconstruction）

最終，每位員工都將收到其他員工累加的份額：
$$[S{]}_1,[S{]}_2,\dots ,[S{]}_n$$

因此，每個人都可以獨立地重構最終輸出，即將所有 份額 相加：
$$S=[S{]}_1+[S{]}_2+\dots +[S{]}_n$$

這個結果正是所有私有輸入的總和。

要理解為什么這樣有效，可以注意到，在這種秘密共享方案中，份額具有加法同態性（additive homomorphism）：

• 兩個 秘密的份額 相加，得到的是這兩個 秘密和 的份額。

在這個具體案例中，之所以能使用這么簡單的協議，是因為要共同計算的函數對私有輸入來說是線性的。而一般情況下，MPC 協議可以用于計算任意函數，但這就需要更復雜的技術。

若想深入了解 MPC 構造的原理，一個很好的起點是：

• Y. Lindell 2020年的綜述論文Secure Multiparty Computation (MPC)。

4. MPC 協議的性質

一個 MPC 協議應滿足兩個主要性質：

• 正確性（Correctness）：協議的輸出應該是函數的正確輸出，就像各方在明文下直接計算的結果一樣。
• 隱私性（Privacy）：各方除了函數的輸出外，不應獲知其他參與方的任何私有輸入信息。

一般來說，假設有一些參與方可能會被腐化，也就是說，攻擊者可能能夠看到這些參與方的輸入以及它們之間交換的消息。如果一個 MPC 協議即使在最多 $t$ 個參與方被腐化的情況下仍然能保持隱私性，則稱該協議是 $t$-隱私（$t$-Private） 的。如果被腐化的參與方超過 $t$ 個，那么可能就會泄露關于誠實參與方私有輸入的信息。

在 本文所提及的“MPC-in-the-Head 轉換” 這個基本的轉換中，只要求 2-隱私（2-Privacy） —— 也就是說，只要腐化的參與方不超過兩個，隱私性就仍然能夠被保證。

此外，本文所描述的 MPC 協議（“MPC-in-the-Head 轉換” ）只需要在半誠實模型（semi-honest model）下是安全的。也就是說，假設所有參與方都會誠實地執行協議，但可能試圖在執行過程中盡可能多地獲取信息。這類參與方通常被稱為“誠實但好奇（honest but curious）”。如，前文描述的那個簡單協議就假設所有參與方都誠實地遵守協議流程：如果有參與方偏離協議執行流程，最終輸出可能會被錯誤地計算出來。

最初的 IKOS 轉換 將底層的 MPC 協議視為一個黑盒，但需要指出的是，在一些效率更高的方案中，MPC 協議是經過特別設計的，以便在應用轉換時能導出一個高效的零知識證明系統。

5. MPC-in-the-Head 轉換

“MPC-in-the-Head 轉換的目標是：

• 利用具備上述性質的任意一個 MPC 協議，來構建一個零知識證明系統，用于某個NP關系 $\mathcal{R}?\mathcal{X}\times \mathcal{W}$。

在這種新的設定中，有兩方參與者：

• 證明者（prover）
• 和 驗證者（verifier）。

證明者希望讓驗證者相信自己知道一個見證 $w$，滿足 $(x,w)\in \mathcal{R}$，其中 $x$ 是公開輸入。

舉個例子，關系 $\mathcal{R}$ 可以是 SHA-256 哈希函數的原像關系：
$$\mathcal{R}=\{(x,w)\mid \text{SHA256}(w)=x\}$$

證明者將見證 $w$ 拆分為加法份額 $w_1,w_2,\dots ,w_n$，使得所有份額的和等于原始的見證 $w$：
$$w=w_1+w_2+?+w_n$$

接著，證明者會在“自己的腦海中（in its head）”模擬整個 MPC 協議：

• 可以想象這是在導演一場由 $n$ 個布偶角色參與的小型舞臺劇，每個角色代表一個協議參與方。
• 這些“布偶”按照一套腳本（即 MPC 協議的執行步驟）進行互動。
• 第 $i$ 個參與方持有份額 $w_i$ 作為自己的私有輸入，所有參與方都共享公開輸入 $x$。
• 這些模擬的參與方共同計算的函數如下：如果關系滿足就返回 1，否則返回 0：
  $$f(x,w_1,w_2,\dots ,w_n)=\{\begin{array}{ll}1& \text{if?}\mathcal{R}(x,w_1+w_2+\dots +w_n)\\ 0& \text{otherwise}\end{array}$$

請注意，由于關系 $\mathcal{R}$ 屬于 $\mathsf{NP}$，它擁有一個多項式時間的驗證算法。因此函數 $f$ 也是高效可計算的：

• 它只需要對局部見證進行求和，然后驗證該關系是否成立。

舉一個具體的例子：對于 SHA-256 原像關系，MPC 協議要計算的函數如下所示：

def f(x, w_1, w_2, ..., w_n):w = w_1 + w_2 + ... + w_nif SHA256(w) == x:return 1else:return 0

在實際中，這個函數通常被表示為定義在某個有限域上的算術電路（arithmetic circuit） $C$。

在模擬完 MPC 協議后，證明者會為每個參與方生成一個 view（視圖）。每個視圖包含：

• 該參與方的私有輸入；
• 該方在模擬執行期間發送和接收的所有消息。

如，如果第 $i$ 個參與方向第 $j$ 個參與方發送了一條消息 $m$，那么：

• 第 $i$ 方的視圖中將包含一個外發消息 $\text{out}(j,m)$；
• 第 $j$ 方的視圖中將包含一個接收消息 $\text{in}(i,m)$。

接下來，證明者會將所有參與方視圖的承諾（commitment）發送給驗證者。承諾方案（commitment scheme）是一種密碼學原語：

• 它允許一方對某個值進行承諾（即固定但不公開），并在之后可以選擇打開該承諾來揭示該值。

一個承諾 $c=Comm(x)$ 應該滿足以下兩個性質：

• 隱藏性（hiding）：該承諾 $c$ 不泄露任何關于值 $v$ 的信息；
• 綁定性（binding）：證明者無法在之后打開一個不同的值 $y\ne x$，卻讓驗證者相信它是 $c$ 的合法打開值。

一個具體示例是，使用抗碰撞哈希函數（collision-resistant hash function）來實現簡單的承諾方案：

c = H(v || r)

其中 $v$ 是要承諾的值，$r$ 是某個隨機數。

def commit(x: bytes) -> bytes:nonce = random(16)return sha256(x + nonce)def verify_opening(x: bytes, nonce: bytes, commitment: bytes) -> bool:return len(nonce) == 16 and sha256(x + nonce) == commitment

在證明者將每個視圖的承諾發送給驗證者之后，驗證者會隨機選擇兩個參與方（設為第 $i$ 個和第 $j$ 個），并要求打開這兩個參與方的視圖。隨后，證明者將這兩個視圖以明文形式發送給驗證者。

此時，驗證者可以獲得以下信息：

• 兩個輸入 $w_i$ 和 $w_j$；
• 兩個參與方（$i$ 和 $j$）在協議執行過程中發送和接收的所有消息記錄。

驗證者會檢查以下幾點：

• 所給視圖是對應承諾的有效打開值；
• 第 $i$ 個和第 $j$ 個參與方誠實地遵守了協議流程；
• 兩個視圖彼此一致，即任何一條雙方之間交換的消息，在兩邊的記錄中內容完全一致；
• 兩個打開的視圖一致地認為函數的輸出是 $1$（即計算結果正確）。

Soundness（完備性）：

• 該方案的完備性（soundness）直接依賴于底層 MPC 協議的正確性。假設 MPC 協議具有完美正確性，那么如果證明者誠實地模擬協議執行，輸出結果必然是正確的。
  但如果證明者嘗試作弊，它必須至少在一個參與方的視圖中作弊。這意味著總會有至少一對視圖與誠實執行的協議不一致。驗證者隨機選擇兩方來檢查的情況下，選中這一對不一致視圖的概率是 $1/\left(\genfrac{}{}{0ex}{}{n}{2}\right)$，因此，證明者成功作弊的概率是：
  $$\epsilon =1?1/\left(\genfrac{}{}{0ex}{}{n}{2}\right)$$
  如同所有零知識證明系統一樣，只要重復執行足夠多次，就可以將 soundness error（證明者成功作弊的概率）降低到指數級小。

Zero-knowledge（零知識性）：

• 零知識性（Zero-knowledge）則直接基于底層 MPC 協議的隱私性。只需注意到，驗證者最多只能看到兩個參與方的視圖，而由于假設底層的 MPC 協議是 $2$-Private 的，因此驗證者無法從中獲得關于其他參與方私有輸入的任何信息。此外，知道 $w_i$ 和 $w_j$ 也不會泄露任何關于完整見證 $w$ 的信息。

5.1 消除交互（Removing interaction）

該協議具有一個非常優美的特性：

• 它是一個公共隨機幣協議（public-coin protocol）。

這意味著驗證者不參與任何復雜操作，只需采樣隨機挑戰并發送給證明者即可。正因為如此，可以使用標準的 Fiat-Shamir 轉換 將該協議轉化為非交互式零知識證明（NIZK）。

5.2 協議改進（Improvements）

雖然上述協議在實踐中效率較低，但后續的一些具體實現對該基本構造進行了大量優化。其中一個導致效率低的主要原因是：

• 為了使 soundness error（欺騙成功的概率）足夠低，證明者必須執行許多輪協議。
  • 這是因為在每一輪中，驗證者只打開兩個視圖，因此單輪的 soundness error 較高。

舉一個具體例子，如果 $n=8$，那么證明者在單輪中成功作弊的概率為：
$$1?1/\left(\genfrac{}{}{0ex}{}{8}{2}\right)\approx 96.4\text{\%}$$

一個直接的改進方法是使用一個 $(n?1)$-Private 的 MPC 協議，使得證明者可以安全地打開除一個之外的所有視圖，而不會泄露隱私（不犧牲零知識性）。在這種設定下，驗證者只選擇一個視圖保持私密，而證明者向驗證者公開其余所有參與方的視圖。

這種方法顯著降低了 soundness error，此時：

• 騙局必須發生在那個被保留不公開的參與方身上，而被選中作為隱藏方的概率為 $\frac{1}{n}$；
• 因此，單輪的 soundness error 變為：
  $$\epsilon =\frac{1}{n}$$

和之前一樣，當 $n=8$ 時，成功欺騙的概率為：
$$\frac{1}{8}\approx 12.5\text{\%}$$

6. 應用于后量子簽名的構造

由 MPC-in-the-Head 轉換所構造的零知識證明系統具有一些非常有趣的特性：

• 如果使用的是一個抗量子攻擊的 MPC 協議，那么轉換后的零知識證明方案也將具備后量子安全性，因為整個轉換僅依賴于基礎的密碼學承諾（commitment），這些承諾可以通過抗碰撞哈希函數來實現，如 SHA3。
• 證明的大小與電路規模線性相關，且具有非常小的常數系數，因此對于門數量較少的電路，在實踐中是高效的。
• 證明者和驗證者的時間復雜度均與電路規模線性相關，基本上兩者所需的計算量是相當的。

這使得該方案在構建后量子數字簽名方案方面非常有吸引力。一般而言，要從零知識證明系統構造一個簽名方案，首先選擇一個單向函數 $H$，它滿足：

• 計算 $H(x)$ 是容易的；
• 但給定 $y$，要找到 $x$ 使得 $H(x)=y$ 是困難的。

一個標準例子是取 $H$ 為某個密碼學哈希函數，然后令關系 $\mathcal{R}$ 為其原像關系：

• 密鑰生成：私鑰 $x$ 隨機采樣，公鑰為 $y=H(x)$。
• 簽名生成：對于某個消息 $m$，簽名者使用零知識證明系統來證明自己知道某個私有 $x$，使得 $H(x)=y$，其中 $y$ 是公鑰。
  • 利用 Fiat-Shamir 轉換，可以高效地將消息 $m$ 融入證明中。讓證明者發送的第一條消息就是該消息 $m$，然后協議照常繼續執行。
  • 這樣得到的就是一種“與消息綁定的知識證明（message-dependent proof of knowledge）”：簽名者證明其知道某個使公鑰成立的原像，但該證明僅對某個特定消息 $m$ 有效。
  • 注意，驗證者生成的每個挑戰都是依賴于該初始消息 $m$ 的，因此這個簽名不能在其他消息上復用。
• 簽名驗證：驗證者首先檢查證明中包含的消息是否等于 $m$，然后驗證關聯的零知識證明是否有效。

目前已經有多個具體簽名方案基于這一思想被提出，例如：

• 2016年論文 ZKBoo: Faster Zero-Knowledge for Boolean Circuits，開源代碼實現見：
  • https://github.com/Sobuno/ZKBoo（C語言））
• 2017年論文 Picnic（Post-Quantum Zero-Knowledge and Signatures from Symmetric-Key Primitives），開源代碼實現見：
  • https://github.com/Microsoft/Picnic（C語言）
  • https://github.com/isec-tugraz/fish-begol（C語言+Python）
• 2018年論文 KKW18（Improved Non-Interactive Zero Knowledge with Applications to
  Post-Quantum Signatures）
• 2023年論文 FAEST（Publicly Verifiable Zero-Knowledge and Post-Quantum Signatures
  From VOLE-in-the-Head），開源代碼實現見：
  • https://github.com/faest-sign/faest-rs/tree/crypto-2023（Rust）

值得注意的是，Ligero 零知識證明系統也可以被看作是對 MPC-in-the-Head 轉換的一種優化實現：

• Ligero通過使用對主動攻擊者安全的 MPC 協議，成功實現了次線性（sub-linear）證明大小。
• 開源代碼見：https://github.com/ligeroinc/ligero-prover（C++和WebAssembly）

參考資料

[1] zkSecurity團隊2025年2月20日博客 A Gentle Introduction to the MPC-in-the-Head Transformation