ESA：一種新型的隱私保護框架

王雷霞 孟小峰

(中國人民大學信息學院 北京 100872)

隨著數據驅動的人工智能等技術的飛速發(fā)展，用戶數據收集的需求越來越迫切.但隨著隱私泄露事件的頻發(fā)，用戶隱私保障逐步成為各企業(yè)數據收集的“壁壘”[1-2].具體而言，近幾年典型的隱私泄露事件包括Uber賬戶數據泄露事件、Facebook劍橋分析事件，造成了千萬級的用戶數據外泄或濫用[3].為嚴防此類事件的頻發(fā)，各國政府都頒布了相關法令以對用戶隱私數據進行法律意義上的保護.典型的，2016年4月，歐盟通過了《通用數據保護條例》(General Data Protection Regulation, GDPR)[4]，明確規(guī)定用戶在數據上的查閱權、被遺忘權等權利；2019年5月，中國國家互聯網信息辦公室發(fā)布了《數據安全管理辦法(征求意見稿)》[5]，以保障用戶個人信息和重要數據在網絡空間中的安全，并從數據收集、處理使用、安全監(jiān)管3個方面討論其辦法.然而，數據的特殊性質決定用戶的隱私問題不能僅通過法律法規(guī)界定其歸屬解決[6]，企業(yè)也不能因此放棄對用戶敏感數據的收集，發(fā)展在大數據收集場景下兼顧數據隱私性與可用性的隱私保護技術勢在必行.

隱私保護技術經過近20年的發(fā)展，已經有了諸多較為成熟的方法與體系[7]，典型的包括匿名化技術[8-11]、差分隱私技術[12-13]、密碼學技術等.在大數據場景下，當前主流的隱私保護技術是差分隱私技術，更具體的指本地化差分隱私技術(local differential privacy, LDP)[14]，谷歌[15]、微軟[16]和蘋果[17]等企業(yè)都借助該技術完成特定的用戶行為信息統(tǒng)計.差分隱私類方法本質上都是在保證數據整體分布不變的情況下對數據進行擾動，本地化差分隱私技術的優(yōu)勢主要體現在對隱私的嚴格定義和對數據收集場景的適用性上.具體地，在隱私定義上，它保證了任意一條用戶數據的增、刪、改都對用戶發(fā)布數據的統(tǒng)計分布幾乎無影響，可從根本上抵御匿名化方法難以應對的背景知識攻擊；在場景適用性上，它直接在用戶本地端對數據進行擾動，并只對外發(fā)布擾動數據以保護隱私，無需依賴任何第三方.但該方法也存在著致命的缺點，即在本地端添加過多噪聲，使得數據的可用性較差.使用該方法，企業(yè)要么承受該數據誤差，要么為提高數據可用性提高隱私損失ε，從而使得用戶數據的隱私度降低.

從理想的角度出發(fā)，是否存在一種隱私保護方法在不對數據擾動的情況下保護隱私，使得數據的隱私性與可用性兩者兼得?2017年谷歌的Bittau等人[18]提出ESA(encode-shuffle-analyze)框架，向該理想狀態(tài)跨出有力的一步.該框架主要由編碼器(encoder)、混洗器(shuffler)和分析器(analyzer)3部分組成：編碼器運行在客戶端，對用戶數據進行本地化的編碼、分割、擾動等處理；混洗器運行在一個半誠信的第三方，它可借助現有的安全混洗協議[19-25]在對數據一無所知的情況下完成安全的混洗操作；分析器運行在真正的數據收集者端，對收集的數據進行校正與分析.該框架中，混洗器完成了對用戶數據完全匿名的操作，使得用戶可以在盡可能對數據本身進行較小擾動的情況，獲得較多的隱私保護.

更具體地，圖1對該例子中數據收集者獲得頻數估計的分布進行展示，基于ESA框架擾動后的結果更接近于原始數據，而本地化差分隱私方法擾動后的結果則與真實結果相距甚遠.值得說明的是，基于ESA框架擾動后的結果與中心化差分隱私方法(central differential privacy, CDP)在該案例下獲得的結果近似，但該中心化差分隱私方法假設數據收集者可信(或存在一個可信第三方)，是在對用戶真實數據的計算結果(即直方圖)上直接添加1次Laplace噪聲得到的，而基于ESA框架的方法上需在用戶本地添加總共n次噪聲.

Fig. 1 Comparison of different methods’ results

當前對ESA框架的研究仍處于起步階段，以混洗差分隱私為主要方法，主要集中在2個方面：1)對其隱私增強效果的理論證明，即隱私放大(privacy amplification)理論；2)基于該模型提出不同統(tǒng)計估計方法.就混洗差分隱私而言，隱私放大理論是指用戶在本地通過本地化差分隱私的方法對數據進行擾動，使得擾動后的數據經混洗實現接近于中心化方法所獲得的數據統(tǒng)計結果.在不同統(tǒng)計估計方法實現時，可基于現有的差分隱私技術[31-32]進行設計，為了進一步提高準確性，也可借助密碼學中Split-Mix方法[33]進行構建.

本文對該新型的隱私保護框架進行綜述，主要貢獻有4個方面：

1) 本文對ESA框架的實現機理與隱私保護程度進行詳盡的分析，并以混洗差分隱私為例與其他差分隱私模型進行對比，以說明該框架的優(yōu)勢(第1節(jié))；

2) 本文對ESA框架實現的主要方法——混洗差分隱私進行分析總結，包括該方法設計與實現的基礎理論與技術(第2，3節(jié))，以及該方法下具體的隱私保護機制(第4，5節(jié)).具體地，本文按研究問題分類，對混洗差分隱私的計數估計、頻數估計、求和估計及其他的簡單統(tǒng)計問題進行了對比分析.

3) 本文通過實驗對混洗差分隱私下不同統(tǒng)計問題的隱私保護機制進行對比.當前絕大多數工作都是理論研究，本文通過實驗對比，可以更直觀地說明不同理論機制在實際應用時的效用和效率差異.

4) 基于對混洗差分隱私的理論與實驗分析，本文提出ESA框架應用與發(fā)展的挑戰(zhàn)問題，對本文進行總結.其中，考慮到混洗差分隱私在應用上固有的局限性、在方法設計中的明顯不足，本文對ESA框架下的非差分隱私方法進行展望(第6，7節(jié)).

1 ESA隱私保護框架

之后，以當前主流的混洗差分隱私框架(即ESA框架與差分隱私的結合)為主要案例，在實現同樣隱私目標的情況下，與傳統(tǒng)的隱私保護框架對比，包括中心化差分隱私框架、本地化差分隱私框架及基于密碼學的差分隱私框架.最終通過對比說明，ESA框架不僅有利于隱私保護中數據高隱私度與高可用性的實現，對當前各企業(yè)已部署的本地化差分隱私框架也極具適應性.

1.1 ESA框架定義

ESA框架如圖2所示，主要由編碼器、混洗器和分析器構成，并假設這三方是不可合謀的.

Fig. 2 ESA framework

① 半誠信參與方(semi-honest party)[36]，又稱誠實且好奇的參與方(honest-but-curious party)，是源于密碼學中的一個安全假設，假設該參與方會正確遵循協議的執(zhí)行，但對計算的中間結果保持好奇，并依此進行推理攻擊(inference attack).

1) 編碼器.主要運行在用戶的本地客戶端，通常被認為是可信的.它的作用是對用戶數據進行編碼，以完成對用戶數據的發(fā)布范圍、粒度、擾動程度以及隨機化程度的控制，在不依賴任何信任假設的情況下保護用戶數據隱私[15].

編碼器可根據其輸出消息的多寡分為單消息模式和多消息模式[34-35].單消息模式指用戶將數據編碼為1條消息，形式上可以是1個數值、1個二元組或1個數組，每個消息都是后續(xù)處理的最小單元；多消息模式指用戶將數據編碼為多條可分別處理的消息，如多個數值、二元組和數組等.對于同一輸入，通常情況下多消息模式可攜帶更多信息，有助于分析器獲取更準確的分析結果.

編碼器的具體實現，可通過數據泛化、數據分割、加密、添加差分隱私噪聲的方式實現，以達到消除或減少數據所蘊含的隱私信息的目的[18].

2) 混洗器.是獨立的半誠信(semi-honest)①服務器，可在對數據內容一無所知的情況下執(zhí)行安全的混洗操作，是ESA框架的核心組件.它的作用是接收用戶編碼后的數據，消除相應的元數據(包括接收時間、順序、IP地址等)，并對接收數據進行混洗(即打亂順序)，以達到匿名目的.為保證足夠的隱私保護效果，該混洗器需等待一段時間收集足夠的用戶數據進行混洗，并對數據量滿足一定閾值的數據進行發(fā)布.當數據量為敏感信息時，可對該閾值添加滿足差分隱私的噪聲進行擾動，或者隨機丟掉一些數據使數據量滿足差分隱私[18]，從而保護數據量隱私.

在混洗器的模式上，可分為單混洗器模式和多混洗器模式[34-35].單混洗器模式是將所有編碼器輸出的數據一起混洗，即從邏輯上使用1個混洗器進行混洗；多混洗器模式是將編碼器輸出的數據按屬性或其他特征進行分類，從邏輯上使用多個混洗器對每個分類內的數據分別進行混洗.多混洗器模式通常用于屬性或分類特征不敏感的情況下，與多消息模式的編碼器相結合.但多混洗器模式并不與編碼器中的多消息模式對應，多消息的消息也可以使用單混洗模式的混洗器.單混洗模式將所有數據混淆，具有更高的隱私性；但對多消息的分類特征不敏感的情況，使用多混洗模式會獲得更高的數據可用性.

混洗器的具體實現可根據該模型部署的條件借助已有的安全混洗協議[18-24]，基于可信硬件[25]、同態(tài)加密[36-38]或安全多方計算[39]等方式完成.特別地，單混洗模式和多混洗模式并不與混洗器具體實現的數量一一對應，這2個混洗模式是從隱私的邏輯層面進行定義的.多混洗模式可使用1個混洗器實現，即為每個分類添加標簽，對屬于不同標簽的數據分別進行混洗；這2個混洗模式都可基于現有的安全協議使用多個混洗器實現，以避免單點失敗.

3) 分析器.由數據收集者運行，是不可信服務器.它的作用是接收混洗器發(fā)布的數據，依據相應的編碼和混洗規(guī)則對數據進行分析與校正，并獲取最終的統(tǒng)計結果.該框架中數據的隱私性主要是針對分析器而言的，即將分析器視為數據的窺探者.

本文綜述的重點在于如何設計編碼器和分析器，選擇恰當的混洗模式來進行滿足一定隱私保證的統(tǒng)計計算.本文將混洗器作為黑盒來使用，假設其可以完成安全的混洗操作，主要原因是安全混洗協議已經發(fā)展成熟，在諸多安全相關的文獻中已有過總結和論述[18-24]；同時安全混洗協議的不同實現并不會對該框架下隱私保護方法的隱私性和可用性造成明顯影響.

1.2 ESA隱私分析

1.3 應用實例：混洗差分隱私方法

通常情況下，研究者們將ESA框架與隱私定義嚴格的差分隱私進行結合，即保證分析器所獲得的最終輸出滿足差分隱私定義，以此來對數據隱私進行保證與度量.該結合被稱為混洗差分隱私，如圖3(b)所示，是本文所探討的核心方法.

Fig. 3 Comparison of differential privacy methods under different frameworks

對發(fā)展歷史已久的差分隱私方法而言，現存在著中心化差分隱私、本地化差分隱私、基于加密的差分隱私等多種基于不同隱私保護框架實現的差分隱私方法.本節(jié)將混洗差分隱私與其他差分隱私方法進行對比，以說明ESA框架在數據隱私性、數據可用性和框架易用性上的顯著優(yōu)勢.

1.3.1 與中心化、本地化差分隱私對比

混洗差分隱私方法與本地化差分隱私方法具有高度的相似性，它們可使用相同的編碼器，實現用戶本地數據的差分隱私.混洗差分隱私方法可視為在本地差分隱私框架上增加混洗器得到的，該混洗器依賴于半誠信的安全假設，相比于無任何可信依賴的本地化差分隱私框架，其可信假設更強.但混洗器所完成的匿名操作，可有效實現隱私增強的效果，意味著在保證同樣ε-差分隱私保護的前提下，混洗差分隱私框架可通過編碼器添加較小的噪聲來提高最終數據的可用性.

中心化差分隱私使用集中式隱私保護框架，將分析器和編碼器集成在一起，放置于一個可信的第三方，該第三方可視為數據收集者.該方法中，數據收集者收集用戶原始數據，在該數據上進行分析，之后發(fā)布添加差分隱私噪聲的分析結果.混洗差分隱私方法與之相比，雖在用戶數據上添加了較多噪聲損失了一定數據的可用性，但擺脫了對可信服務器的強依賴.

總體而言，在模型對可信第三方的依賴程度上，本地化差分隱私<混洗差分隱私<中心化差分隱私，即本地化差分隱私擁有最小的可信假設；以同一ε-差分隱私為目的，在分析結果的可用性上，中心化差分隱私>混洗差分隱私>本地化差分隱私，即中心化差分隱私擁有最高的結果可用性.由此可發(fā)現，混洗差分隱私方法在隱私與可用性上，均介于本地化與中心化差分隱私兩者之間，實現了更好的平衡.

1.3.2 與基于加密的差分隱私對比

僅從數據可用性的角度出發(fā)，基于加密的差分隱私也可在無需可信第三方支持的隱私保護框架上，實現可用性與中心化方法接近的差分隱私[41]，與混洗差分隱私方法的結果相似.如圖4所示，在該框架中，用戶需在本地端對數據進行同態(tài)加密，將加密后的數據發(fā)送給服務器.之后，服務器借助2個不可共謀的云，在加密數據上計算查詢結果并添加滿足差分隱私的噪聲，發(fā)布該擾動的數據.

Fig. 4 Cryptographic differential privacy framework

但相比混洗差分隱私方法，該方法借助同態(tài)加密完成查詢計算，會產生較高的計算代價和通信代價.同時，該框架需針對每一個查詢特別設計隱私協議，而混洗差分隱私框架可通過簡單的更改部署在現有的、廣泛應用的本地化差分隱私框架上，具有較強的適應性.類似基于圖4的加密差分隱私方法還有文獻[42-43]，均具有上述不足.

綜上，通過對不同框架下差分隱私方法的直觀對比，說明了混洗差分隱私在隱私性、可用性和易用性上的突出優(yōu)勢，而這些優(yōu)勢均得益于ESA框架的應用與部署.后文，將對該混洗差分隱私方法進行詳細的理論分析與實驗對比，同時對ESA框架下其他隱私保護問題與方法的實現進行分析與展望.

2 基于ESA的隱私保護基礎理論

本節(jié)以混洗差分隱私為主要方法，對ESA框架下隱私保護機制設計與實現的基礎理論進行介紹.首先，本節(jié)對差分隱私的基本定義和重要性質進行回顧，之后，在ESA框架下基于差分隱私概念提出混洗差分隱私.最終，基于混洗差分隱私，本節(jié)給出ESA框架下隱私放大理論的嚴格定義與實驗分析.該理論嚴格證明了混洗器對用戶本地端隱私保證的增強效果，說明ESA框架可在本地添加較少噪聲來實現較強的隱私保護效果，從而提高數據可用性.

2.1 差分隱私

Pr(M(D)∈S)≤eεPr(M(D′)∈S)+δ.

(1)

該定義為差分隱私的一般定義，也可將其視作中心化差分隱私的定義.相應地，本地化差分隱私考慮分布式數據集，即每個用戶擁有1個數據，且數據收集者可將收集的數據和用戶相關聯.為保證數據收集者所收集的數據滿足差分隱私，需保證每個用戶的輸出均滿足差分隱私，因此得到如下本地化差分隱私的定義：

Pr(M(x)∈S)≤eεPr(M(x′)∈S)+δ.

(2)

在定義1和定義2中，當δ=0時，可得到純差分隱私(pure differential privacy)的定義，可分別標記為ε-DP和ε-LDP；否則稱為近似差分隱私(approximate differential privacy).ε被稱為隱私代價或隱私預算，該值越小，說明相鄰數據集或不同用戶輸入產生同一結果的概率越相近，該算法的隱私保護程度越高.δ表示相鄰數據集輸出結果存在概率δ使其不滿足純差分隱私，該值越小，該算法的隱私保護程度越高.

中心化與本地化的差分隱私均具有序列組合性(sequential composition)、并行組合性(parallel composition)和后處理性(post-processing)這樣3條重要性質.差分隱私的組合性可幫助協議設計者進行隱私預算ε的分割，后處理性質對定義在ESA框架上的差分隱私十分關鍵.

性質1.序列組合性[45].給定數據集D和m個隨機化算法{M1,M2,…,Mm}，算法Mi，1≤i≤m滿足εi-DP，則這m個Mi(D)算法構成的序列滿足∑εi-DP.

性質2.并行組合性[45].給定數據集D={D1∪D2∪…∪Dm}，其中Di，1≤i≤m和Dj，1≤j≤m且i≠j為互不相交的數據集，設Mi滿足εi-DP的算法，則這m個Mi(Di)算法構成的序列滿足max{εi}-DP.

性質3.后處理性[46].給定滿足(ε,δ)-DP的隨機化算法M，令f為任意的隨機化函數，則f°M依舊滿足(ε,δ)-DP.

序列組合性說明隱私預算ε可以在算法設計的不同步驟進行分配；并行組合性則定義了算法在不相交數據集上的隱私保證；后處理性則強調，在滿足ε-DP的數據結果上進行隨機操作，其輸出依舊滿足ε-DP.這3條性質適用于本地化差分隱私時，數據集D相應地定義在用戶本地的數據集上.

2.2 混洗差分隱私

基于定義1～2與性質1～3，結合ESA框架，本節(jié)給出混洗差分隱私的定義.簡單而言，混洗差分隱私要求對分析器來說，其收集的數據滿足定義1中差分隱私的要求.同時，差分隱私的后處理性說明，只要ESA框架中的隨機化編碼器R和混洗器S處理過后的數據滿足差分隱私，最終結果即滿足差分隱私.該結果的隱私效果與分析器無關，分析器的重要作用是對擾動數據進行計算，對估計結果進行校正.

定義3.混洗差分隱私[47].給定n個可信用戶，每個用戶對應1條記錄xi.令R:X→Ym表示隨機化的編碼器，其中m表示編碼后消息的數量；S:Ym→Π(Ym)表示混洗操作；算法A:Π(Ym)→Z為分析函數，其中Π表示亂序，則混洗差分隱私協議可表示為P=(R,S,A).根據后處理性，則協議P滿足(ε,δ)-DP,當且僅當擾動后的數據S°Rn=S(R(x1),R(x2),…,R(xn))=Π(R(x1),R(x2),…,R(xn))滿足(ε,δ)-DP.

定義3假設參與計算的用戶都是可信的，即都會按照協議正確地參與計算.但如果存在用戶不可信、掉線或者與分析器共謀，則會大大影響混洗的效果，從而影響最終的差分隱私效果，由此，具有魯棒性的混洗差分隱私被提出.

定義4.具有魯棒性的混洗差分隱私(robust shuffle differential privacy, RSDP)[48].給定N個用戶和可信用戶比例γ∈(0,1]，如果對于所有的N∈+，γ′>γ，算法S°Rγ′N滿足(ε,δ)-DP，則混洗差分隱私協議P=(R,S,A)滿足(ε,δ,γ)-RSDP.

定義4保證了，在至少有γ比例的用戶正確遵循協議的情況下，混洗差分隱私協議P滿足(ε,δ)-DP.特別說明，此處的魯棒性是對隱私性的保證，而非算法可用性的保證.

2.3 隱私放大理論

隱私放大(privacy amplification)是ESA框架中混洗器對隱私效果增強的理論分析，基于該理論，可將現有的本地化差分隱私方法直接應用在ESA框架上.具體地，在混洗差分隱私框架中，假設用戶在本地端通過隨機編碼器R擾動后的數據滿足εl-LDP，經過混洗后，分析器所獲取的數據滿足εc-DP，從εl到εc的轉變可通過隱私放大理論獲取.εl對應于較大的數值，表示較低的隱私性；εc對應于較小的數值，表示較高的隱私性.針對具體的差分隱私機制，研究者們提出了不同的隱私放大定理.

2.3.1 通用隱私放大定理

與差分隱私相同，混洗差分隱私也存在交互式和非交互式2種隱私保護機制[49-50]，如圖5所示.假設存在n個可信用戶，每個用戶擁有輸入xi和相同的隨機化的編碼協議Ri，在交互機制中，協議Ri的輸入為{R1(x1),R2(x2),…,Ri-1(xi-1),xi}，即與前i-1個編碼器結果和用戶的輸入xi相關；而非交互機制中協議Ri僅與用戶的輸入xi有關，可視為交互機制的簡化.

交互機制可以處理較為復雜的、用戶間有關聯關系的統(tǒng)計分析，如果一些遺傳病的統(tǒng)計，被統(tǒng)計者與其親屬可能存在關聯關系；而非交互機制僅可以處理用戶數據獨立的統(tǒng)計分析.相應地，基于這2種機制，研究者們提出了2個通用隱私放大定理.

Fig. 5 Interactive mechanism and non-interactive mechanism

定理1.通用交互機制的隱私放大定理[26].給定n個用戶，每個用戶對應1條記錄xi，且在本地運行隨機化編碼協議R.對于任意的n>1 000，δ∈(0,0.01)，如果協議R滿足εl-本地化差分隱私，且εl∈(0,0.5)，則協議S°Rn對應混洗后的n個輸出滿足(εc,δ)-DP，其中

(3)

定理2.通用非交互機制的隱私放大定理[47].給定n個用戶，每個用戶對應1條記錄xi，且在本地運行隨機化編碼協議R.對于任意的n∈+，δ∈[0,1]，εl∈(0,ln(n/ln(1/δ))/2]，如果協議R滿足εl-LDP，則協議S°Rn對應混洗后的n個輸出滿足(εc,δ)-DP，其中

(4)

根據定理1和定理2，設定δ=10-9，可得到表1和表2中隱私放大結果.令n表示參與計算的可信用戶數量，表1為根據式(3)計算εl經隱私放大后得到的εc取值；表2為根據式(4)計算εc對應的被放大前的εl取值.根據表1和表2可發(fā)現，通過隱私放大，可輕易實現在用戶本地端添加滿足較大εl-LDP的噪聲，而在分析器端獲得較小的εc-DP保證.同時，隱私放大效果隨著參與用戶數量的增加而增大.

Table 1 Results of Privacy Amplification on General Interactive Mechanism

Table 2 Converse Results of Privacy Amplification on General Non-interactive Mechanism

通過表1中的分析計算可發(fā)現，通用交互機制的隱私放大結果是不適用于現實情況的.由于該機制僅在εl∈(0,0.5)時生效，此時εc的取值往往小于0.2.現實情況中，通常并不需要如此嚴格的(如此小的εc)差分隱私保證，并且用戶端添加過小的εl，會給統(tǒng)計結果造成較大誤差.由此，通用非交互機制的隱私放大定理往往會有更多的應用.

2.3.2 基于隨機響應的隱私放大定理

為了獲取更好的隱私放大的效果，研究者們針對具體的差分隱私機制提出了更精確的隱私放大定理.被應用最多的，是基于隨機響應機制提出的隱私放大定理.隨機響應機制是本地化差分隱私的基本擾動技術，Warner[51]于1965年提出.為方便后續(xù)應用，本節(jié)對該機制進行一定程度的擴展，并描述如下[27,47].

(5)

當k=2時，假設v1=‘Yes’，v2=‘No’，則上述機制即為經典的隨機響應機制，回答“Yes/No”的問題，本文將其稱為布爾隨機響應機制(Boolean random response mechanism).當k≥2時，本文將其稱為k值隨機響應機制(k-random response mech-anism,kRR).之所以將其區(qū)分開，是由于在進行復雜差分隱私機制設計時，通常要考慮對數據01編碼或直接使用該數值的問題，涉及上述2種不同方案.基于此，研究者們提出了2種相應的隱私放大定理.

定理3.布爾隨機響應機制的隱私放大定理[28].給定n個用戶，每個用戶對應1條記錄xi∈{0,1}，且在本地運行協議R.對于任意的n∈+，δ∈[0,1]，λ∈[14 ln(4/δ)/n,1]，如果協議R以λ的概率均勻輸出{0,1}中的值，1-λ的概率輸出真實值，則協議S°Rn對應混洗后的n個輸出滿足(εc,δ)-DP，其中

(6)

在定理3中，當λ=2/(eεl+1)時，布爾隨機響應機制滿足εl-LDP.將該式代入式(6)，通過簡化，可得到寬松的隱私放大效果[52],即當0<εl≤lnn-ln(14 ln(4/δ))時，

(7)

定理4.k值隨機響應機制的隱私放大定理[47].給定n個用戶，每個用戶對應1條記錄xi∈{1,2,…,k}，且在本地運行協議R.對于任意的k,n∈+，λ∈[0,1]，εc∈(0,1]，如果協議R以λ的概率均勻輸出{1,2,…,k}中的值，以1-λ的概率輸出真實值，則當λ滿足式(8)時，協議S°Rn對應混洗后的n個輸出滿足(εc,δ)-DP.

(8)

(9)

與2.3.1節(jié)相同，設定δ=10-9，針對不同的可信用戶數量n，表3表示根據定理3在給定n和εc的情況下，計算εl的取值情況；表4表示根據定理4，在給定n，εc，并假設k=2的情況下，計算εl的取值情況.在表3(表4)的結果中，None表示εl的取值不滿足定理3(定理4)，無法進行隱私放大.

顯然，在針對2個離散值進行擾動時，定理4的隱私放大效果優(yōu)于定理3，由此選用定理4進行基于隨機響應機制的隱私放大是更明智的選擇.同時通過分析發(fā)現，隨著k值的增大，定理4的隱私放大效果會縮減，但并不明顯.通過實驗發(fā)現，在給定n和εc的情況下，不同k值所造成隱私放大逆向計算結果εl的差異僅在小數點后幾位體現.由于該計算結果較為簡單，此處不予以展示.

Table 3 Converse Results of Privacy Amplification on Boolean Random Response Mechanism

Table 4 Converse Results of Privacy Amplification on k Random Response Mechanism

3 基于ESA的隱私保護基礎技術

本節(jié)以混洗差分隱私作為ESA實現的主要方案，對該方案構建的基礎技術進行總結與介紹，為后文不同隱私保護方法的對比分析奠定基礎.

這些基礎技術主要分為2類：一類是差分隱私技術，包括中心化差分隱私、分布式差分隱私和本地化差分隱私中的具體隱私保護機制；另一類是基于匿名的密碼學技術，具體指Split-Mix方法.差分隱私技術中，本地化差分隱私技術可與2.3節(jié)所述的隱私放大定理相結合以實現混洗差分隱私，該途徑所獲得的差分隱私模型較為簡潔.基于匿名的密碼學技術Split-Mix方法通常與中心化或分布式的差分隱私技術相結合以滿足最終的差分隱私保證，在該過程中Split-Mix方法可進一步減少在原始數據中添加的噪聲，使計數結果具有較高的準確性，但同時也會產生較高的通信代價.

3.1 差分隱私技術

差分隱私技術根據不同的使用場景，可分為中心化差分隱私、分布式差分隱私和本地化差分隱私3種，均可通過與ESA框架不同的結合方式實現混洗差分隱私，具體技術如下.

3.1.1 中心化差分隱私技術

中心化差分隱私技術指一般的差分隱私機制，該機制通常在統(tǒng)計分析結果(如直方圖)上添加滿足一定分布的噪聲，使該擾動后的結果滿足(ε,δ)-DP，以響應用戶查詢.為保證擾動后結果的無偏性，通常需要保證添加噪聲的期望為0.常用差分隱私機制如下：

定理5.拉普拉斯機制[46].令f:Xn→是一個敏感度為Δ的函數，即對所有的相鄰數據集D,D′∈Xn，|f(D)-f(D′)|≤Δ.當ε>0時，生成噪聲η～Lap(Δ/ε)，則添加噪聲后的輸出f(D)+η滿足ε-DP.

定理6.二項分布機制[53].令f:Xn→是一個敏感度為Δ的函數，即對所有的相鄰數據集D,D′∈Xn，|f(D)-f(D′)|≤Δ.當ε>0，δ∈(0,1)，λ≥20(eε/Δ+1)/(eε/Δ-1)2ln(2/δ)時，生成噪聲則添加噪聲后的輸出f(D)+η滿足(ε,δ)-DP.

定理7.幾何分布機制[54].令f:Xn→是一個敏感度為Δ的函數，即對所有相鄰數據集D,D′∈Xn，|f(D)-f(D′)|≤Δ.當ε>0時，生成噪聲η～SG(ε)，添加噪聲后的輸出f(D)+η滿足ε-DP.

其中，SG(ε)表示對稱幾何分布，它對應的概率分布函數為Pr(η=x)=e-ε|x|/Δ×(eε/Δ-1)/(eε/Δ+1).該分布可看作離散化的拉普拉斯分布，其期望為0.該機制通常為整數數值添加噪聲.

3.1.2 分布式差分隱私技術

分布式差分隱私技術與中心化差分隱私技術不同的是，該方法不直接在統(tǒng)計結果上添加噪聲，而在用戶端的原始數據上獨立添加滿足一定分布的隨機噪聲，并使得擾動后的數據在服務器端滿足差分隱私.分布式差分隱私技術通常利用拉普拉斯分布無限可分性質，在用戶端獨立添加滿足一定分布的噪聲，使得在服務器端這些噪聲的和滿足拉普拉斯分布[31].

定理8.分布式幾何分布機制[32,55].令n為可信用戶數量,f:Xn→是一個敏感度為Δ的函數，即對所有的相鄰數據集D,D′∈Xn，|f(D)-f(D′)|≤Δ，獨立隨機變量滿足分布Pólya(1/n,e-ε/Δ)，則噪聲η～SG(ε)可通過式(10)模擬：

(10)

3.1.3 本地化差分隱私技術

本地化差分隱私技術在用戶端的原始數據上添加噪聲，并保證任一用戶的發(fā)布數據均滿足差分隱私定義.該技術中最常用的是隨機響應機制，亦可基于一般的差分隱私機制(指中心化差分隱私技術)實現，但會產生較多噪聲.該技術是混洗差分隱私方法設計中最常用的基礎技術，它結合混洗器的隱私放大效果可達到較強的差分隱私保護效果.

具體技術中，為了在隨機響應機制的基礎上進一步降低通信代價和均方誤差，使計算結果不依賴于用戶數據的值域，基于略圖的本地化差分隱私(sketch-based local differential privacy)算法[56-57]被提出，即首先使用散列函數對用戶數據進行映射，對該映射后的值進行擾動.Wang等人[57]針對此類方法以均方誤差為目標函數對該最小值問題進行求解，提出了OLH方法，可在值域較大的情況下，實現與值域[d]大小無關的最優(yōu)誤差，[d]表示{1,2,…,d}.該方法將較大的數據值域[d]通過散列函數進行壓縮，映射至較小的值域[d′]，用戶將其擁有的值先用該散列函數進行散列，而后進行隨機擾動，即以εl/(εl+d′-1)的概率保持該值不變，以1/(εl+d′-1)的概率擾動為值域{1,2,…,d′}內的其他值.當d′=eεl+1時，可使結果對應的均方誤差最小.較大值域[d]指的是d≥3eεl+2時，否則應用通用的k值隨機響應算法即可獲得較小的均方誤差.更多本地化差分隱私方法在文獻[14]中已有詳細綜述，本節(jié)不再贅述.

3.2 基于匿名的密碼學技術

ESA框架中的混洗器相當于完成了徹底的匿名操作，由此可基于Split-Mix方法設計實現滿足分析器端差分隱私的算法.同時，利用Split-Mix方法中類似秘密共享的操作，可進一步對用戶端編碼后的數據提供保護，分析器將會看到幾乎完全隨機的數據分片，如此可進一步減小差分隱私噪聲的添加.Split-Mix方法與加法秘密共享不同的是，后者需保證不同的數據分片(即shares)由不同的參與者擁有，而該算法對數據分割獲得的數據分片可由1個或多個混洗器持有，取決于混洗器的實現方式.

Ghazi等人首次提出并證明使用該算法可以在ESA框架中實現差分隱私[58]，并證明了該算法的誤差上界，以及一輪協議(one-round protocol)下的誤差下界[59].Balle等人[60]給出了與Split-Mix方法結合的差分隱私保證，見定理9.基于定理9，可以進一步設計出多消息模式下的混洗差分隱私機制.

定理9.假設算法M和算法M′的統(tǒng)計距離(總體方差)為μ(σ)，算法M滿足(ε,δ)-DP，則算法M′滿足(ε,δ+(1+eε)μ(σ))-DP.

4 基于ESA的隱私保護方法對比

Table 5 Research Fields of Shuffle Differential Privacy

其中，計數估計、頻數估計和求和估計是統(tǒng)計估計的基礎問題，受到廣泛關注，也是本節(jié)分析的重點.在本節(jié)的理論分析中，一般假設有n個用戶參與計算，實現了分析器端(εc,δ)-DP的隱私保護效果.部分機制假設參與計算的用戶不完全可信，此時使用的N表示用戶數量，γ表示可信用戶比例，可在分析器端實現具有魯棒性的(ε,δ,γ)-RSDP；當γ=1時，它等同于(εc,δ)-DP.同時，在文中使用[d]表示{1,2,…,d}，[n]表示{1,2,…,n}.在不同估計機制的對比表中，通信代價指每個用戶發(fā)送消息的數量，“—”表示該項隱私未得到嚴格的理論保證.

4.1 計數估計

針對該問題，研究者們提出了若干方法，分別實現了不同的隱私目標.Cnt_RR[28]基于隱私放大理論，可實現不同ε的中心端差分隱私和本地端差分隱私.Cnt_2M[61]，Cnt_PURE[62]，Cnt_SGM[48]，Cnt_BN[48]僅考慮中心端差分隱私，其中，Cnt_2M實現近似差分隱私，Cnt_PURE實現純差分隱私，Cnt_SGM和Cnt_BN則進一步考慮了用戶不完全可信的場景，分別實現了分析器端具有魯棒性的純差分隱私和近似差分隱私.具體方法對比見表6，方法分析為：

(11)

Table 6 Comparison of Counting Estimation Methods on Shuffle Differential Privacy

4.2 頻數估計

頻數估計中假設每個用戶擁有1個離散型的值xi∈[d]，分析器端基于匿名的用戶擾動數據估計這些數值頻數count(j),j∈[d]，即估計用戶數據的直方圖.

Table 7 Comparison of Frequency Estimation on Shuffle Differential Privacy

為了在值域[d]較大時進一步減少頻數估計的誤差，研究者們相繼提出了若干頻數估計方案，可實現與值域[d]無關的誤差邊界.

Hist_MM[61]方法基于計數機制Cnt_2M構建，僅考慮分析器端的差分隱私，不考慮用戶端的差分隱私，由此無需根據值域[d]對用戶端的隱私預算進行劃分，分析器也可計算得到與[d]無關的誤差邊界.在該方法中，每個用戶將其擁有的數據進行獨熱(one-hot)編碼，即生成1個d長的向量，第xi位為1，其余位為0.之后對每一位{0,1}分別使用滿足(εc/2,δ/2)-DP的Cnt_2M中的擾動機制進行擾動，得到y(tǒng)ij={1}*.為了使得分析器能夠在徹底的混洗后依然識別yij對應于哪一個離散值，用戶將j×yij發(fā)送給混洗器進行擾動.最終分析器分別統(tǒng)計每一個值j∈[d]的計數，使用Cnt_2M中的校正機制進行校正，計算其頻數.該機制的優(yōu)點在于它的誤差邊界并不依賴于值域[d],但該機制所獲得的估計結果是有偏的，且僅考慮了分析器作為攻擊者時的隱私保護，不能保證對任意攻擊者的用戶端隱私.

SLH機制使用1個混洗器進行混洗，一旦該混洗器與分析器串通，用戶的隱私將不能得到保證.為了解決該問題，Wang等人[40]在SLH方法的基礎上進一步提出了一個通用協議MURS(multi uniform random shufflers)，使用m個混洗器對用戶數據進行混洗，每個混洗器在混洗的過程中都隨機添加一些均勻分布的假數據.此處的多個混洗器完成的是幾乎相同的工作，仍對應于1.1節(jié)中介紹的單混洗器模式，只是使用多個服務器來實現該模式.這樣一來，即使有m-1個混洗器和除被攻擊用戶外其余n-1個用戶都與分析器合謀，用戶數據至少能得到由1個混洗器所添加的假數據構成的“隱私毯子”帶來的保護.

分析器端滿足(εc,δ)-DP.

至此，上述分析的所有方法均針對單值頻數估計，對于多值頻數估計(即用戶擁有多個值的情況)，通常情況下，可通過對隱私預算εc進行分割，或從多值中隨機采樣1個值進行擾動，文獻[65-66]證明后者的誤差更小.而針對ESA模型下的多值頻數估計，Erlingsson等人[52]提出了“屬性分段”(attribute fragmenting)的通用方法.對于一些獨立的自然屬性，如統(tǒng)計人群的年齡、性別等，可將不同的屬性作為單獨的分段分別擾動，每個屬性使用1個單獨的混洗器進行混洗，以提高數據可用性；對于非自然屬性，可人為將其拆分為多個分段，應用該屬性分段技術.該屬性分段的應用特例是，對于用戶擁有的數值xi可進行獨熱編碼，而后使用Cnt_RR方法對每一比特位的數據分別進行擾動與混洗.

4.3 求和估計

研究者們基于上述針對離散值的擾動方法(包括計數估計方法和頻數估計方法)，提出了若干實數求和估計機制，如RSum_RR，RSum_KR，RSum_RM，RSum_DSG，RSum_PURE，其中RSum_PURE實現了純差分隱私，其余均實現了近似差分隱私.每一個方法的提出，都相比前一個方法降低了統(tǒng)計結果的誤差邊界；但兼顧結果可用性和方法通信代價，RSum_RM應是當前可行性較高的估計方法.

在具體實現時，為了應用上述對離散值擾動的方法，首先需要將該實數根據一定規(guī)則編碼為若干整數.通常情況下，研究者們會依據一定的準確度p將實數值xi其放大p倍得到pxi，而后將其無偏映射為離散型的整數，該過程稱為隨機舍入(random rounding).最終，在若干離散型數據上，基于布爾求和或頻數估計方法進行計算.通常隨機舍入算法需保證無偏，以保證最終結果的可用性.求和估計的方法對比見表8，具體方案如下所述.

實數求和估計結果的準確性一方面依賴于隱私預算εc的分配與方法的隱私放大效果；另一方面也與隨機舍入的結果的準確性有關.進一步地，RSum_RM[35]方法將用戶擁有的xi∈[0,1]隨機舍入為多個更為準確的值，以提高方法的可用性.

RSum_RM[35]方法的核心思想是，通過將用戶擁有的數值xi∈[0,1]依據m個固定的準確度編碼為多個值，并對編碼后的值分別獨立地應用隨機響應方法，從而盡可能利用混洗器提供的隱私保護.具體地，給定一系列準確度p1,p2,…,pm∈+，令則

其中

Table 8 Comparison of Sum Estimation on Shuffle Differential Privacy

雖然RSum_DSG方法從理論上獲得了與n無關的均方誤差MSE，但該方法的通信代價過大.通常情況下，選擇方法RSum_RM更具實用性，用戶可根據其帶寬選擇多消息模式編碼器中消息的數量m，當m=2或3時，即可取得可用性相對較好的結果.

4.4 其他統(tǒng)計問題

除了基本的計數估計和頻數估計，研究者們還關注了其他相對復雜的統(tǒng)計和查詢問題，包括不同元素計數(distinct elements counting)、范圍計數和均勻性檢驗，具體可見表7.本節(jié)對這些方法進行理論分析與總結，由于這些方法均使用了多消息模式和單洗牌器模式，不再將這2項羅列在對比的表格當中.

4.4.1 不同元素計數

4.4.2 范圍計數

給定數據的值域[d]，每個用戶擁有1個xi∈[d],該問題統(tǒng)計在范圍[j,j′]內值的計數，也就是取范圍[j,j′]對應的直方圖.令Y=hist(X)表示用戶數據的直方圖統(tǒng)計，w∈{0,1}d為該范圍的編碼表示，其中1≤j≤j′≤d，wj=wj+1=…=wj′=1，其余項為0，則范圍計數的結果可以用[w,Y]表示，[·,·]表示點積.

Ghazi等人在文獻[64]通過矩陣機制[67-68]將該范圍計數問題歸約為頻數估計問題.根據矩陣機制，對于給定的數據集X，可基于可逆矩陣M∈{0,1}d×d，構造噪聲擾動的直方圖Y+ΔM-1ψ，Δ表示敏感度，即M中列的最大1范數，z表示隨機的噪聲向量.擾動后范圍計數的結果[w,Y+ΔM-1ψ]等同于[wM-1,MY+Δψ]，令表示正常的頻數估計方法擾動后的結果，由此范圍計數可通過頻數估計問題得到.基于該歸約，用戶可根據其擁有的數據xi，選擇矩陣M中第xi列非0項對應的索引值j∈[d]作為其編碼，并調用之前任一頻數估計方法分別對每一個值進行擾動并輸出；分析器收到混洗后的用戶數據，首先估計頻數之后通過即可返回范圍計數的結果.

Fig. 6 Range query tree(d=4)

Table 9 Summary of Other Statistic Estimation on Shuffle Differential Privacy

4.4.3 均勻性檢驗

均勻性檢驗是指對于1個在值域[d]上的未知分布，檢驗該分布是否是均勻分布.下述用于均勻性檢驗的2個方法，均滿足具有魯棒性的差分隱私.

AUT[48]實現了具有魯棒性的近似差分隱私.該方法的編碼和擾動過程與PUT方法相似，將應用于編碼后每一位的Cnt_SGM方法替換為Cnt_BN方法即可.與其他問題不同的是，在表9中，這2個方法的誤差用樣本復雜度來度量.

5 實驗評估

基于ESA的隱私保護方法對比中，計數估計、求和估計和頻數估計作為重點的基礎問題，存在著若干種隱私保護方法.本節(jié)將這些方法進行了實現，并對其中的重要參數進行實驗評估，對于本節(jié)未提及的參數，使用該方法在獲得最優(yōu)邊界時的參數設定.該實驗一方面評估部分參數對分析結果的影響，另一方面使同一問題下不同方法的對比更加直觀.

本節(jié)的實驗環(huán)境為Ubuntu系統(tǒng)，2個6核1.70 GHz的Intel?Xeon?CPU，94 GB內存.本節(jié)所使用的數據集為不同分布的人工合成數據集，此類數據集易于調整參數，以便觀察不同分布數據集對不同方法結果的影響.該實驗的參數設置中，所有實驗都給定同一個εc，滿足近似差分隱私的方法給定δ=10-6，使它們盡可能在同一隱私保護程度下進行對比.

5.1 計數估計實驗評估

該節(jié)通過人工生成n項滿足伯努利分布Ber(q)的{0,1}數據作為數據集，并假設每個用戶擁有其中1個數值，對計數估計問題中的Cnt_RR，Cnt_2M，Cnt_SGM，Cnt_BN方法進行實驗評估.此處沒有對Cnt_PURE進行評估，主要原因是根據其理論，該方法僅對n較大且ε較小的情況下適用，很難與其他方法放在同一標尺下度量.如當n=107時，εc需小于0.1，該方法對數據擾動的概率λ才能處于其正確的區(qū)間[0,1]，更具體地，εc=0.01時，λ=0.82；而通常其他方法的εc取小數點后第1位即可.

給定參數n=106，εc=0.9，q=0.5，上述方法的對比結果如圖7(a)所示.在該部分，本節(jié)實現了隨機響應方法[51]和Laplace方法[46]作為本地化差分隱私(LDP)方法和中心化差分隱私(CDP)方法的實現與這些方法進行對比.結果顯示，所有混洗差分隱私方法的RMSE都介于LDP與CDP方法之間，且計算代價和通信代價均高于這2種方法.不同混洗差分隱私方法中，Cnt_SGM有著最小的估計誤差；而Cnt_2M由于使用了多消息模式編碼，并為了保證計數為0時結果永遠為0，對估計結果使用了較為暴力的截斷，有著比其他方法明顯較高的估計誤差和通信代價，以及較低的計算代價.

Fig. 7 Comparison of methods for different estimation issues

在圖8～10中，分別評估不同εc，n和q對不同計數估計方法的影響.

1) 隨著εc的增大，即隱私要求的降低，這些計數估計方法的誤差都有明顯減低，但計算代價和通信代價并無明顯變化.

2) 隨著n的增大，LDP方法誤差增大，但混洗差分隱私方法的誤差卻幾乎維持不動，進一步證明了在n較大的情況下混洗差分隱私方法的優(yōu)越性.在計算代價和通信代價上，這些方法都隨著n的增大而指數級上升.特別地，在對n值變化的實驗對比中，Cnt_SGM方法一直維持著最小的估計誤差；Cnt_2M方法不僅計算代價小，其計算代價增長的速度也比其他混洗差分隱私方法緩慢.

3) 隨著q值的增加，數據集中1的數量變多，大多數混洗差分隱私方法的RMSE、計算代價和通信代價并無明顯變化，Cnt_2M方法由于在用戶端輸出了更多擾動結果{1,1}，因此有著明顯增加的通信代價.

Fig. 8 Impact on counting estimation methods by varying εc

Fig. 9 Impact on counting estimation methods by varying n

Fig. 10 Impact on counting estimation methods by varying q

5.2 頻數估計實驗評估

該節(jié)通過人工生成在給定值域[d]內滿足正態(tài)分布的數據作為數據集，并假設每個用戶擁有其中1個數值，對頻數估計問題中的Hist_KR，Hist_MM，SLH，MURS進行評估，MURS方法實現時假設其添加假數據的數量為用戶數量的1%.而PRHR由于計算代價和通信代價過大，不對其進行實驗評估；PUCM適用于用戶數量小于數據值域d的情況，亦難以與其他方法一同進行實驗比較.具體地，在圖7(b)所給定的參數下對PRHR方法進行評估，僅對30%用戶數據進行編碼就需要花費5 h并占用22 GB內存.對于同樣計算代價較大的SLH和MURS方法，本節(jié)實現時通過預計算散列值與原值對應的索引表，并將該表保存，通過足夠大的存儲空間來換取實驗結果中該方法較小的計算代價.由于現實世界中數據的存儲相對廉價，該技巧對這2個方法的實際應用也是可行的.

圖7(b)中對比的LDP方法是k值隨機響應機制[27]，CDP方法是Laplace機制[46].在該圖中，誤差RMSE的縱軸坐標指數變化，Hist_KR方法有著最小的估計誤差，與CDP方法近似.該結果產生的原因是，限于計算代價和通信代價，本實驗選取了較小的值域對這些方法進行對比，而SLH，MURS方法主要針對值域較大的情況進行優(yōu)化，當值域接近或大于用戶數量時，這些方法才能體現出明顯優(yōu)勢.從計算代價和通信代價上看，基于Cnt_2M方法實現的Hist_MM方法在這2方面均與其他方法有明顯不同，并與Cnt_2M方法的實驗結果相一致.

在圖11～13中，分別評估不同εc，d和n對不同頻數估計方法的影響.

Fig. 11 Impact on frequency estimation methods by varying εc

1) 結果顯示隨著εc的增大，頻數估計的誤差和計算代價都有明顯降低，通信代價幾乎無變化，這與前面的理論分析是一致的.

2) 隨著值域[d]的增大，Hist_KR方法的估計誤差隨之增大，與LDP方法變化的趨勢一致；MURS方法的計算代價逐步增大，但其他混洗差分隱私方法并無明顯變化，與4.2節(jié)的理論分析一致.

3) 隨著用戶數量n的增大，大多數方法在各個方面并沒有顯現出明顯的變化，僅MURS方法的計算代價增加明顯，這主要是混洗器添加假數據所造成的.而該實驗設置中n僅從104變化到106，主要原因是除Hist_KR方法外，其他方法在本機模擬構建的總體計算代價過大(實驗圖僅展示分析器的計算代價)，難以進行評估.需說明的是，總體計算代價大并不代表實際中該方法難以應用，主要原因是實際應用時每個用戶分別對自己的數據進行擾動，n個編碼器是完全并行的；而本節(jié)進行實驗模擬時這n個編碼器串行或部分并行地計算，大多數消息模式方法的編碼過程都長達數小時.

Fig. 12 Impact on frequency estimation methods by varying d

Fig. 13 Impact on frequency estimation methods by varying n

5.3 求和估計實驗評估

該節(jié)通過人工生成滿足正態(tài)分布的[0,1]數據作為數據集，并假設每個用戶擁有其中1個數值，對求和估計問題中的RSum_RR，RSum_KR，RSum_RM，RSum_DSG進行評估.由于RSum_PURE方法基于Cnt_PURE方法實現，基于5.1節(jié)的分析，不對其進行實驗評估.

圖7(c)中，用作對比的LDP方法是Harmony機制[70]，CDP方法是Laplace機制[46].該實驗中，將RSum_RM方法中多消息模式的消息數量設為3，其他方法隨機舍入的精度設為10.結果顯示，RSum_RM方法有著接近小的估計誤差和明顯較小的計算代價，RSum_DSG雖計算代價和通信代價較大，但估計誤差在所有混洗差分隱私方法中最低，與4.3節(jié)的理論分析一致.

在圖14，15中，分別評估不同εc和n對不同求和估計方法的影響.

1) 結果顯示，隨著εc的增大，求和估計的誤差有明顯降低，但計算代價和通信代價并無明顯變化.

Fig. 14 Impact on sum estimation methods by varying εc

Fig. 15 Impact on sum estimation methods by varying n

5.4 實驗小結

從實驗分析的總體上看，混洗差分隱私方法在各統(tǒng)計問題的結果可用性上都有著相比本地化差分隱私方法明顯更優(yōu)的結果.但從通信代價和計算代價的角度分析，ESA框架中混洗器的引入，一方面使得用戶數據與用戶所使用的編碼器之間的關聯性消失，使得分析器端的計算代價增大；另一方面促使研究者們使用富含信息更多的多消息模式對數據編碼，造成了分析器端的通信代價增大.如何兼顧數據的隱私性、可用性、方法的計算代價和通信代價是后續(xù)基于ESA框架構建的隱私保護方法需加以考量的部分.

從各混洗差分隱私方法評估的結果看，隨著εc的增大，各方法的數據可用性均會得到提高；而隨著用戶數據n的增加，基于本地化差分隱私方法設計的混洗差分隱私方法在計算誤差上會有輕微的增加，其他大多數混洗差分隱私方法在計算誤差上沒有明顯變化，甚至部分方法有著輕微的降低.總體上，基于多消息模式設計的混洗差分隱私協議由于攜帶了更多與用戶數據相關的信息，有著相對較高的數據可用性，與第4節(jié)的理論分析相一致.

6 挑戰(zhàn)問題

當前對ESA框架的研究，以混洗差分隱私方法為主，而該方法主要聚焦于理想假設下的理論研究，重點側重在2個方面：一方面是對該機制本身的隱私放大等理論的研究；另一方面致力于統(tǒng)計問題的估計，以謀求比LDP方法更高的可用性，比CDP方法更好的隱私性.但ESA框架在實際應用上，仍存在著諸多挑戰(zhàn)，這些挑戰(zhàn)問題一部分是ESA框架與生俱來的，另一部分是差分隱私方法的應用所帶來的.由此，本節(jié)提出，在ESA框架下探索非差分隱私的隱私保護方法以應對更多更為復雜的隱私問題，是ESA框架未來發(fā)展的主要挑戰(zhàn)與趨勢.

6.1 ESA的有效性

如實驗部分所示，ESA框架中混洗器的引入，打破數據之間的關聯性，有效增加了數據的隱私性和可用性，但相比同類方法，分析器端存在著明顯增加的計算代價和通信代價.同時由于混洗器本身通?；贛ixNet等密碼學網絡構建，對加密數據的安全混洗操作本身就有著昂貴的計算與通信開銷.帶寬受限、算力受限、需要處理實時任務，這些都是ESA框架應用受阻的重要因素.如何基于該框架設計兼顧隱私度、準確度、計算代價和通信代價的隱私保護方法是ESA框架的挑戰(zhàn)之一.

對于基于ESA框架實現的混洗差分隱私，為提高結果的準確性，設計方法通常會引入如散列簇、多消息模式的編碼器、多混洗模式的混洗器等方法對數據進行處理，往往伴隨著計算代價或通信代價的增加.盡管保證數據隱私性和可用性是差分隱私方法的核心，算法的計算代價和通信代價亦不容忽視.

6.2 ESA的魯棒性

ESA框架中的混洗器作為ESA框架隱私保護的核心組件，存在著單點失敗的可能，極易對整個框架的平穩(wěn)運行造成影響.一旦框架中的混洗器出現問題，如被攻擊、與分析器合謀、宕機等，分析器便不能收集或收集到錯誤的用戶信息.如何增強混洗器在實際應用過程中的魯棒性，對其混洗結果的正確性進行有效驗證，亦是ESA框架的挑戰(zhàn)之一.

對于基于ESA框架實現的混洗差分隱私方法，其方法的魯棒性難以得到保證.一方面，當前方法假設參與計算的n個用戶是可信用戶，且會幾乎同時發(fā)送他們擾動后的數據給混洗器.但實際問題中，該條件很難獲得保證.基于現有的上述方案，當存在用戶端被攻擊者控制或網絡狀況差使用戶掉線時，要么混洗器需等待極其長的時間，收集滿足要求(有時是為了滿足隱私放大定理中的參數n)的足量數據；要么，分析器會得到可用性和隱私性都相對理論較差的結果.另一方面，當前的混洗器分為單混洗器模式和多混洗器模式2種，但無論哪種，任一混洗器失效都會使系統(tǒng)存在單點失敗的可能.應用現有的具有魯棒性的秘密共享機制實現混洗器[32]是一種可能的解決方案，但應如何與基于ESA模型實現的具體問題進行結合，尚待研究.

此處，仍需重復闡明一點，第4節(jié)中介紹的部分方法可實現具有魯棒性的差分隱私RSDP，但該魯棒性并非本節(jié)所探討的系統(tǒng)魯棒性.RSDP的魯棒性是僅針對隱私而言，即保證可信用戶數量大于一定閾值γ時，分析器端依舊可以獲得滿足(ε,δ)-DP，該定義不對與數據的可用性、算法(尤其是混洗器)的等待時間、混洗器本身相關的魯棒性做任何定義與約束.

6.3 ESA的復雜問題應用

當前ESA框架主要通過與差分隱私結合，用于解決簡單的統(tǒng)計問題，但ESA框架本身應支持解決更復雜的問題，并不局限于此.具體而言，該復雜問題應包含2類：

一類是ESA與差分隱私結合可能解決，但尚未解決的復雜問題.如值域未知情形下的混洗差分隱私、高維度數據上的混洗差分隱私、復雜數據類型上的混洗差分隱私等.在實際應用中，這樣復雜的應用場景隨處可見，如當需要對用戶瀏覽的網頁進行統(tǒng)計時，由于網頁的數量在不斷增長，很難對當前作為候選集的網頁進行枚舉，需可處理值域未知的混洗差分隱私方法；又如，將混洗差分隱私應用在機器學習上，往往涉及到成千上萬個維度的數據，需有效的隱私保護方法對其進行處理；再如，生活中常見的相對復雜的鍵值對類型數據，如果對鍵與值分別擾動，鍵與值之間的關聯性很可能被混洗器打斷，難以獲得有效的估計結果.這些問題通過應用散列函數映射[52]、數據降維[71]等可能會被解決，但如何應用仍是挑戰(zhàn).

另一類是ESA可能解決，但差分隱私不能解決的問題，需要基于該框架對非差分隱私的方法進行探索.具體而言，差分隱私本質上可用于回答“有多少”的問題，而不是回答“是什么”的問題，對一個點是不是異常點、一個人是不是新冠肺炎的感染者這樣的問題，應用差分隱私將這些數據進行擾動并不能得到可用的答案，差分隱私更趨向于將這樣出現頻數極低的點抹平，使其不在結果中凸顯以保護隱私[72-73].但ESA框架為這樣問題的回答創(chuàng)造了可能性，即ESA框架可在對數據進行盡可能少的擾動情況下保護隱私，便為異常點檢測、新冠肺炎發(fā)現這樣的問題提供條件.由此，發(fā)展非差分隱私的ESA方法十分關鍵!

6.4 ESA與聯邦學習

聯邦學習算法近2年在工業(yè)界和學術界迅速發(fā)展，該模型一定程度上打破數據孤島，解決了隱私問題[74].該模型的基本思想是基于用戶或企業(yè)獨立的數據在本地進行模型的訓練與更新，將模型的參數(如梯度)在服務器端進行安全聚合，從而訓練一個中心化的模型提供服務器.雖然聯邦學習不直接傳遞用戶數據，僅與服務器共享模型參數，但該參數往往包含著一定程度的用戶隱私，易遭受成員推理攻擊[75-76]，需使用高可用性的隱私保護方法進行保護.

ESA框架與聯邦學習均適用于用戶在本地端進行數據處理，對處理后數據進行收集的場景，ESA框架本身的特性與聯邦學習的需求不謀而合.ESA與聯邦學習最簡單的結合，即使用第4節(jié)所述的混洗差分隱私方法對用戶共享的梯度進行保護，但該方法如何適用于參數維度巨大的機器學習模型的訓練仍是難點[77-78].同時，混洗差分隱私雖相比本地化差分隱私方法引入了較小噪聲，但在數據量較小、隱私損失較小的情況下仍對數據可用性有著不小的威脅.基于ESA框架發(fā)展與聯邦學習高度適配的隱私保護方法應該是該方向的主要挑戰(zhàn).

7 結束語

數據驅動的人工智能時代，數據隱私問題備受關注，但數據可用性亦是社會與科技發(fā)展的重中之重.ESA框架為提出數據可用性更好、隱私性亦更好的隱私保護方法開辟了新的路徑，混洗差分隱私即為該框架下的典型方法.混洗差分隱私方法兼具了本地化差分隱私在數據收集場景中的易用性和中心化差分隱私在數據分析結果上的可用性，在多種統(tǒng)計問題上的表現卓越.本文對ESA框架及其應用——混洗差分隱私方法進行了詳細的綜述，對混洗差分隱私下的研究方向進行總結，針對不同統(tǒng)計問題的若干算法進行理論分析與實驗對比.基于上述總結分析的結果，本文提出了當前ESA框架應用面臨的主要挑戰(zhàn)，并以混洗差分隱私為例對這些挑戰(zhàn)進行詳細的說明.本文提出，混洗差分隱私是ESA框架應用的有效途徑，但不是唯一途徑，存在著諸多具有現實意義的復雜問題混洗差分隱私難以解決，但ESA為這些問題的解決創(chuàng)造了條件.基于ESA框架探索適用性更廣的、可用性更高的、非差分隱私的隱私保護算法是數據隱私保護未來可能的發(fā)展方向之一.

作者貢獻聲明：王雷霞負責論文總結、撰寫與實驗；孟小峰指導總體架構.