一種基于VCG機制的差分式隱私服務定價機制

史武超，吳振強，劉 海

(1.現代教學技術教育部重點實驗室，陜西 西安 710062； 2.陜西師范大學 計算機科學學院，陜西 西安 710062)

一種基于VCG機制的差分式隱私服務定價機制

史武超1,2，吳振強1,2，劉 海1,2

(1.現代教學技術教育部重點實驗室，陜西 西安 710062； 2.陜西師范大學 計算機科學學院，陜西 西安 710062)

大數據環境下，數據具有種類多、數量大、增長速度快及價值密度低等特點，若對所有的隱私數據都提供相同程度的保護必然會造成計算資源的浪費，因此必須對隱私數據施行分級保護。差分隱私是具有嚴格數學定義的隱私保護模型，其以概率為基礎量化了隱私保護程度，可以利用隱私預算ε對隱私保護程度劃分等級。假設存在隱私保護等級的前提下，提出了分級隱私保護服務模型，基于VCG機制與最優匹配相結合的方法，為各級隱私保護服務制定合理的價格以引導用戶理性地選擇隱私保護服務等級。運用該機制為6個等級的隱私保護服務制定了相應的價格。分析表明，該服務模型中的定價機制可以合理地制定每個等級之間的價格，實現了隱私數據分級保護，優化了社會資源的配置。

VCG機制；最優匹配；差分隱私；服務分級

1 概 述

過去幾十年中，互聯網技術取得了飛速發展，徹底改變了人們的生產生活方式，例如人們可以通過互聯網進行辦公、交流、在線娛樂等。然而，當人們在享受網上沖浪樂趣的同時，也在承受著個人隱私數據被泄露的風險。“棱鏡門”事件披露出用戶的網絡行為可以被實時監控，折射出一個令人深思的隱私保護問題。

大數據時代，用戶的信息安全問題更為突出。如用戶的個人信息在商業貿易中有很高的潛在價值，通過分析這些信息，進行數據挖掘，可以預測用戶的偏好，為用戶提供個性化服務，增加商業利潤。由于受到巨大的經濟利益的驅使，一些不法分子會收集并利用這些個人信息，嚴重威脅用戶的信息安全。然而大數據環境下，數據不僅量大而且種類繁多，無法對用戶的所有信息進行保護，而且過度保護也會抑制網絡應用的創新，降低互聯網為用戶帶來的福利。因此可以根據數據的重要程度對用戶的隱私信息分級，以應對不同的應用場景。例如在用戶的各類身份信息中，身份鑒別信息的保護程度最高，通信錄信息次之，用戶基本資料第三，虛擬身份信息的保護程度最低。考慮到個體對隱私保護的差異性需求、保護過程中的計算與存儲開銷等，根據網絡安全技術的發展經驗，未來的隱私保護必定會根據隱私保護程度進行分級，較為敏感信息的隱私保護程度較高，而一般隱私信息的保護程度就可以略低一些。分級保護可以避免“一刀切”帶來的失衡，為用戶提供更加合理的隱私保護服務。隱私分級還有一個好處就是，當出現新的隱私保護技術時，分級模型可以作為評判該技術的隱私保護程度高低的基準，也可以比較各種隱私保護技術的優劣。

現有的隱私保護技術分為加密、匿名和失真等，其保護程度是密碼學方法最高，匿名方法次之，失真方法最低。基于加密的隱私保護技術是對原始數據進行加密以實現隱私保護，其隱私保護程度基于所采取的加密算法的安全性，由于無法對加密方法分級，所以加密方法無法對隱私保護水平分級。匿名技術主要包括k-anonymity及其改進方案[1-3]，然而當攻擊者掌握了一定的背景知識，可以找到對應的攻擊方法，而且匿名技術沒有嚴格的數學證明過程，無法衡量其隱私保護程度，因此現階段也無法用匿名方法對隱私保護程度分級。差分隱私保護[4]是Dwork提出的一種完全獨立于攻擊者掌握的背景知識，是基于失真的隱私保護模型，它較好地解決了傳統隱私保護方法中缺乏嚴格數學模型的不足之處。該模型假設攻擊者在除去某條要保護的記錄之外，知道其他所有記錄信息的條件下，該記錄的隱私信息仍可被保護；此外，該模型用嚴謹的數學定義量化了隱私保護程度，因此對隱私分級保護提供了可能性。

目前差分隱私保護的研究熱點主要集中在隱私數據發布、隱私數據挖掘和基于差分隱私的框架系統等。隱私保護數據發布的問題是在滿足差分隱私的基礎上如何使得發布的數據或查詢結果盡可能精確，分為交互式和非交互式兩種。交互式方式主要是直方圖發布方法[5-7]，由原始數據集產生加噪后的直方圖，根據直方圖響應用戶的查詢請求。非交互式方式主要有三種：批量查詢發布[8]是一次性發布所有可能出現的查詢結果；分組發布[9]方法是對原始數據集進行泛化處理之后再發布；凈化數據集發布[10]方法是對原始數據集加入噪音后產生凈化數據集后發布。隱私保護數據挖掘主要有接口模式和完全訪問模式。接口模式下的隱私保護數據挖掘方法主要有分類和聚類，典型算法有DiffP-C4.5[11]、K-means[12]等；完全訪問模式下的隱私保護挖掘算法主要有回歸和頻繁項集挖掘方法，典型算法有Learning guarantees[13]、Diff-FPM[14]等。基于差分隱私的框架系統有微軟的交互式數據分析系統PINQ[15]，美國伯克利大學的非交互式數據分析系統GUPT[16]，德克薩斯大學的基于MapReduce聚集分析系統Airavat[17]以及新加坡ADSC研究所的Pioneer系統[18]。

差分隱私保護的研究主要集中在隱私數據的發布與隱私數據挖掘上，對隱私分級方面的研究還比較欠缺。若在沒有任何約束的情況下，用戶普遍偏向選擇等級較高的隱私保護服務，導致非重要信息采取相對較高的隱私保護就是對資源的浪費，同時過度保護也不利于互聯網的發展。

如果把隱私保護服務看成一種特殊的商品，通過價格調節機制引導用戶理性地選擇有差別的隱私保護服務。為此，在隱私保護等級已存在的假設前提下，提出了分級的隱私保護服務模型。該模型能夠保證服務商向用戶提供不同等級的隱私保護服務，用戶按需購買服務。結合經濟學中VCG拍賣機制與最優匹配原理，按照最優匹配原理使所有競拍者的隱私估值之和最大的條件為競拍者分配隱私保護服務等級，進而得到不同等級服務的VCG價格。當用戶請求某個等級的服務并付款后，就會獲得服務商提供的相應等級的隱私保護服務。

2 研究基礎

2.1 隱私保護國際標準

ISO/IEC JTC1是專門研究信息安全領域標準的國際化委員會，下設有專門負責隱私保護相關標準制定的WG5工作組，近年來已經制定了許多相關方面的標準。其中ISO/IEC 29100[19]《信息技術 安全技術 隱私框架》規定了一些通用的隱私術語、隱私防護要求等，是隱私保護方面的一般性標準，因此該標準為其他隱私保護標準提供了基礎。ISO/IEC 29190[20]《信息技術 安全技術 隱私能力評估模型》提供了一個如何評估其管理和歸檔隱私相關輸出的能力成熟度的高層次指南，標準中規定了隱私保護能力評估級別集合，對隱私能力進行評估的關鍵功能領域，還提供了如何將評估級別映射到企業隱私模型的操作指南。該標準將隱私保護程度分為六個評估級別：不完全過程、執行過程、管理過程、建立過程、預測過程和創新過程，為其他組織或機構提供了借鑒。并且提供了一個評估級別到企業隱私評估級別的定量映射，包括：基本沒有實現(0～15%)、部分實現(15%～50%)、大部分實現(50%～85%)、基本完全實現(85%～100%)。這些標準為差分隱私保護分級工作提供了規范，具有一定的指導意義。

2.2 差分隱私保護

差分隱私保護是基于數據失真的隱私保護模型。在兩個相鄰數據集D和D'(相鄰數據集指的是數據庫D和D'中只相差一條記錄，其他記錄都相同)中，對數據集D所做的任何查詢操作f(D)與數據集D'中所做的同樣操作f(D')得到的結果差別很小，也就是說這條記錄是否存在數據集中，對相同查詢的結果基本沒有影響。此外，差分隱私完全獨立于攻擊者所掌握的背景知識，即使攻擊者知道除某一條記錄外的所有記錄信息，攻擊者也無法獲取該條記錄的敏感信息。差分隱私保護定義如下：

給定兩個相鄰數據集D和D'，一個隱私保護算法A，Range(A)為A的取值范圍。若算法A在數據集D和D'上任意輸出結果為O(O∈Range(A))，滿足式(1)：

Pr[A(D)=O]≤eε×Pr[A(D')=O]

(1)

則稱算法A滿足ε-差分隱私。其中，ε稱為隱私保護預算，ε越小隱私保護程度越高，ε越大隱私保護程度越低。差分隱私的定義為劃分隱私保護服務等級提供了理論基礎[21]。

2.3 VCG拍賣機制

VCG[22](Vickrey-Clarke-Groves)機制是針對網絡空間無法對數字產品或服務進行價格估值的情況下，以Vickrey提出的單品次價拍賣為基礎，由Clarke和Groves推廣到更一般的多品次價拍賣機制。競拍者首先提交對于每件拍品的報價，由拍賣系統以社會最優的方式給每個競拍者分配拍品，競拍者得到某件拍品支付的費用由其獲得這件拍品對其他競拍者造成的損失來表示，也就是說，每個競拍者支付的價格等于該競拍者不出現時，其他競拍者得到的價值總和提高的那部分。

VCG機制有兩個特點：一是該機制能激勵競拍者按照其對拍品的真實估值出價；二是該機制可以達到社會最優分配。

3 隱私服務等級定價機制設計

定義1：設Li(1≤i≤k)為已劃分好的k個隱私保護服務等級，其中L1為最低級別，Lk為最高級別，隱私保護的等級集合為{L={L1,L2,…,Lk}}。vi(1≤i≤k)為隱私保護強度，即每個隱私保護服務等級對應的隱私保護水平，v1

定義2：設矩陣Vij=vi×bj(1≤i≤k,1≤j≤k)是出價為bj的競拍者對于隱私保護強度為vi對應的隱私服務等級的隱私估值。

定義5：設有二部圖(x,y)，對于y中任意一組節點集合U，與這組集合中所有節點有邊相連的x節點集合N(U)，若|U|>|N(U)|，則U為一組受限組。

定義6：設能為買家用戶提供最大化回報的一個或多個隱私保護服務商為偏好賣家，則在每個買家和其偏好賣家之間連線形成的圖為一個偏好賣家圖，用符號GP表示。

隱私保護服務作為一種特殊商品，由隱私保護服務商提供，用戶只需選擇想要達到的隱私保護等級，然后服務商根據用戶的選擇為其提供對應的服務。服務商的工作可以分為兩部分：一是定價過程，即為每個等級的隱私保護服務制定價格；二是當用戶選擇某個等級的服務時，為用戶提供相應的隱私保護服務。該隱私保護分級服務模型如圖1所示。

圖1 隱私保護分級服務模型

3.1 構建最優匹配

(1)for(i=1;i<=k;i++)

(2){pi=0} //初始化隱私保護服務等級的初始價格

(3)for(i=1;i<=k;i++)

(4){for(j=1;j<=k;j++)

(5){Vij=vi×bj;}} //計算每個人對于每個隱私保護等級的隱私估值

(6)構造偏好賣家圖GP;

(7)if(存在完美匹配)

(8){匹配過程結束;}

(9)else

(10){與受限賣家關聯的商品價格pi+1;

(11)回到步驟(6);}

3.2 計算每個服務等級的VCG價格

3.3 用戶合理選擇隱私保護服務

定價機制完成后，就得出每個隱私保護服務等級的價格。用戶根據自己的需求和每個等級的價格，選擇一個等級的服務。服務商接收到用戶的請求后，根據該等級對應的隱私保護預算ε的區間選擇一個值，應用拉普拉斯機制或者指數機制添加噪音，然后將結果返回給用戶。

4 機制分析

定價機制可以使得每個用戶都按照自己對隱私保護服務等級的真實需求出價，同時使得所有人的隱私估值最大。下面模擬一組數據說明該定價機制的執行過程并對該隱私分級服務模型作簡要分析。

圖2 定價過程

假設共有6個隱私保護等級L1,L2,…,L6，每個等級對應的隱私保護強度v1,v2,…,v6為：0.1,0.3,0.5,0.6,0.8,0.9。現有4個競拍者，出價b1,b2,…,b6依次為：50,60,70,80,90,100。首先進行一次最優匹配，這樣每個競拍者都得到了一個隱私保護服務等級，此次把L6匹配給b6，L5匹配給b5，L4匹配給b4，L3匹配給b3，L2匹配給b2，L1匹配給b1；接下來以隱私保護等級L3為例，計算出價為b4的競拍者應該為L3等級的服務支付的VCG價格。首先計算除過L3，b3這對節點，剩余匹配的估值總和，見式(2)：

∑1=100×0.9+90×0.8+80×0.6+60× 0.3+50×0.1=233

(2)

然后計算除過出價為b4的競拍者，其他人重新進行最優匹配的估值總和，見式(3)：

∑2=100×0.9+90×0.8+80×0.6+60× 0.5+50×0.3=255

(3)

最后計算出價為b3的競拍者為L3等級支付的VCG價格：

∑2-∑1=255-233=22

(4)

其他等級的VCG價格可以照此方法計算，最終得到L6的價格為54，L5的價格為50，L4的價格為29，L3的價格為22，L2的價格為10，L1的價格為0。

4.1 定價效果分析

圖3為每個隱私保護等級服務對應的價格曲線，反映了隱私保護服務等級越高則對應的價格也越高，而且呈現出階梯性價格差。第一級的隱私保護強度最低，對應于ISO/IEC 29190標準中的不完全過程級別，基本沒有實現隱私保護功能，因此定價為0；第二級實現部分隱私保護功能，因此價格較低；第三級和第四級大部分實現了隱私保護功能，因此價格適中；第五級和第六級基本完全實現了隱私保護功能，隱私價格最高。該價格符合市場一般規律，同時也合理拉開了各個等級之間的價格。

圖3 隱私保護服務等級對應的價格曲線圖

4.2 最優匹配算法有窮性分析

最優匹配算法不會無限循環，一定可以找到這組最優匹配。為了說明該匹配過程一定會結束，定義買家勢能Eb為某個競拍者可能獲得的最大回報；賣家勢能Es為某個隱私保護服務等級當前的價格；整個匹配勢能Ea為所有參與者的勢能之和，即Ea=Eb+Es。匹配開始時，所有賣家的勢能Es=0，每個買家的勢能Eb為其最大估值。由于在匹配過程中有受限組U出現，與受限組相關的集合N(U)中的商品價格提高一個單位，受限組中的每個買家的勢能Eb就下降一個單位，由于集合U的大小比集合N(U)大，因此整個匹配系統的勢能Ea-1，即下降一個單位。也就是說，每經過一輪匹配，整體的勢能Ea就會減小，但Es會變大，整體上Ea>0，即Ea的值一直減小，最后達到某個大于0的值，因此該匹配過程一定會結束。

4.3 最優匹配算法可以找到一個社會最優匹配

由于價格總和獨立于選擇哪種匹配，因此這組匹配M的回報最大，即這個匹配可以達到估值總和最大。

5 結束語

基于VCG機制與最優匹配原理，對假設已存在的隱私保護服務等級制定價格。實驗結果表明，不同隱私保護等級之間的價格被合理拉開，符合市場經濟的一般規律。然而現有的工作均是在假設差分隱私保護等級已經劃分好的情況下進行的，因此下一步工作的重點是研究差分隱私保護的分級模型和分級算法，劃分出合理實用的差分隱私保護等級。

[1] Sweeney L.K-anonymity:a model for protecting privacy[J].International Journal on Uncertainty,Fuzziness and Knowledge-based Systems,2002,10(5)：557-570.

[2] Machanavajjhala A,Kifer D,Gehrke J,et al.L-diversity:privacy beyond k-anonymity[J].ACM Transactions on Knowledge Discovery from Data,2007,1(1):1-3.

[3] Li N,Li T.t-Closeness:privacy beyond k-anonymity and l-diversity[C]//Proceedings of the 23rd international conference on data engineering.Istanbul,Turkey:[s.n.],2007：106-115.

[4] Dwork C.Differential privacy：a survey of results[C]//Proceeding of the 5th international conference on theory and applications of models of computation.Xi’an,China:[s.n.],2008:1-19.

[5] Xiao Y,Xiong L,Yuan C.Differentially private data release through multidimensional partitioning[C]//Proceedings of the 7th VLDB conference on secure data management.Singapore:[s.n.],2010：150-168.

[6] Xiao Y, Gardner J, Xiong L.DPCube:releasing differentially private data cubes for health information[C]//Proceedings of the 2012 IEEE 28th international conference on data engineering.Washington,USA:IEEE,2012:1305-1308.

[7] Xu J,Zhang Z,Xiao X,et al.Differentially private histogram publication[C]//Proceedings of the 2012 IEEE 28th international conference on data engineering.Washington,USA:IEEE,2012:32-43.

[8] Xiao X, Wang G, Gehrke J.Differential privacy via wavelet transforms[J].IEEE Transactions on Knowledge and Data Engineering,2011,23(8):1200-1214.

[9] Mohammed N,Chen R,Fung B C M,et al.Differentially private data release for data mining[C]//Proceedings of the 17th ACM SIGKDD international conference on knowledge discovery and data mining.San Diego,USA:ACM,2011:493-501.

[10] Dwork C,Rothblim G N,Vadhan S.Boosting and differential privacy[C]//Proceeding of the 2010 IEEE 51st annual symposium on foundations of computer science.Las Vegas,USA:IEEE,2010:51-60.

[11] Friedman A,Schuster A.Data mining with differential privacy[C]//Proceedings of the 16th ACM SIGKDD international conference on knowledge discovery and data mining.Washing-ton,USA:ACM,2010:493-502.

[12] Blum A,Dwork C,McSherry F,et al.Practical privacy:the SuLQ framework[C]//Proceedings of the 24th ACM SIGMOD-SIGACT-SIGART symposium on principles of database systems.Baltimore,USA:ACM,2005:128-138.

[13] Chaudhuri K,Monteleoni C.Privacy-preserving logistic regression[C]//Proceedings of the 22nd annual conference on neural information processing systems.Vancouver,Canada:[s.n.],2008:289-296.

[14] Shen E,Yu T.Mining frequent graph patterns with differential privacy[C]//Proceedings of the 19th ACM SIGKDD international conference on knowledge discovery and data mining.Chicago,USA:ACM,2013:545-553.

[15] McSherry F.Privacy integrated queries:an extensible platform for privacy-preserving data analysis[C]//Proceedings of the ACM SIGMOD international conference on management of data.Providence,Rhode Island,USA:ACM,2009:19-30.

[16] Mohan P,Thakurta A,Shi E,et al.GUPT:privacy preserving data analysis made easy[C]//Proceedings of the ACM SIGMOD international conference on management of data.Scottsdale,USA:ACM,2012:349-360.

[17] Roy I,Setty S T V,Kilzer A,et al.Airavat:security and privacy for MapReduce[C]//Proceedings of the 7th USEINIX symposium on networked systems design and implementation.San Jose,USA:USEINIX,2010:297-312.

[18] Peng S,Yang Y,Zhang Z,et al.Query optimization for differentially private data management systems[C]//Proceedings of the 29th IEEE international conference on data engineering.Brisbane,Austrial:IEEE,2013:1093-1104.

[19] ISO/IEC JTC1/SC27 N10360,Information technology-security techniques-privacy framework[S].Geneva:ISO/IEC,2011.

[20] ISO/IEC JTC1/SC27 N14300,Information technology-security techniques-privacy capability assessment model[S].Geneva:ISO/IEC,2015.

[21] 張嘯劍，孟小峰.面向數據發布和分析的差分隱私保護[J].計算機學報，2014,37(4):927-949.

[22] Nisam N,Tim R,Eva T,et al.Algorithmic game theory[M].Cambridge:Cambridge University Press,2007:216-219.

A Pricing Mechanism of Differential Privacy Service with VCG Mechanism

SHI Wu-chao1,2，WU Zhen-qiang1,2，LIU Hai1,2

(1.Key Laboratory of Modern Teaching Technology of Ministry of Education,Xi’an 710062,China; 2.School of Computer Science,Shaanxi Normal University,Xi’an 710062,China)

Data has many characteristics like various kinds,large quantity,high increment speed and low value density under the environment of big data.Meanwhile,computing resources can be wasted if all the privacy data be protected by the same kind of protection level.Therefore,privacy data must be protected in a hierarchical way.Since differential privacy is a strictly mathematical defined privacy preserve model which quantifies the level of privacy preserve based on probability theory,its parameterεcan be used to rank the levels of privacy preserve.A hierarchical privacy preserve service model has been proposed under the hypothesis that there already exists certain rank of the privacy preserve levels.The hierarchical service pricing mechanism in the model is composed of VCG mechanism and optimal matching theory,which make reasonable prices of every rank of services for users to choose reasonably.The prices for six levels of privacy preserve service have been established with this proposed mechanism.The results of analysis show that the pricing mechanism in the model proposed has widen the gap among all the six levels to fulfill the hierarchical privacy preserve service and to balance the allocation of social resources.

VCG mechanism;optimal matching;differential privacy;hierarchical service

2016-07-01

2016-11-03 網絡出版時間：2017-04-28

國家自然科學基金資助項目(61602290，61173190)；中央高校基本科研業務費(GK201501008，GK261001236)

史武超(1991-)，男，碩士研究生，研究方向為隱私保護；吳振強，教授，研究方向為隱私保護與分子通信。

http://kns.cnki.net/kcms/detail/61.1450.TP.20170428.1703.036.html

TP309.2

A

1673-629X(2017)06-0119-05

10.3969/j.issn.1673-629X.2017.06.025