多方安全計(jì)算（Secure Multi-Party Computation， MPC）是密碼學(xué)的一個(gè)分支，在無可信第三方的情況下，仍可安全地按照公開的計(jì)算邏輯，進(jìn)行數(shù)據(jù)協(xié)同計(jì)算，并輸出結(jié)果。
即使參與各方輸入的數(shù)據(jù)只有自己知道，仍可以通過加密算法，各自得到自己想要的計(jì)算結(jié)果，但無法推斷出原始加密數(shù)據(jù)，從而保障了隱私安全。
MPC起源于姚期智院士在1982年提出的百萬(wàn)富翁問題。自MPC理論創(chuàng)立以來，已經(jīng)衍生出多個(gè)技術(shù)分支，包括混淆電路、秘密分享、同態(tài)加密，不經(jīng)意傳輸，隱私集合交集和差分隱私等。
混淆電路
混淆電路（secret sharing，SS）又稱姚氏加密電路。它在1986年由姚期智教授提出，所以又稱姚氏電路。
其核心是將安全計(jì)算函數(shù)編譯成布爾電路的形式，對(duì)電路本身進(jìn)行加密。對(duì)于混淆電路存在兩種操作：
一種是生成混淆電路，先生成一個(gè)特定功能的布爾電路，再以此為基礎(chǔ)，將其中的邏輯門（真值）轉(zhuǎn)換為混淆門（假值），即可生成一個(gè)混淆電路；
另一種操作稱為求值操作，先生成混淆電路，再使用混淆電路計(jì)算得到輸出。
混淆電路也可以理解為一種密碼學(xué)協(xié)議，它基于混淆電路形成安全計(jì)算協(xié)議，由最初的兩方安全協(xié)議，推演出多方安全協(xié)議。
秘密分享
秘密分享（secret sharing，SS）由Shamir和Blakley于1979年提出，秘密分享算法是將極為復(fù)雜的電路設(shè)計(jì)，簡(jiǎn)化為簡(jiǎn)約高效的數(shù)學(xué)思路。
其基本形式是將每個(gè)數(shù)字拆散成多個(gè)數(shù)，并將這些數(shù)分發(fā)到多個(gè)參與方，而每個(gè)參與方只能拿到原始數(shù)據(jù)的一部分。
結(jié)果是，要想還原真實(shí)數(shù)據(jù)，只有大家把各自所分得的數(shù)據(jù)放在一起才能實(shí)現(xiàn)，缺一不可。
由于秘密拆分方式不同，秘密分享分為基于多項(xiàng)式插值的秘密分享和加性秘密分享。
加性算術(shù)秘密分享能夠計(jì)算線性運(yùn)算、加性布爾秘密分享能夠計(jì)算比較大小等非線性運(yùn)算。
加性秘密分享只需要進(jìn)行簡(jiǎn)單的運(yùn)算，計(jì)算開銷小，在MPC中得到了廣泛的應(yīng)用。秘密分享的缺點(diǎn)是交互輪數(shù)和電路深度有關(guān)。
不經(jīng)意傳輸
不經(jīng)意傳輸（oblivious transfer，0T）由Rabin于1981年提出，消息發(fā)送方擁有多個(gè)消息，接收方只能獲得其中某個(gè)值，而發(fā)送方也不知道接收方的選擇信息。
其衍生技術(shù)相關(guān)不經(jīng)意傳輸（correlated oblivioustransfer，COT）可以生成具有關(guān)系的隨機(jī)數(shù)。
OT，COT是重要的密碼學(xué)組件，能夠?yàn)镚C傳輸導(dǎo)線標(biāo)簽、為SS生成相關(guān)隨機(jī)數(shù)，只使用OT技術(shù)也能實(shí)現(xiàn)MPC協(xié)議。
在OT的性能優(yōu)化歷程中，OT擴(kuò)展（OT Extension）技術(shù)引入對(duì)稱加密來降低計(jì)算開銷，靜默OT擴(kuò)展（silent OT Extension）技術(shù)在本地?cái)U(kuò)展隨機(jī)數(shù)種子來降低通信開銷。
同態(tài)加密
同態(tài)加密（homomorphic encryption，HE）的概念由Rivest等人于1978年提出，可以在無需解密的情況下直接對(duì)加密數(shù)據(jù)執(zhí)行計(jì)算。
在發(fā)展過程中先后有部分同態(tài)加密方案與淺同態(tài)加密方案提出，直到2009年Gentry構(gòu)造出首個(gè)全同態(tài)加密方案。
同態(tài)加密的優(yōu)點(diǎn)是能以最小的通信成本設(shè)計(jì)輪數(shù)較優(yōu)的MPC協(xié)議，缺點(diǎn)是乘法同態(tài)運(yùn)算會(huì)帶來較大的計(jì)算和存儲(chǔ)開銷，目前加法同態(tài)在實(shí)際中應(yīng)用較多。
差分隱私
差分隱私（Differential Privacy，DP）技術(shù)是Dwork在2006年針對(duì)數(shù)據(jù)庫(kù)的隱私泄露問題提出的一種新型密碼學(xué)手段。
該機(jī)制是在源數(shù)據(jù)或計(jì)算結(jié)果上添加特定分布的噪音，確保各參與方無法通過得到的數(shù)據(jù)分析出數(shù)據(jù)集中是否包含某一特定實(shí)體。
差分隱私包括本地差分隱私和計(jì)算結(jié)果差分隱私。
本地差分隱私指在匯聚和計(jì)算前對(duì)數(shù)據(jù)加入噪聲，用于數(shù)據(jù)收集方不可信的場(chǎng)景；
計(jì)算結(jié)果差分隱私是指最終計(jì)算結(jié)果發(fā)布前對(duì)其加噪聲。
隱私集合交集
隱私集合求交（Private Set Intersection，PSI）是多方安全計(jì)算領(lǐng)域中的經(jīng)典問題，它要求參與方在互相不公開本地集合的前提下，共同計(jì)算得出多個(gè)參與方的集合的交集，且不能向任何參與方泄露交集以外的信息。
PSI 是隱私計(jì)算關(guān)鍵技術(shù)之一，也是縱向聯(lián)邦學(xué)習(xí)的關(guān)鍵支撐技術(shù)。
在縱向聯(lián)邦學(xué)習(xí)場(chǎng)景中，PSI 也被稱為樣本對(duì)齊（Sample Alignment）或者數(shù)據(jù)庫(kù)撞庫(kù)，即各參與方需要首先求出各自的訓(xùn)練樣本ID集合之間的交集。
基于計(jì)算得到的訓(xùn)練樣本ID 交集進(jìn)行后續(xù)的縱向聯(lián)邦模型訓(xùn)練。
零知識(shí)證明
零知識(shí)證明（zero-knowledge proof）是指證明者能夠在不向驗(yàn)證者提供任何有用的信息的情況下，使驗(yàn)證者相信某個(gè)論斷是正確的計(jì)算技術(shù)。
零知識(shí)證明的原理在于構(gòu)建一個(gè)多方協(xié)議，即參與的多方需要完成一項(xiàng)任務(wù)所需采取的一系列步驟，通過完成這些步驟。
證明者向驗(yàn)證者證明并使其相信自己知道或擁有某一消息，但證明過程不能向驗(yàn)證者泄漏任何關(guān)于被證明消息的信息。
小結(jié)
目前MPC技術(shù)最典型的應(yīng)用場(chǎng)景是隱私保護(hù)機(jī)器學(xué)習(xí)（privacy-preserving machine learning，PPML）。
從算法應(yīng)用來說，多方安全計(jì)算根據(jù)其可在各方不泄露輸入數(shù)據(jù)的前提下完成多方協(xié)同分析、處理和發(fā)布結(jié)果這一技術(shù)特點(diǎn)，廣泛應(yīng) 用于聯(lián)合統(tǒng)計(jì)、聯(lián)合查詢、聯(lián)合建模、聯(lián)合預(yù)測(cè)等場(chǎng)景，也可以支持用戶自定義計(jì)算邏輯的通用計(jì)算需求。
本文是對(duì)多方安全計(jì)算的概述，后續(xù)會(huì)分別介紹各個(gè)技術(shù)特點(diǎn)，以及如何利用MPC技術(shù)來實(shí)現(xiàn)PPML方案。
參考文獻(xiàn)
- 郭娟娟，王瓊霄等. 安全多方計(jì)算機(jī)器在機(jī)器學(xué)習(xí)中的應(yīng)用. 計(jì)算機(jī)研究與發(fā)展. 2021.06
- 隱私計(jì)算聯(lián)盟. 隱私計(jì)算白皮書（2021）. 2021.07
