差分隱私在雙向異質(zhì)頻譜拍賣方案中的研究①

巫朝霞, 王 路

(新疆財(cái)經(jīng)大學(xué)統(tǒng)計(jì)與數(shù)據(jù)科學(xué)學(xué)院,烏魯木齊 830012)

0 引 言

為保證頻譜用戶私密信息得到有效保障，針對(duì)拍賣過程中的隱私泄露和安全性能低等問題, 現(xiàn)有許多新的安全算法。文獻(xiàn)[1]提出的采用混合圖的雙向異質(zhì)頻譜拍賣算法使用混合圖準(zhǔn)確量化了買家之間的頻譜干擾情況，顯著提高了頻譜利用率，隱私安全性能有待提高。Zhou等人中首先引入了現(xiàn)代市場(chǎng)經(jīng)濟(jì)學(xué)理論中的頻譜拍賣模型,提出了一種新的頻譜拍賣計(jì)算方案[2]。TRUS第一個(gè)成功地設(shè)計(jì)實(shí)現(xiàn)了這種頻譜的可復(fù)用性的真實(shí)雙向同質(zhì)頻譜拍賣定價(jià)機(jī)制的解決方案[3]，在設(shè)計(jì)的拍賣機(jī)制中，多個(gè)參與方可以根據(jù)各自的需求進(jìn)行頻譜交易。文獻(xiàn)[4](結(jié)合同態(tài)加密和加密電路的高效頻譜拍賣方案)有機(jī)結(jié)合了同態(tài)加密和加密電路技術(shù)對(duì)用戶隱私信息提供了安全保證，可花費(fèi)通信開銷過大。基于此，保護(hù)買家的隱私是設(shè)計(jì)頻譜拍賣方案時(shí)的需要著重考慮的。在具有隱私保護(hù)的前提下，設(shè)計(jì)了具有隱私保護(hù)的頻譜拍賣方案DPDA，具有較好的頻譜收益和隱私安全性。

1 預(yù)備知識(shí)

1.1 拍賣模型

DPDA頻譜拍賣方案建立在雙向異質(zhì)頻譜拍賣模型的基礎(chǔ)上，頻譜買家可以根據(jù)不同的喜好購買一個(gè)或多個(gè)頻段，對(duì)不同的頻段具有不同的頻譜報(bào)價(jià)，同時(shí)具有多個(gè)頻譜賣家，這假設(shè)每個(gè)頻譜買家僅出售一個(gè)頻段，對(duì)出售的頻段有頻段的頻譜報(bào)價(jià)，拍賣人作為中間代理，主持并完成頻譜拍賣的整個(gè)流程。如圖1所示：

圖1 雙向頻譜拍賣模型

1.2 差分隱私

差分隱私通過對(duì)原始數(shù)據(jù)集添加噪聲擾動(dòng)，對(duì)真實(shí)的數(shù)據(jù)進(jìn)行掩蓋，從而達(dá)到保護(hù)隱私的目的。差分隱私對(duì)于一個(gè)隨機(jī)差分算法M,Pm為該隨機(jī)算法M中可以被導(dǎo)入輸出的全部函數(shù)值的集合。如果對(duì)于任意的一對(duì)相鄰映射數(shù)據(jù)的子集D和D′,Pm的任意一個(gè)相鄰子集Sm, 算法都可以滿足:

Pr[M(D)∈Sm]≤eεPr[M(D)∈Sm]

(1)

則稱該分析算法M所滿足的為差分個(gè)人隱私, 其中參數(shù)ε是進(jìn)行差分個(gè)人隱私保護(hù)的隱私保護(hù)成本預(yù)算，D表示原來的數(shù)據(jù)集，D則是其中相鄰的數(shù)據(jù)集。差分隱私嚴(yán)格的數(shù)學(xué)推理，保障兩個(gè)臨近數(shù)據(jù)集最多相差一個(gè)記錄數(shù)據(jù)。不管兩者是否同時(shí)包含某條記錄數(shù)據(jù)，輸出結(jié)果的概率分布函數(shù)無顯著變化，其中ε隱私預(yù)算一定程度上決定了概率分布函數(shù)差異程度。

1.3 Diffie-Hellman算法

首先Alice和Bob選取大素?cái)?shù)P和a，其中a是P的本原元。這兩個(gè)整數(shù)不必是秘密的，故Alice和Bob可以通過即使是不安全的途徑協(xié)商它們。它們可以在一組用戶中公用。

協(xié)議如下：

(1)Alice選取一個(gè)大的隨機(jī)整數(shù)xA，并發(fā)送給Bob：YA=axAmodP

(2)Bob選取一個(gè)大的隨機(jī)整數(shù)xB，并發(fā)送給Alice：YB=axBmodP

(3)Alice計(jì)算k1=YBxAmodP

(4)Bob計(jì)算k2=YAxBmodP

則會(huì)有：

k1=YBxAmodP=axAxBmodP

k2=YAxBmodP=axAxBmodP

(2)

2 差分隱私頻譜拍賣方案DPDA

2.1 DPDA模型框架

對(duì)于賣家而言，其效用函數(shù)可以如(3)表示：

(3)

其中pj表示買家的報(bào)價(jià)，aj,i用來表示頻段i是否已經(jīng)分配給買家j，當(dāng)aj,i=1時(shí)，意味著買家j成功獲取頻段i，否則aj,i=0。

對(duì)于買家而言，其效用函數(shù)可以如(4)表示：

(4)

每位賣家和買家都向代理人提交加了噪聲的結(jié)果以保證投標(biāo)價(jià)格的隱私。通過加密系統(tǒng)將數(shù)據(jù)安全傳輸給代理人之后，代理人對(duì)數(shù)據(jù)進(jìn)行處理之后利用匹配原則對(duì)頻譜進(jìn)行匹配，從而達(dá)到對(duì)資源的最大利用。差分隱私DPDA方案分三個(gè)階段：差分隱私投標(biāo)階段、差分隱私價(jià)格判定階段、確定贏家階段。具體流程圖如圖2。

圖2 DPDA算法流程圖

2.2 方案具體實(shí)施

2.2.1 差分隱私投標(biāo)階段

拍賣人選取大素?cái)?shù)m和n其中m和n對(duì)應(yīng)的本原元分別為a和b，并將m和a、n和b分別公開。

(1)拍賣人選取兩個(gè)大的隨機(jī)整數(shù)xA、xB分別計(jì)算Xs=axAmodm和Xr=bxBmodn發(fā)送給頻譜賣家和頻譜買家。

(2)每位頻譜賣家選取一個(gè)大的隨機(jī)整數(shù)yA，并計(jì)算Ys=ayAmodm發(fā)送給拍賣人。

(3)每位頻譜買家選取一個(gè)大的隨機(jī)整數(shù)zA,并計(jì)算Zr=bzAmodn發(fā)送給拍賣人。

(4)此時(shí)拍賣人分別計(jì)算Ks=aYsmodm和Kr=bZrmodn。

(5)每位頻譜賣家計(jì)算Ks=aXsmodm獲取密鑰Ks。

(6)每位頻譜買家計(jì)算Kr=bXrmodn獲取密鑰Kr。

影響高速公路施工的因素主要有四個(gè)方面：施工材料的儲(chǔ)備、拌和、運(yùn)輸和攤鋪。施工材料在施工過程中是對(duì)施工質(zhì)量影響最大的因素，而材料的儲(chǔ)備和拌和更是直接影響著施工材料的質(zhì)量以及效果。盡管施工材料的問題影響非常大，然而目前還沒有關(guān)于施工材料的儲(chǔ)備、運(yùn)輸?shù)陌踩珮?biāo)準(zhǔn)，因此實(shí)際施工中較容易出現(xiàn)安全問題。材料的管理與統(tǒng)籌需要更加標(biāo)準(zhǔn)化的方式。

(7)頻譜賣家和拍賣人完成密鑰交換Ks=aXsmodm=axAyAmodm=Ks。

(8)頻譜買家和拍賣人完成密鑰交換Kr=bXrmodn=bxBzAmodn=Kr。

(5)

(6)

將頻譜賣家和頻譜買家發(fā)加密后的數(shù)據(jù)CM={C1,C2,…,CM}和CN={C1,C2,…,CN}傳輸給拍賣人。

2.2.2 差分隱私價(jià)格判定階段

拍賣人在收到頻譜賣家和頻譜買家發(fā)送的數(shù)據(jù)后，通過加和這些加密的數(shù)據(jù)值，得到如(7)元組：

(7)

(8)

(9)

對(duì)于頻譜買家的發(fā)送的加密數(shù)據(jù)，拍賣人進(jìn)行數(shù)據(jù)加和得到：

(10)

拍賣人利用自己的密鑰SL0獲得解密買家的報(bào)價(jià)價(jià)格：

(11)

確定的頻譜交易價(jià)格Pc由如(12)計(jì)算得到：

(12)

根據(jù)計(jì)算的出的最終頻譜交易價(jià)格，將其定義為基準(zhǔn)價(jià)格，對(duì)于頻譜賣家而言，如果存在PiPc則意味著所有大于基準(zhǔn)價(jià)格的競(jìng)標(biāo)價(jià)可以被允許購買。最后將符合條件的買家和賣家寫進(jìn)一個(gè)列表中。

2.2.3 買賣匹配階段

考慮到頻譜拍賣所具有的可復(fù)用性，使用頻譜買家提供的地理位置信息L=[L1,L2,L3,…LN]對(duì)頻譜買家構(gòu)建拓?fù)鋱D，也就是說可以為一個(gè)頻譜分配多個(gè)互不干擾的獲勝買家，以最大限度地提高頻譜賣家的收入。使用沖突圖G=(V,E)來描述買家之間的干擾關(guān)系。在干擾圖G中，每個(gè)頂點(diǎn)和邊分別表示所有買家對(duì)頻譜賣方的出價(jià)及其干擾關(guān)系。連接兩個(gè)買家的邊緣表示他們?cè)谕ㄟ^同一頻譜傳輸時(shí)相互干擾。因此，將哪些買家可以同時(shí)分配給一個(gè)頻譜的問題，轉(zhuǎn)化為在沖突圖上找到最大獨(dú)立集的問題。最后，如果存在買家想要繼續(xù)匹配其他頻譜資源，根據(jù)買家的意向列表可以對(duì)資源進(jìn)行再匹配，實(shí)現(xiàn)資源的最大利用。

2.3 安全性分析

DPDA是在雙向異質(zhì)頻譜拍賣方案下結(jié)合了差分隱私機(jī)制以及Diffie-Hellman算法所提出的，該算法在三個(gè)階段保證了頻譜需求者的敏感信息隱私安全。差分隱私投標(biāo)階段,頻譜買賣雙方在該階段用噪音掩蓋自己真實(shí)的頻譜報(bào)價(jià)價(jià)格，使用Diffie-Hellman密鑰交換協(xié)議與拍賣人進(jìn)行密鑰交換，加密自己的報(bào)價(jià)，可以看到在該階段，除卻身份ID、地理位置等信息外，任何有關(guān)頻譜拍賣的價(jià)格敏感信息都做了噪音以及加密處理，沒有任何敏感信息的泄露。差分隱私價(jià)格判定階段，計(jì)算小組價(jià)格，確定基準(zhǔn)價(jià)格，在整個(gè)計(jì)算過程中，所有的有關(guān)價(jià)格的敏感信息都是加入噪音擾動(dòng)的。也就是說沒有拍賣人并不能對(duì)有關(guān)價(jià)格的敏感信息得到有價(jià)值的東西。確定贏家階段，拍賣人確定買家價(jià)格對(duì)比基準(zhǔn)價(jià)格判定，確定最終的贏家價(jià)格，根據(jù)設(shè)定的差分隱私噪聲機(jī)制可以發(fā)現(xiàn)最終價(jià)格是小組的平均價(jià)格，也就是說頻譜買家和頻譜賣家提交的報(bào)價(jià)信息是沒有辦法知道的，故在該階段該算法也是安全的。以下是基于文章中差分隱私方案DPDA證明機(jī)制符合差分隱私的相關(guān)證明：

其中，∈是一個(gè)大于0的參數(shù)，e1,e2,…em是從集合分布中提取的一組獨(dú)立的隨機(jī)變量，b″的兄弟價(jià)格設(shè)為b',可以顯然得到所有價(jià)格的和如下表示：

(13)

該函數(shù)的概率密度函數(shù)如(14)表示：

(14)

根據(jù)價(jià)格和的輸出空間及概率，推導(dǎo)如(15)：

(15)

由此可見，差分隱私拍賣方案DPDA符合ε-差分隱私。

時(shí)間復(fù)雜度計(jì)算：

DPDA的算法復(fù)雜度為O(KM2N2X),其中K與X為密鑰的長(zhǎng)度，M與N代表買家與賣家的數(shù)目。

證明：算法的復(fù)雜性包括三個(gè)部分：(1)M個(gè)頻譜買家和N個(gè)頻譜賣家加密噪聲價(jià)格的算法復(fù)雜性，以及拍賣人解密這些加密數(shù)據(jù)所耗費(fèi)的計(jì)算量；(2)尋找頻譜買家與其偏好的最大獨(dú)立集的復(fù)雜性；(3)買家與賣家之間匹配的復(fù)雜性。首先，加密方案的復(fù)雜性來自密鑰大小和買家、賣家的數(shù)量，即O(KMN)，其中K是密鑰大小。然后，由于貪婪算法求最大獨(dú)立集的復(fù)雜性，將其設(shè)置為O(X)。最后，匹配的復(fù)雜性由買家和賣家的總數(shù)決定，即O(MN)。因此，總的復(fù)雜度為O(KM2N2X)。

2.4 實(shí)驗(yàn)結(jié)果與分析

2.4.1 實(shí)驗(yàn)配置

實(shí)驗(yàn)背景是在雙向頻譜拍賣模型之下，多個(gè)頻譜賣家提供多個(gè)頻譜資源給購買者。設(shè)置賣家的數(shù)量從5位到40位不等，以5為單位遞增；買家的數(shù)量定為20。由于考慮到頻譜資源的干擾距離對(duì)分組匹配有影響，固定設(shè)置任何兩位買家的距離不少于50m以避免重疊。賣家和買家的距離被隨機(jī)設(shè)置區(qū)間為[20，80]。在實(shí)驗(yàn)中，假設(shè)每一位頻譜買家的頻譜需求和每一位頻譜賣家的賣出請(qǐng)求都是符合在區(qū)間(0,1]的統(tǒng)一分布，競(jìng)標(biāo)結(jié)果從區(qū)間[1，20]隨機(jī)抽取。每一組實(shí)驗(yàn)的重復(fù)計(jì)算次數(shù)為100次。

2.4.2 頻譜交易的有效性

圖3呈現(xiàn)的是DPDA方案對(duì)比隨機(jī)選擇方案和分組選擇方案的結(jié)果。圖中可以看到，隨著賣家數(shù)量的增加，DPDA方案中可接受的賣家數(shù)量大于隨機(jī)選擇方案和分組選擇方案的，并且線性增加趨勢(shì)，收入取決于明確價(jià)格和DPDA接受的賣家的數(shù)量，如圖4所示我們可以看到參與人數(shù)越多，獲得的收入就越高。評(píng)估匹配算法的性能在DPDA中以賣家滿意度衡量為標(biāo)準(zhǔn)，即滿足其優(yōu)先級(jí)的賣家的數(shù)量。可以得出：DPDA不僅可以獲得更好的性能，而且可以提高賣家參與頻譜拍賣的動(dòng)機(jī)。

圖3 可接受的賣家數(shù)量

圖4 收入對(duì)比

2.4.3 投標(biāo)隱私保護(hù)性能

圖5和圖6說明了接受的差分隱私下可接受的賣家數(shù)量和買家的收入?？梢宰⒁獾剑诓罘蛛[私添加噪聲的情況下，接受后的賣家數(shù)量和買家的收入對(duì)比沒有噪音的性能稍差。另外，它的表現(xiàn)當(dāng)∈為1時(shí)更接近。原因是∈表示隱私差異隱私預(yù)算，當(dāng)∈較小時(shí)，表示較高差異隱私級(jí)別，導(dǎo)致參與者提交的數(shù)據(jù)有更多的噪音。

圖5 可接受的賣家數(shù)量

圖6 收入對(duì)比

3 結(jié) 語

差分隱私頻譜拍賣方案DPDA方案綜合考慮了雙向異質(zhì)的頻譜拍賣模型中個(gè)人隱私安全問題，通過對(duì)頻譜買賣雙方提交的個(gè)人隱私信息加入噪聲機(jī)制對(duì)進(jìn)行掩蓋，并利用Diffie-Hellman算法在拍賣人和頻譜買賣雙方之間進(jìn)行密鑰交換，保護(hù)了頻譜拍賣過程中的個(gè)人隱私。在安全性分析中通過對(duì)DPDA方案的安全性證明、服從差分隱私的數(shù)學(xué)證明以及時(shí)間復(fù)雜度的計(jì)算，說明了該方案的安全有效性，實(shí)驗(yàn)仿真模擬對(duì)DPDA方案頻譜交易的有效性和隱私保護(hù)性能兩個(gè)指標(biāo)做了對(duì)比分析，結(jié)果證明，差分隱私的雙向異質(zhì)頻譜拍賣方案DPDA具有高效益性和隱私安全性。