1.2 數(shù)據(jù)隱私技術

自20世紀60年代至今，伴隨數(shù)據(jù)隱私問題的發(fā)展，諸多隱私保護技術被提出。本質上，隱私保護技術是用數(shù)據(jù)的效用或效率來換取隱私。例如，基于擾動的差分隱私技術使用數(shù)據(jù)可用性換取隱私保證，加密技術則使用數(shù)據(jù)計算的計算代價或通信代價來換取隱私保證。因此，如何平衡隱私、效率與效用，是隱私技術研究中亙古不變的主題。

從方法上，我們可以將隱私保護的技術分為模糊技術、擾動技術、加密技術、混合隱私技術、分布式計算框架和區(qū)塊鏈技術。接下來，我們將對其進行一一的介紹，分析其特征，并進行對比。

1.2.1 模糊技術

模糊技術指針對數(shù)據(jù)的屬性進行模糊，即通過壓縮、聚類、劃分、泛化等操作切斷數(shù)據(jù)標識屬性（可表示一條數(shù)據(jù)的屬性或屬性組）與隱私屬性間的一對一關系，以隱藏單條數(shù)據(jù)或單個數(shù)據(jù)點的隱私信息，適用于數(shù)據(jù)發(fā)布的場景。該項技術由于會對信息造成損失，因此如何在保證數(shù)據(jù)隱私保護的前提下，盡量減少信息損失和信息扭曲度是該技術的核心問題。

該技術中最典型的是k-匿名技術[5]，k-匿名技術由Latanya Sweeney和Pierangela Samarati于1998年提出，可保證發(fā)布的個人數(shù)據(jù)與其他至少k-1條數(shù)據(jù)不能區(qū)分。在具體實現(xiàn)時，可基于發(fā)布數(shù)據(jù)的準標識符劃分等價組，使每個等價組至少包含k條數(shù)據(jù)。對準標識符進行k-匿名時，可通過刪除部分信息、用區(qū)間范圍代替具體信息等方法，使至少k條數(shù)據(jù)的準標識符相等。但該技術易遭受同質攻擊（homogeneity attack）[9]，即當根據(jù)準標識符確定的等價類保護相同敏感信息時，攻擊者若能通過其背景知識確定某用戶對應的等價類，即可獲取其敏感信息。

為改進該問題，抵御同質攻擊，Machanavajjhala Ashwin提出了l-多樣性[9]，它的基本思想是在k-匿名的基礎上要求一個等價組中至少保護一種內容不同的敏感屬性，即保證等價組中敏感屬性的多樣性。但l-多樣性相比k-匿名而言更難實現(xiàn)，同時也易遭受偏斜攻擊（skewness attack）。如為保證l-多樣性，使某等價組中人群是否患有癌癥的概率相同，但事實上癌癥患者的比例遠低于此。在沒有考慮敏感屬性總體分布的情況下，保證l-多樣性可能使個人隱私泄露的風險增大。為彌補l-多樣性的局限性，防御偏斜攻擊，t-closeness[10]被提出，它保證在同一個等價組中，敏感屬性的分布與該屬性的全局分布一致，其差別不超過閾值t。同時，針對動態(tài)的數(shù)據(jù)插入、修改、刪除操作，m-不變性（m-invariance）[11]被提出，其主要思想是保證同時出現(xiàn)在先后兩個發(fā)布版本中的記錄所在的等價組具有完全相同的隱私屬性集合。

然而，上述技術均不能避免攻擊者針對敏感屬性的背景知識攻擊。另外，基于模糊的方式，其信息損失相對其他技術較大，近年來，其應用已逐漸減少。

1.2.2 擾動技術

擾動技術對數(shù)據(jù)本身進行擾動，主要指差分隱私技術，同時適用于數(shù)據(jù)發(fā)布和大數(shù)據(jù)收集的場景。該技術通過在數(shù)據(jù)上直接添加隨機噪聲，或者將原本的值以一定概率擾動為隨機值來實現(xiàn)。通過擾動的方式保護數(shù)據(jù)隱私，同樣會造成數(shù)據(jù)可用性的降低，即影響計算結果的準確性，因此如何在保護數(shù)據(jù)隱私的前提下，盡可能提高擾動所影響的數(shù)據(jù)可用性是該技術的核心問題。

差分隱私（Differential Privacy，DP）于2006年由微軟研究院的Cynthia Dwork提出[6]，可以保證任意一條數(shù)據(jù)的改變都不會影響最終的輸出結果的分布，從而隱藏輸出結果中的個人隱私信息。也就是說，對于給定的任意兩個僅相差一條記錄的相鄰數(shù)據(jù)集D和D′，滿足差分隱私的隨機化算法M需保證，擾動后的輸出滿足Pr(M(D)∈S)≤eεPr(M(D′)∈S)+δ，其中S表示任意輸出的子集。生成一個滿足差分隱私的算法，通常有兩種數(shù)據(jù)擾動的方式：一種是直接在計算結果上添加噪聲，常用的包括拉普拉斯機制、指數(shù)機制等（具體介紹見第4章）；另一種是以一定的概率對數(shù)據(jù)進行擾動，即隨機響應機制（具體介紹見第5章）。

依據(jù)不同的安全假設，差分隱私技術可分為中心化差分隱私和本地化差分隱私。中心化差分隱私，即傳統(tǒng)的差分隱私概念，假設存在一個可信的服務器擁有用于發(fā)布的所有用戶數(shù)據(jù)，該服務器在由原始數(shù)據(jù)計算得到的結果上直接添加滿足差分隱私的噪聲，最后發(fā)布該擾動后的結果。但現(xiàn)實中，可信的服務器難以部署，它可以看到所有原始數(shù)據(jù)，一旦被攻擊，用戶的數(shù)據(jù)隱私將受到極大的威脅。由此，本地化差分隱私[7]被提出，該模型不依賴任何可信的第三方，用戶在其本地直接對數(shù)據(jù)進行一定概率的擾動，使其滿足差分隱私。雖然該技術在可信假設上有所提高，但相比中心化差分隱私算法僅在結果上添加一次噪聲，本地化差分隱私在每個用戶端都進行數(shù)據(jù)的擾動，其數(shù)據(jù)可用性約為中心化差分隱私數(shù)據(jù)可用性的1/O()倍，其中n表示參與的用戶數(shù)量。

以差分隱私為主的擾動技術相比以匿名為主的數(shù)據(jù)模糊技術，可抵御任意的背景知識攻擊。也就是說，即使攻擊者擁有除被攻擊對象外其他所有用戶的個人信息作為背景知識，也不能推測出個體的隱私信息。目前該技術在工業(yè)界的應用最為廣泛，尤其是本地化差分隱私技術。該技術更適用于當下數(shù)據(jù)監(jiān)控和數(shù)據(jù)收集場景，如谷歌使用該技術收集用戶瀏覽器的主頁設置等信息，蘋果使用該技術收集用戶常用的emoji表情和新單詞。

1.2.3 加密技術

加密技術不同于模糊和擾動的技術，該技術不會損害數(shù)據(jù)的可用性，但隨之而來的是，基于密碼學的技術需付出額外的計算代價和通信代價。其主要原因是，經(jīng)數(shù)據(jù)加密后的密文通常較大，對密文進行計算會造成產生較大的計算代價和通信代價。因此，如何在保護數(shù)據(jù)隱私的前提下盡可能降低加密技術與密文計算的技術代價和通信代價是該技術的核心問題。

當下常用的密碼學技術主要包括同態(tài)加密技術和秘密共享技術。同態(tài)加密（Homomorphic Encryption，HE）的概念最早于1978年被Ron Rivest[4]等人提出，允許用戶對密文進行特定的代數(shù)計算，結果仍是加密數(shù)據(jù)，且該結果與對明文做相應計算后再加密的結果相同。抽象地，用E(·)表示加密，⊕表示特定的代數(shù)操作，同態(tài)加密具有以下兩個性質：

? 加法同態(tài)性質：E(a)⊕E(b)=E(a+b)

? 乘法同態(tài)性質：E(a)⊕E(b)=E(a*b)

僅滿足加法同態(tài)或乘法同態(tài)的算法稱為半同態(tài)加密（semi-homomorphic encryption）或部分同態(tài)加密（somewhat-homomorphic encryption），典型的有滿足乘法同態(tài)的RSA（Rivest，Shamir，Adleman）算法和ElGamal算法[12]，滿足加法同態(tài)的Paillier加密[13]和DGK（Damg?rd，Geisler，Kr?igaard）加密[14]。以上兩種性質都滿足的同態(tài)加密算法稱為全同態(tài)加密（full homomorphic encryption）。實際應用時，大多隱私保護方案基于半同態(tài)加密方法設計，全同態(tài)加密過長的加密解密時間、過大的計算代價不符合實際應用的需求。

秘密共享技術也支持密文的加法計算，但更適用于分布式計算的場景。該技術假設有n個參與者，數(shù)據(jù)擁有者擁有數(shù)據(jù)a，他將數(shù)據(jù)均勻地分成n個分片a_i，并將這n個分片隨機分給n個參與者。在該過程中沒有一個參與方知道原始的值a是什么，只有當這n個參與者合作才能通過a_i計算得到a的值。除此之外，常用的還有基于多項式方程組構建的(t,n)-門限秘密共享，僅需其中n個分片中的t個就可恢復原數(shù)據(jù)的值。

同態(tài)加密技術有較大的計算代價，而秘密共享技術有較大的通信代價。除此之外，加密技術還包括一些基礎的對稱加密算法，如DES算法、AES算法，以及基礎的散列算法，如信息摘要算法第五版（Message-Digest Algorithm 5，MD5）、安全散列算法256位（Secure Hash Algorithm 256，SHA-256）等。在面對諸多實際問題時，如隱私保護的查詢問題、機器學習等，通常需將多種加密算法結合起來使用。

1.2.4 混合隱私技術

模糊和擾動的技術會降低數(shù)據(jù)的可用性，加密技術會降低數(shù)據(jù)的計算和通信效率，那么能否將二者結合，各取其優(yōu)點呢？出于該目的，混合隱私技術得以發(fā)展。混合隱私技術主要指將擾動技術與加密技術進行混合，根據(jù)其組合方式與目的的差異，可分為Cryptography for Differential Privacy和Differential Privacy for Cryptography兩種[15]。

Cryptography for Differential Privacy即C4DP，是用密碼學改進差分隱私的方法，該類方法以提升差分隱私方法的隱私性與可用性為目標，探索差分隱私方法隱私性與可用性的最優(yōu)平衡。該類方法又可進一步分為基于密文計算改進和基于安全混洗改進兩個部分。前者將中心化差分隱私方法中的可信第三方替換為不可信第三方，并將該第三方的所有操作替換為密文操作，從而在保證較小計算誤差的差分隱私基礎上，提高系統(tǒng)隱私性。后者在本地化差分隱私方法的基礎上引入安全混洗的操作，使用戶本地擾動后的數(shù)據(jù)實現(xiàn)完全的匿名，從而通過分析匿名與差分隱私聯(lián)合帶來的隱私放大效果，提高最終計算結果的準確性。

Differential Privacy for Cryptography即DP4C，是用差分隱私改進密碼學的方法，該類方法將差分隱私擾動的思想引入密碼學協(xié)議中，以改善其計算代價與通信代價。在復雜密碼學協(xié)議執(zhí)行的過程中，攻擊者們可以通過計算過程中一些中間結果的大小、通信的次數(shù)等信息，來對計算的數(shù)據(jù)或結果進行推斷，進行推理攻擊。我們可以基于差分隱私的思想，對密碼學協(xié)議中中間結果的大小、通信的次數(shù)進行適度的擾動，一方面避免過多假的密文數(shù)據(jù)或通信消息的引入，另一方面防止推理攻擊。

基于混合隱私技術，我們可以盡可能實現(xiàn)數(shù)據(jù)隱私、效率與效用之間的平衡。當前基于混洗改進差分隱私的技術，即編碼-混洗-分析（Encode-Shuffle-Analyze，ESA）框架[16]，可基于本地化差分隱私框架直接部署，被谷歌和蘋果等企業(yè)廣泛關注。

1.2.5 分布式計算框架

上述隱私保護技術直接對數(shù)據(jù)進行保護，防止隱私泄露。除此之外，還有另一種思路可以防止隱私泄露，即分布式計算框架，包括安全多方計算和聯(lián)邦學習。這兩種技術不直接對數(shù)據(jù)進行保護，旨在不直接發(fā)送真實數(shù)據(jù)的分布式情況下完成較高準確度的數(shù)據(jù)計算。

安全多方計算（Secure Multi-Party Computation，SMPC）[17]，通過多次多方之間的密文通信，支持多方安全地計算任意函數(shù)。該技術最初于1982年由姚期智教授提出，用于解決百萬富翁問題，即兩個富翁Alice和Bob如何在不暴露各自財富的前提下比較出誰更富有。根據(jù)參與方的數(shù)量不同，安全多方計算分為安全兩方計算和參與方多于兩人的安全多方計算。通用的安全多方計算包括BMR（Beaver，Micali，Rogaway）、GMW（Goldreich，Micali，Wigderson）、BGW（Ben-Or，Goldwassert，Wigdemon）、SPDZ（Smart，Pastro，Damg?rd，Zakarias）等多種協(xié)議[18]，涉及混淆電路、秘密共享、同態(tài)加密、不經(jīng)意傳輸?shù)榷喾N密碼學技術。

聯(lián)邦學習的思想是保證數(shù)據(jù)不出本地，參與的多方之間僅分享模型參數(shù)，從而聯(lián)合完成模式的訓練。此工作的典型代表為2017年谷歌提出的聯(lián)邦學習（federated learning）框架[19]。聯(lián)邦學習框架具備數(shù)據(jù)隱私保護的特質，其訓練數(shù)據(jù)無須集中存放，不會產生由大規(guī)模數(shù)據(jù)收集帶來的直接隱私泄露問題。但研究表明，盡管聯(lián)邦學習使用戶擁有了個人數(shù)據(jù)的控制權，卻依然無法完全防御潛在的間接隱私攻擊。直觀上，我們可以理解為，用戶端訓練的模型參數(shù)是對用戶數(shù)據(jù)在某些維度上的提煉，因此仍包含用戶的隱私信息。具體實現(xiàn)時，該技術仍需與差分隱私或安全聚集技術結合，以保證用戶隱私。

分布式計算框架在保護隱私時，往往存在通信開銷昂貴的問題，因此如何在保護隱私的同時控制通信開銷是該技術的關鍵問題。特別地，對聯(lián)邦學習而言，保護模型參數(shù)的隱私信息對用戶隱私也十分重要。

1.2.6 區(qū)塊鏈技術

區(qū)塊鏈技術旨在通過溯源問責方式保護隱私。面對當前的大規(guī)模數(shù)據(jù)收集的現(xiàn)狀，傳統(tǒng)的隱私保護技術不可能做到面面俱到，在隱私保護技術無效的情況下，可以采用溯源問責的形式去保護隱私。區(qū)塊鏈具有透明、去中心和不可篡改的特性，這些特性與溯源問責的需求天然匹配[20]。

區(qū)塊鏈起源于比特幣。在2008年，化名為中本聰?shù)膶W者發(fā)表“比特幣：一種點對點的電子現(xiàn)金系統(tǒng)”一文，并提出比特幣的概念。這種數(shù)據(jù)貨幣支持互不可信的雙方在無可信第三方介入的情況下進行貨幣交易。區(qū)塊鏈作為比特幣的核心技術，是將數(shù)據(jù)區(qū)塊按照順序鏈接得到的鏈式數(shù)據(jù)結構，它通過密碼學方式保證記錄的不可偽造和不可篡改。

目前，區(qū)塊鏈的不可能三角問題是影響其應用的主要問題之一。區(qū)塊鏈系統(tǒng)的不可能三角是指去中心化、可擴展性和安全性三個需求不可能同時做到最優(yōu)。

? 去中心化是區(qū)塊鏈系統(tǒng)的最基本原則。比特幣在設計上完全實現(xiàn)去中心化，它采用工作證明（Proof of Work，PoW）共識算法。但是，在完全去中心化的系統(tǒng)中，可擴展性會相對較差。與此同時，在某種程度上，這些系統(tǒng)的安全性也受到很大挑戰(zhàn)。例如，比特幣和以太坊的密鑰被盜、智能合約漏洞、隱私泄露等問題也比較突出。

? 可擴展性是區(qū)塊鏈技術在各個領域應用的關鍵性能要求。已有很多研究提出了兼顧去中心化和可擴展性的方法，包括側鏈、跨鏈、權益證明（Proof of Stake，PoS）、委托權益證明（Delegate Proof of Stake，DPoS）、分片、閃電網(wǎng)絡等。

? 安全性是每一個區(qū)塊鏈系統(tǒng)都要面對的問題，也是區(qū)塊鏈技術應用的重要保障。通常，安全性涉及網(wǎng)絡安全、數(shù)據(jù)安全、計算節(jié)點安全、智能合約安全、錢包安全，以及隱私保護等多個方面。

總體而言，對去中心化、可擴展性和安全性三者最大限度地均衡，就是通用型區(qū)塊鏈系統(tǒng)的技術創(chuàng)新的主要方向。

1.2.7 技術的比較

在本節(jié)所闡述的隱私技術中，模糊技術、擾動技術、加密技術、混合隱私技術和分布式計算框架主要用于解決隱私保護問題，區(qū)塊鏈技術主要用于解決隱私問責問題。由此，我們從數(shù)據(jù)隱私性與效用、隱私性與效率兩個方面對這幾種隱私防護技術進行比較，如圖1.2和圖1.3所示。分布式計算框架由于其實現(xiàn)依賴于其他幾種基礎技術的組合，因此不列入該比較。

通過比較可發(fā)現(xiàn)，加密技術和模糊技術分別代表了“高隱私、高效用、低效率”和“低隱私、低效用、高效率”兩個極端。而擾動技術和混合隱私技術在這兩個方面相對較為平衡?；旌想[私技術通過融合加密技術和擾動技術，實現(xiàn)了隱私、效用和效率之間的最優(yōu)平衡。由此，本書主要基于擾動的差分隱私技術和混合差分隱私技術，對不同的隱私挑戰(zhàn)問題及其解決方案進行探討。