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

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

1 引 言

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

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

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

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

2 問題建模

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

2.1 系統(tǒng)模型

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

圖1 帶隱私保護的任務(wù)分配模型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 設(shè)計目標

本文是在考慮隱私保護的基礎(chǔ)上,設(shè)計一種群智感知的任務(wù)分配機制,以所有任務(wù)發(fā)布者的利益最大化為優(yōu)化目標,從而實現(xiàn)任務(wù)與用戶之間的最佳匹配.

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

(1)

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

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

(2)

2.3 相關(guān)加密技術(shù)

1)Paillier同態(tài)加密系統(tǒng)[20]

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

(3)

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

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

c=E(M)=gM·rNmodN2

(4)

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

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

(5)

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

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

(6)

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

(7)

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

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

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

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

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

3.1 任務(wù)與用戶的匹配機制

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

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

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

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

(8)

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

(9)

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

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

i100101102104105106π(i)951842395470652346

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

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

(10)

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

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

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

輸出:任務(wù)的分配結(jié)果X={xi,j}i∈U,tj∈T.

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

2)for(每個任務(wù)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)平臺將擾亂后的任務(wù)集合T′={E(δ1bj+δ2)}tj∈T和用戶集合U′={π(i),yi,j,E(δ1bi,j+δ2)}i∈U,tj∈T發(fā)送給半可信第三方.

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

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

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

12) 設(shè)置umax=-1;

13) for(每個任務(wù)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) 設(shè)置umax=E(ui,j);

18) 設(shè)置I=i,J=j;

19) end if

20) end for

21) end for

22) if(umax≥0)

23) 設(shè)置xI,J=1;

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

25) else

26) break;

27) end if

28)end while

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

30)平臺根據(jù)X的內(nèi)容將任務(wù)分配給用戶,并告知相應(yīng)的任務(wù)發(fā)布者.

3.2 基于數(shù)字簽名的支付機制

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

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

圖2 平臺向任務(wù)發(fā)布者索要支付過程Fig.2 Platform ask for payment

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

(11)

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

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

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

算法2.基于數(shù)字簽名的支付機制

輸入:成功分配的任務(wù)及其對應(yīng)的任務(wù)發(fā)布者和用戶、群智感知平臺以及半可信第三方.

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

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

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

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

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

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

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

8)if(d3==d4)

9) 支付憑證cj是平臺發(fā)送且內(nèi)容完整;

10)end if

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

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

3.3 隱私保護分析

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

定理1.所設(shè)計的群智感知任務(wù)分配機制可以保護任務(wù)發(fā)布者的任務(wù)報價隱私.

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

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

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

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

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

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

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

4 實驗分析

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

4.1 計算開銷

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

表3 m個任務(wù)、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

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

圖4 用戶數(shù)量與系統(tǒng)運行時間關(guān)系(m=20)Fig.4 Relationship between number of users and run time(m=20)

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

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

4.2 任務(wù)數(shù)量對任務(wù)發(fā)布者總收益的影響

為了驗證進行隱私保護后,任務(wù)分配的性能,我們選取任務(wù)發(fā)布者的總收益和任務(wù)成交率作為衡量指標.任務(wù)發(fā)布者的總收益定義為系統(tǒng)中所有任務(wù)發(fā)布者的任務(wù)收益總和.任務(wù)成交率定義為系統(tǒng)中分配到用戶的任務(wù)數(shù)量與總?cè)蝿?wù)數(shù)的比值.

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

4.3 用戶人數(shù)對總收益與任務(wù)成交率的影響

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

圖5 任務(wù)數(shù)量對任務(wù)發(fā)布者總收益的影響Fig.5 Impact of number of tasks on total profit of requesters

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

5 總 結(jié)

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