一種基于VCG機(jī)制的差分式隱私服務(wù)定價(jià)機(jī)制

史武超，吳振強(qiáng)，劉 海

(1.現(xiàn)代教學(xué)技術(shù)教育部重點(diǎn)實(shí)驗(yàn)室，陜西 西安 710062； 2.陜西師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院，陜西 西安 710062)

一種基于VCG機(jī)制的差分式隱私服務(wù)定價(jià)機(jī)制

史武超1,2，吳振強(qiáng)1,2，劉 海1,2

(1.現(xiàn)代教學(xué)技術(shù)教育部重點(diǎn)實(shí)驗(yàn)室，陜西 西安 710062； 2.陜西師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院，陜西 西安 710062)

大數(shù)據(jù)環(huán)境下，數(shù)據(jù)具有種類多、數(shù)量大、增長(zhǎng)速度快及價(jià)值密度低等特點(diǎn)，若對(duì)所有的隱私數(shù)據(jù)都提供相同程度的保護(hù)必然會(huì)造成計(jì)算資源的浪費(fèi)，因此必須對(duì)隱私數(shù)據(jù)施行分級(jí)保護(hù)。差分隱私是具有嚴(yán)格數(shù)學(xué)定義的隱私保護(hù)模型，其以概率為基礎(chǔ)量化了隱私保護(hù)程度，可以利用隱私預(yù)算ε對(duì)隱私保護(hù)程度劃分等級(jí)。假設(shè)存在隱私保護(hù)等級(jí)的前提下，提出了分級(jí)隱私保護(hù)服務(wù)模型，基于VCG機(jī)制與最優(yōu)匹配相結(jié)合的方法，為各級(jí)隱私保護(hù)服務(wù)制定合理的價(jià)格以引導(dǎo)用戶理性地選擇隱私保護(hù)服務(wù)等級(jí)。運(yùn)用該機(jī)制為6個(gè)等級(jí)的隱私保護(hù)服務(wù)制定了相應(yīng)的價(jià)格。分析表明，該服務(wù)模型中的定價(jià)機(jī)制可以合理地制定每個(gè)等級(jí)之間的價(jià)格，實(shí)現(xiàn)了隱私數(shù)據(jù)分級(jí)保護(hù)，優(yōu)化了社會(huì)資源的配置。

VCG機(jī)制；最優(yōu)匹配；差分隱私；服務(wù)分級(jí)

1 概 述

過(guò)去幾十年中，互聯(lián)網(wǎng)技術(shù)取得了飛速發(fā)展，徹底改變了人們的生產(chǎn)生活方式，例如人們可以通過(guò)互聯(lián)網(wǎng)進(jìn)行辦公、交流、在線娛樂(lè)等。然而，當(dāng)人們?cè)谙硎芫W(wǎng)上沖浪樂(lè)趣的同時(shí)，也在承受著個(gè)人隱私數(shù)據(jù)被泄露的風(fēng)險(xiǎn)?！袄忡R門”事件披露出用戶的網(wǎng)絡(luò)行為可以被實(shí)時(shí)監(jiān)控，折射出一個(gè)令人深思的隱私保護(hù)問(wèn)題。

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

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

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

差分隱私保護(hù)的研究主要集中在隱私數(shù)據(jù)的發(fā)布與隱私數(shù)據(jù)挖掘上，對(duì)隱私分級(jí)方面的研究還比較欠缺。若在沒(méi)有任何約束的情況下，用戶普遍偏向選擇等級(jí)較高的隱私保護(hù)服務(wù)，導(dǎo)致非重要信息采取相對(duì)較高的隱私保護(hù)就是對(duì)資源的浪費(fèi)，同時(shí)過(guò)度保護(hù)也不利于互聯(lián)網(wǎng)的發(fā)展。

如果把隱私保護(hù)服務(wù)看成一種特殊的商品，通過(guò)價(jià)格調(diào)節(jié)機(jī)制引導(dǎo)用戶理性地選擇有差別的隱私保護(hù)服務(wù)。為此，在隱私保護(hù)等級(jí)已存在的假設(shè)前提下，提出了分級(jí)的隱私保護(hù)服務(wù)模型。該模型能夠保證服務(wù)商向用戶提供不同等級(jí)的隱私保護(hù)服務(wù)，用戶按需購(gòu)買服務(wù)。結(jié)合經(jīng)濟(jì)學(xué)中VCG拍賣機(jī)制與最優(yōu)匹配原理，按照最優(yōu)匹配原理使所有競(jìng)拍者的隱私估值之和最大的條件為競(jìng)拍者分配隱私保護(hù)服務(wù)等級(jí)，進(jìn)而得到不同等級(jí)服務(wù)的VCG價(jià)格。當(dāng)用戶請(qǐng)求某個(gè)等級(jí)的服務(wù)并付款后，就會(huì)獲得服務(wù)商提供的相應(yīng)等級(jí)的隱私保護(hù)服務(wù)。

2 研究基礎(chǔ)

2.1 隱私保護(hù)國(guó)際標(biāo)準(zhǔn)

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

2.2 差分隱私保護(hù)

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

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

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

(1)

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

2.3 VCG拍賣機(jī)制

VCG[22](Vickrey-Clarke-Groves)機(jī)制是針對(duì)網(wǎng)絡(luò)空間無(wú)法對(duì)數(shù)字產(chǎn)品或服務(wù)進(jìn)行價(jià)格估值的情況下，以Vickrey提出的單品次價(jià)拍賣為基礎(chǔ)，由Clarke和Groves推廣到更一般的多品次價(jià)拍賣機(jī)制。競(jìng)拍者首先提交對(duì)于每件拍品的報(bào)價(jià)，由拍賣系統(tǒng)以社會(huì)最優(yōu)的方式給每個(gè)競(jìng)拍者分配拍品，競(jìng)拍者得到某件拍品支付的費(fèi)用由其獲得這件拍品對(duì)其他競(jìng)拍者造成的損失來(lái)表示，也就是說(shuō)，每個(gè)競(jìng)拍者支付的價(jià)格等于該競(jìng)拍者不出現(xiàn)時(shí)，其他競(jìng)拍者得到的價(jià)值總和提高的那部分。

VCG機(jī)制有兩個(gè)特點(diǎn)：一是該機(jī)制能激勵(lì)競(jìng)拍者按照其對(duì)拍品的真實(shí)估值出價(jià)；二是該機(jī)制可以達(dá)到社會(huì)最優(yōu)分配。

3 隱私服務(wù)等級(jí)定價(jià)機(jī)制設(shè)計(jì)

定義1：設(shè)Li(1≤i≤k)為已劃分好的k個(gè)隱私保護(hù)服務(wù)等級(jí)，其中L1為最低級(jí)別，Lk為最高級(jí)別，隱私保護(hù)的等級(jí)集合為{L={L1,L2,…,Lk}}。vi(1≤i≤k)為隱私保護(hù)強(qiáng)度，即每個(gè)隱私保護(hù)服務(wù)等級(jí)對(duì)應(yīng)的隱私保護(hù)水平，v1

定義2：設(shè)矩陣Vij=vi×bj(1≤i≤k,1≤j≤k)是出價(jià)為bj的競(jìng)拍者對(duì)于隱私保護(hù)強(qiáng)度為vi對(duì)應(yīng)的隱私服務(wù)等級(jí)的隱私估值。

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

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

隱私保護(hù)服務(wù)作為一種特殊商品，由隱私保護(hù)服務(wù)商提供，用戶只需選擇想要達(dá)到的隱私保護(hù)等級(jí)，然后服務(wù)商根據(jù)用戶的選擇為其提供對(duì)應(yīng)的服務(wù)。服務(wù)商的工作可以分為兩部分：一是定價(jià)過(guò)程，即為每個(gè)等級(jí)的隱私保護(hù)服務(wù)制定價(jià)格；二是當(dāng)用戶選擇某個(gè)等級(jí)的服務(wù)時(shí)，為用戶提供相應(yīng)的隱私保護(hù)服務(wù)。該隱私保護(hù)分級(jí)服務(wù)模型如圖1所示。

圖1 隱私保護(hù)分級(jí)服務(wù)模型

3.1 構(gòu)建最優(yōu)匹配

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

(2){pi=0} //初始化隱私保護(hù)服務(wù)等級(jí)的初始價(jià)格

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

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

(5){Vij=vi×bj;}} //計(jì)算每個(gè)人對(duì)于每個(gè)隱私保護(hù)等級(jí)的隱私估值

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

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

(8){匹配過(guò)程結(jié)束;}

(9)else

(10){與受限賣家關(guān)聯(lián)的商品價(jià)格pi+1;

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

3.2 計(jì)算每個(gè)服務(wù)等級(jí)的VCG價(jià)格

3.3 用戶合理選擇隱私保護(hù)服務(wù)

定價(jià)機(jī)制完成后，就得出每個(gè)隱私保護(hù)服務(wù)等級(jí)的價(jià)格。用戶根據(jù)自己的需求和每個(gè)等級(jí)的價(jià)格，選擇一個(gè)等級(jí)的服務(wù)。服務(wù)商接收到用戶的請(qǐng)求后，根據(jù)該等級(jí)對(duì)應(yīng)的隱私保護(hù)預(yù)算ε的區(qū)間選擇一個(gè)值，應(yīng)用拉普拉斯機(jī)制或者指數(shù)機(jī)制添加噪音，然后將結(jié)果返回給用戶。

4 機(jī)制分析

定價(jià)機(jī)制可以使得每個(gè)用戶都按照自己對(duì)隱私保護(hù)服務(wù)等級(jí)的真實(shí)需求出價(jià)，同時(shí)使得所有人的隱私估值最大。下面模擬一組數(shù)據(jù)說(shuō)明該定價(jià)機(jī)制的執(zhí)行過(guò)程并對(duì)該隱私分級(jí)服務(wù)模型作簡(jiǎn)要分析。

圖2 定價(jià)過(guò)程

假設(shè)共有6個(gè)隱私保護(hù)等級(jí)L1,L2,…,L6，每個(gè)等級(jí)對(duì)應(yīng)的隱私保護(hù)強(qiáng)度v1,v2,…,v6為：0.1,0.3,0.5,0.6,0.8,0.9?，F(xiàn)有4個(gè)競(jìng)拍者，出價(jià)b1,b2,…,b6依次為：50,60,70,80,90,100。首先進(jìn)行一次最優(yōu)匹配，這樣每個(gè)競(jìng)拍者都得到了一個(gè)隱私保護(hù)服務(wù)等級(jí)，此次把L6匹配給b6，L5匹配給b5，L4匹配給b4，L3匹配給b3，L2匹配給b2，L1匹配給b1；接下來(lái)以隱私保護(hù)等級(jí)L3為例，計(jì)算出價(jià)為b4的競(jìng)拍者應(yīng)該為L(zhǎng)3等級(jí)的服務(wù)支付的VCG價(jià)格。首先計(jì)算除過(guò)L3，b3這對(duì)節(jié)點(diǎn)，剩余匹配的估值總和，見(jiàn)式(2)：

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

(2)

然后計(jì)算除過(guò)出價(jià)為b4的競(jìng)拍者，其他人重新進(jìn)行最優(yōu)匹配的估值總和，見(jiàn)式(3)：

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

(3)

最后計(jì)算出價(jià)為b3的競(jìng)拍者為L(zhǎng)3等級(jí)支付的VCG價(jià)格：

∑2-∑1=255-233=22

(4)

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

4.1 定價(jià)效果分析

圖3為每個(gè)隱私保護(hù)等級(jí)服務(wù)對(duì)應(yīng)的價(jià)格曲線，反映了隱私保護(hù)服務(wù)等級(jí)越高則對(duì)應(yīng)的價(jià)格也越高，而且呈現(xiàn)出階梯性價(jià)格差。第一級(jí)的隱私保護(hù)強(qiáng)度最低，對(duì)應(yīng)于ISO/IEC 29190標(biāo)準(zhǔn)中的不完全過(guò)程級(jí)別，基本沒(méi)有實(shí)現(xiàn)隱私保護(hù)功能，因此定價(jià)為0；第二級(jí)實(shí)現(xiàn)部分隱私保護(hù)功能，因此價(jià)格較低；第三級(jí)和第四級(jí)大部分實(shí)現(xiàn)了隱私保護(hù)功能，因此價(jià)格適中；第五級(jí)和第六級(jí)基本完全實(shí)現(xiàn)了隱私保護(hù)功能，隱私價(jià)格最高。該價(jià)格符合市場(chǎng)一般規(guī)律，同時(shí)也合理拉開了各個(gè)等級(jí)之間的價(jià)格。

圖3 隱私保護(hù)服務(wù)等級(jí)對(duì)應(yīng)的價(jià)格曲線圖

4.2 最優(yōu)匹配算法有窮性分析

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

4.3 最優(yōu)匹配算法可以找到一個(gè)社會(huì)最優(yōu)匹配

由于價(jià)格總和獨(dú)立于選擇哪種匹配，因此這組匹配M的回報(bào)最大，即這個(gè)匹配可以達(dá)到估值總和最大。

5 結(jié)束語(yǔ)

基于VCG機(jī)制與最優(yōu)匹配原理，對(duì)假設(shè)已存在的隱私保護(hù)服務(wù)等級(jí)制定價(jià)格。實(shí)驗(yàn)結(jié)果表明，不同隱私保護(hù)等級(jí)之間的價(jià)格被合理拉開，符合市場(chǎng)經(jīng)濟(jì)的一般規(guī)律。然而現(xiàn)有的工作均是在假設(shè)差分隱私保護(hù)等級(jí)已經(jīng)劃分好的情況下進(jìn)行的，因此下一步工作的重點(diǎn)是研究差分隱私保護(hù)的分級(jí)模型和分級(jí)算法，劃分出合理實(shí)用的差分隱私保護(hù)等級(jí)。

[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] 張嘯劍，孟小峰.面向數(shù)據(jù)發(fā)布和分析的差分隱私保護(hù)[J].計(jì)算機(jī)學(xué)報(bào)，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 網(wǎng)絡(luò)出版時(shí)間：2017-04-28

國(guó)家自然科學(xué)基金資助項(xiàng)目(61602290，61173190)；中央高?；究蒲袠I(yè)務(wù)費(fèi)(GK201501008，GK261001236)

史武超(1991-)，男，碩士研究生，研究方向?yàn)殡[私保護(hù)；吳振強(qiáng)，教授，研究方向?yàn)殡[私保護(hù)與分子通信。

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