帶隱私保護的群智感知任務分配機制

曹 振,孫玉娥,黃 河,,陸 樂,杜 揚,黃劉生

1(蘇州大學 計算機科學與技術學院,江蘇 蘇州 215006)2(蘇州大學 軌道交通學院,江蘇 蘇州 215137)3(中國科學技術大學 蘇州研究院,江蘇 蘇州 215123)

1 引 言

群智感知技術利用智能移動終端上配備的各類傳感器,能夠在廣泛的感知區域內實時獲取用戶感興趣的各類感知信息.與傳統的數據采集技術相比,它利用大量分散的移動終端用戶,可以在不添加額外專用設備的基礎上,實現更為快速、便捷和低廉的大規模數據采集.因此,近年來針對群智感知的研究越來越多,也涌現出大量的群智感知系統.而其中的任務分配問題,即如何把感知任務分配給最合適的用戶,實現任務與用戶之間的最優匹配問題是群智感知中的核心問題,也是實現群智感知系統所面臨的最主要挑戰之一.

現有群智感知任務分配問題研究主要可以分為:最優任務分配問題相關研究[1-9]和任務分配過程中的隱私保護問題研究[10-19]兩大類.其中,針對最優任務分配問題,中科大肖明軍等人[3]在 TMC 2017 中針對移動社交網絡中群智感知系統基于完工時間最優的任務分配問題分別設計了兩種分配算法AOTA和LOTA.美國亞利桑那州立大學 Shibo He 等人在 Infocom 2014 中提出了一種考慮移動用戶地理位置以及時間預算(time budget)的任務近似最優分配機制 LRBA[5].然而,上述研究并沒有考慮群智感知任務分配過程中存在的隱私泄露問題.為了解決該問題,文獻[13]提出的PESP算法通過引入隨機數據擾動技術(data perturbation)保護了用戶在參加群智感知任務時上傳的各類敏感數據.文獻[14-16]通過隱匿技術(cloaking technique)保護了參與感知任務用戶的位置信息.文獻[17,18]不僅保護了用戶的地理位置信息,同時針對參與感知用戶行動軌跡(trajectory)隱私保護問題進行了相關研究.上海交通大學吳帆,陳貴海研究團隊在文獻[19]中提出的SLICER隱私保護算法應用k-匿名技術保護了感知用戶所上傳多媒體數據中的敏感信息.

群智感知中的隱私保護問題應該包括兩個方面:用戶的個人隱私保護問題和雙向拍賣中的任務發布者隱私保護問題.當群智感知平臺中僅有一個任務發布者時,該平臺通常屬于該任務發布者.此時,平臺不存在泄露任務發布者隱私的風險.而當群智感知系統中存在多個任務發布者時,任務發布者需要向第三方的公共平臺提交自身對任務的預算以及收益函數.然而,這些信息對任務發布者來說屬于商業隱私,并不希望泄露給自己的競爭者或第三方.遺憾地是,現有群智感知隱私保護的相關研究均集中在用戶的個人隱私保護上,并沒有對任務發布者的隱私信息保護展開研究.如果任務發布者的隱私問題得不到足夠的重視,將阻礙第三方公共群智感知平臺的發展,從而進一步影響群智感知系統的大規模普及應用.

因此,本文設計了一種能同時保護用戶和任務發布者隱私的群智感知任務分配方法.首先,用戶在所設計的機制中采用動態IP與平臺交互,從而實現了匿名化,保護所提交感知數據中潛在的隱私數據不會泄露.除此之外,用戶的報價和任務的預算采用同態加密技術進行加密,并在平臺與半可信第三方交互時利用隨機擾亂和置換技術進行二次加密,從而保證平臺和引入的半可信第三方均無法獲取真實值,以保護用戶和任務發布者的價格隱私.最后,所設計的機制還通過電子簽名技術完成支付,保證平臺無法建立用戶與所提供數據之間的關聯.仿真實驗結果對所設計機制的計算開銷進行了分析,并驗證了分配方案的相關性能.

2 問題建模

本章首先給出所研究的帶隱私保護的群智感知任務分配機制的系統模型,然后進一步地闡釋其設計目標,并在最后介紹本文使用的隱私保護加密工具.

2.1 系統模型

如圖1所示,本文所研究的系統由一個群智感知平臺、一個半可信第三方、若干個任務發布者、以及一系列用戶U={1,2,…,n}組成.其中,半可信第三方會好奇用戶或任務發布者的隱私,但不會與平臺共謀.任務分配分周期進行.在任務分配開始前,所有任務發布者將待分配的任務發送給平臺,那么平臺獲得一個任務集合T={t1,t2,t3,…,tm},Tk?T表示任務發布者k提交的需求集合.每一個任務tj可以表示為tj={bj,Dj},其中bj表示任務發布者對任務tj的報價,即任務發布者在用戶完成任務后愿意支付的最大價值;Dj則是任務的描述信息,包含了任務的詳細需求.在實際發送時,任務發布者會利用半可信第三方下發的加密公鑰Pka,將每一個任務tj的報價bj加密成E(bj),再將tj={E(bj),Dj}發送給平臺.平臺收到任務發布者的任務后,會將任務需求發布.每個用戶i∈U可以表示為i={Yi,Bi},其中Yi是用戶i閱讀平臺發布的任務描述后,自身感興趣的任務集合;Bi則是用戶i對任務的報價,因為每個用戶感興趣的任務不止一個且這些任務也不盡相同,所以我們假設Bi是一個集合,每個元素bi,j∈Bi表示為用戶i完成任務tj所要求的最低報酬.同樣地,每個用戶將自己報價發送給平臺之前,需要利用加密公鑰將報價集合Bi中每個元素bi,j加密為E(bi,j).平臺根據任務和用戶集合中的相關信息,通過與半可信第三方的交互計算,利用某種規則完成任務與用戶之間的分配.用戶會根據任務發布者的要求完成任務,并提交結果,最后再通過平臺完成支付.至此,一次任務分配周期結束.表1將給出本文常用的符號表示及其含義.

圖1 帶隱私保護的任務分配模型Fig.1 Structure of the allocation system

表1 本文使用的一些符號表示
Table 1 Some symbols used in this paper

SymbolSymbol MeaningT,UThe set of tasks and users in the systemm,nThe number of tasks and users in the systemtj,bjA task in T,bid value of task tjbi,jBid value of user i for task tjui,jThe utility of task requester for task tj completed by user iPka,SkaThe encrypt key and decrypt key of the semi-trus-ted third partyEk,DkThe encrypt key and decrypt key of the task re-questerEK′,DK′The encrypt key and decrypt key of the platformπ(i)The permutation for the ID of usersYi,yi,jThe interest vector of user i,where yi,j=1 if user i prefers task tj;otherwise yi,j=-1X,xi,jThe allocation matrix,where xi,j=1 if task tj can be allocated to user i;otherwise xi,j=0

2.2 設計目標

本文是在考慮隱私保護的基礎上,設計一種群智感知的任務分配機制,以所有任務發布者的利益最大化為優化目標,從而實現任務與用戶之間的最佳匹配.

任務發布者給出的報價bj代表了任務tj的預算,而用戶i對某個感興趣任務tj的報價bi,j則是任務完成后,任務發布者需要向用戶實際支付的酬勞,即完成此任務的代價.我們假設每個任務完成后都會為任務發布者帶來一定的利益,那么用戶i完成任務tj后,所能帶來的收益可以定義為:

(1)

本文的另一設計目標是實現所有任務發布者的收益最大化,所以要計算所有可行的任務與用戶組合的收益,將任務分配給能夠帶來最大收益的用戶.在平臺無法直接利用加密數據進行收益排序時,因為只有半可信第三方擁有解密私鑰,所以平臺需要將相關加密報價發送給半可信第三方解密后再進行收益計算.如果平臺直接將加密后的報價發送給半可信第三方,那解密后他就可以獲得雙方報價的真實值,這就違背了隱私保護的目標.所以,平臺需要引入一定數量的隨機數,利用同態操作先對密文進行隨機擾亂后再發送給半可信第三方.這樣半可信第三方解密得到的報價都是通過相同的隨機數擾亂的,通過這些報價進行計算,雖然無法得到真實收益,但并不影響真實收益之間的大小關系比較.

在進行收益計算時,任務集合T中的每個任務之間都是平等的,而且這些任務可能來自不同的任務發布者,從而維護了多個任務發布者的公平性和使用平臺的積極性.用xi,j={0,1}表示任務tj是否分配給用戶i:若xi,j=1表示平臺將任務tj分配給了用戶i,否則xi,j=0.最終的優化目標是在隱私保護的前提下,實現所有任務發布者的總收益最大化,所以可以將其歸約為:

(2)

2.3 相關加密技術

1)Paillier同態加密系統[20]

本文采用的是一個1024位長的Paillier同態加密系統,主要包括以下三個步驟:

(3)

其中gcd(a,b)表示變量a和b的最大公約數,λ為p-1與q-1的最小公倍數.那么加密公鑰Pk為(N,g),解密私鑰Sk為λ.

加密:假設待加密報價明文M∈N,加密時首先任取一個隨機數r∈然后計算密文:

c=E(M)=gM·rNmodN2

(4)

其中,c是M的加密后的密文且N和g來自公鑰Pk.因為每次加密都會引入一個隨機數r,所以每次加密同一個報價,使用同一個加密公鑰,得到的密文也會不同.

解密:密文c的解密過程如下:

(5)

平臺要將加密后的報價進行隨機擾亂再發送給半可信第三方,實際上是在密文上的操作,為了半可信第三方能夠解密得到正確的處理結果,具體加法和數乘同態操作如下:

E(msg1)E(msg2)=E(msg1+msg2)

(6)

E(msg1)msg2=E(msg1*msg2)

(7)

其中,E(msgi)是msgi的密文.

2)RSA數字簽名技術[21]

本文中,平臺和用戶間的通信都是采用動態IP的方式,所以要保證支付信息的真實有效和支付過程的安全性,我們嘗試采用RSA數字簽名技術.RSA數字簽名是利用RSA算法對消息進行數字簽名.RSA算法是一種非對稱的加密方法,發送方利用加密私鑰進行消息加密,接收方利用解密公鑰進行消息驗證.由于RSA算法需要使用大素數的模冪計算,所以時間效率不夠好.所以,我們通常先利用hash函數,例如MD5等將消息原文散列出一個規模較小的摘要,然后通過加密私鑰將摘要加密形成數字簽名.發送時,發送方將消息原文連同數字簽名一起發送.接收方進行消息認證時,先利用發送方下發的解密公鑰將數字簽名解密,再通過相同的hash函數提取原文的摘要,若摘要值完全一致,則說明消息原文完整且未被篡改,否則拒絕接收.

3 帶隱私保護的群智感知任務分配機制

所設計機制的目標是在群智感知系統中,以保護用戶和任務發布者隱私為前提,實現任務與用戶間的最佳匹配.主要包括帶隱私保護的任務與用戶匹配機制和基于RSA數字簽名的支付機制,并在本章最后進行隱私保護的相關證明.

3.1 任務與用戶的匹配機制

在任務分配開始之前,半可信第三方會通過Paillier加密系統生成一組加密公鑰Pka和解密私鑰Ska.然后將加密公鑰在系統中公開,并獨自持有解密私鑰.首先每個任務發布者利用公鑰Pka將所有任務報價bj加密,并將任務tj={E(bj),Dj}發送給平臺,其中E(bj)為任務報價加密后的密文.待平臺收到所有任務發布者的任務后,將其放入一個總集合,形成任務集合T={t1,t2,t3,…,tm}.然后,平臺將所有任務的需求信息發布給用戶.

用戶閱讀完任務描述后,會選擇是否對這個任務感興趣.我們用yi,j={-1,1}記錄用戶i是否對任務tj感興趣.若yi,j=1,表示感興趣,同時用戶i會給出任務tj的用戶報價bi,j;否則表示不感興趣,并設置bi,j=0.當用戶閱讀完所有任務后,利用半可信第三方下發的公鑰Pka將所有用戶報價bi,j加密為E(bi,j),然后通過動態IP的方式與平臺進行通信,將{i,yi,j,E(bi,j)}tj∈T發送給平臺.待平臺收到用戶發送信息后,將其放入用戶集合U={1,2,…,i,…,n}中.此時平臺收到的總任務集合和用戶集合中的敏感信息都是經過加密的,所以平臺無法獲得真實的報價金額.

由于平臺收到的報價信息都是經過加密的,無法直接進行收益計算.只有半可信第三方持有解密私鑰Ska,所以平臺只能將相關報價發送給半可信第三方進行解密.因為要保護隱私,所以平臺需要引入隨機數將報價擾亂后才能發送.這樣半可信第三方解密的報價和計算的收益都是經過擾亂的,就無法得到任何有用的信息.帶隱私保護的任務分配機制如算法1.首先,平臺任取兩個隨機數δ1∈2γ1、δ2∈2γ2,分別對任務集合T用戶集合U中所有任務報價bj和用戶報價bi,j進行同態操作可以得到:

E(δ1bj+δ2)=E(bj)δ1E(δ2)

(8)

E(δ1bi,j+δ2)=E(bi,j)δ1E(δ2)

(9)

這里隨機數的范圍[1,2γ1]與[1,2γ2]需要保證解密后的結果δ1bj+δ2和δ1bi,j+δ2小于同態加密系統的運算規模.為了防止半可信第三方通過用戶ID與用戶產生關聯,平臺還會利用隨機置換技術對用戶ID進行擾亂.假設我們隨機生成一個置換π,其置換表的一部分如表2所示,如果我們給定一組用戶的ID為100→105,那通過π(i)置換得到的用戶ID結果為{951,842,3954,706,52,346}.在每個分配周期,平臺都會隨機生成一張置換表,所以半可信第三方無法將任務分配結果與真實用戶對應起來.

表2 置換π的部分置換表
Table 2 Permutation table ofπ

i100101102104105106π(i)951842395470652346

在完成相關信息的擾亂后,平臺將擾亂后的任務集合T′和任務集合U′發送給半可信第三方.半可信第三方首先利用私鑰Ska將加密的雙方報價解密后得到δ1bj+δ2與δ1bi,j+δ2.顯然解密結果都是經過隨機數擾亂的,并不能得到報價的真實情況.接下來,我們要以所有任務發布者收益最大化為優化目標進行任務分配.假設采用貪心的思想進行迭代,在每輪迭代之前,首先判斷任務集合T′或用戶集合U′是否為空.若T′為空,表示所有任務發布者的任務均已得到分配;若U′為空,則說明所有用戶都已分配到任務,系統中已無空閑用戶.此時,半可信第三方對任務的預分配結束,并將分配結果Xi,j發送給平臺.在每次迭代時,半可信第三方通過公式(10)計算出每個任務組合擾亂后的收益:

E(ui,j)=δ1(bj-bi,j)yi,j=δ1ui,j

(10)

從式(10)可以看出,δ2在雙方報價相減時被消去,擾亂后的收益E(ui,j)實際上是真實收益的δ1倍.而δ1又是一個隨機正整數,所以半可信第三方并不會得到真實收益的大小;而且對擾亂后的收益進行排序的結果和真實情況相同,從而保證了機制的正確性.然后遍歷所有可行的任務組合,用umax記錄這些組合中的最大收益,I、J分別記錄最大收益組合中的用戶和任務.一次迭代結束時,若umax≥0,則通過設置xI,J=1來告知平臺可以將任務tJ分配給用戶I,并分別從集合T′和U′中刪除任務tJ和用戶I.半可信第三方重復執行上述迭代過程,直到任務集合T′或用戶集合U′為空,或所有任務組合收益均小于零,即umax<0為止.最終,半可信第三方將所有任務的預分配結果X={xi,j}tj∈T′,i∈U′返回給平臺,平臺將按照xi,j=1將具體的任務分配給用戶,并將分配結果告知相應的任務發布者.至此,本周期任務分配過程全部結束.

算法1.帶隱私保護的任務與用戶匹配算法

輸入:一個群智感知平臺及其收到的總任務集合T、用戶集合U,若干個任務發布者、n個用戶以及一個半可信第三方.

輸出:任務的分配結果X={xi,j}i∈U,tj∈T.

1)平臺隨機生成兩個隨機數δ1∈21012、δ2∈21012,并生成 一個置換i→π(i).

2)for(每個任務tj∈T)

4) for(每個用戶i∈U)

5) 通過π置換表將i置換為π(i);

6) 計算E(δ1bi,j+δ2)=E(bi,j)δ1E(δ2);

7) end for

8)end for

9)平臺將擾亂后的任務集合T′={E(δ1bj+δ2)}tj∈T和用戶集合U′={π(i),yi,j,E(δ1bi,j+δ2)}i∈U,tj∈T發送給半可信第三方.

10)半可信第三方利用私鑰Ska=λ分別將所有任務和用戶報價解密得到δ1bj+δ2和δ1bi,j+δ2.

選取2017年11月-2018年11月,到某院進行分娩的孕產婦100例,將100例孕產婦隨機分為兩組,編號為實驗組和對照組,每組孕產婦為50例。對選取的孕產婦設定標準,選取的孕產婦年齡為19-31歲,且孕產婦都為初產婦,能夠準確的計算孕產婦孕齡,且胎兒生命跡象良好,并無提前分娩跡象。兩組孕產婦年齡,胎兒狀況等并無顯著性差異,分組不具有統計學意義。

11)while(T′≠? &&U′≠?)

12) 設置umax=-1;

13) for(每個任務tj∈T′)

14) for(每個用戶i∈U′)

15) 計算E(ui,j)=δ1(bj-bi,j)yi,j;

16) if(E(ui,j)≥umax&&E(ui,j)≥0)

17) 設置umax=E(ui,j);

18) 設置I=i,J=j;

19) end if

20) end for

21) end for

22) if(umax≥0)

23) 設置xI,J=1;

24) 從集合T′和U′中刪除任務tJ和用戶I;

25) else

26) break;

27) end if

28)end while

29)半可信第三方將分配結果X={xi,j}i∈U,tj∈T發送給平臺;

30)平臺根據X的內容將任務分配給用戶,并告知相應的任務發布者.

3.2 基于數字簽名的支付機制

當任務被分配后,平臺需要向對應的任務發布者索要支付.對于每個任務,任務發布者實際支付的金額應當等于用戶的報價.而且任務分配成功表示用戶報價往往小于任務發布者的預算報價,如果可以獲知具體任務的支付金額,那么很有可能導致任務發布者在下一輪分配中減少任務的預算,從而不斷壓價.另一方面,如果平臺直接將待支付的用戶報價發送給半可信第三方進行解密,那么平臺和半可信第三方都可以得到用戶報價的真實值.假設在任務分配結束時,任務發布者生成一組密鑰對:加密公鑰Ek用于數據加密,對系統公開;解密私鑰Dk獨自持有.當需要進行用戶報價解密時,半可信第三方先將擾亂后的報價解密,再利用任務發布者下發的公鑰Ek進行加密后,將結果返回給平臺.平臺利用公鑰Ek將用于擾亂的兩個隨機數進行加密,并將半可信第三方返回的結果一同發送給任務發布者.因為只有任務發布者擁有解密私鑰Dk,所以只能由其解密得到實際支付的金額.平臺收到任務發布者的支付的金額后,并不會直接支付給用戶,而是將任務發布者的支付憑證發送給他.由于平臺和用戶之間是采用動態IP進行通信的,為保證數據傳輸的真實有效性和完整性,支付憑證的加密和驗證是通過RSA數字簽名技術進行的.當用戶完成任務,并提交感知數據后,使用平臺下發的支付憑證向平臺索要報酬.

首先如圖2,任務發布者利用Paillier加密系統生成一組密鑰對Ek和Dk,Ek對整個系統公開,用于隱私數據的加密,Dk為解密私鑰,用于任務發布者自己解密得到實際的支付金額.然后,平臺將用戶加密的報價發送給半可信第三方進行解密.為防止其他用戶報價泄露,平臺重新獲取兩個不同的隨機數δ3∈21012和δ4∈21012,將用戶報價bi,j擾亂:

圖2 平臺向任務發布者索要支付過程Fig.2 Platform ask for payment

E(δ3bi,j+δ4)=E(bi,j)δ3E(δ4)

(11)

平臺將擾亂后的用戶報價發送給半可信第三方.半可信第三方利用解密私鑰Ska將用戶報價解密得到δ3bi,j+δ4,如果直接將解密后的結果發送給平臺,那么平臺可以消去隨機數得到真實的用戶報價.所以,半可信第三方利用任務發布者下發的加密公鑰Ek將用戶報價加密為Ek(δ3bi,j+δ4)后,再發送給平臺.平臺收到半可信第三方發送的數據后,需要向任務發布者索要支付,如果只發送Ek(δ3bi,j+δ4),那么任務發布者解密后并不能得到實際支付的金額.所以,平臺先利用公鑰Ek將兩個隨機數加密形成Ek(δ3,δ4),再將{Ek(δ3,δ4),Ek(δ3bi,j+δ4)}發送給任務發布者.任務發布者收到后,可以利用解密私鑰Dk解密得到δ3、δ4和δ3bi,j+δ4,通過計算就可以消去隨機數,得到實際的支付金額bi,j,并向平臺支付.

圖3 用戶向平臺索要報酬過程Fig.3 User ask for reward

用戶向平臺索要報酬的過程如圖3,平臺收到任務發布者的款項后,并不會直接支付給用戶,而是將支付憑證發送給他.平臺會通過RSA算法生成一組密鑰對,EK′作為私鑰,用于支付憑證的加密;DK′則作為公鑰,發送給相應用戶,用于數字簽名的解密.為節省數字簽名加密時間,平臺會利用MD5消息摘要算法將支付憑證單向散列為一段128位的憑證摘要d1,平臺再利用私鑰EK′對d1進行加密,形成數字簽名d2.實際發送時,平臺將{cj,d2}發送給用戶,其中cj表示任務發布者的支付憑證原文.用戶收到支付憑證后,先使用平臺公開的解密公鑰DK′將數字簽名d2解密得到d3,再利用相同的消息摘要函數MD5對收到的支付憑證原文cj提取摘要,得到d4.比較d3和d4的內容,若完全一致,則說明此支付憑證是平臺發來且內容是完整的.接下來,平臺會等待用戶完成任務,或進行其他任務的分配.待用戶完成任務并提交感知數據后,為保護隱私,用戶會更改IP地址,并使用相同的數字簽名方式與平臺進行支付憑證的驗證.驗證通過后,平臺會向其支付相應的金額.至此,任務完成且支付完畢.基于數字簽名的支付機制的具體實現如算法2.

算法2.基于數字簽名的支付機制

輸入:成功分配的任務及其對應的任務發布者和用戶、群智感知平臺以及半可信第三方.

1)任務發布者利用Paillier加密系統生成一組密鑰對:加密公鑰Ek和解密私鑰Dk,并將Ek在系統中公開.

2)平臺任取兩個隨機數δ3∈21012、δ4∈21012,通過公式(11)將用戶報價擾亂,并發送至半可信第三方進行解密.

3)半可信第三方先利用解密私鑰Ska將擾亂的報價解密得到δ3bi,j+δ4,再通過任務發布者下發的加密公鑰Ek,將其加密為Ek(δ3bi,j+δ4)并返回平臺.

4)平臺利用公鑰Ek將隨機數加密形成E(δ3,δ4),并發送{Ek(δ3,δ4),Ek(δ3bi,j+δ4)}向任務發布者索要支付.

5)任務發布者利用解密私鑰Dk進行解密,分別得到δ3、δ4和δ3bi,j+δ4,通過計算將bi,j還原,并按照bi,j的金額向平臺支付.

6)平臺通過RSA算法生成密鑰對EK′和DK′,將解密公鑰DK′在系統中公開.平臺通過MD5算法提取支付憑證cj的摘要d1,再利用加密私鑰EK′將d1加密形成d2,并將{cj,d2}發送給用戶.

7)用戶通過相同的算法提取cj的摘要d3,再利用公鑰DK′將d2解密,得到d4.

8)if(d3==d4)

9) 支付憑證cj是平臺發送且內容完整;

10)end if

11)待完成任務并提交感知數據后,用戶更改IP地址,憑支付憑證cj向平臺索要報酬.

12)平臺驗證支付憑證通過后,完成相應支付.

3.3 隱私保護分析

本文提出的帶隱私保護的群智感知任務分配機制最重要的目標是保護任務發布者和用戶的真實報價,從而能在誠實的情況下,完成任務分配.我們提出的機制主要包括群智感知平臺和半可信第三方兩個服務端,而且他們并非是完全可信的.所以接下來我們將證明在任務與用戶匹配以及支付的過程中,報價并不會泄露給這兩端.

定理1.所設計的群智感知任務分配機制可以保護任務發布者的任務報價隱私.

證明:在任務分配的過程中,群智感知平臺獲得的任務報價是任務發布者利用半可信第三方下發的公鑰加密的.平臺沒有解密密鑰,無法解密獲得真實報價,所以保證了任務報價對平臺保密.

根據本文提出的機制,半可信第三方收到的任務報價密文是經過平臺引入隨機數進行擾亂的.半可信第三方雖然擁有解密私鑰,但是他還是無法通過解密直接獲取真實的任務報價.假設半可信第三方收到n個任務報價,那么他可以構建n個方程來求解這些報價.但由于存在兩個擾亂隨機數,方程組中就至少包含n+2個變量,由于未知數的數量大于方程數,所以根本無法求出方程組的解,即半可信第三方無法通過構造方程獲得真實任務報價.

定理2.所設計群智感知任務分配機制可以保護了用戶的個人隱私.

證明:對平臺來說,用戶采用動態IP的方式與其進行交互,可以保護所提交的報價及感知數據中,包含的潛在用戶自身隱私不會泄露,實現了匿名化.平臺無法通過追蹤用戶IP獲取更多的用戶隱私信息.群智感知平臺收到的用戶報價是用戶通過半可信第三方下發的密鑰進行加密的,平臺沒有解密私鑰,所以無法解密得到真實報價.同時,在任務分配成功后,平臺需要將對應的用戶報價發送給半可信第三方進行解密,以此向任務發布者索要支付.但是半可信第三方返回的是利用任務發布者下發的公鑰進行加密的結果,平臺并不能從中挖掘其他有用的信息.用戶向平臺索要報酬時,距離平臺下發支付憑證已經隔了一段時間,即使報酬等于用戶報價,但平臺并不知道此金額與哪一個任務相關.所以,機制保證了用戶的個人隱私以及用戶報價隱私.

對于半可信第三方,平臺將用戶的報價信息發送給半可信第三方進行解密前,通過隨機置換的方式將用戶ID進行擾亂,每一輪分配均采用不同的置換表,這樣半可信第三方就無法將分配結果中的任務與真實用戶產生關聯.由于平臺對用戶報價的隨機數擾亂操作與任務報價相同,因此用戶報價對半可信第三方的隱私證明可以參照定理1中的相關證明.

任務發布者在支付階段,可以利用平臺發送的{Ek(δ3,δ4),Ek(δ3bi,j+δ4)}解密出實際支付的金額,且此金額為用戶的報價.但一個任務發布者有多個任務,他們并不能判斷本次支付對應的具體任務,所以用戶報價能夠對任務發布者保密,且保證任務發布者在之后分配過程的報價誠實性.任務發布者并不與用戶進行交互,且并不知道完成任務的具體用戶,所以用戶的個人隱私不會泄露給任務發布者.

綜上,所設計的群智感知任務分配機制保證了報價的隱私性以及用戶個人隱私.

4 實驗分析

對于任務匹配和支付兩個階段,本章將構造一個模擬實驗模型,通過實驗的方式來分析機制的加密解密計算開銷,且從任務發布者的總收益和任務成交率兩方面分析加密后實際性能.

4.1 計算開銷

多個任務發布者和多個用戶各自的運算過程是并行的,而且他們和平臺的交互也是彼此獨立的,所以在分析系統的加密開銷時,只需要考慮一個用戶和一個任務發布者,加密的開銷主要來自群智感知平臺和半可信第三方.分別使用E1、D1、E2、D2、RP表示Paillier加密、Paillier解密、RSA加密(包括提取摘要)、RSA解密以及隨機置換的計算開銷.假設若干個任務發布者共有m個待分配任務,其中任務發布者k的任務數量為mk,n個用戶的任務興趣比為0.1,即每個用戶只對「0.1m?個任務感興趣.計算開銷如表3所示,在任務匹配階段,任務發布者只需要將任務的預算報價利用Paillier公鑰進行加密,所以計算開銷為mkE1.同樣地,用戶也只需要將報價加密,為「0.1m?E1.平臺需要將收到的任務與用戶報價擾亂,由式(8)和式(9)可以得到,每次擾亂都要對一個隨機數進行加密,同時平臺還要將用戶ID進行隨機置換,所以平臺的加密開銷為(m+n「0.1m?)E1+nRP.半可信第三方則需要將加密的雙方報價解密后,進行收益比較,所以計算開銷為(m+n「0.1m?)D1.在向任務發布者索要支付時,平臺需要任取兩個新的隨機數對用戶報價進行擾亂,同時還需要利用任務發布者下發的Paillier公鑰將兩個隨機數加密,因為都是通過Paillier系統進行加密,所以加密開銷為(mr+2)E1,其中r為任務的成交率.半可信第三方需要將加密的用戶報價解密,同時需要利用任務發布者的密鑰將再其加密,所以計算開銷為mr(D1+E1).任務發布者需要解密兩個隨機數和用戶報價來獲取實際支付金額,故需要三次解密,開銷為3D1.在最后平臺向用戶支付報酬時,平臺需要將支付憑證利用RSA公鑰加密形成數字簽名,同時在用戶憑支付憑證索要支付時,需要將數字簽名解密進行驗證,所以計算開銷為mr(E2+D2).同樣地,用戶接收平臺發送的憑證時需要驗證,索要報酬時需要形成簽名,故開銷為E2+D2.

表3 m個任務、n個用戶的計算開銷
Table 3 Calculation overhead for m tasks and n users

Task requesterPlatformSemi-trusted third partyUsersTask matchmkE1(m+n|0.1m|)E1+nRP(m+n|0.1m|)D1「0.1m?E1Ask for payment3D1(mr+2)E1mr(D1+E1)0Pay for user0mr(E2+D2)0E2+D2

我們對機制的計算開銷進行了相關模擬實驗,假設在每一輪分配中有m個待分配任務和n個用戶.首先設m=20,用戶的數量n為{10,20,30,40},假設興趣比為0.1,即每個用戶選取2個任務作為自己感興趣的任務并給出報價.用戶數n與系統的運行時間如圖4所示.

圖4 用戶數量與系統運行時間關系(m=20)Fig.4 Relationship between number of users and run time(m=20)

由圖4可以得到,一開始用戶數量很少時,用戶感興趣的任務總量也比較少,所以平臺需要擾亂和半可信第三方需要解密的用戶報價就很少,同時在用戶很少時,任務成交率也較低,導致支付過程也比較快,所以總運行時間只有3秒多.但隨著用戶數量的增加,所有用戶的報價總量增多,平臺需要對更多的報價進行擾亂且半可信也需要對更多的任務組合進行解密、比較,所以平臺和半可信第三方的運行時間都逐漸提高,從而導致總運行時間也逐漸上升.

其次,我們又針對不同任務數量進行了實驗:設系統中有30個用戶,即n=30.任務的數量將分布在[5,20]之間,在用戶興趣比仍為0.1的情況下進行了任務分配并統計運行時間.由于任務數量的增加,需要進行加密解密的任務報價數量會隨之上升,同時用戶感興趣的任務數量也會變多,從而會給出更多的用戶報價.因此,隨著任務數量的增多,任務分配過程會消耗更多的時間.

4.2 任務數量對任務發布者總收益的影響

為了驗證進行隱私保護后,任務分配的性能,我們選取任務發布者的總收益和任務成交率作為衡量指標.任務發布者的總收益定義為系統中所有任務發布者的任務收益總和.任務成交率定義為系統中分配到用戶的任務數量與總任務數的比值.

分別針對用戶人數n=50、n=100和n=150進行了任務數量對總收益影響的對比實驗,假設任務數量分布在[40,300],實驗對比結果如圖5所示.從實驗結果可以看出,當n=150時,所有任務發布者的總收益最高.在用戶人數一定時,隨著任務數量的增加,更多的用戶可以分配到任務,所以總收益呈上升趨勢.

4.3 用戶人數對總收益與任務成交率的影響

分別針對任務數m=50、m=100和m=150進行了對比實驗.用戶數n分布在[40,200]之間,假設興趣比為0.1,即每個用戶分別選取5、10、15個任務作為感興趣的任務,并給出用戶報價.從實驗結果可以看出,當任務數m=150,能帶來最高的任務發布者總收益.隨著用戶人數的增加,更多的待分配任務可以被完成.同時對每個任務而言,每增加一個用戶,就增加了以更低成本完成任務的概率.所以隨著用戶數量的增加,所有任務發布者的總收益也會隨之上升.圖6為用戶人數的變化對任務成交率的影響.對于任務的成交率,由于一開始任務數大于用戶的數量,而且用戶報價并不總會低于任務發布者的任務報價,所以任務成交率較低.但是,隨著更多用戶的加入,用戶感興趣的任務總量變多,更多的任務可以分配到用戶,從而導致任務成交率上升.當用戶人數超過一定數量后,因為系統中低于任務預算報價的用戶都已經分配到了任務,或者所有任務都得到分配,所以最終任務成交率會達到一個平穩的趨勢.由于任務越多,不同任務對用戶的要求也越多,所以當m=150時,任務的成交率最低.

圖5 任務數量對任務發布者總收益的影響Fig.5 Impact of number of tasks on total profit of requesters

圖6 用戶人數對任務成交率的影響Fig.6 Impact of number of users on task turnover ratio

5 總 結

當存在多個任務發布者時,所采用的公共群智感知平臺并不一定是可信的,但現有相關研究均未考慮任務發布者的隱私保護問題.為了解決該問題,本文在引入半可信第三方的前提下,設計了一種能夠同時保護用戶個人隱私和任務發布者預算隱私的群智感知任務分配機制.首先,用戶在所設計的機制中使用動態IP與平臺交互,且在任務完成后采用基于數字簽名的支付機制完成支付,保證了平臺和任務發布者均無法將用戶與所提交的數據建立關聯,從而保護了用戶潛在的隱私不被泄露.其次,所設計的機制通過同態加密技術、隨機擾亂技術以及置換技術,保證平臺和半可信第三方均無法根據自身所得到的數據挖掘出用戶或任務發布者的報價或預算隱私.最后,我們通過理論分析證明了所設計的機制可以保護用戶和任務發布者的隱私,且通過仿真實驗驗證了所設計機制的有效性.