云環(huán)境保護(hù)競價(jià)隱私的最佳路徑算法

王 超 張 磊* 張春玲

1(佳木斯大學(xué)信息電子技術(shù)學(xué)院 黑龍江 佳木斯 154007)2(牡丹江技師學(xué)院 黑龍江 牡丹江 157000)

0 引 言

隨著云技術(shù)的發(fā)展尤其是基于位置服務(wù)以及導(dǎo)航的廣泛應(yīng)用[1]，最佳路徑選擇已成為人們?nèi)粘３鲂?、外出旅游的首選服務(wù)[2-3]。與最短路徑不同，通常情況下，最佳路徑指用戶在固定區(qū)間內(nèi)可在最短時(shí)間或最佳體驗(yàn)效果的情況下到達(dá)指定目的地的移動路徑[4-5]。雖然在很多情況下最佳路徑就是最短路徑，但是仍存在較大概率最短路徑并不能滿足用戶的最佳體驗(yàn)。因此，相對于最短路徑的計(jì)算，最佳路徑處理計(jì)算更為復(fù)雜，但云技術(shù)的發(fā)展為最佳路徑的計(jì)算帶來了便捷。在云環(huán)境下，最佳路徑計(jì)算一般由不同用戶提供移動路徑競價(jià)，同時(shí)經(jīng)過云環(huán)境比較并給予一定補(bǔ)償后獲得。因此，在競價(jià)過程中，為云環(huán)境提供最佳路徑信息的用戶更加關(guān)心自己提供的信息尤其是競價(jià)信息是否安全。針對云環(huán)境處理最佳路徑隱私的問題，Zhang等[6]就考慮過受限最佳路徑的云環(huán)境處理，并利用同態(tài)加密技術(shù)對用戶信息加密實(shí)現(xiàn)了對最佳路徑信息的隱私保護(hù)。Xi等[7]也通過使用PIR(Private Information Retrieval)方法實(shí)現(xiàn)了導(dǎo)航最佳路徑競價(jià)數(shù)據(jù)的隱私保護(hù)。Aivodji等[8]更是提出使用多方安全計(jì)算實(shí)現(xiàn)多用戶同時(shí)最佳路徑計(jì)算并保障多用戶競價(jià)隱私的處理方法。但是，當(dāng)前對于競價(jià)的隱私保護(hù)手段一般使用加密技術(shù)，并通過競價(jià)多方與云之間的信息交互來實(shí)現(xiàn)競價(jià)比較[9-10]，雖然能夠有效地保護(hù)競價(jià)隱私，但通常會由于加密處理以及密態(tài)環(huán)境下的比較導(dǎo)致處理效率相對較低，且很難實(shí)現(xiàn)多輪競價(jià)。針對效率和多輪競價(jià)問題，閆小勇等[11]提出最佳路徑搜索的二進(jìn)制協(xié)議，該方法雖然能夠提升效率卻又無法有效保護(hù)競價(jià)隱私。因此，本文基于二進(jìn)制前綴族提出一種可包含用戶競價(jià)隱私的云環(huán)境下的最佳路徑算法。利用二進(jìn)制前綴碼建立前綴族，并通過對前綴族使用哈希加密的方法建立保密環(huán)境下的比較集合，然后將該集合提交給云環(huán)境，并由云環(huán)境比較后獲得最佳路徑。整個(gè)計(jì)算比較過程中，一方面由于使用的是前綴族，使得云環(huán)境無法在該族群內(nèi)準(zhǔn)確地識別用戶提交的最佳路徑競價(jià)，另一方面由于前綴族使用哈希加密，其他競價(jià)用戶即使獲得競價(jià)信息也無法獲知用戶的真實(shí)競價(jià)。同時(shí)，本文算法在處理效率上要優(yōu)于同類的多方安全計(jì)算方法，既可以支持多輪競價(jià)，又不需要在用戶和云之間重復(fù)多次計(jì)算，因此其時(shí)間效率要優(yōu)于現(xiàn)有的多方安全計(jì)算方法。

1 最佳路徑競價(jià)和前綴族

1.1 最佳路徑競價(jià)

通常情況下，云環(huán)境下的最佳路徑比較可看作是一種通過云環(huán)境實(shí)現(xiàn)的多方競價(jià)的網(wǎng)絡(luò)拍賣過程，即通過由云環(huán)境提供的物質(zhì)激勵(lì)對協(xié)作用戶提交的最佳路徑進(jìn)行競價(jià)[9]，競價(jià)獲勝者能夠獲得物質(zhì)獎勵(lì)。與網(wǎng)絡(luò)競拍不同的是，該過程是經(jīng)過比較獲得競價(jià)最低值，即最佳路徑取值。因此，這種競價(jià)過程可表示為如圖1所示的最低競價(jià)比較過程。

圖1 云環(huán)境最佳路徑的競價(jià)過程

可以看出，在云環(huán)境下競價(jià)者之間不僅存在一次競價(jià)比較，還存在當(dāng)前出價(jià)失敗之后的二次競價(jià)甚至三次競價(jià)，直到不存在最佳路徑競價(jià)才能獲得最后的競價(jià)結(jié)果。因此，這種最佳路徑競價(jià)是一種多輪競價(jià)方式，故基于加密技術(shù)實(shí)現(xiàn)的隱私保護(hù)單輪競價(jià)方式無法滿足需要。同時(shí)，由于在競價(jià)的過程中，任何競價(jià)者都不希望其競爭者獲知其競價(jià)數(shù)值，因此還需在多輪競價(jià)中保持用戶競價(jià)隱私。

1.2 前綴族

前綴族是通過交運(yùn)算來驗(yàn)證某一數(shù)值是否在被判定的某一區(qū)間范圍內(nèi)，即通過交運(yùn)算來檢測數(shù)值范圍[12]。對于s-前綴族{0，1}s{*}w-s有s個(gè)0或者1，以及s個(gè)(w-s)*s，其中*可用0或者1來替代。例如：1***表示1-前綴族，而11*表示2-前綴族。由此，一個(gè)s-前綴族可代表一個(gè)從{0,1}s{0}w-s到{0,1}s{1}w-s之間的數(shù)值范圍。例如：p=1****表示的范圍是[10 000,11 111]，也就意味著一個(gè)數(shù)值滿足s-前綴族當(dāng)且僅當(dāng)具有相同首位的s位二進(jìn)制數(shù)與s-前綴族相同。假設(shè)存在w比特長度的二進(jìn)制數(shù)x=b1,b2,…,bw，則關(guān)于x的前綴族可表示為F(x)={b1,b2,…,bw,b1,b2,…,bw-1*,…,b1*…*,*…*}，該前綴族有(w+1)個(gè)元素，其中第i個(gè)可表示為b1,b2,…,bw-1+i*…*。例如數(shù)字9的二進(jìn)制表示是01001，則F(9)={01001,0100*,010**,01***,0****,*****}，于是有對于一個(gè)給定的數(shù)值x以及前綴p，x位于p范圍內(nèi)當(dāng)且僅當(dāng)p∈F(x)。其中，前綴族的范圍[d1,d2]可表示為P([d1,d2])，該范圍包含多個(gè)前綴，每個(gè)前綴覆蓋范圍[d1,d2]中的一個(gè)子范圍，并且所有前綴覆蓋整個(gè)前綴族的范圍[d1,d2]。例如，p([7,25])={001111,011110,111100,111000,110000,1****}，所以，x∈[d1,d2]當(dāng)且僅當(dāng)F(x)∩P([d1,d2])≠?。因此可利用前綴族這一特性制定一種隱私保護(hù)的競拍策略，一方面防止同類競價(jià)者獲得競價(jià)隱私信息，另一方面能夠?qū)崿F(xiàn)多輪競價(jià)?；谶@一思想，本文提出一種基于前綴族的隱私保護(hù)競價(jià)的最佳路徑算法，并以此實(shí)現(xiàn)隱私保護(hù)的多輪競價(jià)。

2 基于前綴族的隱私保護(hù)競價(jià)

2.1 隱私競價(jià)處理

使用前綴族的隱私保護(hù)競價(jià)可以簡單地劃分為兩個(gè)階段：第一階段為最佳路徑競價(jià)的前綴族編碼，第二階段為最佳路徑多輪競價(jià)秘密比較。為了進(jìn)一步增強(qiáng)算法的隱私保護(hù)能力，將最佳路徑競價(jià)使用哈希加密增強(qiáng)競價(jià)的保密性。因此，競價(jià)的處理可按照前綴族編碼和多輪競價(jià)秘密比較展開。

最佳路徑競價(jià)前綴族編碼階段：

第1步云平臺發(fā)布指定起始點(diǎn)位置區(qū)域最佳路徑任務(wù)，同時(shí)給出最佳路徑的最高競價(jià)；

第2步各競價(jià)者在收到競價(jià)任務(wù)后，將自己的競價(jià)按照前綴族進(jìn)行編碼，并同時(shí)將自己的競價(jià)與最高競價(jià)合并建立競價(jià)區(qū)間；

第3步各競價(jià)者使用哈希函數(shù)對前綴族和競價(jià)區(qū)間進(jìn)行加密，并獲得加密后的信息H(F(x))和H(P([d1,d2]))并發(fā)送給云平臺。

最佳路徑多輪競價(jià)秘密比較階段：

第1步云平臺將收到的由各個(gè)競價(jià)者發(fā)送的哈希值按照前綴族和競價(jià)區(qū)間加以區(qū)分；

第2步平臺執(zhí)行算法1對前綴族和競價(jià)區(qū)間加以比較并獲得當(dāng)前最佳路徑取值；

第3步云平臺發(fā)布當(dāng)前競價(jià)勝者，并同時(shí)接收第二輪競價(jià)前綴族和競價(jià)區(qū)間；

第4步重復(fù)執(zhí)行第2、3步，直到無后續(xù)競價(jià)。

算法1前綴族最佳路徑競價(jià)比較

輸入：接收到的n個(gè)競價(jià)者發(fā)送來的哈希加密后的前綴族集合Hi(F(x))和競價(jià)區(qū)間集合Hi(P([d1,d2]))，1≤i≤n,k=n。

輸出：最低競價(jià)結(jié)果前綴族min(H(F(x)))。

1. for(i=1;i<=n;i++)

2. for(j=1;j<=n;j++)

3. if(Hj(F(x))∩Hi(P([d1,d2]))≠?)

//判斷集合交集

4.k=k-1;

//計(jì)算元素重合次數(shù)，即交集出現(xiàn)次數(shù)

5. end if

6. if(k<2)

7. min(H(F(x)))=Hi(F(x));

//獲得最佳路徑競價(jià)

8. else

9. 算法執(zhí)行失??；

10. end if

11. end

12. end

上述過程可表示為前綴族與競價(jià)區(qū)間中每個(gè)子項(xiàng)之間的相交關(guān)系。例如：假設(shè)云環(huán)境提出的當(dāng)前最佳路徑競價(jià)的最高值為25，存在4個(gè)競價(jià)者向云環(huán)境提出競價(jià)，且分別是2、3、5、6，則按照前綴族編碼將得到表1所示的競價(jià)前綴族和競價(jià)區(qū)間。

表1 前綴族的競價(jià)編碼

可以看出，[2,25]這樣的競價(jià)區(qū)間與包含在該區(qū)間內(nèi)的所有競價(jià)之間的交集都不為空，則該區(qū)間為包含最佳路徑區(qū)間。此時(shí)與該區(qū)間同時(shí)提交的競價(jià)為最佳路徑競價(jià)。同時(shí)，對應(yīng)于使用哈希函數(shù)加密后的集合中的每個(gè)元素，由于哈希算法的抗碰撞性上述元素交集計(jì)算成立，且由于哈希加密的單向性，上述競價(jià)不會被包括云環(huán)境在內(nèi)的各個(gè)競價(jià)實(shí)體所獲知，競價(jià)隱私得到了保護(hù)。

2.2 安全性分析

使用前綴族在云環(huán)境下比較獲得最佳路徑競價(jià)的安全性取決于包括云環(huán)境在內(nèi)的各個(gè)實(shí)體無法準(zhǔn)確地獲知競價(jià)者出價(jià)。本文算法將競價(jià)內(nèi)容轉(zhuǎn)換為前綴族，使得單一競價(jià)被擴(kuò)展為一組至少由6個(gè)二進(jìn)制數(shù)組成的前綴族，同類競價(jià)用戶即使通過搭線等攻擊手段獲得該族，也只能得到k個(gè)近似二進(jìn)制競價(jià)，準(zhǔn)確獲知用戶的真實(shí)競價(jià)的比例為1/k。在競價(jià)過程中，用戶利用哈希函數(shù)對前綴族中的每一個(gè)二進(jìn)制數(shù)進(jìn)行加密，而由于哈希函數(shù)的單向加密和抗碰撞特性，使得包括云服務(wù)器在內(nèi)的整個(gè)參與競價(jià)的實(shí)體均無法對所獲得的競價(jià)信息加以解密，進(jìn)一步保障競價(jià)信息的隱秘性。整個(gè)競價(jià)的比較過程是通過利用H(F(x))和H(P([d1,d2]))進(jìn)行交運(yùn)算結(jié)果是否為空的比較獲得最佳競價(jià)的，整個(gè)過程中不需要進(jìn)行任何的實(shí)際價(jià)值對比，同時(shí)也不似同態(tài)加密那樣進(jìn)行密態(tài)環(huán)境下的數(shù)值計(jì)算。因此無論云環(huán)境是否具有極強(qiáng)的計(jì)算能力以及信息分析能力，均無法猜測獲得競價(jià)信息，進(jìn)一步保障整個(gè)競價(jià)處理過程中的信息隱蔽性，提高了最佳路徑競價(jià)比較的安全性。

3 實(shí)驗(yàn)驗(yàn)證

為驗(yàn)證本文算法在執(zhí)行過程中的計(jì)算效率以及算法在多輪隱私競價(jià)方面的隱私保護(hù)能力，本文在Windows 10環(huán)境下，使用Core i7處理器，8 GB內(nèi)存的筆記本電腦利用MATLAB 2017a進(jìn)行模擬驗(yàn)證。參與比較的算法有基于編碼和加密的RADP算法[12]、使用同態(tài)加密進(jìn)行比價(jià)的PPSP算法[6]、基于差分隱私的TATP算法[10]以及基于加密的CMQN算法[9]。實(shí)驗(yàn)將在算法執(zhí)行時(shí)間、最高同價(jià)競價(jià)比較次數(shù)、競價(jià)信息不確定性以及加密競價(jià)的可猜測概率等方面展開比較。

圖2給出了不同算法在隨競價(jià)人數(shù)增加的情況下算法的執(zhí)行時(shí)間差異?？梢钥闯?，所有算法的執(zhí)行時(shí)間均隨著競價(jià)人數(shù)的增加而增加，這是由于各算法需要對每個(gè)競價(jià)進(jìn)行比較。本文算法的執(zhí)行時(shí)間最短，這是由于本文算法僅需進(jìn)行集合交集運(yùn)算，而不需要數(shù)值比較。TATP算法采用添加噪聲的方法，需要同時(shí)對噪聲數(shù)據(jù)進(jìn)行數(shù)值比較，執(zhí)行時(shí)間稍高。CMQN算法對加密數(shù)值進(jìn)行比較，其比較過程需要解密后才能完成，因而其執(zhí)行時(shí)間高于CMQN算法。RADP算法雖然也使用集合，但是其編碼效率要低于本文算法，而且需要進(jìn)行密文比較而不是集合交集運(yùn)算，因此其執(zhí)行時(shí)間同樣高于本文算法。PPSP算法采用基于同態(tài)加密的多方安全計(jì)算方式，需要在競價(jià)用戶與云服務(wù)器之間多次進(jìn)行秘密計(jì)算，算法執(zhí)行時(shí)間最高。

圖2 算法執(zhí)行時(shí)間

圖3給出了出現(xiàn)相同最高競價(jià)情況下，不同算法對相同最高競價(jià)的處理輪次。對于相同最高競價(jià)，一般的處理方法是需要競價(jià)用戶重新進(jìn)行出價(jià)，并再次進(jìn)行競價(jià)比較。從圖3中可以看出，本文算法的比較次數(shù)最低，這是由于在相同競價(jià)產(chǎn)生之后本文算法僅需對再次競價(jià)用戶進(jìn)行競價(jià)比較，不需要與其他已完成競價(jià)的用戶比較。RADP算法與本文算法相類似，但是需要在最后的比較中與前次比較的次優(yōu)用戶進(jìn)行比較，因此比較次數(shù)要高于本文算法。CMQN算法采用加密實(shí)現(xiàn)隱私競價(jià)，但其主要針對的是單次競價(jià)，在重新競價(jià)時(shí)需要與所有用戶進(jìn)行比較。TATP算法與CMQN算法類似，但是由于添加的噪聲同樣需要加以比較，因此其比較次數(shù)高于CMQN算法。PPSP算法采用基于同態(tài)加密的多方安全計(jì)算，其比較不僅需要對所有競價(jià)重新進(jìn)行秘密比較，還需要進(jìn)行每個(gè)用戶間的隱私競價(jià)比較，因此最高同價(jià)競價(jià)比較次數(shù)最多。

圖3 最高同價(jià)競價(jià)比較

圖4給出了競價(jià)用戶提交競價(jià)所組成的競價(jià)集合中真實(shí)競價(jià)的不確定性?？梢钥闯?，隨著競價(jià)人數(shù)的增加，本文算法、RADP算法和TATP算法的不確定性都隨之增加，而PPSP算法和CMQN算法卻未產(chǎn)生變化。這主要是因?yàn)镃MQN算法使用加密處理，其信息不確定性并不受競價(jià)人數(shù)影響，且始終保持競價(jià)的單一加密性。PPSP算法盡管也是采用加密手段，但是由于同態(tài)加密的同態(tài)特性，其秘密計(jì)算是在競價(jià)用戶之間進(jìn)行，所以其信息不確定性要高于CMQN算法。TATP算法通過噪聲實(shí)現(xiàn)隱私比較，其競價(jià)信息不確定性隨用戶增加而增大。RADP算法采用競價(jià)分組模式，其競價(jià)分組數(shù)量隨競價(jià)人數(shù)增加而增加，因而具有更高的不確定性。本文算法不僅采用競價(jià)分組模式，而且分組數(shù)量隨著競價(jià)值位數(shù)的變化而增加，因而具有最高的不確定性。

圖4 競價(jià)信息不確定性

圖5給出了云環(huán)境在強(qiáng)計(jì)算能力下，對加密的用戶競價(jià)成功猜測的成功概率?？梢钥闯?，隨著競價(jià)人數(shù)的增加，云環(huán)境對競價(jià)成功用戶的猜測成功率逐漸降低。但是，TATP算法由于只是簡單地添加了噪聲競價(jià)，因而其猜測成功率要高于其他算法。CMQN算法僅對競價(jià)進(jìn)行單一加密，這使得其猜測成功率雖然低于TATP算法但仍然很高。PPSP算法采用多方安全計(jì)算，在共謀的情況下其競價(jià)隱私存在一定的被識別概率，因而其猜測成功率要高于RADP算法和本文算法。RADP算法采用分組后加密比較的方式實(shí)現(xiàn)隱私競價(jià)比較，但是其分組數(shù)量有限，影響了該算法的隱私保護(hù)能力，因而其加密競價(jià)的可猜測概率高于本文算法。本文算法一方面使用哈希加密后的集合交集運(yùn)算，增加了競價(jià)信息的隱私比較特性，另一方面隨著競價(jià)值位數(shù)的變化增加當(dāng)前競價(jià)分組數(shù)，進(jìn)一步增加了競價(jià)信息的不確定性，可猜測概率最低。

圖5 加密競價(jià)可猜測概率

4 結(jié) 語

為了保障在云環(huán)境處理下對用戶最佳路徑的隱私競價(jià)給予保護(hù)，本文提出一種基于二進(jìn)制前綴族的云環(huán)境下保護(hù)競價(jià)隱私的最佳路徑算法。一方面將用戶競價(jià)轉(zhuǎn)換為泛化后的前綴族二進(jìn)制編碼，令攻擊者無法準(zhǔn)確識別；另一方面，將這種前綴族利用哈希函數(shù)加密為單向不可逆的加密編碼，進(jìn)一步加大對競價(jià)的保護(hù)。同時(shí)，由于采用前綴族與競價(jià)區(qū)間加密值交運(yùn)算比較的方式獲得最佳路徑，整個(gè)計(jì)算處理過程并沒有受上述處理影響而增加計(jì)算復(fù)雜度和處理負(fù)載，因此具有較好的執(zhí)行效率。通過與其他同類算法在隱私保護(hù)能力與算法執(zhí)行效率兩個(gè)方面的比較結(jié)果也可看出，本文算法具有更好的適用性。然而，本文算法僅可用于最佳路徑的競價(jià)計(jì)算過程，仍無法解決云環(huán)境其他計(jì)算處理的隱私問題，今后的研究工作將在云環(huán)境數(shù)據(jù)隱私保護(hù)以及數(shù)據(jù)隱私利用等方面展開。