Apple 怎麼安全的蒐集我們的隱私？
本文先介紹一下大數據與 AI 造成的隱私問題，再介紹一種隱私保護的演算法 Differential Privacy (DP)，接著實際的探討在 Apple 的數據蒐集方案中是怎麼利用 DP 來保護用戶的隱私，並探討 DP 算法的適用時機。
大數據 + AI = 隱私問題
隱私包含很多的層面，比方說我們的信用卡資料、聊天紀錄、購買紀錄、電話號碼等等。我在資安公司工作的時候學到了很多密碼學相關的知識，試圖用各種加密手段來確保這些個人信息不會外流。然而，在 AI+大數據時代，加密已經不足以保護個人信息，因為這些信息通常需要被進一步利用。
舉個例子：輸入法鍵盤。輸入法通常都會有候選清單，而這些候選清單是由機器學習的方式更新的。機器學習需要數據，數據就是你的鍵盤輸入，這意味著你對鍵盤輸入的結果必須不時的上傳，作為機器學習的糧食。這些數據不只有機器能看到，後台的維護人員也可以。
匿名蒐集不足以保護隱私
時至今日，蒐集數據已經司空見慣，各大公司都在收集我們的數據，並且保證會透過匿名的方式蒐集。但是是否透過匿名收集就可以保持用戶的隱私？有時候答案是否定的。
Netflix 在 2006 年舉辦了一個公開競賽 (Netflix Prize Data)，並提供了一份公開數據集，目的是提升推薦系統的精準度。雖然這份數據集的用戶 ID 都已經被 Random ID 給取代，但是研究員 Arvind Narayanan 和 Vitaly Shmatikov 透過將這份匿名數據與 IMDB 連結，成功還原出了 99% 的個人資訊。
匿名數據能夠破解的方式很簡單，就是利用外部的訊息。這種破解方式可以類比於「三國殺」或「狼人殺」：雖然你無法看見對方的身分牌，但是你可以透過其他玩家的身分來反推他的身分牌；不考慮犯規的話，你也可以利用場外信息來反推身分牌。在 Netflix Prize Data 的例子裡，場外信息就是 IMDB。
Differential Privacy
Differential Privacy (DP) 是一種隱私保護 (Privacy-Preserving) 的演算法，可以在收集群體資料的同時能夠保護單體用戶的 Data。從應用領域來說，DP 不能保護用戶的數據不被看見，但是 DP 能做到的是保護「數據與單個用戶的關聯」。
DP的概念很簡單，就是加入隨機性。如果匿名數據裡面包含的數據是經過隨機處理的，那就很難通過其他線索來反推回個人數據。以 Netflix Prize Data 的例子中，DP 的隨機性可以加入在用戶評分或是評分日期中，甚至可以稍微擾亂電影 ID。只要用戶評價的數據有稍微的隨機性，就很難透過 IMDB 之類的第三方數據反推回用戶 ID。
加入隨機性的程度會影響隱私保護的程度。通常隨機性參數會用符號 ε (epsilon) 來表示，因此也被稱為 ε- Differential Privacy。在 DP 中，「隱私保護」與「數據可用性」往往是一個 Trade-off，因此選擇適當的 ε 也是至關重要。
Differential Privacy 的適用時機
Differential Privacy 是一種應用層面很廣的隱私保護方法。在實務中，DP 幾乎是另用領域最廣的隱私保護演算法，因為他的方法足夠簡單，在各種任務中都可以順利應用，例如：推薦演算法、趨勢預測、用戶分群等等。
但是 DP 對於數據無可避免的傷害也限制了他的可用性，因此對於一些對於數據要求較高的機器學習演算法，例如機器視覺，就不太能夠直接使用。
Apple 應用 Differential Privacy 的數據蒐集架構
Apple 的機器學習研究團隊在文章與論文中公開了他們的 DP 數據蒐集架構。包含下列三種：
- Private Count Mean Sketch (CMS)
- Private Hadamard Count Mean Sketch (HCMS)
- Sequence Fragment Puzzle (SFP)
礙於篇幅，以下只細講 CMS 的實作方式，對於 HCMS 與 SFP 僅會做簡單的介紹。更多細節可以參考 Apple 的論文《Learning with Privacy at Scale》，或是參考以下公開 blog：
CMS: Private Count Mean Sketch
CMS 是一種簡單的 DP counting 演算法，可以利用於許多需要統計的場景，例如：統計用戶中使用的各種表情符號次數。除了表情符號外，CMS需要還 k 個 hash 函數，其中每個 hash 包含 m 種可能的輸出。
CMS 中引用了兩個隨機性保護。第一，CMS 會隨機選擇 k 個 hash 函數的其中一種來做 hash，得到一個 one-hot vector。這相當於對輸入做了一層加密，因為光看這個 one-hot vector 並無法反推輸入的原始內容。
第二，CMS 對於產生的 one-hot vector 的每個元素會做一次 0–1 之間的隨機性的翻轉，而這個翻轉機率由參數 ε 控制。透過這個第二層機率反轉，相當於抹去了單個用戶的統計數據，達到 DP 的保護效果。
透過以上兩個隨機處理，CMS 在每個 client 端會產生一個 shape=[k, m] 的矩陣，稱為 sketch matrix。透過加總這些 sketch matrix， Server 端就可以統計表情符號的出現次數。
以下是我寫的一個簡單的 CMS Sample code，大家可以透過程式碼更加理解其中的原理：
HCMS: Private Hadamard Count Mean Sketch
HCMS 與 CMS 大部分相同，都是 DP Counting 演算法的一種。但是 CMS 有一個的缺點：CMS 的上傳數據量太大，因為每個 client 都必須上傳一個 sketch matrix。
為了解決 CMS 的問題，HCMS 在 sketch matrix 後面再加上一個 Hadamard matrix 做線性轉換，並且只針對轉換後的 row vector 隨機選取一個 column 做 DP 的隨機翻轉並上傳。
因此，HCMS 只上傳 3 個整數：所選的 hash 函數 index、所選的隨機 column index、隨機翻轉後數值 (-1 or 1)。
在 server 端統計的時候，可以利用 client 端上傳的翻轉數值與位置做 debias，並起且透過 Hadamard 的可逆性做逆矩陣計算，得到加總後的 sketch matrix。
SFP: Sequence Fragment Puzzle
前述的 CMS 與 HCMS 都只能解決有限級的統計問題，但是有些統計任務的輸入是難以窮舉的，例如輸入法的英文單詞。
Sequence Fragment Puzzle (SFP) 解決的就是無窮集合的 DP Counting 問題。具起來說就是把「完整的單字」與「單字中的子字串」分別計算一次 CMS。雖然因為 hash 有可能會相撞的特行，Hash(單字) 出來的結果可能不為唯一，但是加上單字中更短的子字串做第 2 次 CMS，這兩次 CMS 的結果組合應該是唯一的。
Apple 利用 SFP 對 iOS 輸入法也做了很多的數據蒐集，例如發現各種用戶習慣的英文縮寫 (kno, lov…)、還有各種流行的名字。而這些蒐集最終都會反饋到鍵盤輸入法的候選欄中。
補充資料
這裡有一篇用動畫的方式來說明 DP 的影片，比較簡單易懂：
除了 DP 之外，還有 Federated Learning, Homomorphic 等方法；關於隱私保護的學習方法，下面這篇文章做了 5 種不同等級的解釋（從小孩到專家），有興趣的同學可以看一下。
