隨機響應(yīng)機制效用優(yōu)化研究

周異輝，魯來鳳，吳振強,3

（1. 陜西師范大學(xué)計算機科學(xué)學(xué)院，陜西 西安 710119；2. 陜西師范大學(xué)數(shù)學(xué)與信息科學(xué)學(xué)院，陜西 西安 710119；3. 貴州大學(xué)貴州省公共大數(shù)據(jù)重點實驗室，貴州 貴陽 550025）

1 引言

在大數(shù)據(jù)時代，用戶隱私和數(shù)據(jù)安全已經(jīng)成為人們普遍關(guān)注的熱點問題。在各種隱私保護模型中，建立在嚴(yán)格數(shù)學(xué)理論基礎(chǔ)上的差分隱私模型[1]能夠量化隨機機制對用戶數(shù)據(jù)的隱私保護強度，保證統(tǒng)計數(shù)據(jù)庫的查詢結(jié)果不會受到任何單一用戶數(shù)據(jù)的影響，因此成為當(dāng)前隱私保護研究領(lǐng)域中備受關(guān)注的隱私保護模型之一。

差分隱私主要分為中心化差分隱私和本地化差分隱私，其中中心化差分隱私是數(shù)據(jù)擁有者將數(shù)據(jù)提供給數(shù)據(jù)收集者。數(shù)據(jù)發(fā)布分為交互式和非交互式2種。在交互式環(huán)境下，數(shù)據(jù)分析者向數(shù)據(jù)管理者提出查詢請求，數(shù)據(jù)管理者根據(jù)查詢請求對數(shù)據(jù)集進行操作，并將結(jié)果進行擾動后反饋給數(shù)據(jù)分析者，數(shù)據(jù)分析者不能看到數(shù)據(jù)集的全貌，從而保護數(shù)據(jù)集中的個體隱私。在非交互式環(huán)境下，數(shù)據(jù)管理者針對所有可能的查詢，在滿足差分隱私的條件下一次性發(fā)布所有查詢的結(jié)果；或者數(shù)據(jù)管理者發(fā)布一個不精確的數(shù)據(jù)集，即原始數(shù)據(jù)集的“凈化”版本，數(shù)據(jù)分析者可以對該版本的數(shù)據(jù)集自行進行所需的查詢操作。由于中心化差分隱私存在數(shù)據(jù)分析者不可信的安全隱患，因此，近年來，本地化差分隱私備受關(guān)注。在本地化差分隱私中，數(shù)據(jù)擁有者將數(shù)據(jù)進行擾動后發(fā)給數(shù)據(jù)分析者，以抵御不可信數(shù)據(jù)收集者的隱私攻擊。為保證用戶信息的隱私性，蘋果公司于2016年6月宣布使用本地化差分隱私方法收集用戶數(shù)據(jù)[2]，Google也利用本地化差分隱私技術(shù)收集用戶的行為統(tǒng)計數(shù)據(jù)[3]。隨機響應(yīng)機制是 Warner[4]于 1965年提出的，現(xiàn)為本地化差分隱私保護技術(shù)的主要擾動機制，其主要思想是利用敏感信息的不確定性來保護數(shù)據(jù)信息，因此，本文針對隨機響應(yīng)機制的效用優(yōu)化展開研究。

數(shù)據(jù)的隱私性和效用性是隱私保護技術(shù)中最重要的2個衡量指標(biāo)，如何在隱私預(yù)算確定的條件下，尋找效用最高的差分隱私保護機制是許多學(xué)者關(guān)注的問題。不同研究背景采用不用的效用測度，Comas等[5]以噪聲分布在0附近的集中程度作為評價標(biāo)準(zhǔn)；Geng等[6-8]以期望損失為效用測度，證明了階梯型分布噪聲是最優(yōu)的；Holohan等[9]使用輸入數(shù)據(jù)分布估計誤差作為效用函數(shù)，探討了在隱私強度保證的前提下二元隨機響應(yīng)機制的效用優(yōu)化問題。本文主要研究的問題是在確保隱私預(yù)算的前提下，分別針對ε-差分隱私（ε-DP）和(ε,)δ-差分隱私（(ε,)δ-DP）這2種隱私保護模型，研究二元隨機響應(yīng)機制的效用優(yōu)化問題，并將其推廣到多元隨機響應(yīng)機制。

下面舉例說明本文要研究的問題。假如某校的教務(wù)處對全校師生進行問卷調(diào)查以了解其對教務(wù)管理系統(tǒng)的滿意情況，問卷問題為“您對我校的教務(wù)管理系統(tǒng)是否滿意”。為了保護師生的隱私，師生不必如實回答問卷調(diào)查，而是采用隨機方法（比如投硬幣）以某概率如實回答問卷。本文研究的問題是在保證差分隱私的前提下，以多大的概率如實回答問卷問題才能使如實回答問題的師生比例的數(shù)學(xué)期望達到最大。本文討論的問題可抽象如下：設(shè)數(shù)據(jù)提供者的數(shù)據(jù)x來自輸入字母表，經(jīng)擾動后輸出數(shù)據(jù)為y，屬于輸出字母表，這里只討論的情形。假設(shè)利用輸入與輸出相同的記錄占總記錄比例的數(shù)學(xué)期望作為效用測度，給定隱私預(yù)算ε（和參量δ），在所有滿足ε-DP（或((ε,)δ-DP)）的機制中，尋求影響效用最優(yōu)機制和效用最優(yōu)值的相關(guān)因素，探討效用最優(yōu)機制的條件概率矩陣和最優(yōu)效用值。

2 ε-DP下二元隨機響應(yīng)機制效用優(yōu)化

2.1 ε-DP下的效用優(yōu)化模型I

設(shè)πi表示數(shù)據(jù)i(i∈{0,1})在輸入數(shù)據(jù)庫中的比例，則0≤πi≤1且π0+π1=1。對于離散數(shù)據(jù)，只有輸出與輸入相同時，數(shù)據(jù)才有價值，因此結(jié)合輸入數(shù)據(jù)庫的分布情況，本文用輸出關(guān)于輸入數(shù)據(jù)庫正確率的數(shù)學(xué)期望作為效用度量，即

優(yōu)化模型I表示為

約束條件為

2.2 模型求解

優(yōu)化模型I為線性規(guī)劃問題。由于變量只有2個，首先用圖解法求解，然后用最優(yōu)性判定定理進行證明，最后用Matlab軟件求解驗證所得結(jié)論。

2.2.1 圖解法求解

圖1為ε=0.1時優(yōu)化模型I的可行域，兩組平行直線的斜率分別為-eε和，頂點分別為和目標(biāo)函數(shù)等值線的斜率為從圖1可以看出5種情形，分別如下。

圖1 優(yōu)化模型I的可行域(ε=0.1)

故可得最優(yōu)值u*與隱私預(yù)算ε和0π的函數(shù)關(guān)系為

圖2為按照式(4)給出的優(yōu)化模型I的最優(yōu)值u*與隱私預(yù)算ε和輸入分布0π的函數(shù)關(guān)系。

圖2 優(yōu)化模型I中最優(yōu)效用值與隱私預(yù)算和輸入分布的關(guān)系

2.2.2 模型Ⅰ最優(yōu)性證明

將線性規(guī)劃問題化為標(biāo)準(zhǔn)型

約束條件為

其中，A為m×n矩陣，秩為m。若對于選定的基將式(5)所示的問題化為典則形式（簡稱典式）使

定理1最優(yōu)性判別定理[10]。在線性規(guī)劃問題的典式中，設(shè)是對應(yīng)于基B的一個基可行解，若有

下面利用定理1證明式(4)確為優(yōu)化模型I的最優(yōu)值。

證明將優(yōu)化模型 I化為標(biāo)準(zhǔn)型，其中，

根據(jù)定理1，有

1) 取A的1、2、3、4、7、8列作為基B1，將優(yōu)化模型I化為相應(yīng)的典式，得到的判別系數(shù)為

此對應(yīng)于圖解法的第1)情形。

2) 取矩陣A的1、2、4、6、7、8列作為基B2，將優(yōu)化模型I化為相應(yīng)的典式，得到的判別系數(shù)為

此對應(yīng)于圖解法的第2)情形。

3) 取矩陣A的1、2、3、5、7、8列作為基B3，將優(yōu)化模型I化為相應(yīng)的典式，得到的判別系數(shù)為

此對應(yīng)于圖解法的第3)情形。

則線段BC上的點對應(yīng)的效用值為

此對應(yīng)圖解法的第4)情形。

此對應(yīng)圖解法的第5)情形。

證畢。

2.2.3 軟件求解驗證模型I最優(yōu)解

求解線性規(guī)劃問題一般采用單純形法，有不少現(xiàn)成的數(shù)學(xué)軟件。利用Matlab中的linprog命令求解模型I，并繪制最優(yōu)值的圖形，如圖3所示，與圖2對比可以發(fā)現(xiàn)兩者是一致的。但Matlab軟件只能對給定的隱私預(yù)算和輸入分布給出相應(yīng)的最優(yōu)解，而不能給出函數(shù)關(guān)系的解析式。

2.3 模型Ⅰ數(shù)值仿真

圖4為根據(jù)不同的輸入數(shù)據(jù)分布情況按照式(4)給出的最優(yōu)機制做出的仿真實驗。比較圖2和圖4可以看出，仿真結(jié)果與最優(yōu)值基本一致。因為效用度量是數(shù)學(xué)期望值，而仿真實驗只能重復(fù)多次取平均值，所以二者不可能完全吻合。

圖3 Matlab軟件求解優(yōu)化模型I最優(yōu)值的結(jié)果

圖4 優(yōu)化模型I效用最優(yōu)值仿真結(jié)果

從式(4)和圖3及圖4可以看出，給定隱私預(yù)算ε，在滿足ε-差分隱私的所有機制中，效用最優(yōu)機制與輸入數(shù)據(jù)庫中各記錄所占的比例有關(guān)：如果記錄 0所占比例超過則效用最優(yōu)機制為即不管輸入0還是1，輸出總是0，效用最優(yōu)值為0π；反之，如果記錄0所占比例低于，則效用最優(yōu)機制為即不管輸入 0還是1，輸出總是1，效用最優(yōu)值為1-π0。以上2種情況中最優(yōu)機制均為確定機制，當(dāng)記錄0所占比例介于和之間時，效用最優(yōu)機制為即不管輸入0還是1，輸出值與輸入值相同的概率為不同的概率為效用最優(yōu)值為

3 (ε,δ)-DP下二元隨機響應(yīng)機制效用優(yōu)化

為避免隨機機制成為確定的，可以稍微放松隱私要求，采用(ε,)δ-DP模型，并比較二者的效用。

3.1 (ε,δ)-DP下的效用優(yōu)化模型II

目標(biāo)函數(shù)為

約束條件為

3.2 模型Ⅱ求解

3.2.1 圖解法解模型Ⅱ

優(yōu)化模型II可行域如圖5所示，其中，ε=0.1，δ=0.2。頂點為從3種情況進行分析，具體如下。

圖5 優(yōu)化模型II的可行域 (ε=0.1,δ=0.2)

故最優(yōu)值u*與ε、δ和0π的關(guān)系如式(15)所示，函數(shù)圖像如圖6所示。

圖6 優(yōu)化模型II中效用最優(yōu)值與隱私預(yù)算和輸入分布的關(guān)系

3.2.2 模型II最優(yōu)性證明

證明將模型II化為標(biāo)準(zhǔn)型，其中X、C、A與

1) 取A的1、2、3、4、7、8列作為基B1，將優(yōu)化模型II化為相應(yīng)的典式，得到的判別系數(shù)為

此對應(yīng)于圖解法的第1)情形。

2) 取矩陣A的1、2、3、4、5、8列作為基B2，得到的判別系數(shù)為

此對應(yīng)于圖解法的第2)種情形。

3) 取矩陣A的1、2、3、4、6、7列作為基B3，得到的判別系數(shù)為

此對應(yīng)于圖解法的第3)種情形。

證畢。

3.2.3 軟件求解驗證模型II最優(yōu)解

利用Matlab中的linprog命令求解優(yōu)化模型II，并繪制最優(yōu)值的圖形，如圖7所示，與圖6對比發(fā)現(xiàn)兩者一致。

圖7 Matlab軟件求解優(yōu)化模型II最優(yōu)值結(jié)果

3.3 模型II數(shù)值仿真

圖8為根據(jù)不同的輸入數(shù)據(jù)分布情況按照式(15)中的最優(yōu)機制做出的仿真實驗。比較圖6和圖8可以看出，仿真結(jié)果與最優(yōu)效用值一致、而且從圖 8可以看出，(ε,)δ-DP避免了ε-DP中當(dāng)0π足夠大或足夠小時，機制退化為確定機制的缺點。

圖8 優(yōu)化模型II最優(yōu)效用值仿真結(jié)果

從式(15)和圖7及圖8可以看出，給定隱私預(yù)算ε和參量δ，在滿足(ε,)δ-DP的所有機制中，效用最優(yōu)機制與輸入數(shù)據(jù)庫中各記錄所占的比例有關(guān)：如果記錄0所占比例超過則效用最優(yōu)機制為即輸入0時輸出總是0，輸入1時，輸出1的概率為δ，最優(yōu)效用值為反之，如果記錄 0所占比例低于，則最優(yōu)效用機制為即輸入 1時輸出總是1，輸入0時，輸出是0的概率為δ，效用最優(yōu)值為當(dāng)記錄 0所占比例介于和之間時，最優(yōu)效用機制為即不管輸入0還是1，輸出值與輸入值相同的概率為不同的概率效用最優(yōu)值為

對比ε-DP和(ε,)δ-DP這2種情形可以發(fā)現(xiàn)，最優(yōu)機制中(ε,)δ-DP情形的效用比ε-DP情形好，但會損失一些隱私保護程度。以第1節(jié)的例子為例，設(shè)全校師生共10 000名，ε=0.1，δ=0.15。用“0”表示對教務(wù)系統(tǒng)不滿意，“1”表示對教務(wù)系統(tǒng)滿意。假 設(shè)π0=0.2，π1=0.8。 因 為π0=0.2＜，所以效用最優(yōu)的ε-DP機制的設(shè)計矩陣為即所有人都回答“滿意”，最優(yōu)效用值為0.8。效用最優(yōu)的(ε,)δ-DP機制的設(shè)計矩陣為最優(yōu)效用值為 0.83。對其他比例的0π和1π，也可得到相應(yīng)的結(jié)論。

4 多元本地化差分隱私效用

效用優(yōu)化模型的目標(biāo)函數(shù)為

約束條件為

這里有n2個變量，n2(n-1)個差分隱私限制，n個行和為 1限制，2n個非負(fù)限制。因為，所以每一行可以保留(n-1)個變量，另一個變量用其他元素表示。比如，令這樣有n(n-1)個變量，2(1)nn-個差分隱私限制，n個小于或等于 1的限制和n(n-1)個非負(fù)限制。

首先，由于變量個數(shù)比較多，不能用圖解法求解。其次，由于最優(yōu)性判定定理只是最優(yōu)性判定的充分條件，且與基的選擇有關(guān)系，只能用于檢驗?zāi)匙宰兞咳≈凳欠駷樽顑?yōu)解。隨著元數(shù)的增加，自變量個數(shù)也越來越多，導(dǎo)致給出最優(yōu)效用值與差分隱私預(yù)算及輸入數(shù)據(jù)集分布的關(guān)系越來越難。再者，雖然各種數(shù)學(xué)軟件求解線性規(guī)劃問題很容易，但是只是針對給定的系數(shù)，而不能得到最優(yōu)值與隱私預(yù)算及數(shù)據(jù)分布間關(guān)系的解析式。

然而，線性規(guī)劃問題的最優(yōu)解在可行域的極值點處取得，因此對差分隱私可行域極值點的研究是廣大學(xué)者研究的重點[11-12]。本文采用極值點法對優(yōu)化模型I求解。

證明文獻[11]中的結(jié)論：如果n元差分隱私機制P中存在，則第j列元素全為 0，換句話說，差分隱私機制的列向量要么全部為 0，要么全部為非0。文獻[12]中的結(jié)論：n元差分隱私機制恰有一個非0列的極值點為只有一列全部為1其他元素全部為0的矩陣；恰有2個非0列的極值點，機制中非0列元素為或。根據(jù)上述結(jié)論可得，二元本地化差分隱私可行域的所有極值點為時，對應(yīng)的效用值為和。因為，所以，因此只需比較0π、的大小，具體如下。

證畢。

5 結(jié)束語

本文在大數(shù)據(jù)環(huán)境中隱私泄露嚴(yán)重、隱私保護需求日益增強的背景下，針對差分隱私中隨機響應(yīng)機制的效用優(yōu)化問題展開研究。首先研究了廣義二元隨機響應(yīng)機制的效用優(yōu)化問題，分別針對ε-DP和(ε,)δ-DP情形建立效用優(yōu)化模型并求解，得到了最優(yōu)解與隱私預(yù)算和輸入數(shù)據(jù)分布的解析式，給出了相應(yīng)的最優(yōu)機制，并通過數(shù)值仿真驗證所得結(jié)論。針對多元廣義差分隱私的效用優(yōu)化問題展開討論，用差分隱私可行域的極值點去研究最優(yōu)效用，其中多元隨機響應(yīng)機制的效用最優(yōu)值與輸入分布和隱私預(yù)算間的函數(shù)表達式有待進一步研究。