聯邦學習：保護用戶資料隱私

對資料保護通常是對資料做加密或移除敏感資訊，但實際上即使移除了敏感資訊，有足夠多的真實的資訊，還是可以通過演算法是找到對應的人的，如：

• 卡內基梅隆大學的Latanya Sweeney的將匿名化的GIC資料庫（包含每位患者的出生日期、性別和郵政編碼）與選民登記記錄相連后，可以找出馬薩諸塞州州長的病歷，
• 2006年的Netflix的機器學習比賽，雖然可識別單個客戶的所有個人資訊已被洗掉，并且所有客戶ID已用隨機分配的ID替代，但德克薩斯州大學奧斯汀分校的研究員Arvind Narayanan和Vitaly Shmatikov利用一種叫做record linkage的技術將Netflix匿名化的訓練資料庫與IMDb資料庫（根據用戶評價日期）相連，能夠部分反匿名化Netflix的訓練資料庫，

也就是，如果你公布一個資料集，僅僅只是移除一些ID名稱，這遠遠是不夠的，因為結合外部的一些資訊是可以將資料集還原的，所以我們需要一些新的技術去保護用戶的資料隱私，現在最熱門的就是聯邦學習，全球各地越來越多的國家出臺保護用戶隱私的相關法律——國外的個人資料隱私保護法，倒逼企業不斷提升用戶隱私保護技術，

Federated Learning，也叫Collaborative Learning，最初由谷歌在2016年提出，在國內叫聯邦學習、協同學習，

聯邦學習在保護隱私方面最重要的三大技術分別是：差分隱私(Differential Privacy)、同態加密(Homomorphic Encryption)和隱私保護集合交集(Private Set Intersection)，

差分隱私(Differential Privacy)

差分隱私是用戶資料加密后上傳到平臺服務器后，平臺可以用這些加密后的資料計算出用戶群體的相關特征，但無法決議某個個體的資訊，

通常采用的做法是給資料加入噪聲，這個噪聲不是隨便加的，加得太大，資料失真，加得太少，起不到保護作用，噪聲是有要求的，假設資料集D，現在加入噪聲M等到資料集D’，將資料集D中隨意拿到一個記錄，再加入噪聲M得到D”，對D’和D”的資料計算結果要一樣的才可以，

詳細原理示例：

假設現在有一家10個員工的公司，員工想知道自己的工資水平在公司的水平，但又不想直接將自己的工資資料分享出去，所以它們找了一個第三方的人，然后讓第三方的人去統計平均工資：

但如果其中有一個人知道其他八個人的工資，只有一個人的是不知道：

如果他知道平均工資，那么可以推斷出那個人是45K，為了防止這種情況出現，第三方的人在資料中加入噪聲，使得即使減少掉一個人計算出來的平均值也是在合理范圍內

然后計算平均薪酬，這個薪酬是添加了噪聲之后計算，就倒推不出那個人的工資，從而保護用戶的隱私：

常用的噪音機制有指數、拉普拉斯和高斯，

差分隱私不是一個新的概念，十幾年前就已經提出來了：

• 2006年，微軟的 C. Dwork 提出差分隱私的概念，因為在該年Netflix的機器學習比賽使用的資料集被反匿名化，由此引發重視，
• 2014年，谷歌將差分隱私引入了Chrome，Google 使用名為RAPPOR的自定義系統來收集有關Chrome用戶瀏覽模式的概率資訊，在該系統中，瀏覽器使用哈希函式將字串（如URL）轉換為短字串，然后添加概率噪聲并將結果報告給Google，
• 2016年，蘋果在WWDC 大會上提到了一項 Differential Privacy 差分隱私技術，按蘋果的說法，蘋果是唯一一家將差分隱私作為標準大規模布署的公司，此后這一領域廣受關注，
• 2017年，Uber于發布了差分隱私工具，限制從司機處獲得的資料，
• 2019年，谷歌宣布開源創新隱私保護技術的開源版，
• 2019年，微眾銀行AI團隊自研并推出了基于聯邦學習開源框架Federated AI Technology Enabler (簡稱FATE)，
• 2020年，小米在MIUI 12系統中還運用到了“差分隱私”保護演算法，這項技識訓在資料上傳之前添加一些干擾噪聲，確保上傳資料已經不是用戶的真實資料，僅可以用于整體資料的趨勢研究，

差分隱私有兩種作業模式：Global Privacy和Local Privacy，

Global Privacy

資料中心統一加噪聲后再對外提供服務，

Local Privacy

在用戶設備本地完成模型的訓練，上傳權重引數，而非資料，不再需要用戶把資料發送到服務器，然后在服務器上進行模型訓練，而是用戶本地訓練，加密上權重引數，服務器端會綜合成千上萬的用戶模型后再反饋給用戶模型改進方案，

在全球范圍內，Local通常更準確，更為保守，更安全的模式，

這種方式也是有缺點的：首先對于小型資料不適用；其次要加入噪聲，是對資料準確度要求高的也不適用，如做例外監測的時候，你給它加個干擾項？

同態加密(Homomorphic Encryption)

同態加密屬于密碼學領域，同態加密是一種加密形式，它允許人們對密文進行特定形式的代數運算得到仍然是加密的結果，將其解密所得到的結果與對明文進行同樣的運算結果一樣，從資料的角度如下圖：

同態加密可以分為以下4個步驟：

• 密鑰生成演算法：Keygen就是秘鑰生成演算法，它生成了秘鑰EncKey和解密演算法Deckey
• 加密演算法：用秘鑰演算法生成的的秘鑰Enckey對資料Plaintext做加密Encryption，生成加密的Cliphertext
• 計算演算法：對加密資料Cliphertext做處理結算
• 解密演算法：就是DecKey，可以將加密資料Cliphertext還原成Plaintext

同態加密很早就提出了，但直到2009年Gentry開發出首個全同態加密方案后才有顯著發展：

• 1978年，Ron Rivest, Leonard Adleman, 以及Michael L. Dertouzos就以銀行為應用背景提出了的隱私同態 (privacy homomorphic) 這個概念，
• 2009年，斯坦福大學的博士生Gentry基于理想格提出一個全同態加密方案，實作了同態加密，此后便快速發展，

全同態加密

全同態加密（Fully Homomorphic Encryption, FHE），自2009年提出經過10年的發展，已經有了很大的突破，可以分為三個階段：

第一代方案：理想格（ideal lattice）

第一代方案其實是包含基于理想格和基于最大近似公因子問題的變種兩種方案：

• 基于理想格（ideal lattice）的方案：Gentry 和 Halevi 在 2011 年提出的基于理想格的方案可以實作 72 bit 的安全強度，對應的公鑰大小約為 2.3 GB，同時重繪密文的處理時間需要幾十分鐘，
• 基于整數上近似 GCD 問題的方案：Dijk 等人在 2010 年提出的方案（及后續方案）采用了更簡化的概念模型，可以降低公鑰大小至幾十 MB 量級，

這一代方案缺點是密鑰尺寸大、效率低下，

第二代方案：容錯學習

第二代全同態加密方案通常基于（R）LWE假設，LWE全稱是Learning with Eror，是有錯誤學習，

• BV方案（Brakerski-Vaikuntanathan）：2011 年，Brakerski 和 Vaikuntanathan基于 LWE 與 RLWE 分別提出了全同態加密方案，其核心技術是再線性化和模數轉換，他們還提出了回圈安全的類同態加密方案，但由于不能自舉，所以達不到全同態，
• BGV方案（Brakerski-Gentry-Vaikuntanathan ）：依次使用模數轉換能夠很好的控制噪音的增長，層次型全同態加密可以同態計算任意多項式深度的電路，從而在實際應用中無需啟用計算量過大的自舉，

這一代方案計算是簡單，缺點是在使用密鑰交換技術時需要增加大量用于密鑰交換的矩陣，從而導致公鑰長度的增長，

第三代方案：特征向量

第三代是一種基于矩陣近似特征向量的全同態加密方案，

• GSW方案：Gentry 等人利用“ 近似特征向量”技術，設計了一個無需計算密鑰的全同態加密方案，
• 此后很多方案都是基于GSW的優化，

不再需要密鑰交換與模轉換技術

半同態加密

半同態加密或部分同態加密，英文簡稱為SWHE（Somewhat Homomorphic Encryption）或PHE（Partially Homomorphic Encryption）：

乘法同態

乘法同態性表現為 E(m1)E(m2)=E(m1m2)：

• RSA演算法：RSA 演算法是建立在因子分解困難性假設基礎上的公鑰加密演算法
• ElGamal演算法：ElGamal演算法建立在計算有限域上離散對數困難性假設基礎上

加法同態

加法同態性表現為 E (m1 )E(m2)=E(m1+m2 mod n)：

• Paillier：建立在合數模的高階剩余計算困難性假設基礎上

隱私保護集合交集(Private Set Intersection)

隱私保護集合交集屬于安全多方計算領域的特定應用問題，安全多方計算(Secure Multi-party Computation, SMC)是解決分布式環境下多個參與者在計算程序中的 隱私保護技術之一. 保護隱私的集合運算(Private Set Intersection, PSI)是安全多方計算的一個重要研究分支,

隱私保護集合交集允許雙方私下加入他們的集合并發現他們共有的識別符號，一般使用一個不經意問題的變種協議，它只標記加密的識別符號而不學習任何識別符號，在資料由不同管理者持有的條件下，通過 PSI 計算達到保護隱私與資訊共享的雙贏局面，

問題模型可以抽象為：

• 雙方擁有的一定數量的用戶，其中部分是共有的
• 在不泄露用戶輸入的任何隱私資訊下，這些共同用戶的資料打通

這種情況很像線上廣告投放，線下轉化的資料打通，已經公司在這么做，