🔒 多方安全計算(MPC) 學習筆記

一、背景與應用場景

1. 經典問題：百萬富翁問題

• 目標：兩個富翁比較財富，不泄露具體數值，只得到比較結果
• 意義：MPC的起源問題

2. 典型應用場景

• 聯合模型訓練：多方數據聯合訓練高精度機器學習模型
• 基因診斷(GWAS)：保護隱私的基因數據分析
• 聯合風控：金融機構間隱私保護的聯合風險分析

二、MPC發展歷程

三、MPC分類體系

1. 按不誠實參與方數量

• 誠實大多數：t < n/2
• 不誠實大多數：t ≥ n/2（通常t = n-1）

2. 按敵手行為

• 半誠實敵手：被動攻擊，按協議執行但記錄信息
• 惡意敵手：主動攻擊，執行任意攻擊行為

3. 按敵手計算能力

• 概率多項式時間：計算安全協議
• 無限計算能力：信息論安全協議（僅誠實大多數）

4. 按輸出可達性

• 中止安全：惡意方可獲得輸出後終止協議
• 公平性：所有實體同時獲得輸出
• 保證輸出傳送：所有實體一定獲得輸出

5. 按計算模型

• 布爾電路：邏輯門(XOR、AND)
• 算術電路：域/環上操作(ADD、MULT)
• RAM程序：讀、寫操作

6. 按腐化策略

• 靜態腐化：協議運行前確定被腐化實體
• 自適應腐化：協議運行過程中動態決定

7. 按通信網絡

• 同步網絡：固定延時內消息一定到達
• 異步網絡：更現實的網絡假設

四、兩大MPC設計方法

🔹 混淆電路方法

• 特點：通信帶寬高，常數輪複雜度
• 適用：兩方計算，輪數敏感場景

🔹 秘密分享方法

• 特點：通信帶寬低、吞吐率高，輪數與電路深度線性相關
• 適用：多方計算，高吞吐需求場景

趨勢：部分協議融合兩種方法

五、混淆電路技術細節

1. 基本流程

Garbler → 混淆電路(GC) → Evaluator
    ↓           ↓           ↓
  編碼(e)      傳輸       解碼(d)

2. 優化技術演進

• Free XOR：XOR門零通信成本
• 半門技術：AND門通信降至1.5k
• 切割技術：進一步優化通信

3. 相關基礎協議

• 不經意傳輸(OT)：GC的基礎組件

• OT擴展：

  • IKNP類：計算量小，通信量大
  • PCG類：通信量小，計算量大
  • PCF類：亞線性通信，可分批計算

4. 多方混淆電路協議

• BMR：對稱形，所有參與方計算GC
• WRK：非對稱形，只有1方計算GC

六、秘密分享技術體系

1. 線性秘密分享(LSSS)

• 性質：加法同態性、隱私性、正確性
• 操作：Share(x)、Reconstruct([x])、Open([x])

2. 常用秘密分享方案

• 加法秘密分享：x = x₁ + ⋯ + xₙ（適用於不誠實大多數）
• Shamir秘密分享：基於多項式插值（適用於誠實大多數）
• 複製秘密分享：支持更靈活的訪問結構
• 打包秘密分享：提高通信效率

3. 基於秘密分享的MPC框架

輸入分享 → 電路計算 → 輸出重構
    ↓         ↓           ↓
  Share(x)   ADD/MULT   Reconstruct(y)

4. 關鍵協議技術

• GMW協議：基於OT的布爾電路計算
• Beaver三元組：預處理+在線計算，降低通信

• 分佈式乘法計算：

  • GRR方法：Shamir分享的多項式相乘
  • 預處理優化：減少在線通信開銷

七、安全模型與惡意敵手防護

1. 通用編譯器

• GMW編譯器：零知識證明驗證消息合法性
• IPS編譯器：MPC-in-the-Head技術

2. SPDZ協議

• 核心思想：信息論消息認證碼
• 認證分享：[x] = (份額, MAC)，其中MAC = x·Δ
• 批量驗證：大幅降低通信開銷

八、總結與展望

性能對比

當前挑戰

1. 混淆電路通信下界突破（當前≈1.5k/AND門）
2. 惡意模型性能優化（比半誠實慢數倍）
3. 協議多樣性帶來的標準化困難

未來趨勢

• 通信優化：MPC主要效率瓶頸
• 性能提升：與明文計算差距不斷縮小
• 惡意模型效率：逐漸接近半誠實模型性能

九、重要思考題

1. 如何使用1-out-of-2 OT實現比特乘法？
2. 如何擴展GMW協議到算術電路？
3. 如何擴展兩方協議到多方(n > 2)？
4. 如何用PRG減少通信開銷？
5. 如何證明Yao協議在半誠實模型下的安全性？