王雷霞 孟小峰

(中國(guó)人民大學(xué)信息學(xué)院 北京 100872)

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

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

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

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

Fig. 1 Comparison of different methods’ results

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

本文對(duì)該新型的隱私保護(hù)框架進(jìn)行綜述，主要貢獻(xiàn)有4個(gè)方面：

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

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

3) 本文通過(guò)實(shí)驗(yàn)對(duì)混洗差分隱私下不同統(tǒng)計(jì)問(wèn)題的隱私保護(hù)機(jī)制進(jìn)行對(duì)比.當(dāng)前絕大多數(shù)工作都是理論研究，本文通過(guò)實(shí)驗(yàn)對(duì)比，可以更直觀地說(shuō)明不同理論機(jī)制在實(shí)際應(yīng)用時(shí)的效用和效率差異.

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

1 ESA隱私保護(hù)框架

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

1.1 ESA框架定義

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

Fig. 2 ESA framework

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

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

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

編碼器的具體實(shí)現(xiàn)，可通過(guò)數(shù)據(jù)泛化、數(shù)據(jù)分割、加密、添加差分隱私噪聲的方式實(shí)現(xiàn)，以達(dá)到消除或減少數(shù)據(jù)所蘊(yùn)含的隱私信息的目的[18].

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

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

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

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

本文綜述的重點(diǎn)在于如何設(shè)計(jì)編碼器和分析器，選擇恰當(dāng)?shù)幕煜茨Ｊ絹?lái)進(jìn)行滿足一定隱私保證的統(tǒng)計(jì)計(jì)算.本文將混洗器作為黑盒來(lái)使用，假設(shè)其可以完成安全的混洗操作，主要原因是安全混洗協(xié)議已經(jīng)發(fā)展成熟，在諸多安全相關(guān)的文獻(xiàn)中已有過(guò)總結(jié)和論述[18-24]；同時(shí)安全混洗協(xié)議的不同實(shí)現(xiàn)并不會(huì)對(duì)該框架下隱私保護(hù)方法的隱私性和可用性造成明顯影響.

1.2 ESA隱私分析

1.3 應(yīng)用實(shí)例：混洗差分隱私方法

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

Fig. 3 Comparison of differential privacy methods under different frameworks

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

1.3.1 與中心化、本地化差分隱私對(duì)比

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

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

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

1.3.2 與基于加密的差分隱私對(duì)比

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

Fig. 4 Cryptographic differential privacy framework

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

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

2 基于ESA的隱私保護(hù)基礎(chǔ)理論

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

2.1 差分隱私

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

(1)

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

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

(2)

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

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

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

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

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

序列組合性說(shuō)明隱私預(yù)算ε可以在算法設(shè)計(jì)的不同步驟進(jìn)行分配；并行組合性則定義了算法在不相交數(shù)據(jù)集上的隱私保證；后處理性則強(qiáng)調(diào)，在滿足ε-DP的數(shù)據(jù)結(jié)果上進(jìn)行隨機(jī)操作，其輸出依舊滿足ε-DP.這3條性質(zhì)適用于本地化差分隱私時(shí)，數(shù)據(jù)集D相應(yīng)地定義在用戶本地的數(shù)據(jù)集上.

2.2 混洗差分隱私

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

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

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

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

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

2.3 隱私放大理論

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

2.3.1 通用隱私放大定理

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

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

Fig. 5 Interactive mechanism and non-interactive mechanism

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

(3)

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

(4)

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

Table 1 Results of Privacy Amplification on General Interactive Mechanism

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

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

2.3.2 基于隨機(jī)響應(yīng)的隱私放大定理

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

(5)

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

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

(6)

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

(7)

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

(8)

(9)

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

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

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的隱私保護(hù)基礎(chǔ)技術(shù)

本節(jié)以混洗差分隱私作為ESA實(shí)現(xiàn)的主要方案，對(duì)該方案構(gòu)建的基礎(chǔ)技術(shù)進(jìn)行總結(jié)與介紹，為后文不同隱私保護(hù)方法的對(duì)比分析奠定基礎(chǔ).

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

3.1 差分隱私技術(shù)

差分隱私技術(shù)根據(jù)不同的使用場(chǎng)景，可分為中心化差分隱私、分布式差分隱私和本地化差分隱私3種，均可通過(guò)與ESA框架不同的結(jié)合方式實(shí)現(xiàn)混洗差分隱私，具體技術(shù)如下.

3.1.1 中心化差分隱私技術(shù)

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

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

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

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

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

3.1.2 分布式差分隱私技術(shù)

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

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

(10)

3.1.3 本地化差分隱私技術(shù)

本地化差分隱私技術(shù)在用戶端的原始數(shù)據(jù)上添加噪聲，并保證任一用戶的發(fā)布數(shù)據(jù)均滿足差分隱私定義.該技術(shù)中最常用的是隨機(jī)響應(yīng)機(jī)制，亦可基于一般的差分隱私機(jī)制(指中心化差分隱私技術(shù))實(shí)現(xiàn)，但會(huì)產(chǎn)生較多噪聲.該技術(shù)是混洗差分隱私方法設(shè)計(jì)中最常用的基礎(chǔ)技術(shù)，它結(jié)合混洗器的隱私放大效果可達(dá)到較強(qiáng)的差分隱私保護(hù)效果.

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

3.2 基于匿名的密碼學(xué)技術(shù)

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

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

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

4 基于ESA的隱私保護(hù)方法對(duì)比

Table 5 Research Fields of Shuffle Differential Privacy

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

4.1 計(jì)數(shù)估計(jì)

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

(11)

Table 6 Comparison of Counting Estimation Methods on Shuffle Differential Privacy

4.2 頻數(shù)估計(jì)

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

Table 7 Comparison of Frequency Estimation on Shuffle Differential Privacy

為了在值域[d]較大時(shí)進(jìn)一步減少頻數(shù)估計(jì)的誤差，研究者們相繼提出了若干頻數(shù)估計(jì)方案，可實(shí)現(xiàn)與值域[d]無(wú)關(guān)的誤差邊界.

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

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

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

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

4.3 求和估計(jì)

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

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

實(shí)數(shù)求和估計(jì)結(jié)果的準(zhǔn)確性一方面依賴于隱私預(yù)算εc的分配與方法的隱私放大效果；另一方面也與隨機(jī)舍入的結(jié)果的準(zhǔn)確性有關(guān).進(jìn)一步地，RSum_RM[35]方法將用戶擁有的xi∈[0,1]隨機(jī)舍入為多個(gè)更為準(zhǔn)確的值，以提高方法的可用性.

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

其中

Table 8 Comparison of Sum Estimation on Shuffle Differential Privacy

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

4.4 其他統(tǒng)計(jì)問(wèn)題

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

4.4.1 不同元素計(jì)數(shù)

4.4.2 范圍計(jì)數(shù)

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

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

Fig. 6 Range query tree(d=4)

Table 9 Summary of Other Statistic Estimation on Shuffle Differential Privacy

4.4.3 均勻性檢驗(yàn)

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

AUT[48]實(shí)現(xiàn)了具有魯棒性的近似差分隱私.該方法的編碼和擾動(dòng)過(guò)程與PUT方法相似，將應(yīng)用于編碼后每一位的Cnt_SGM方法替換為Cnt_BN方法即可.與其他問(wèn)題不同的是，在表9中，這2個(gè)方法的誤差用樣本復(fù)雜度來(lái)度量.

5 實(shí)驗(yàn)評(píng)估

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

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

5.1 計(jì)數(shù)估計(jì)實(shí)驗(yàn)評(píng)估

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

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

Fig. 7 Comparison of methods for different estimation issues

在圖8～10中，分別評(píng)估不同εc，n和q對(duì)不同計(jì)數(shù)估計(jì)方法的影響.

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

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

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

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 頻數(shù)估計(jì)實(shí)驗(yàn)評(píng)估

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

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

在圖11～13中，分別評(píng)估不同εc，d和n對(duì)不同頻數(shù)估計(jì)方法的影響.

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

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

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

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

Fig. 12 Impact on frequency estimation methods by varying d

Fig. 13 Impact on frequency estimation methods by varying n

5.3 求和估計(jì)實(shí)驗(yàn)評(píng)估

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

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

在圖14，15中，分別評(píng)估不同εc和n對(duì)不同求和估計(jì)方法的影響.

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

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

Fig. 15 Impact on sum estimation methods by varying n

5.4 實(shí)驗(yàn)小結(jié)

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

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

6 挑戰(zhàn)問(wèn)題

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

6.1 ESA的有效性

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

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

6.2 ESA的魯棒性

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

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

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

6.3 ESA的復(fù)雜問(wèn)題應(yīng)用

當(dāng)前ESA框架主要通過(guò)與差分隱私結(jié)合，用于解決簡(jiǎn)單的統(tǒng)計(jì)問(wèn)題，但ESA框架本身應(yīng)支持解決更復(fù)雜的問(wèn)題，并不局限于此.具體而言，該復(fù)雜問(wèn)題應(yīng)包含2類：

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

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

6.4 ESA與聯(lián)邦學(xué)習(xí)

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

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

7 結(jié)束語(yǔ)

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

作者貢獻(xiàn)聲明：王雷霞負(fù)責(zé)論文總結(jié)、撰寫(xiě)與實(shí)驗(yàn)；孟小峰指導(dǎo)總體架構(gòu).