了解人們?nèi)绾问褂盟麄兊脑O備通常有助于改善用戶體驗。但是，若想得到能洞察用戶行為的數(shù)據(jù)（例如用戶在鍵盤上打了什么字、訪問了什么網(wǎng)站），可能會侵犯他們的隱私。

近日，蘋果公司開發(fā)了一個系統(tǒng)架構(gòu)，利用本地化差分隱私（local differential privacy）并結(jié)合現(xiàn)有的保護隱私的最佳方法，實現(xiàn)規(guī)模化學習（learning at scale）。研究人員設計了高效可擴展的本地化差分隱私算法，經(jīng)過嚴謹?shù)姆治龃_定了應用程序、隱私、服務器計算能力和設備帶寬四個要素的重要性應如何分配。平衡這些因素將有助于成功地部署本地差分隱私。這一部署將覆蓋數(shù)以億計的用戶，例如在Safari中跟蹤最受歡迎的emoji、最常用的健康數(shù)據(jù)類型以及媒體播放偏好。后臺回復“dp”可查看完整版論文。

項目介紹

深入了解用戶的整體行為對于改善用戶體驗至關(guān)重要，但所需的數(shù)據(jù)較為敏感私密，公司必須予以保密。除此之外，利用這些數(shù)據(jù)部署學習系統(tǒng)還必須考慮資源開銷、計算成本和通信成本。在本文中，作者概述了將差分隱私和現(xiàn)有的隱私保護方法相結(jié)合，然后從用戶群體中學習的系統(tǒng)架構(gòu)。

經(jīng)過嚴格的數(shù)學證明，差分隱私是目前最強的隱私保障法之一。它的原理在于用仔細調(diào)整過的噪聲掩蓋用戶的數(shù)據(jù)。當許多人提交數(shù)據(jù)時，增加到其中的噪聲達到平衡，并產(chǎn)生有意義的信息。

在差分隱私框架內(nèi)，有兩種設定：中心（central）和本地（local）。在這套系統(tǒng)中，蘋果不收集中心化差別隱私所需的服務器上的原始數(shù)據(jù)，而是采用本地化差別隱私，這種形式更加可靠。本地差分隱私在數(shù)據(jù)被發(fā)送前就做了隨機處理，所以服務器無法看到或接收到原始數(shù)據(jù)。

該系統(tǒng)非常透明，用戶可以自愿選擇是否加入。若用戶不同意上報使用信息，則不會記錄或傳輸他們的私人數(shù)據(jù)。通過本地化的差分隱私，用戶的設備依據(jù)時間等級進行加密。另外，該系統(tǒng)還限制上傳隱私事件的數(shù)量。將信息傳輸?shù)椒掌髅刻熘挥幸淮危沂窃诩用芡ǖ郎线M行，沒有用戶ID。用戶信息最終會到達一個訪問受限的服務器，其中沒有IP標識符，也沒有與其他記錄相關(guān)聯(lián)的信息。所以，我們無法區(qū)分一個emoji和另一個Safari網(wǎng)頁記錄是否來自同一個用戶，也就是說這些信息是完全保密的。這些記錄經(jīng)過處理后加入統(tǒng)計數(shù)據(jù)中，然后再由蘋果內(nèi)部相關(guān)團隊進行分析。

同時，蘋果的研究人員還在估計各種記錄的頻率，例如emoji和網(wǎng)絡域名。他們有兩個想法：從已知的所有類別的記錄中生成直方圖，或者自己創(chuàng)造一個能表現(xiàn)出數(shù)據(jù)集中出現(xiàn)頻率最多的圖表。

系統(tǒng)架構(gòu)

該系統(tǒng)架構(gòu)由設備端和服務端的數(shù)據(jù)組成。在設備上，原始數(shù)據(jù)在加密階段分別進行處理。受限訪問的服務器在對數(shù)據(jù)處理后進一步將其分為數(shù)據(jù)接入和數(shù)據(jù)聚合階段。下面就為大家詳細介紹每一個階段。

信息加密（Privatization）

用戶可在macOS或iOS的“系統(tǒng)偏好設置”里選擇是否同意共享個人記錄以供分析。對于不愿加入的用戶，系統(tǒng)將不會開啟服務。而對于愿意使用這項功能的用戶，蘋果內(nèi)部為每個用戶行為都設置了隱私參數(shù)?。

蘋果還對每天傳輸?shù)拿宽椨涗浽O置了數(shù)量限制。而對于隱私參數(shù)?的選擇，則是基于每個記錄的基礎(chǔ)數(shù)據(jù)集的隱私特性。這些值與其他研究差分隱私的項目提出的參數(shù)是一致的。而且，由于hash沖突，下面的算法給用戶提供了進一步的否認條件。除了上述的方法，蘋果還會刪除用戶的ID和IP地址來進一步加強隱私，服務器上所產(chǎn)生的的用戶ID和IP地址是分隔開的，所以多個記錄之間沒有關(guān)聯(lián)。

無論何時用戶使用了設備，數(shù)據(jù)會立即通過有特殊參數(shù)?的本地差分隱私進行加密，并使用數(shù)據(jù)保護（data protection）臨時儲存在設備上，而不是立即傳輸?shù)椒掌魃稀?/p>

系統(tǒng)會根據(jù)設備的情況進行延遲，之后會隨機抽取不同的私人記錄，并將采樣記錄發(fā)送給服務器。這些記錄不包括設備ID或該行為發(fā)生的時間。設備和服務器之間的通信使用TLS進行加密。

加密過程

在iOS中打開“設置”>“隱私”>“分析”>“分析數(shù)據(jù)”后可看到“差分隱私”（DifferentialPrivacy）的入口。在macOS上，這些記錄在“關(guān)于本機”的“系統(tǒng)報告”中可見。下圖是算法對最受歡迎的emoji使用情況的樣本記錄，記錄所涉及的算法和參數(shù)在下文會有體現(xiàn)。

加密記錄的樣本報告

數(shù)據(jù)接入和聚合

在數(shù)據(jù)接入之前，加密記錄會刪除掉IP地址，然后數(shù)據(jù)庫收集所有用戶數(shù)據(jù)后進行批量處理。這一過程將刪除元數(shù)據(jù)，例如記錄發(fā)生的時間，并且根據(jù)記錄情況把它們分類。在將結(jié)果輸入到下一階段前，數(shù)據(jù)庫也會隨機對每個用戶行為記錄進行排序。

聚合器收到來自數(shù)據(jù)庫的記錄后，根據(jù)算法為每個使用記錄生成個性化的直方圖。計算統(tǒng)計數(shù)據(jù)時，無需合并來自多個記錄的數(shù)據(jù)。在這些直方圖中，只有高于規(guī)定閾值T的域名才算入其中。

算法

下面就為大家介紹三種本地化差分隱私算法。

1.Private Count Mean Sketch（CMS）

Private Count Mean Sketch（CMS）算法聚合了設備提交的記錄，并在域名類別中輸出數(shù)量的直方圖，同時保留本地化差分隱私。這一過程分為兩個階段：客戶端處理和服務器端聚合。

舉個例子吧，假設一名用戶訪問了 www.example.com 這個網(wǎng)站。客戶端算法從一組散列函數(shù)（hash function）{h1，h2，h3，…，hk}中隨機抽取一個，假設抽到了h2，然后用它將上述網(wǎng)站域名以m的大小編碼，即h2(www.example.com)=31。該編碼被寫成大小為m的one-hot向量，其中第31位被設置為1。為了確保隱私的差分性，one-hot向量的每一位獨立地以概率翻轉(zhuǎn)，其中?是隱私參數(shù)，它構(gòu)成了私有化的向量。這個向量和被選擇的散列函數(shù)一起被輸送至服務器。

服務器端的算法通過聚合加密向量組成了sketch矩陣M。該矩陣有k行、m列，每一行都代表一個散列函數(shù)，每一列代表從客戶端傳輸來的矢量大小。

當記錄到達服務器時，算法將加密過的矢量添加到第j行的矢量，其中j是設備采樣的散列函數(shù)的指數(shù)。然后適當?shù)卣{(diào)整m的值，以便每行都能為每個類別進行無差別的頻率計算。

為了計算 www.example.com 的頻率，該算法通過讀取每個j行的M，然后計算這些結(jié)果的平均值。在原始論文中有詳細的分析過程。

2.Private Hadamard Count Mean Sketch（HCMS）

在完整版論文中，作者討論了如何通過增加設備帶寬讓CMS里的計算更精確。但是，這就增加了用戶的傳輸成本。蘋果希望在降低傳輸成本的同時把對準確性的影響降到最小，于是就有了Private Hadamard Count Mean Sketch算法（HCMS），其優(yōu)點是設備可以以極小的精度損失進行傳輸。

依然用上面的來舉例。與CMS類似，客戶端同樣是從一組散列函數(shù){h1，h2，h3，…，hk}中隨機抽取一個，假設抽到了h3。然后有h3(www.example.com)=42。編碼被寫成v=(0,0,…,0,1,0,…,0,0)的one-hot向量，這里第42位設置為1。因為我們只想傳輸一位信息，所以一個簡單的方法就是從向量中抽樣并發(fā)送一個隨機坐標。但是這可能導致結(jié)果直方圖的錯誤或變化。為了減少誤差，研究人員用Hadamard將v進行轉(zhuǎn)化，即v’=Hv=(+1,-1,…,+1)。同樣，為了確保隱私性，向量中的每一位以的概率翻轉(zhuǎn)。下圖展示了這一過程。

Hadamard Count Mean Sketch中客戶端的算法

同樣，服務端的算法與CMS的大致相同。

Hadamard Count Mean Sketch中服務端的算法

3.Private Sequence Fragment Puzzle（SFP）

上述兩種算法都假設有已知的域名集合，服務器可根據(jù)它來列舉樣本，以確定相應的計數(shù)。

然而在某些情況下，一些域名非常大，由于計算能力有限無法全部列舉。例如，當研究人員在研究常用單詞時，即使限制只能輸入10位區(qū)分大小寫的英文單詞，服務器也要進行至少5210次循環(huán)。

所以，蘋果開發(fā)了一種名為Sequence Fragment Puzzle（SFP）的算法，并將其用于發(fā)現(xiàn)新單詞的任務中。由于一個流行字符串的子字符串使用也很頻繁，所以研究人員利用這一點，用客戶端的CMS算法對打出的字進行加密。

成果

通過這三種新穎的算法，蘋果在提升用戶體驗方面有了很大的收獲。以下是三個典型案例：

發(fā)現(xiàn)流行的emoji

emoji是聊天中必不可少的要素，蘋果公司想要知道用戶最常用的emoji都有哪些，以及地區(qū)的相對分布。于是，他們在鍵盤語言環(huán)境中部署了算法。CMS的中的參數(shù)設置為：m=1024，k=65536，?=4，本地emoji庫中含有2600個emoji。

數(shù)據(jù)顯示，鍵盤設置不同，emoji使用也有差異。下圖是英文和法語兩個語言環(huán)境下的emoji使用情況。根據(jù)這一結(jié)果，蘋果可以對emoji的快捷輸入做本地化調(diào)整。

英法兩種鍵盤下人們使用emoji的區(qū)別

找到Safari中占用大量內(nèi)存的網(wǎng)站

有些網(wǎng)站真的是非常消耗資源，蘋果公司想找到這些網(wǎng)站，以優(yōu)化用戶體驗。他們的目標有兩類：瀏覽時占用大量內(nèi)存的以及大量占用CPU拖慢速度的。在iOS11和manOS High Sierra中，Safari可以自動檢測到這些域名，并通過差分隱私上報這些域名。

利用算法，研究人員發(fā)現(xiàn)，最常見的需要消耗大量資源的網(wǎng)站有視頻網(wǎng)站、購物網(wǎng)站和新聞網(wǎng)站。

擴充詞匯庫

為了優(yōu)化“自動糾錯”功能，蘋果不斷地尋找詞庫中沒有的詞語。這里就用到了上面說的SFP算法。

該算法不僅能用在英語環(huán)境中，還能用于法語和西班牙語。拿英語來說吧，算法學習到的新單詞可以被分為以下幾類：

縮寫：wyd（what you doing），wbu（what about you），idc（I don’t care）；

習慣表達：bruh（bro），hun（honey），bae（baby），tryna（trying to）；

流行語：Mayweather，McGregor，Despacito，Moana，Leia；

外文詞匯：dia，queso，aqui，jai…

蘋果正是利用這些數(shù)據(jù)不斷更新在線詞典，改善鍵盤體驗。

他們還發(fā)現(xiàn)，現(xiàn)在很多人在打字時都會省去結(jié)尾的“e”或者“w”，比如lov（love），th（the）或者kno（know）。所以如果用戶不小心選擇了第一個預測詞語，也就是你目前所打出來的所有字符，那么系統(tǒng)會自動在單詞后面添加一個空格，而不是自動替換成你想要輸入的那個單詞。這一功能正是本地化差分隱私算法帶來的。

這篇文章介紹了蘋果公司為改善用戶體驗，同時保護用戶隱私推出的一種新穎的學習系統(tǒng)架構(gòu)，將本地化差分隱私算法覆蓋到各個使用層面。同時還提出了三種獨特的算法——CMS、HCMS和SFP。這些工具幫助公司看到在不同語言環(huán)境下人們使用emoji的差異，并且搜索當下最流行的詞語，促進他們改善軟件的體驗。

研究人員希望這一項目能夠彌合隱私理論與實踐之間的差距，同時他們相信這一工作將繼續(xù)推進大規(guī)模學習問題的研究，同時進一步增強用戶隱私保護。