隨機響應機制效用優化研究

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

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

1 引言

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

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

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

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

2 ε-DP下二元隨機響應機制效用優化

2.1 ε-DP下的效用優化模型I

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

優化模型I表示為

約束條件為

2.2 模型求解

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

2.2.1 圖解法求解

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

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

故可得最優值u*與隱私預算ε和0π的函數關系為

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

圖2 優化模型I中最優效用值與隱私預算和輸入分布的關系

2.2.2 模型Ⅰ最優性證明

將線性規劃問題化為標準型

約束條件為

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

定理1最優性判別定理[10]。在線性規劃問題的典式中，設是對應于基B的一個基可行解，若有

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

證明將優化模型 I化為標準型，其中，

根據定理1，有

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

此對應于圖解法的第1)情形。

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

此對應于圖解法的第2)情形。

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

此對應于圖解法的第3)情形。

則線段BC上的點對應的效用值為

此對應圖解法的第4)情形。

此對應圖解法的第5)情形。

證畢。

2.2.3 軟件求解驗證模型I最優解

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

2.3 模型Ⅰ數值仿真

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

圖3 Matlab軟件求解優化模型I最優值的結果

圖4 優化模型I效用最優值仿真結果

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

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

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

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

目標函數為

約束條件為

3.2 模型Ⅱ求解

3.2.1 圖解法解模型Ⅱ

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

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

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

圖6 優化模型II中效用最優值與隱私預算和輸入分布的關系

3.2.2 模型II最優性證明

證明將模型II化為標準型，其中X、C、A與

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

此對應于圖解法的第1)情形。

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

此對應于圖解法的第2)種情形。

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

此對應于圖解法的第3)種情形。

證畢。

3.2.3 軟件求解驗證模型II最優解

利用Matlab中的linprog命令求解優化模型II，并繪制最優值的圖形，如圖7所示，與圖6對比發現兩者一致。

圖7 Matlab軟件求解優化模型II最優值結果

3.3 模型II數值仿真

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

圖8 優化模型II最優效用值仿真結果

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

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

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

效用優化模型的目標函數為

約束條件為

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

首先，由于變量個數比較多，不能用圖解法求解。其次，由于最優性判定定理只是最優性判定的充分條件，且與基的選擇有關系，只能用于檢驗某自變量取值是否為最優解。隨著元數的增加，自變量個數也越來越多，導致給出最優效用值與差分隱私預算及輸入數據集分布的關系越來越難。再者，雖然各種數學軟件求解線性規劃問題很容易，但是只是針對給定的系數，而不能得到最優值與隱私預算及數據分布間關系的解析式。

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

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

證畢。

5 結束語

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