带隐私保护的群智感知任务分配机制

曹 振,孙玉娥,黄 河,,陆 乐,杜 扬,黄刘生

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与平台交互,且在任务完成后采用基于数字签名的支付机制完成支付,保证了平台和任务发布者均无法将用户与所提交的数据建立关联,从而保护了用户潜在的隐私不被泄露.其次,所设计的机制通过同态加密技术、随机扰乱技术以及置换技术,保证平台和半可信第三方均无法根据自身所得到的数据挖掘出用户或任务发布者的报价或预算隐私.最后,我们通过理论分析证明了所设计的机制可以保护用户和任务发布者的隐私,且通过仿真实验验证了所设计机制的有效性.