Conservative or Liberal? Personalized Differential Privacy
保守或自由?個(gè)性化的微分隱私

Abstract-差異隱私被廣泛接受為為聚合數(shù)據(jù)分析提供強(qiáng)有力的正式隱私保證的強(qiáng)大框架。該模型的一個(gè)限制是，所有個(gè)人都享有同等程度的隱私保護(hù)。然而，數(shù)據(jù)主體對(duì)其數(shù)據(jù)的可接受的隱私水平有不同的期望，這是很常見(jiàn)的。因此，差別隱私可能會(huì)導(dǎo)致一些用戶的隱私保護(hù)不足，而過(guò)度保護(hù)其他用戶。我們認(rèn)為，通過(guò)接受并非所有用戶都需要相同級(jí)別的隱私，通?？梢酝ㄟ^(guò)不向不想要隱私的用戶提供過(guò)多的隱私來(lái)獲得更高級(jí)別的實(shí)用價(jià)值。我們提出了一種新的隱私定義，稱為“個(gè)性化差異隱私”(P（personalized）DP)，這是一種對(duì)差異隱私的推廣，其中用戶為其數(shù)據(jù)指定了個(gè)人隱私需求。然后介紹了幾種實(shí)現(xiàn)PDP的新機(jī)制。我們的主要機(jī)制是一個(gè)通用機(jī)制，可以自動(dòng)將任何現(xiàn)有的差異私有算法轉(zhuǎn)換成滿足PDP的算法。受著名的指數(shù)機(jī)制的啟發(fā)，我們還提出了一種更直接的實(shí)現(xiàn)PDP的方法。我們通過(guò)在真實(shí)和合成數(shù)據(jù)上的大量實(shí)驗(yàn)來(lái)證明我們的框架。

INTRODUCTION

簡(jiǎn)單的介紹了差分隱私最近幾年的發(fā)展，和現(xiàn)在發(fā)展的方向，還介紹了本文和其之間的

Contributions

在本文中，我們考慮了受信任的數(shù)據(jù)分析師希望從包含許多個(gè)人用戶個(gè)人數(shù)據(jù)的數(shù)據(jù)集中發(fā)布匯總統(tǒng)計(jì)數(shù)據(jù)的設(shè)置。每個(gè)用戶都可能對(duì)其數(shù)據(jù)有不同的隱私要求，分析人員希望發(fā)布關(guān)于數(shù)據(jù)的有用的聚合信息，同時(shí)滿足貢獻(xiàn)者的個(gè)人隱私要求。為此，我們提出了一種新的隱私框架，稱為個(gè)性化差異隱私(PDP)，這是一種對(duì)差異隱私的推廣，。我們還證明了差異隱私的組合屬性可以遺傳給PDP，允許從單個(gè)PDP組件構(gòu)建復(fù)雜的隱私保護(hù)算法。

A.這可以利用非統(tǒng)一的隱私要求，以達(dá)到更好的效用，而不是通過(guò)差別的隱私。我們的第一種機(jī)制是通用的，可以很容易地將任何現(xiàn)有的差異私有算法自動(dòng)轉(zhuǎn)換為PDP算法。該機(jī)制是一個(gè)兩步過(guò)程，涉5及到在單個(gè)元組級(jí)別上的非統(tǒng)一采樣步驟，然后在采樣數(shù)據(jù)集上調(diào)用適當(dāng)?shù)牟町愃接袡C(jī)制。在采樣步驟中，根據(jù)相應(yīng)用戶的個(gè)人隱私需求計(jì)算每個(gè)元組的包含概率。我們證明，這兩步程序引入的隨機(jī)性的兩個(gè)來(lái)源結(jié)合起來(lái)，產(chǎn)生了精確的個(gè)性化保證要求。我們的第二個(gè)機(jī)制是一種更直接的實(shí)現(xiàn)PDP的方法，。在第三節(jié)中，我們介紹了新的隱私定義，然后討論了如何滿足定義，在第四節(jié)中，第五節(jié)介紹了我們的實(shí)驗(yàn)研究，第六節(jié)總結(jié)了

B. 第二節(jié)：PRELIMINARIES

主要介紹差分隱私的概念

Definition 1 (Dataset).：

Definition 2 (Neighboring datasets)：

Definition 3 (￡-Differential Privacy）：

Definition 4 (Global Sensitivity ).：

Theorem 1 (Laplace Mechanism )：

Theorem 2 (Exponential Mechanism）

[if !supportLists]C. [endif]Related Work

k-匿名的個(gè)性化隱私:要求一條數(shù)據(jù)至少和其他k-1條記錄不可分，這通常是通過(guò)泛化或抑制屬性值來(lái)實(shí)現(xiàn)的。在肖和陶的方法中，用戶通過(guò)在泛化層次中為他們的數(shù)據(jù)指定最小泛化級(jí)別來(lái)指定他們的隱私偏好。（抑制：就是用一個(gè)沒(méi)有意義的符號(hào)去代替某一個(gè)值，泛化：用不夠具體但在語(yǔ)義上一致）

后面主要說(shuō)和最近的一些論文對(duì)比，本文的陳述和技術(shù)貢獻(xiàn)優(yōu)越性，本文提供的算法：PDP的主要機(jī)制沒(méi)有這樣的限制;它可以自動(dòng)將任何不同的私有算法——無(wú)論是拉普拉斯機(jī)制的實(shí)例、指數(shù)機(jī)制，還是多個(gè)不同私有模塊的組合——轉(zhuǎn)換成滿足我們個(gè)性化隱私定義的算法，關(guān)于隱私拍賣的工作(在[2 1]中進(jìn)行了調(diào)查)，表面上與目前的工作相似。這項(xiàng)工作主要是關(guān)于如何準(zhǔn)確計(jì)算用戶群體的統(tǒng)計(jì)數(shù)據(jù)，這些用戶要求對(duì)其參與所造成的隱私損失進(jìn)行經(jīng)濟(jì)補(bǔ)償。用戶對(duì)其隱私進(jìn)行(可能是非統(tǒng)一的)評(píng)估，表示參與e- difference私有分析(作為e的函數(shù))所產(chǎn)生的隱私成本，以及如果使用其數(shù)據(jù)應(yīng)支付的賠償金額

Definition 5 (Privacy Specification)：隱私規(guī)范是將: U -+ R+從用戶映射到個(gè)人隱私好，其中較小的值表示較強(qiáng)的隱私偏好。Fleta"(0.01 , 1 .0)用來(lái)表示與用戶對(duì)應(yīng)的隱私偏好。

在實(shí)踐中，期望典型用戶選擇有意義的數(shù)字隱私設(shè)置可能是不合理的。相反，我們?cè)O(shè)想這樣一個(gè)場(chǎng)景:領(lǐng)域?qū)＜覍⑦m當(dāng)?shù)闹蹬c用戶友好的描述符關(guān)聯(lián)起來(lái)(例如，低、中、高隱私)，用戶從中進(jìn)行選擇。這是一種可能性;一般來(lái)說(shuō)，為不同的私有系統(tǒng)選擇一個(gè)合適的隱私參數(shù)是一個(gè)開放的問(wèn)題，在本文中我們沒(méi)有進(jìn)一步考慮它。全局參數(shù)e，不能被個(gè)人影響，我們的模型假設(shè)隱私規(guī)范是公共知識(shí)。在傳統(tǒng)的微分隱私這反映了情況,全球隱私設(shè)置€被假定為一個(gè)公共參數(shù)。但是，這意味著用戶的隱私參數(shù)不能表示關(guān)于其敏感值的任何信息。我們認(rèn)為這是一個(gè)合理的假設(shè)，因?yàn)殡[私規(guī)范是在用戶級(jí)別定義的，而不是在元組級(jí)別定義的。也就是說(shuō)，我們可以將隱私設(shè)置看作是擁有數(shù)據(jù)的用戶的函數(shù)，而不是數(shù)據(jù)的函數(shù)

Definition 6 (Personalized Differential Privacy (PDP))：

差分隱私定義

也就是將差分隱私里面的隱私預(yù)算換成了個(gè)人預(yù)算，從而保證個(gè)性化隱私

Theorem 3 (Differential Privacy Implies PDP)：M : V -> R，滿足￡-DP也滿足Fleta-PDP，with privacy specification = {(u,￡) u 屬于 U}.

組合定理1

組合定理2

證明過(guò)程大概就是討論著證明連個(gè)過(guò)程串行時(shí)數(shù)據(jù)集在進(jìn)行組合時(shí)候的處理，討論兩個(gè)算法有對(duì)數(shù)據(jù)集合中重復(fù)部分進(jìn)行預(yù)算時(shí)候，為兩個(gè)或多個(gè)算法隱私預(yù)算之和。若沒(méi)有重合的話那么就是其中算法算法的隱私預(yù)算

原始機(jī)制：

我們現(xiàn)在引入的樸素基線機(jī)制在技術(shù)上實(shí)現(xiàn)了PDP，但是沒(méi)有利用個(gè)性化的隱私偏來(lái)

福實(shí)用程序。在剩下的部分,我們將使用符號(hào)DP F€(D)來(lái)表示,計(jì)算輸入在數(shù)據(jù)集D上的函

數(shù)f（）并且滿足滿足傳統(tǒng)€-DP微分隱私的任何計(jì)算機(jī)制。DP F€(D)可以是用來(lái)實(shí)現(xiàn)指

機(jī)制或者laplace機(jī)制或者更復(fù)雜的組合。最簡(jiǎn)單的就是直接應(yīng)用應(yīng)用原理3，我們找到

小的個(gè)人隱私用戶預(yù)算，然后將其作為該函數(shù)的隱私預(yù)算，達(dá)到最強(qiáng)的隱私保護(hù)作用，以

下就是最小化的的隱私預(yù)算，（講真，這種做法感覺(jué)繞圈子，從每個(gè)用戶上升到了全體來(lái)闡釋什么是差分隱私，不過(guò)這樣寫，也就是說(shuō)，最小的，即這個(gè)就是最嚴(yán)格的，但這個(gè)超過(guò)了大多數(shù)人的需要，而且太強(qiáng)烈意味著要添加更多噪音，影響數(shù)據(jù)的使用）

Definition 7 (Minimum)：

最小最基本機(jī)制.png

定義和證明都很清楚，就不多做解釋了。

如果有一個(gè)數(shù)據(jù)集，里面較多的人不關(guān)注隱私，而一部分人關(guān)注隱私，一種做法就是對(duì)這個(gè)數(shù)據(jù)集進(jìn)行分類，強(qiáng)的那一部分按照最嚴(yán)格的差分隱私方法執(zhí)行

Definition 8 (Threshold)：介紹了一個(gè)新的入門的機(jī)制

，也就是人為設(shè)置一個(gè)t，然后，用戶對(duì)隱私要求在這之下的元組將會(huì)被刪除，然后證明了這個(gè)滿足差分隱私D6.

實(shí)現(xiàn)PDP通過(guò)抽樣

我們現(xiàn)在為實(shí)現(xiàn)PDP提供了一種更智能的通用機(jī)制，在許多情況下，它能夠獲得比基線更高的實(shí)用級(jí)別。在計(jì)算中引入兩個(gè)獨(dú)立的隨機(jī)性來(lái)源：1，元組級(jí)別的非均勻隨機(jī)抽樣，其中元組的包含概率取決于相應(yīng)用戶的個(gè)人隱私偏好.2：通過(guò)在抽樣輸入上調(diào)用傳統(tǒng)的差異私有機(jī)制引入了額外的均勻隨機(jī)性，其中隱私參數(shù)f依賴于t。將這兩個(gè)隨機(jī)性源組合在一起,就產(chǎn)生了每個(gè)元組所需的精確隱私量。（簡(jiǎn)單的說(shuō)，就是先按個(gè)人隱私偏好進(jìn)行隨機(jī)抽樣，然后對(duì)其進(jìn)行個(gè)性化差分隱私處理。）

image.png

image.png

R，romove隨機(jī)選擇刪除

Theorem 5. The Sample mechanism Sf satisfies

-PDP

簡(jiǎn)單的機(jī)制滿足

證明過(guò)程

備注：說(shuō)受一片論文影響隨機(jī)抽樣有隱私放大的效果，這在第二章B部分有介紹

討論：第一，可以把該機(jī)制看成黑盒子；第二：我們看到簡(jiǎn)單機(jī)制有效的引入兩種隨機(jī)機(jī)制的同時(shí)也引入了兩種誤差，t越小，抽樣步驟丟棄的更少（抽樣誤差更低），但是會(huì)造成添加更多的噪音，t最小是就變成了最小線性機(jī)制，t最大的話就會(huì)變成給每個(gè)元組都提供了差分隱私保護(hù)，也就是很簡(jiǎn)單，較為基本的隱私保護(hù)

這個(gè)可調(diào)閾值t很有用，t是用戶對(duì)自己數(shù)據(jù)集的隱私預(yù)算拼分，t很大時(shí)，提供完全E-DP機(jī)制的隱私保護(hù)，但有的人不需要，不一定達(dá)到最好的效果。通過(guò)較小的t，達(dá)到隱私預(yù)算，并且添加較小的噪音

由于抽樣造成的誤差不僅取決于隱私規(guī)范，而且還取決于數(shù)據(jù)的密度。因此，對(duì)于足夠大的數(shù)據(jù)集，設(shè)置一個(gè)較低的閾值(例如，可以極大地提高具有強(qiáng)烈隱私要求的用戶的樣本率，代價(jià)是略微增加噪音，但總誤差較低

下面有一個(gè)例子：

在總用戶為200中，開始t=1，err=150，而將t=0.2.err=50。

實(shí)際上，采用改方法可以避免一種情況，全局敏感度很高，但對(duì)于大多數(shù)元組和集合度，敏感度較低，對(duì)輸出的影響較小。

在實(shí)踐中，為任意f精確地優(yōu)化t可能不是件小事，因?yàn)楸M管DP/可能在不了解數(shù)據(jù)集的情況下被量化，但抽樣的影響確實(shí)取決于輸入數(shù)據(jù)。因此，必須小心謹(jǐn)慎，以免通過(guò)調(diào)優(yōu)過(guò)程泄露隱私。在某些情況下，一種可能的選擇是使用不再敏感(或不那么敏感)的舊數(shù)據(jù)(來(lái)自類似的分布)，在不違反隱私的情況下近似地優(yōu)化閾值。在其他情況下，可以使用較保守用戶的部分隱私預(yù)算，并從數(shù)據(jù)子集估算所需的數(shù)量。我們推遲對(duì)閾值優(yōu)化策略的深入研究，以供今后工作參考。在第五節(jié)中，我們將演示對(duì)于許多函數(shù)，設(shè)置t = max

或t =1/|u|

”的簡(jiǎn)單啟發(fā)法，通常會(huì)在真實(shí)數(shù)據(jù)和隱私問(wèn)題上給出良好的結(jié)果。

兩步機(jī)制，通過(guò)采樣步驟實(shí)現(xiàn)PDP，然后是一個(gè)標(biāo)準(zhǔn)的差異私有機(jī)制,接下來(lái)將介紹一種高效直接的機(jī)制。

image.png

理解：r在F（D）中出現(xiàn)的次數(shù)，如果沒(méi)有的話就是負(fù)數(shù)，表示需要經(jīng)過(guò)多少次改變才能達(dá)到這個(gè)要求，鄰近數(shù)據(jù)集不同，那我們就需要對(duì)不同的進(jìn)行區(qū)分，以最大化r。

通過(guò)修改指數(shù)機(jī)制的打分函數(shù)，構(gòu)成新的指數(shù)機(jī)制

Definition 10 (PE Mechanism)

image.png

image.png

image.png

image.png

表示D和D’相差幾個(gè)元組，大概據(jù)說(shuō)當(dāng)查詢函數(shù)為預(yù)定參數(shù)r是中用戶設(shè)置的最大隱私預(yù)算，帶蓋就是將打分函數(shù)換了以后，輸出到r的概率，原來(lái)是用指數(shù)機(jī)制（使其輸出o∈O 的概率正比于exp（E*q(D,r)）/2 dq，則說(shuō)M 是滿足 ?-DP 的指數(shù)機(jī)制），現(xiàn)在改了打分函數(shù)，所以我們就需要重新證明：

接下來(lái)就是三個(gè)式列：

image.png

image.png

D. [endif]EXPERIMENTAL STUDY實(shí)驗(yàn)研究

接下來(lái)，我們將PDP機(jī)制應(yīng)用于兩個(gè)常見(jiàn)的聚合函數(shù)，count和中值，以及更復(fù)雜的多元線性回歸任務(wù)。雖然count和中值是相對(duì)簡(jiǎn)單的函數(shù)，但它們是構(gòu)建更復(fù)雜算法]的重要基元。對(duì)于計(jì)數(shù)函數(shù)和中值函數(shù)，我們比較了簡(jiǎn)單機(jī)制和類似指數(shù)的PE機(jī)制。對(duì)于線性回歸，我們使用抽樣機(jī)制來(lái)轉(zhuǎn)換由Zhang.[33]引入的一種最近的線性回歸差分私有方法，生成了algo的PDP版本算法。

本實(shí)驗(yàn)要證明該算法提供可調(diào)度的隱私保證，通過(guò)原數(shù)據(jù)集（包含用戶對(duì)自己數(shù)據(jù)聚設(shè)置的隱私預(yù)算，沒(méi)有設(shè)置也可以用均值代替）和生成數(shù)據(jù)集之間均方根誤差來(lái)調(diào)節(jié)閾值t。

為了為我們的實(shí)驗(yàn)生成隱私規(guī)范，我們將用戶(記錄)隨機(jī)分為三組:保守派，代表高度關(guān)注隱私的用戶;適中，代表中等關(guān)注的用戶;自由主義者，代表那些不太關(guān)心用戶的人。保守組和中度組的用戶比例由參數(shù)fc和fM決定;自由派用戶的比例是1.0 - (fe + fM)“在我們的實(shí)驗(yàn)中使用的默認(rèn)值是fc = 0.54和fM = 0.37。保守組和中等組的用戶的隱私偏好分別從[ce, CM]和[CM, CL]區(qū)間(舍入到最接近的百分位)均勻隨機(jī)繪制

下面是實(shí)驗(yàn)當(dāng)中的一些一些參數(shù)變化范圍：

image.png

實(shí)驗(yàn)數(shù)據(jù)集大小

實(shí)驗(yàn)數(shù)據(jù)集大小

計(jì)數(shù)當(dāng)中出現(xiàn)1的次數(shù)

自由用戶隱私預(yù)算

中等用戶隱私預(yù)算

保守用戶隱私預(yù)算

中位數(shù)查詢當(dāng)中的標(biāo)準(zhǔn)差

中位數(shù)查詢當(dāng)中的均值

保守派的用戶比列

中等組的用戶比列

自由組的用戶比列

我們上面介紹了四種機(jī)制：最小數(shù)機(jī)制，入門機(jī)制，簡(jiǎn)單機(jī)制，新指數(shù)機(jī)制然后按照上面寫的用數(shù)據(jù)集進(jìn)行賦閑，里面可以說(shuō)Laplace機(jī)制和指數(shù)機(jī)制或者他們的組合機(jī)制