移动群智感知中融合数据的隐私保护方法

王涛春 金 鑫 吕成梅 陈付龙 赵传信

(安徽师范大学计算机与信息学院 安徽芜湖 241002)

(网络与信息安全安徽省重点实验室(安徽师范大学) 安徽芜湖 241002)(wangtc@nuaa.edu.cn)

随着集成多种传感器(温度传感器、GPS、加速度传感器、相机等)的移动智能设备(例如智能手机、智能手环等)的大量普及，一种新的传感范式群智感知逐渐兴起.群智感知[1]是一种利用便携式移动智能设备携带的传感器收集数据，然后将数据上传给群智感知服务商，获得一定的奖励或应用.随着移动智能设备集成的传感器越来越多，群智感知收集的数据类型也越来越广，使得应用领域更加广泛.服务提供商利用参与者收集大量的信息向需求者提供服务，需求者利用这些信息进行分析解决问题[2-6]，例如交通导航、环境监测[7]、社区服务[8]等.

然而群智感知的应用也引出一系列隐私安全问题.例如攻击者通过获取参与者发送的医疗等敏感信息来推导参与者的健康状况，从而进行一系列恶意攻击.同时，参与者传输给应用服务器的数据带有时空信息(参与者收集数据时的位置)，攻击者可能利用这些时空信息推导出参与者的生活习惯、行为规律等敏感信息来进行恶意攻击.因此，确保群智感知中参与者敏感信息的隐私是推动群智感知应用的关键因素.数据融合是群智感知数据收集的主要操作方式之一，目前群智感知中融合数据的隐私保护前提是服务提供商平台是可信的，文献[9]提出了一种基于同态加密的数据融合方案，该方案可以对密文进行融合操作，能够有效进行各种数据融合(如均值、方差、偏差等)，然而第三方服务提供商能够获得每个节点的信息，所以该方案的应用前提是第三方是可信的.此外，现有的群智感知中隐私保护数据融合方法没有考虑到节点(移动智能设备)移动性的特点，文献[10]提出了一种基于Diffie-Hellman的加密方案，当节点加入或是失效时，需要更新所有节点的加密密钥，节点的动态加入或失效处理复杂困难.

基于此，提出了群智感知中基于椭圆曲线的数据融合隐私保护算法(privacy preservation data aggre-gation algorithm based on elliptic curve cryptography, ECPPDA)，服务器对所有节点进行随机分簇，簇内节点通过自身的公钥构建簇公钥，并利用簇公钥对簇内节点采集到的数据进行加密，簇内节点对密文数据进行融合，最后将融合结果传输给应用服务器.应用服务器通过与簇内节点协作完成数据解密得到数据融合结果.由于应用服务器不能直接解密密文，从而保证节点数据的隐私性，解决了第三方必须是可信的应用场景.同时，ECPPDA算法中，节点的加入或失效只需要更新簇内节点的少量数据信息，因此本算法对节点动态加入或失效处理简单，较适用于群智感知这类节点具有移动性特点的分布式网络.理论分析和实验结果表明ECPPDA不仅能够保护用户的数据隐私抵御共谋攻击且兼顾节点移动性，而且能有效地降低节点的通信开销.

1 相关工作

根据服务器收集的数据类型，群智感知数据收集分为2类：1)原始数据收集，移动智能设备直接上传采集到的数据(如GPS坐标、加速度读数等).2)融合数据，服务器需要得到区域内节点数据的融合结果(求和、平均值、方差等).例如，服务器通过获得参与者平均运动量(步数、运动传感器)能够推导出参与者普遍的公共健康状况.本文将这2类分别称为基于原始数据的收集和基于融合数据的收集.当前国内外学者对群智感知中隐私保护问题进行了广泛研究.现有方案主要利用4类方法[11]：分组统计、可信第三方验证、k-匿名和数字加密.

基于分组统计的技术思想是参与者在上传感知数据阶段，将数据进行切片分成多个数据片，然后将数据片转发给邻节点，之后邻节点上传数据，应用服务器收集数据片并进行融合从而得到原始数据.文献[12]提出了HP3(hot-potato-privacy-protection algorithm)方案，在服务器不可信的情况下实现保护隐私的分组转发.HP3方案中参与者不是直接将数据上传到服务器，而是将数据传输给参与者的一个朋友(可信)，朋友选择另一个朋友并传输数据，以此类推，直到到达参与者定义的阈值，然后最后一个用户将数据上传到服务器.这种方案虽然解决了在服务服不可信情况下保证参与者的位置隐私，但前提是参与者有可信朋友.文献[13]提出了一种基于编码k-匿名方案(coding-based privacy preserving scheme)SLICER，SLICER集成了数据编码技术和消息传输策略，以实现对参与者隐私的保护，同时保持高数据质量.SLICER方案没有考虑共谋攻击.文献[14]提出了PEPPeR(privacy enhancing protocol for participatory sensing)方案，PEPPeR能够保护查询者的数据隐私，查询者和参与者由可信第三方服务器分配令牌，查询者和参与者传输数据时需要经过它们和第三方服务器之间的Tor(the onion router)网络.这些方案的隐私保护全都需要可信的第三方，这种第三方更容易被攻击.k-匿名是指区域内k个参与者和它们发出的信息不能被攻击者区分出来.文献[15]提出了AnonySense方案，该方案通过k-匿名技术来保护参与者的位置隐私.文献[16]的作者利用可信的邻居构建多个k-匿名区域发布虚假查询，来防止攻击者构建真实轨迹.数字加密是利用密码学的知识对数据进行加密防止攻击者窃听参与者在传输时的数据内容.这4种技术常用来组合使用保护参与者的数据隐私.

针对群智感知中数据融合的隐私保护问题，近年来国内外学者已经提出了许多解决方案.文献[17]提出的方案先利用多假名机制来克服由于参与者密度低而导致的漏洞，接着提出2种基于Paillier密码系统的方法抵御sybil攻击.文献[10]提出了一种基于Diffie-Hellman的加密方案，但这些方案无法有效地支持动态连接和失效.以文献[10]中的工作为例，当节点加入或失效时，需要更新所有节点的加密密钥，这意味着群智感知应用程序具有高额的通信开销.文献[8]提出了一种基于同态加密的数据融合方案，该方案对密文能够有效地进行各种数据融合(如均值、方差、偏差等)，然而第三方服务提供商能够获得每个节点的信息，所以该方案应用前提是具有可信的第三方.文献[18]中提出了不需要可信第三方来保护融合数据隐私的协议，该协议通过节点间参数共享来抵御共谋攻击.文献[19]提出了2种具有隐私保护能力的加法融合数据方案：第1种方案是基于簇的隐私数据融合方案(cluster-based private data aggregation, CPDA),利用多项式的聚类协议和代数属性完成隐私保护的数据融合;第2种方案是基于切片-混合的数据融合方案(slice-mix-aggregate, SMART),基于切片技术和加法关联属性.SMART方案的优点是计算开销相对较少，但SMART对每个数据都分成多段，因此节点的通信开销较大.文献[20]提出了一种基于信任的数据融合方案ERTDA(energy-efficient reliable trust-based data aggregation)，ERTDA通过节点行为来计算和评估节点的信任值，并能够及时检测和排除受损节点.ERTDA能够有效地提高融合数据的精确度，降低节点能耗，提高数据传输的可靠性，但节点信任值的评估以及受损节点的检测需要大量的计算开销，且ERTDA基于可信节点进行操作.

2 模型介绍

2.1 群智感知网络框架

群智感知网络主要由4个部分组成：移动节点、数据请求者、应用服务器和接入网络，如图1所示：

Fig. 1 Basic framework of the crowd sensing application

1) 移动节点(mobile node, MN).MN是具有感知、计算、存储、通信等基本功能的移动智能设备，如智能手机、运动手环等.它们是群智感知网络的基本单元，主要用于各类数据的采集，如温度、湿度、位置、声音等，并通过无线网络将采集来的数据上传到应用服务器.这些移动智能设备常由用户随身携带，所以能够随时随地进行数据采集,在群智感知中也常被称作参与者.

2) 数据请求者(data requester, DR).DR通过应用服务器发布感知任务，然后应用服务器将任务下达给参与者，服务器收集到请求者所需的数据时，将数据传输给请求者.在群智感知系统中参与者也可以通过他们的移动智能设备向服务器发布任务，所以参与者也可以是数据请求者.

3) 应用服务器(application server, AS).AS是对节点上传的数据进行处理，如解密、分类、融合、存储等，并与数据请求者实现数据的共享.根据移动节点提供的数据来回答数据请求者的各种问题，如请求者查找距离居住宾馆最近的餐厅等.本文应用场景是最常见的半诚实模型，即参与者和服务器严格按照协议要求执行操作，另一方面，他们通过获取信息推导出其他参与者的隐私信息.

4) 接入网络.指数据传输的通道，通常是通过无线网络进行数据传输的例如移动蜂窝网络、蓝牙、WIFI等无线网络，目前感知网络主要利用移动蜂窝网络进行数据传输.

2.2 攻击模型

根据攻击来源可将攻击划分为2类：外部攻击和内部攻击.1)外部攻击指的是攻击者通过窃听群智感知网络获取感知数据，破坏数据机密性.2)内部攻击指的是群智感知网络的参与者或服务提供商进行的攻击，例如参与者获取其他参与者的隐私信息，或服务提供商获取参与者的隐私数据，并通过这些隐私信息进行恶意攻击.本文主要采用的是半诚实模型，即群智感知中所有成员(服务提供商和参与者)严格执行设计的协议，但成员试图通过协议执行过程获得的数据来推导出其他成员的敏感信息.通过对传输数据加密能够有效抵抗外部攻击，而内部攻击以及共谋(多个参与者或服务器与参与者)攻击是ECPPDA研究的重点.

3 ECPPDA算法

本节主要介绍ECPPDA给出问题定义、算法思想，以及算法的具体执行步骤，最后对参与者的动态加入和失效处理过程进行描述.

3.1 问题定义及算法思想

ECPPDA假设有m个参与者和1个应用服务器，参与者采集感知数据、加密并融合，应用服务器得到融合后的密文数据，参与者ni采集的感知数据为di(i=1,2,…,m).

3.2 ECPPDA算法步骤

ECPPDA融合参与者采集到的感知数据，其处理主要包括3个阶段：

2) 数据传输.簇头节点随机选择簇内某个节点作为簇头节点，簇头节点随机选择一个始节点，始节点通过簇公钥加密自身的感知数据并将密文传输给中间节点，中间节点接收到前一个节点发送的密文并与自己的密文融合，再将融合结果发送给下一个中间节点，以此继续，直至终节点得到簇内所有节点密文的融合结果并发送给服务器.

3) 解密.服务器接收每个簇的密文融合结果后，需分别与每个簇内节点协同合作计算得到簇融合结果的明文，最后服务器对所有的簇明文进行融合从而得到所需数据.

3.2.1 初始化

簇划分具体过程为：在任务区域内接受任务节点ni发送公钥Yi给服务器，服务器随机选择k个节点形成一个簇，从而将任务区域划分为g个簇，并给每个簇随机选择一个节点作为簇头节点.对于每个簇，服务器对簇内k个节点的公钥进行融合形成簇公钥，然后将簇公钥和簇信息(包括簇头节点和簇成员信息)发送给簇内的所有节点.其操作包括3个步骤：

具体过程见算法1.

算法1.节点分簇.

① for(i=1;i≤n;i++)*节点ni操作*

③Yi=xi×G;

④Yi→NAS;*将公钥Yi发送给应用服务器NAS*

⑤ end for

⑥ for(i=1;i≤g;i++)*服务器操作*

⑦ 簇Ci={n1,n2,…,nk};*随机选择k个节点构成簇Ci*

⑨ 随机选取簇头节点nh;

⑩ 簇Ci:DCi→节点ns,ns∈Ci;*包括簇公钥和簇头等分簇信息DCi发送给簇内所有成员节点*

3.2.2 数据传输

每个簇的操作相同，现以一个簇操作为例介绍数据传输进程.节点ni通过簇公钥PCK加密它的数据di，簇头节点随机选择一个节点作为始节点(密文发送的初始节点)，始节点将密文发送给随机选择的下一个节点(中间节点)，中间节点接收始节点的密文并与自身的密文进行融合，再发送给下一个中间节点，如此继续，直至簇内所有节点完成密文融合，最后一个节点(终结点)把最终的融合结果发送给服务器.

节点ni的感知数据为di，椭圆曲线参数为E(Fp)，阶数为q，G是基点.节点ni选择一个随机数xi作为节点的私钥，然后计算节点ni的公钥Yi=xi×G.E(Fp)，q，G是群智感知中公共参数，并广播给簇内所有成员.

步骤2. 簇头随机选择一个成员节点ni(i=1,2,…,k)为始节点，并通知节点ni.以此，可以将节点分为始节点、中间节点和终节点.

3.2.3 解密

服务器接收到簇Ci发送过来的密文数据后，首先与簇成员协同合作计算Di，进而计算得到簇明文的融合结果Sumj，最后对所有簇数据进行融合得到任务区域内所有节点的数据融合结果Sum.每个簇Ci的密文解密步骤为：

步骤1. 服务器把簇融合密文中的Ca广播给簇内所有成员节点ni(i=1,2,…,k).

步骤2. 节点ni计算Di=xi×Ca并以密文传输的方式将Di传输给服务器.

(1)

式(1)的正确性证明：

证毕.

群智感知中所有数据通过无线传输，且参与节点具有动态性特征，数据传输过程中出现数据丢失是普遍情况.ECPPDA采用简化的超时重传机制来处理传输过程中数据丢失情况.重传机制的主要思想为：数据传输过程中，当数据接收者收到数据时要立刻返回一个确认信息给数据发送者，如果数据发送者的重传超过时间(retransmission time out， RTO)T，即在时间T内没有收到数据接收者的确认信息则默认为数据丢失，再次发送一份相同的数据.其中T=2TR，TR为数据在2个端点平均往返时间.简化的超时重传机制能够弱化网络传输中的各种复杂问题.

3.3 节点加入和节点失效

群智感知是一种特殊的无线传感器网络，它的节点由移动智能设备构成，而设备持有人由于自身原因离开任务区域或关闭移动智能设备，所以与传统的无线传感器网络相比，群智感知节点具有更显著的移动性特征，而现有的方法很少考虑群智感知节点移动性特征.基于此，ECPPDA考虑节点移动性特征，更加方便快捷处理节点的加入和节点失效情况.

3.3.1 节点加入

算法2.节点加入.

① 输入b;*其中b是加入任务的节点数*

② for (i=1;i

④Yi=xi×G;*计算节点ni公钥*

⑤Yi→NAS;

⑥ end for

⑦ if(b<γ×n+2)*判断加入节点数是否超过下限*

⑧ 查询并选择节点数量最少的簇Ci;

⑨ if (b+|Ci|<2×γ×n+4)*|Ci|为簇Ci内节点数量*

3.3.2 节点失效

簇Ci内节点ni失效有2种情形：

1) 主动失效即节点ni失效前向服务器发送离开信息.节点ni发送离开信息给服务器申请离开簇，服务器接收信息后查看簇Ci内剩余成员节点的数量，当剩余成员节点数量大于γ×n+2时，服务器计算新的簇公钥PCK=PCK-Yi，并随机选取簇头，更新簇Ci内剩余成员节点的簇信息.当剩余成员节点数量小于γ×n+2时，服务器解散簇Ci，然后将该簇剩余节点按照流程加入到其他簇.

2) 被动失效节点ni没有发送任何信息就离开簇.簇Ci的节点ni被动失效有2种假设：①假设节点ni在接收数据前失效，节点nj传输数据给节点ni，节点ni已经失效无法返回确认信息给节点nj.由于超时重传机制，节点nj将不停地传输数据直到重传次数达到设置的阀值(超时重传机制中最大重传次数)时节点ni没有发送返回信息则认为节点ni失效，然后节点nj向服务器发送信息表示节点ni失效，服务器接收信息后按照节点失效情形1)的方式更新簇信息.②假设节点ni在接收信息后失效，节点ni失效无法继续传输数据，因此服务器不能接收簇Ci的数据，服务器对簇Ci内节点进行失效查询(服务器向簇Ci内所有节点发送信息，没有响应的节点被确认为失效节点)，确定失效节点ni后服务器按照节点失效情形1的方式进行处理.

4 性能分析

本节ECPPDA算法与现有算法在应用环境、算法的安全性和复杂度等方面进行分析.

4.1 应用环境

应用环境主要从第三方是否确定可信、能否抗共谋攻击、节点动态性、数据丢失处理以及数据实用性等方面进行对比.从表1可以看出，与PDAIF[22](private data aggregation with integrity assurance and fault tolerance)相比，ECPPDA可以抵御共谋攻击且不需要可信的第三方平台；与CTPPSP[18](collusion-tolerable privacy-preserving sum and product calculation)相比，ECPPDA对数据丢失进行了处理，提高了方案的健壮性，且ECPPDA没有降低数据实用性且保留了节点移动性的特征.

Table 1 Comparison in Advantages and Disadvantages of Existing Schemes

4.2 安全性分析

本节对外部攻击、内部攻击和共谋攻击3方面进行安全性分析.

1) 外部攻击

2) 内部攻击

3) 共谋攻击

4.3 复杂度分析

群智感知中参与节点资源通常相对受限，而服务器资源比较丰富，所以本文主要考虑节点的资源消耗情况.ECPPDA算法主要由3个部分组成：初始化、数据传输、解密.初始化阶段节点经过计算得到公钥，然后传输公钥和分簇信息给服务器以完成节点分簇，所以初始阶段单个节点的时间与空间复杂度为O(1)，通信量为O(|G|)(|G|表示基点G的点长)，因此，群智感知网络在初始化阶段时间与空间复杂度为O(n)以及总通信量为O(n|G|)；数据传输阶段，每个节点需完成一次数据加密和密文融合，并将融合密文传输给下一节点，所以此该阶段单个节点的时间与空间复杂度分别为O(1)和O(|G|)，通信量为O(|G|)，该阶段网络总的时间与空间复杂度分别为O(n)和O(n|G|)，总通信量为O(n|G|)；解密阶段，节点通过服务器发送的聚合密文(Ca,Cb)计算得到Di并传输给服务器，所以解密阶段单个节点的时间与空间复杂度分别为O(1)和O(|G|)，以及通信量为O(|G|).综上分析，ECPPDA算法总的时间与空间复杂度分别为O(n)和O(n|G|)，群智感知网络总通信量为O(n|G|).

5 实验与结果实验评估

实验环境为Win7 OS，Intel Core i5 CPU和16 GB内存，采用GeoLife项目[18,24]中的公开数据点来对本文提出的方案进行评估.该公开数据点是由不同的GPS记录器每间隔5～10 m或者2～5 s采集的.随机选择中间的70个数据点，经过相应的坐标放大变换转化为2维相对坐标.为了对算法的通信量和隐私性能进行比较，下面对PDAIF[22]算法和ECPPDA算法进行仿真实验对比.

图2给出了2种算法在簇内节点数目k不同时节点的通信量比较，由于PDAIF算法通过未来消息缓冲机制保证容错性，节点每次传输的是2份数据，且在构建簇时预先在服务器缓存B个备份数据，所以ECPPDA方案可以有效地降低节点的通信消耗.

Fig. 2 Communication overhead with different number of nodes

图3给出了在恶意节点概率为10%时，不同簇节点数目下任意节点的数据隐私泄露概率，即攻击者通过第三方服务器和恶意参与者进行共谋攻击，解密单个节点数据的概率，由于PDAIF协议没有考虑共谋攻击，当簇内节点越多时，共谋攻击情况下单个节点数据隐私泄露的概率就越高.ECPPDA方案通过簇内所有成员共同协作进行密文解密的方式来抵御共谋攻击，其次通过数据加密抵御外部窃听攻击来保证数据的机密性，所以ECPPDA方案可以有效地保护节点数据的隐私.

Fig. 3 The leakage probability of single node

Fig. 4 The leakage probability of cluster

图4给出了簇内成员节点数目不同时(恶意节点概率为10%)，簇内所有节点的感知数据发生隐私泄露的概率，即攻击者通过服务器和恶意参与者进行共谋攻击，获得簇内诚实节点的感知数据的概率，由于PDAIF算法没有考虑共谋攻击，仅与左右邻居节点交换参数，因此当攻击者与目标节点的左右邻节点进行共谋就能获得该节点的感知数据.ECPPDA算法中每个节点数据的解密需要簇内所有节点协同合作，因此ECPPDA算法中节点数据发生隐私泄露的概率远远低于PDAIF算法，如图4所示.

由安全性分析可知只要簇内节点数量不小于k时，所有节点数据泄露概率可忽略不计，即使不满足节点数量要求，节点数据泄露的概率也较低，特别当簇内节点数量超过6时，节点数据发生隐私泄露概率几乎忽略不计.当簇内节点数为2时，单个节点数据泄露概率较高，因为只要有1个恶意节点就会导致数据泄露.如图5所示：

图6给出簇内成员节点数初始值k不同情况下，新加入节点数b不同时需要更新簇公钥的节点数量.由图6可知，当加入节点数量小于簇内成员节点数量时，需要更新的节点数量为簇内成员节点数，因为加入的节点会选择1个簇加入然后管理器需要更新该簇内原有节点的公钥.当加入节点数量大于簇内节点k值时，需要更新的节点数为0，因为加入节点会选择建立新簇，因此不会影响到原有节点.

6 总 结

群智感知中设计具有高安全、高效率、高质量隐私保护的融合数据方案是一个挑战性的问题.本文提出了一种具有隐私保护的融合数据算法ECPPDA.ECPPDA通过服务器构造多个簇，然后簇节点利用簇公钥加密数据并在簇内融合传输，直到最后1个簇节点将融合数据上传至服务器，服务器通过与簇的所有成员协同合作簇融合密文进行解密，并对所有簇的数据进行融合得到任务区域内所需的融合数据.数据传输过程中采用超时重传机制来解决数据丢失问题.由于密文是通过多方协同合作进行解密，所以ECPPDA可以抵御共谋攻击.理论分析和实验表明ECPPDA算法能够保护每个参与者数据的隐私性，显著降低了参与者的通信开销，并保证了数据的实用性.