馮登國院士團隊重磅論文《具體高效的安全多方計算協定綜述》解讀

論文作者為中國科學院院士、北京資訊科學技術研究院院長、中國科學院軟體所客座研究員、博士生導師馮登國教授和密碼科學技術國家重點實驗室楊糠副教授。本文為開放隐私計算社群整理，分享僅供學習參考，如有轉載，請标記出處。

1全文摘要

安全多方計算(MPC)允許一組參與者在他們的私有輸入上聯合計算一個函數，隻顯示函數的輸出。在過去的十年裡，MPC已經從一個純粹的理論研究迅速發展成為一個具有實際意義的研究對象，人們對隐私保護機器學習(PPML)等實際應用越來越感興趣。本文是一篇關于“具體高效的安全多方（MPC）計算協定”的綜述性文章，全面調查了在多數不誠實和多數誠實設定中，針對半誠實和惡意的兩種安全性條件下具體高效 MPC 協定的現有工作。本文專注于考慮帶有中止特性的安全性概念，這意味着惡意方可能會阻止誠實方在收到輸出請求後完成接收輸出。本文提出了基礎和關鍵的一整套方法，設計不同風格的 MPC 協定和 MPC 的關鍵子產品。對于 MPC 應用程式，本文比較了基于 MPC 建構的已知 PPML 協定，并描述了最先進的 PPML 協定其私有推理過程和訓練的效率。此外，本文總結了幾個用以突破 MPC 協定效率所存在的目前挑戰和未解決的問題，以及一些值得解決的未來工作。本文的目的是向有興趣了解、改進和應用具體高效的 MPC 協定的研究人員提供 MPC 的最新發展和關鍵方法。

2安全多方計算簡介

安全多方計算(MPC)允許一組參與者在他們的私有輸入上聯合計算一個函數，而不洩露函數的輸出。具體來說，MPC允許N方共同計算以下函數：

其中每一方持有一個輸入，得到一個輸出，除了外什麼也學不到，函數通常被模組化為一個布爾電路或算術電路。MPC是密碼學的基礎，也是大資料時代協作計算中保護資料隐私的核心技術。

安全多方計算保證隐私（意味着協定隻顯示輸出）和正确性（意味着計算出正确的函數），以及其他（例如，輸入的獨立性，意味着一方不能根據其他方的輸入選擇其輸入）。在存在對抗行為的情況下，必須保證安全屬性。目前主要考慮兩個經典的對手：

• 半誠實：半誠實的對手（又稱被動對手）遵循協定規範，但可能試圖從協定記錄中了解更多；
• 惡意：惡意對手（即活動對手）可以執行任意攻擊政策，試圖破壞協定。

設計 MPC 協定的主要方法有兩種：

• 秘密共享方法，它使各方為電路的每個非線性門進行互動，并且具有低通信帶寬，但循環次數與電路深度呈線性關系；
• 亂碼電路方法，讓各方建構一個加密版本的電路，隻允許計算一次，并且輪數恒定，但通信帶寬大。

一般來說，秘密共享方法更适用于區域網路（LAN）等低延遲網絡，而亂碼電路方法在廣域網（WAN）等高延遲網絡中表現更好。

3基于秘密共享的MPC協定

基于秘密共享方法，具體高效的 MPC 協定使各方能夠在每個非線性門中發送短消息，但具有與正在計算的電路深度成線性關系的輪數。目前，具體高效的 MPC 協定主要采用三種線性秘密共享方案（LSSSs）：加法秘密共享、Shamir 秘密共享和複制秘密共享（又名 CNF 秘密共享），其中加法秘密共享主要用于多數不誠實設定中的 MPC 協定，而 Shamir 和複制秘密共享用于多數誠實 MPC 協定。本文首先以統一的視角回顧這些 LSSSs 的結構。為了實作應對惡意方的安全性，加法秘密共享需要配備資訊論消息認證碼（IT-MACs），是以本文定義了多數不誠實在 MPC 中使用的兩種類型的 ITMAC。請注意，對于多數誠實設定中的 Shamir/複制秘密共享，IT-MAC 是不必要的。然後，基于 LSSSs，本文描述了如何建構具有統一結構的半誠實 MPC 協定。最後展示了如何使用最先進的檢查技術将半誠實的 MPC 協定轉換為惡意保護 MPC 協定。

線性秘密共享方案

MPC 中使用的三種 LSSSs 都是 -門檻值秘密共享方案，它使 方可以在各方之間共享秘密 ，使得 方的任何子集都無法獲得關于秘密 的任何資訊，而任何 方的子集可以重建秘密 。加性秘密共享隻能在 時進行，而 Shamir/複制 秘密共享允許任何 （對于多數誠實 MPC，通常采用 。三種 LSSSs 定義在字段 上。雖然加法/複制秘密共享允許任意大小的字段（包括 ），但 Shamir 秘密共享需要 。接下來将描述這些 LSSSs 的結構以及設計 MPC 協定的有用程式。

一般的LSSSs執行流程如下：

• ：對于 ，中介生成 份秘密 。通過 表示秘密 的共享。
• ：這個過程隻允許 獲得秘密 。當任何 份 通過私有通道發送給 時，秘密 可以由 重構。
• ：這個過程允許所有參與方都知道 。這很容易通過執行 , 來實作，其中不需要私有通道。

資訊論消息認證碼

在多數不誠實設定中，MPC 協定可以使用加法秘密共享來私下執行電路評估。這對于半誠實的安全性來說已經足夠了。然而，在惡意設定中，需要引入 IT-MAC 來保證秘密值的正确性。目前，在 MPC 協定中使用了兩種風格的 IT-MAC：BDOZ 風格和 SPDZ 風格。雖然最初的 IT-MAC 是在單個大字段上定義的，但很容易對其進行擴充，以便在任意大小的字段 上定義值，并在一個大的擴充字段 上完成身份驗證。

SPDZ 風格的 IT-MAC 比 BDOZ 風格的 IT-MAC 更緊湊。然而，在應用于MPC時，這兩種風格的IT-MAC是無法比拟的。雖然 BDOZ 風格的 IT-MAC 更适合用于基于分布式亂碼的恒定輪 MPC 協定，但 SPDZ 風格的 IT-MAC 主要用于将半誠實的 GMW 協定轉換為具有惡意安全性的高效 MPC 協定。

半誠實協定

在半誠實的設定中，本文使用一個簡單的架構來統一最先進的具體高效的 MPC 協定，包括 1）基于加法秘密共享的優化的 GMW 協定；2）基于Shamir秘密共享的具有優化的BGW協定；3）基于複制秘密共享的安全三方計算（3PC）協定。這裡，對于基于複制秘密共享的 MPC，為了簡單起見，本文重點關注三方案例。

雖然最初的 GMW 協定隻考慮布爾電路，但很容易将其擴充到任何有限域 上的算術電路。類似地，雖然在多數誠實設定中具有半誠實安全性的最先進的 3PC 協定專注于布爾電路的情況，但很容易将該協定擴充到任何有限域 .對于更多的參與方（例如，參與方的數量是 或 ），可以有效地建構基于複制秘密共享的 MPC 協定。在存在半誠實的對手的情況下，類 GMW 協定和基于複制秘密共享的 MPC 協定可以直接擴充為在諸如 （ 或 ）的環上工作。此外，類似 BGW 的協定基于 Shamir 秘密共享的協定也可以在通用環上工作。雖然整數計算模型 對于現代計算機來說更自然，并且可能有助于簡化機器學習 (ML) 等實作和應用程式。

本文展示了半誠實設定中基于秘密共享的 MPC 協定的架構，如下圖所示。

具體來說，輸入在各方之間秘密共享，然後逐層評估電路其中一層中的所有門都可以并行計算，是以通信輪次與電路深度成線性關系。最後，重構每一方的輸出。雖然加法門在沒有任何通信的情況下是免費的，但 MPC 協定的主要成本是通過執行半誠實乘法協定 來計算乘法門。對于不同種類的 LSSSs， 的構造方式不同。本文在下圖中勾勒出 的三種經典結構，對應于三種秘密共享，其中協定分為兩個階段：電路和輸入未知的預處理階段和電路和輸入已知的線上階段各方。

惡意安全協定

上述的基于秘密共享的 MPC 協定在半誠實的對手存在時保證安全。為了實作“惡意安全”，需要增加一些檢查程式。在多數不誠實 MPC 和多數誠實 MPC 之間，確定抵禦惡意對手安全的底層技術是不同的。例如，不誠實多數設定中的 MPC 需要 IT-MAC 來驗證各方共享的值，但這對于多數誠實的 MPC 來說是不必要的。是以，本文在兩種不同的設定中展示了惡意安全 MPC 的開發。

多數不誠實： Goldreich、Micali 和 Wigderson (GMW) 提出了一種通用編譯器，用于将半誠實的 MPC 協定轉換為惡意安全的 MPC 協定，以完成相同的計算任務。然而，這個編譯器是非黑盒的，它使用通用的零知識證明來證明每一步計算的正确性，是以效率不高。後來，Ishai、Prabhakaran 和 Sahai (IPS) 提出了一種黑盒編譯器，其中具有半誠實安全性的内部 MPC 協定在 OT 混合模型中計算電路，而具有惡意安全性的外部 MPC 協定在多數誠實設定用于在存在惡意對手的情況下保證整個 MPC 協定的安全性。IPS 編譯器針對多方設定進行了改進，并針對兩方設定進行了進一步優化。然而，基于 IPS 編譯器的惡意安全 MPC 協定的具體效率仍然不夠高。最近，基于 IPS 架構，Hazay 等人提出了一種使用兩級共享的新編譯器，其中外層是 Shamir 秘密共享或代數幾何（AG）秘密共享，内層是加性秘密共享。他們的編譯器允許在半誠實的 GMW 協定上具有恒定通信開銷的任意大小的字段，但具體效率仍然很低。

多數誠實： 在惡意設定中，隻需要檢查乘法門的正确性，因為加法門是在本地計算的并且總是正确的。2017 年，Lindell 和 Nof 觀察到，半誠實的 協定在存在惡意對手的情況下保證了秘密值的隐私，并允許對手在輸出中引入附加錯誤，即兩個共享 , ， 協定将輸出一個共享 ，其中 其中 是一個附加誤差。這一觀察也适用于 GRR 協定和基于複制秘密共享的乘法協定。他們采用 Beaver 三元組和随機線性組合方法來檢查乘法門的正确性，與半誠實協定相比，這引入了相對較大的開銷。随後，Chida 等人提出了一種不同的方法來驗證乘法門的正确性，其中半誠實乘法協定被執行兩次，然後各方使用另一個相關的乘法三元組檢查乘法門的正确性。與半誠實的 協定相比，他們的 MPC 協定仍然引入了兩倍的通信開銷。同時，Nordholt 和 Veeningen 也實作了兩倍的通信開銷。在三方設定中，Furukawa 等人使用“Cut-and-Choose”方法将布爾電路的半誠實協定轉換為惡意安全協定，這将引入 的開銷，其中 是乘法門的數量，此開銷小于自然重複方法，但不是最佳的。

4基于亂碼電路的恒輪MPC

目前，已知的具體有效的恒輪 MPC 協定是基于亂碼電路建構的，這些電路是基礎電路的加密版本，隻能計算一次。首先考慮半誠實協定，然後展示如何編譯它們以惡意保護 MPC 協定。

半誠實協定

安全的兩方計算：Yao 提出了第一個恒輪安全兩方計算（2PC）協定，實作了半誠實的安全性。Yao 的 2PC 協定采用亂碼電路（GC）和 OT 作為建構塊。具體來說，使用亂碼方案，亂碼器 能夠生成亂碼電路 、編碼資訊 和解碼資訊 。

然後，評估器 可以用 評估 ，然後根據 獲得輸出位。亂碼方案使 能夠獲得函數輸出，但不會透露有關 輸入的任何其他資訊。大緻上，Yao 提出的具有半誠實安全性的 2PC 協定如下圖所示。

2PC 協定可以使用預計算 OT 思想進一步優化，其中在預處理階段運作随機不經意傳輸（ROT）協定，并在線上階段使用選擇的選擇位将 ROT 轉換為标準 OT。此外，GC 可以以流水線方式發送，這允許 GC 實作擴充到無限數量的門使用幾乎恒定的記憶體。後續研究主要集中在優化2PC協定兩個方面：改進GCs的建構和設計更高效的OT擴充協定。

安全的多方計算：在多方設定中，恒輪MPC必須處理多方合謀欺騙誠實方的情況。是以，不能隻讓一方建構亂碼電路，而是讓各方以分布式的方式共同建構亂碼電路，使用分布式亂碼方案來生成多方亂碼電路。第一個分布式亂碼方案由 Beaver、Micali 和 Rogaway 在 1990 年引入。基于分布式亂碼，他們提出了一個在不誠實多數設定下的恒輪 MPC 協定，但該協定的具體效率非常低。令人驚訝的是，在不誠實的多數設定中，直到 2016 年，BMR 亂碼才首次使用 free-XOR 技術進行優化。基于優化的BMR亂碼電路，他們提出了一種具有半誠實安全性的高效恒輪MPC協定，特别是他們改進的 BMR 亂碼電路。

惡意安全協定

安全的兩方計算：對于恒輪 2PC 協定，在 2017 年之前，一種流行的設計惡意安全協定的方法是使用“Cut-and-Choose”（C&C）技術。使用這種技術有兩種不同的風格。第一個是由 Lindell 和 Pinkas 引入并優化的電路級 C&C 方法，其中準備了許多亂碼電路，打開并驗證其中的随機子集，其餘未經檢查電路進行評估。在單執行設定中，在輸入上一次計算電路，需要為統計安全性 準備 亂碼電路，并且此設定中最有效的 2PC 協定是由 Wang 等人提出的。在不同輸入上多次評估相同電路的攤銷設定中，隻需要準備 亂碼電路來對 執行進行攤銷，并且此設定中最著名的 2PC 協定是由 Rindal 和 Rosulek 提出的。第二種是由 Nielsen 和 Orlandi 引入并稱為 LEGO 的門級 C&C 方法，其中準備了許多單獨的亂碼 AND 門，其中的一個随機子集被打開和驗證，其餘未經檢查的亂碼使用 XOR 同态承諾将門焊接到亂碼容錯電路。随後，LEGO協定進行了優化，與電路級 C&C 方法相比，門級 C&C 方法具有較低的漸近複雜度 ，并支援電路和輸入均未知的函數無關預處理（不支援此類預處理）通過電路級 C&C 方法，但在攤銷設定中效率較低，并且在單執行設定中的某些功能的效率也較低。2017 年，Wang、Ranellucci 和 Katz 的裡程碑式工作提出了建構高效 2PC 協定的認證亂碼方法，其中建構和傳輸單個“認證”亂碼電路。

安全的多方計算：在多數不誠實設定中，對于容忍非一個惡意破壞的恒定輪次 MPC 協定，一些研究采用剪切和選擇方法或 BMR 和 SPDZ 的組合方法來建構 MPC 協定。但是，它們的具體效率非常低。在這種情況下，最著名的 MPC 協定遵循基于 TinyOT 類協定的分布式亂碼架構。這些 MPC 協定與 2PC 協定具有相同的結構，但需要執行一緻性檢查程式來檢查多次執行之間共享或全局密鑰的一緻性。最近，Poddar 等人應用具有惡意安全性的恒定輪次 MPC 協定建構了一個稱為參議院的系統，該系統允許 方協作運作分析 SQL 查詢，同時保持個人資料的私密性。Yang等人提出了具有惡意安全性的最先進的常量輪MPC協定，并可用于進一步提高上述應用程式的性能。雖然半門優化完全應用于兩方設定中的分布式亂碼建構，但這僅在多方設定中部分完成。将半栅技術（甚至最近的切片和切割技術）完全應用于多方亂碼電路是一個挑戰。

在多數誠實設定中，可以使用較少的通信和計算基于複制的秘密共享來建構恒定輪次 MPC 協定。在最多一個惡意方的三方設定中，Mohassel 等人通過建構單個 Yao 式的亂碼電路，提出了目前最有效的三輪 3PC 協定，其中惡意安全的 3PC 協定與半誠實的 Yao 的 2PC 協定具有基本相同的成本。同時，Ishai 等人建構了一個兩輪3PC協定，同時需要發送三個亂碼電路。在最多有一次惡意破壞的四方設定中，Byali 等人提出了最先進的協定，并且有五輪通信，需要發送一個單Yao式的亂碼電路。該協定可以實作更強的安全屬性，即GOD。在最多有兩個惡意破壞的五方設定中，Chandran 等人提出了最著名的 MPC 協定，進行了 8 輪通信。他們采用 BMR 亂碼電路來防止串通，并提出了一種經過驗證的 OT 原語，使整個 MPC 協定隻依賴于對稱密鑰原語，而不需要 OT 協定。在通信成本方面，它們的惡意安全協定比不誠實多數的半誠實 MPC 協定減少 60%，而其半誠實變體需要的通信減少 8 倍。他們的構造也可以擴充到門檻值的 方。後來，Byali等人建構了具有公平性或 GOD 的安全五方計算 (5PC)，其開銷比 5PC 協定的開銷小，滿足中止的安全性。

5不經意轉移和不經意線性函數評估

不經意轉移

不經意傳輸 (OT) 是發送者 和接收者 之間的基本密碼原語，它使 隻能獲得 的兩個輸入消息之一，而 在 的選擇位上一無所知。它不僅可以用來構造Yao氏的2PC協定，還可以用來構造許多其他具有半誠實和惡意安全的MPC協定。此外，OT還可以用來設計很多其他種類的密碼協定。OT 協定可以從不同的加密假設建構，包括決策 Diffie-Hellman (DDH) 、計算 Diffie-Hellman (CDH) 、學習錯誤 (LWE) 、學習奇偶噪聲 (LPN) 和交換超奇異同源 Diffie-Hellman (CSIDH) 。但是，當需要生成大量的 OT 關聯時（特别是對于 MPC 應用），這些基于公鑰操作的 OT 協定是非常昂貴的。為了解決這個問題，Beaver 引入了 OT 擴充的概念，其中使用快速運算将少量基本 OT 有效地擴充到大量 OT（甚至是任何多項式數量的 OT）。Beaver的第一個 OT 擴充協定以非黑盒方式使用僞随機生成器 (PRG)，是以僅在理論上有意義。目前，具體有效的 OT 擴充協定分為兩種風格：一種基于 IKNP 架構，另一種基于 PCG 架構。IKNP 風格的協定采用對稱密鑰原語 PRG 進行擴充并支援選擇位，而 PCG 風格的協定利用 LPN 問題中噪聲的稀疏特性來實作擴充，隻允許随機選擇位。

不經意線性函數評估

OLE： 不經意線性函數評估 (OLE) 是 OT 的算術推廣，特别适用于為大範圍的算術電路設計 MPC 協定。特别是，OLE 直接給出了兩個秘密值相乘的兩方加法共享。是以，通過成對的 OLE 協定執行，可以在多方設定中使用 OLE 生成 Beaver 乘法三元組而無需驗證。OLE 可以使用 OT 擴充和 Gilboa 乘法方法 建構，計算成本低，但通信成本高。存在一種使用基于 RLWE 的加性同态加密 (AHE) 設計 OLE 的标準方法，該方法已用于 Overdrive 和最近的工作，其中接收器 将 發送到發送器 ，并且然後 計算 并将其發送給 ， 解密以獲得大場 的 。這裡，AHE 需要滿足電路隐私财産。此外，OLE 也可以從某種同态加密建構，但需要更大的通信。在不依賴同态加密的情況下，OLE 也可以直接從 Ring-LWE建構。此外，還可以從 OT 和嘈雜的 Reed-Solomon 編碼或 Paillier 加密建構 OLE 協定。在所有 OLE 協定中，基于 AHE 的協定獲得了最佳的通信效率，而來自 RLWE 的協定具有最優的一輪通信。

最近，Boyle等人提出了一種直接基于 LPN 的 OLE 結構，其通信成本比上述 OLE 協定低得多，但需要至少 的計算成本來生成 個 OLE 相關性。後來，他們使用環 LPN 假設的變體解決了計算問題，并建構了用于計算大量 OLE 相關性的 OLE 協定。該 OLE 協定比基于 RLWE 的協定具有非常低的通信成本，并且提供了 的計算複雜度。他們基于 ring-LPN 的 PCG 方法是生成大量 OLE 相關性的好方法（例如，）。對于少數 OLE 相關性，基于 RLWE 的方法可能更好。基于 ring-LPN，得到的 OLE 相關性是随機的（即 是一緻随機的），但足以設計 MPC 協定，其中在預處理階段隻需要生成随機乘法三元組。

VOLE： 向量不經意線性函數評估 (VOLE) 是 COT 對大域的算術推廣，定義如下：

• 發送者持有一個統一的全局密鑰 。
• 對于每個 VOLE 執行，發送者獲得一個向量 ，接收者獲得兩個向量 ，，使得 。

6MPC在機器學習中的應用

機器學習 (ML) 的最新進展推動了許多現實生活中的應用，例如醫療保健、金融風險分析、面部識别、自動駕駛汽車的圖像和視訊分析、推薦系統、文本翻譯、語音助手、圖像分類等。對于關鍵任務應用程式（例如醫療保健），所需的準确度水準很高。準确性主要受兩個因素控制：1）訓練深度學習模型所需的大量計算能力；2）資料集的差異，來自于從多個不同來源收集資料，單個公司通常無法實作。

為此，多家公司（例如，微軟、亞馬遜、谷歌）提供機器學習即服務（MLaaS），它以以下兩種不同的方式工作：

• 推理：公司提供經過訓練的 ML 模型，客戶能夠查詢特征輸入以獲得推理結果。
• 訓練：多家公司合作使用他們的資料集訓練一個高精度模型。

在第一種情況下，公司希望對 ML 模型保密，因為訓練模型可能需要大量資金，并且客戶希望保護其輸入的隐私，其中輸入資訊可能是敏感的，例如個人健康資料或人臉。在第二種情況下，公司不願意共享他們的資料，因為資料是公司的專有資訊，這些公司可能具有競争力，并且由于隐私法而被禁止共享客戶資訊。在這裡，ML 模型是保密的，這意味着模型參數是隐藏的，但模型結構（例如，使用了哪些函數）仍然是已知的。在保持 PPML 具體高效的同時保護模型結構的隐私是一項挑戰。

文章導讀： 論文作者為中國科學院院士、北京資訊科學技術研究院院長、中國科學院軟體所客座研究員、博士生導師馮登國教授和密碼科學技術國家重點實驗室楊糠副教授。本文為開放隐私計算社群整理，分享僅供學...