一种基于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