基于WSN的全同态数据加密聚合方案

王彩芬,成玉丹,刘 超

(西北师范大学 计算机科学与工程学院,兰州 730070)

0 概述

无线传感器网络(Wireless Sensor Network,WSN)的基本结构有树形和簇形,均由若干个传感器节点和一个基站(Base Station,BS)组成,通信方式是无线链路通信,并且能够实时监测、感知和收集网络覆盖范围内的各种环境信息[1]。传感器能量受限,存储和计算能力较小,但基站有固定的能量来源,是整个网络的核心,存储空间大,计算能力强。

目前,国内外学者针对WSN中数据的安全传输问题进行了一定研究。早期采用基于对称加密机制的点到点数据聚合算法[2],该算法的优点是容易实现且方便快捷,但其会造成密钥和明文的泄露。为得到较好的安全性能,文献[3]提出2-DNF非对称密码系统,通过同态的加乘运算实现数据的聚合,但其在数据验证和防止抵赖等方面仍存在局限性。此后,又出现了多个针对该方案的改进方法。文献[4]提出能够抵御内部攻击的数据聚合方案。文献[5]提出在WSN中基于同态原语的数据聚合方案。文献[6]在数据的机密性和完整性上进行改进,提出基于同态加密的WSN数据融合的机密性和完整性方案。文献[7]提出基于同态加密的可验证隐私数据聚合方案。文献[5-7]对2-DNF非对称密码系统的计算效率和安全性能均做了改进,但仍有不足之处:文献[5]需要一个额外的可信第三方来分发保密干扰因子,而且方案的构造方式复杂;文献[6]在抵御内部攻击上存在局限性;文献[7]通过聚合器本身对每一个传感器节点分配干扰因子,计算复杂度高,并且其采用ElGamal方案加密隐私数据,仅满足了乘法同态性,并不满足全同态性。

针对上述方法的不足,本文在文献[7]的基础上,基于簇的网络结构提出WSN中全同态的数据加密聚合方案。采用具有全同态性的DGHV[8]方案加密隐私数据,同时将包含节点身份信息的签名嵌入到密文中,通过签名验证其正确性,使方案具有抵抗数据被篡改、追查并纠正错误数据的能力。本文方案以簇为单位,通过聚合器为簇内的传感器节点分发保密干扰因子,以避免由第三方带来的安全问题。

1 预备知识

1.1 符号和参数定义

给定安全参数λ,参数的设置为:ρ表示噪音长度,η表示私钥长度,γ表示公钥长度,τ表示公钥中整数的个数。为满足该方案的安全性,上述参数需满足如下条件:

1)ρ=ω(lbλ),使方案能够抵抗噪音的蛮力攻击。

2)η≥ρΘ(λlb2λ),使方案能够支持足够深的电路同态评估。

3)γ=ω(η2lbλ),使方案能阻止各种基于格的攻击,比如近似的最大公因子(Greatest Common Divisor,GCD)问题。

4)τ≥γ+(ωlbλ),使方案能够在GCD中使用剩余的哈希引理。

1.2 双线性映射

1)双线性:对任意的u,v∈G1,满足e(ua,vb)=e(u,v)ab。

2)非退化性:e(u,v)≠1G2,其中,1G2为G2中的单位元。

3)可计算性:对任意u,v∈G1,存在有效算法能够计算e(u,v)。

1.3 困难问题假设

定义3(GCD问题)[8]参数为ρ、η、γ,p为一个随机的ηbit的素数,x0=pq0,q0∈Z∩[0,2γ/p)。

求p的过程就是GCD问题。

1.4 全同态加密

定义4(全同态加密)[10]同态加密指在不解密密文的情况下,通过对密文执行操作来实现对明文的加密,且其结果一致,这里的全同态是指同时满足加法同态和乘法同态。全同态加密方案中包含4个函数:KeyGen(λ),Encrypt(pk,m),Decrypt(sk,c)和Evaluate(pk,C,c)。其具体操作如下:

1)KeyGen(λ):根据安全参数λ产生公私钥对(pk,sk)。

2)Encrypt(pk,m):在公钥pk下把明文m加密成密文c。

3)Decrypt(sk,c):用私钥sk解密密文c,得到明文m。

4)Evaluate(pk,C,c):输入一个公钥pk、电路C和一个密文元组c=〈c1,c2,…,ct〉,输出另一个密文元组c。

1.5 DGHV方案

文献[8]在Gentry方案的基础上提出基于整数的全同态加密方案DGHV。其中各函数具体操作如下:

3)Decrypt(sk,c):输出明文m←[[c]p]2。在解密过程中,首先通过密文模私钥p,再模2即可得到1 bit的明文。

4)Evaluate(pk,C,c1,c2,…,ct):输入公钥pk、电路C和t个密文c1,c2,…,ct,其中,ci=Encrypt(pk,mi),i=1,2,…,t。输出c*=Evaluate(pk,C,c1,c2,…,ct)且满足Decrypt(sk,c*)=C(m1,m2,…,mt)。该算法集中体现了全同态加密的技术优势,其通过门电路或者函数对密文进行任意操作后再解密,结果和操作明文的结果一致。

2 WSN中全同态数据加密方案

WSN的构建方式有多种,同时也产生了很多标准协议,如文献[11]提出的标准聚合协议和文献[12]中的网络构建方式。假定本文方案中的聚合器拥有足够的计算能力且是诚实但好奇的,即其可能会自主地做出一些错误的举动,但不会与其他实体实施共谋攻击[13]。同时,它能够有效地完成方案中涉及的签名验证和解密操作。

目前提出的基于WSN的同态加密聚合方案仅仅实现了加法同态或乘法同态,文献[7]以簇为单位分发干扰因子,但是每一个传感器拥有独立的干扰因子在很大程度上增加了方案的计算复杂度。由干扰因子的作用可知,它不涉及隐私信息,所以对它的改进主要是提高运算效率,降低计算复杂度。因此,本文在文献[7]的基础上,以簇为网络结构,提出基于WSN的全同态数据加密聚合算法,实现隐私数据的加法和乘法同态。在干扰因子的分发过程中,每一个簇内的传感器节点拥有相同的干扰因子,这样既保证了方案能够抵抗内部攻击,又在很大程度上降低了计算复杂度。

2.1 网络模型

本文采用的网络模型是基于簇的网络结构[14],如图1所示。该结构的优点是将簇内节点的信息收集起来,统一向上一级节点传送,能够节省通信开销,增强扩展性。网络模型结构包含3类角色:基站BS,聚合器Agg和传感器节点。整个网络由多个非重叠的簇组成,每个簇中包含一个聚合器(簇头)和n个传感器节点。簇头的功能是给簇内的每一个传感器节点分发干扰因子π和身份标识ID,π只分发一次,即每一个传感器节点具有相同的干扰因子,同时从传感器节点接收加密的数据,将其聚合验证后传给BS;每一个传感器节点将接收到的数据采用带有干扰因子的DGHV方案加密,用自己的身份标识签名,然后将密文发送给聚合器。

图1 基于簇的网络拓扑

2.2 方案设计

在基于簇的WSN构建完成后,加密聚合方案主要包括3个基本过程:系统建立阶段,加密签名阶段和验证聚合阶段。在系统建立阶段,聚合器作为整个簇的核心,为每一个传感器节点分配身份标识ID、公私钥和干扰因子π;在加密签名阶段,传感器节点收集信息,利用公私钥和π对消息加密,用ID对消息签名;在验证聚合阶段,聚合器发出消息聚合的命令,每一个传感器节点将加密的消息发送给聚合器,聚合器完成数据的聚合并进行验证,若验证成功,则进行相应操作得到消息,若验证失败,则检测每一个节点的数据,并要求数据传输错误的节点重新传输数据。

2.2.1 系统建立阶段

设在每一个簇内由一个聚合器控制着n个传感器节点Ui(i=0,1,…,n-1)。聚合器作为密钥生成中心,通过DGHV[8]方案和DF[15]方案为簇内的每一个节点分配公私钥和干扰因子。该阶段的2个基本操作如下:

1)密钥生成阶段:

(1)聚合器对控制的每一个传感器节点分配身份标识IDi(i=0,1,…,n-1)。

(2)设置安全参数λ。

(4)生成N阶乘法循环群G。

(5)在G中取生成元g。

(6)发布公钥PK={pk,g},私钥SK=p。

2)分配保密干扰因子πk(k=0,1,…,n-1,表示聚合器的个数)。

保密干扰因子的生成和分发过程是保密的,由于它不涉及核心消息mi,因此对它的保密要求比较低,而对其效率的要求较高。本文采用与DF[15]方案相同的分配方式,若聚合器为每一个传感器都分配保密干扰因子,会增加计算复杂度。为降低计算复杂度,本文采用基于簇的传感器网络。假设以n个传感器节点为一个簇,每一个簇分配一个保密干扰因子,即n个节点具有相同的干扰因子。聚合器(簇头)的具体分配过程如下:

2.2.2 加密签名阶段

当传感器节点Ui(i=0,1,…,n-1)收到聚合器发布的数据聚合的命令时,进行数据加密签名的操作,在此过程中,传感器节点可以对多次加密的数据实现全同态操作,再用身份标识IDi签名,然后上传给聚合器。具体过程如下:

4)计算签名σi=H(ci‖IDi)p及yi=gp。

5)将{ci,yi,σi}(i=0,1,…,n-1)发送至聚合器。

2.2.3 验证聚合阶段

在验证聚合阶段,聚合器首先对上传的数据进行聚合,然后利用双线性映射验证其正确性,若验证正确,则可以计算得到聚合的消息,具体操作如下:

1)聚合器接收所有传感器节点Ui传来的数据{ci,yi,σi}(i=0,1,…,n-1)。

2.3 方案的正确性分析

本文方案的正确性分析具体如下:

1)签名验证的正确性:

2)聚合解密的正确性:

3 方案性能分析

3.1 全同态性分析

由于本文方案的加密算法运用了基于整数的全同态加密方案DGHV,因此其全同态性的详细证明过程可参考文献[8]。

3.2 保密干扰因子的安全性分析

在本文方案中,保密干扰因子πk(k=0,1,…,n-1表示聚合器的个数)是以簇为单位分配的,作用是在保证安全的基础上提高方案的效率,其分配方式根据DF[15]方案构造,故本文方案中保密干扰因子安全性的详细证明过程可参考文献[15]。

3.3 基于AGCD问题的安全性证明

本文方案的安全性基于近似公因子(AGCD)难题和计算版本的Co-Diffie-Hellman问题。Co-Diffie-Hellman问题作为一些密码系统困难问题的基础,已经得到了证明和广泛应用。本文对基于AGCD问题的安全性进行证明,主要证明思路是使用攻击算法A来构造求解困难问题的算法B,该过程包括4个步骤:1)利用困难问题产生方案的公钥;2)利用A构造求解p的商的最小比特位;3)执行Binary-GCD算法;4)恢复p。

定理1在第2.1节的方案中,固定参数(ρ,η,γ,τ)与安全系数λ。任意的攻击者A以优势ε攻击加密方案,都可以转化成求解器B以至少ε/2优势求解参数为(ρ,η,γ)的近似AGCD问题。B的运行时间是tA、λ和1/ε的多项式,其中,tA是A的运行时间。

证明攻击者A以ε的优势攻击本文方案,即A以ε的优势输入公钥和密文(由本文方案的算法获得公钥和密文),正确输出明文的概率至少是1/2+ε。

在参数为ρ、η、γ时,构造求解近似AGCD困难问题的求解器B,对于随机选取的ηbit的奇整数p,求解器B需要从Dr,ρ(p)分布中获得多个样本来求解目标p。步骤如下:

步骤1创建公钥。首先,求解器B为方案创建一个公钥pk=〈x0,x1,…,xτ〉。

步骤2利用最低有效位(Least Significant Bit,LSB)子程序求解p的近似倍数的最小比特位。B调用以下子程序:

子程序Learn-LSB(z,pk)

输入z∈[0,2γ),|rp(z)|<2ρ,公钥pk=〈x0,x1,…,xτ〉

输出qp(z)的最低有效位

1.For i=1 to poly(λ)/ε do://ε是A的整体优势;

4.调用A访问随机预言机得到ai←A(pk,ci);

5.设置bi←ai⊕parity(z)⊕mi;

步骤3运用Binary-GCD算法[8]计算p。给定任意的2个整数z1=qp(z1)·p+rp(z1)和z2=qp(z2)·p+rp(z2)(rp(zi)<

综上,若随机预言机能计算出[qp(z)]2(z的噪声远小于p),则B就可以恢复p。接下来分析在随机预言机模型下B成功的概率。

由步骤1可得,求解器B产生公钥的分布与本文方案产生的正确分布相同,如文献[8]所述:如果A猜测成功的可能性为ε,则敌方猜测成功的可能性至少为ε/2。如果固定p,在对应的公钥pk下A猜测成功的可能性至少是ε/4,敌方猜测成功的可能性至少为ε/4。在子程序Learn-LSB(z,pk)的步骤4中,A猜测成功的可能性至少是ε/4-negl,对于该子程序而言,返回正确值的可能性很大,B有很大概率恢复出p。对于这样的p,公钥pk下的概率ε/4-negl也成立,则求解器B在运行中恢复p的概率至少是1/2(ε/4-negl),B重复调用算法(8/ε)ω(lbλ)次,此时B的时间复杂度是poly(λ,1/ε),因此,求解器B成功恢复p的概率至少是ε/2。至此,定理1证明完毕,本文方案是IND-CPA安全的。

3.4 网络内部攻击分析

网络内部的攻击者可以在数据聚合前后的2个阶段获得数据。从这2个方面进行如下分析:

1)在聚合前,内部攻击者要获得明文消息mi,在得到传感器的加密私钥p的同时,也要得到干扰因子πk。由于本文方案以簇为单位分配干扰因子,因此簇内每一个节点的干扰因子都相同。为获知内部攻击者是否会进行重复性攻击,作如下证明:在一个簇内随机选取一个节点的2个消息m1、m2,加密之后的密文为c1、c2。

(1)

(2)

式(1)、式(2)相减并化简可得:

(3)

对于式(3),分2种情况讨论:

(1)m1-m2的值未知,则不能得到干扰因子πk。

(2)假设m1-m2的值已知,在N阶乘法循环群内求解πk属于离散对数困难问题,故也不能得到干扰因子πk。因此,πk的获取是困难的。

由以上分析可得,本文方案可有效抵御来自网络内部的攻击。

4 不同方案性能对比

表1所示为文献[4,7,14]中的经典方案和本文方案的主要性能对比。其中,同态性指方案是否能实现全同态性。

表1 4种方案性能比较

由表1可以看出,与文献[4]方案相比,本文方案无需可信第三方并且满足全同态性;与文献[7]方案相比,本文方案时间复杂度更低且能够进行全同态运算;与文献[14]方案相比,本文方案能够抵御内部网络攻击。因此,与已有方案相比,本文方案在无需可信第三方的情况下,时间复杂度较低且满足全同态性。

5 结束语

为改善WSN中的数据聚合效果,本文提出一种基于全同态加密的数据聚合方案,该方案具有如下优点:1)采用全同态加密方案,聚合器无需对密文解密就可以进行全同态运算;2)聚合器没有解密密钥,每个簇内的传感器都有保密因子,并且不需要可信第三方来分配,因此,该方案既可以抵御内部攻击也能节约存储空间;3)以簇为单位分配保密干扰因子,将计算复杂度降低到O(1)。实验结果验证了该方案的性能优越性。下一步考虑改进公钥产生算法并缩短公钥的长度,以减少本文算法的运行时间,提高运算效率。