格上基于同态加密的数据完整性验证方案

牛淑芬, ,,

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

0 概述

随着云计算的快速发展,越来越多的企业和个人选择将数据的存储和处理外包给云端的服务器,此举不仅可以减少个人或组织的存储和计算负担,而且可以随时随地地访问存储在云端的数据。但是,云存储服务提供商(Cloud Server Provider,CSP)被认为是半可信的,它有可能篡改或丢失用户储存的数据,由此带来的数据保密和隐私问题引起了业界的广泛关注。为保证数据的完整性和准确性,有研究者提出了验证CSP上数据完整性的有效方法。

文献[1-2]提出2个可证明安全性的数据持有性(Provable Data Possession,PDP)方案,但是这2个方案仅用于数据完整性验证,没有考虑到分布式存储系统与动态数据更新,且由于方案是基于RSA密码技术,算法中存在大量模指数的运算,因此方案中都存在极大的计算开销。文献[3-4]为实现数据更新操作提出改进方案,允许用户执行有限的数据块更新,但是在数据更新过程中,用户需要重新生成已保留的挑战,这不适用于大文件的情况。文献[5]改进PDP方案,用基于等级的认证跳表进行数据块的动态更新,但该方案不能满足独立数据块的完整性验证。文献[6]定义可恢复性证明(Proof of Retrievability,POR)的概念,提出可恢复性证明方案,该方案能保证数据的可恢复性与完整性,但是其支持的验证次数有限。文献[7]利用BLS签名提出一个POR方案,该方案虽然能满足公开审计,但是会泄漏用户隐私。文献[8]为减少用户的计算量,提出基于代数签名的完整性验证方案,该方案具有代数的性质且计算量较小。

上述数据完整性验证方案多数基于大整数分解和有限域上的离散对数等问题,运算速度较慢,且不能抵御量子攻击和亚指数攻击。格密码作为典型的后量子密码的代表,具有可抵抗量子攻击、运用小向量的线性运算、计算复杂度低、安全性基于格困难问题等优点。因此,本文提出一种格上基于同态加密的数据完整性验证方案,并通过性质与效率分析验证其性能。

1 相关知识

1.1 格

(1)

1.2 高斯分布

(2)

其中,ρσ,c(Λ)为正则化因子,c=0时,其简写为DΛ,σ。

1.3 格困难问题

LWE(Learning With Errors)问题是学习部分和错误问题的一个概括,具体定义如下。

以上描述的表达式中As+e可以简记为As,χ,相对应的LWE问题可以表示为LWEq,χ。量子规约算法证实了(平均情况下的)LWE问题的困难性等同于(最差情况下的)任意n维格上的SVP问题和SIVP问题[13]。

定义5一个多项式时间概率算法D的优势定义如下:

(4)

1.4 公钥同态加密

定义6(公钥同态加密方案) 方案由以下4个多项式时间算法组成:

1)ParamGen(1λ,h)→pp:λ是安全参数,h是一个密文安全更新的最大值。

2)KeyGen(1λ)→(pk,sk):pk是公钥,sk是私钥。

3)Enc(pk,m)→c:加密算法返回密文c。

4)Dec(sk,c)→m:解密算法返回消息m。

定义7[14]对于一个公钥同态加密方案,在敌手A和挑战者C之间有如下游戏:

1)系统建立,挑战者C产生pp和密钥对(pk,sk),将pp和pk发给敌手A。

2)挑战,敌手A选择2个相同长度的明文m0和m1提交给挑战者C,挑战者C随机返回b∈{0,1}并计算C*=Enc(pk,mb)。挑战密文C*被返回给敌手A,然后A生成一个比特b′。

2 系统模型

公钥同态加密方案的云存储体系结构如图1所示,其由用户、CSP和第三方审计(Third Party Auditor,TPA)3个部分组成[15]。用户拥有大量数据,需要保存在CSP中;CSP具有较强的存储空间和计算能力,为用户提供数据储存或计算服务;TPA被认为是可信的,可以代替用户对其存储在云中的数据执行完整性验证任务,且被认为没有与CSP或用户勾结的动机。

图1 公钥同态加密方案云存储体系结构

3 安全模型

为保证云存储中数据的完整性和准确性,验证者必须不定期地对存储在云服务器中的数据进行完整性验证。已有研究定义格上的数据完整性验证方案的安全模型为:在验证数据完整性时,不可能存在一个多项式敌手让验证者以不可忽略的概率接收所生成的证据。

本文将格上的同态加密数据完整性验证方案的安全模型描述为:敌手A扮演证明者角色,挑战者C扮演验证者角色,游戏基于如下假定,如果敌手A能在多项式时间范围内以不可忽略的概率产生一组证据p*且证据通过了验证,则挑战者C在敌手A的帮助下解决了LWE困难问题。

4 数据完整性验证方案

4.1 方案步骤

将文件F划分成n个数据块:f[1],f[2],…,f[n],用户将数据存储在云上,通常情况下认为云端是半可信的实体。数据完整性验证通常由用户、CSP和可信的TPA组成。验证方案包括以下4个阶段。

1)初始化设计阶段

用户首先通过执行KeyGen算法生成公私钥对(pk,sk),公钥pk用于生成数据块的验证标签,私钥sk用于验证数字标签的合法性。具体步骤如下:

然后,计算每个数据块的唯一标签T[i],具体步骤如下:

(1)计算加密数据块c[i]:

c1[i]=e1A+pe2,c2[i]=e1P+pe3+f[i]

c[i]=(c1[i],c2[i])

(2)计算加密属性块B[i]:

B1[i]=e1A+pe2

B2[i]=e1P+pe3+IDF‖i‖Vi

B[i]=(B1[i],B2[i])

(3)生成数据块标签T[i]:

T[i]=c[i]‖B[i]

(5)

2)挑战阶段

进行数据检测时,当TPA收到用户发给它的一个标签请求后,它将所需的标签返回,用户用私钥sk验证标签的合法性。然后,TPA从(1,2,…,n)中随机选取c(1≤c≤n)个数,依次放入集合csi*中,chal={csi*,g}(g=qs,i*=1,2,…,c)作为一个挑战信息,被发送给CSP。

3)证据生成阶段

就业内人士的分析来看，两家企业融合发展在解决磷肥企业绿色发展的问题上仍存在一定的困难，涉及资金、市场、政策等方面。但不管怎样说，开磷集团和瓮福集团的融合发展已经在路上，从绿色发展中要效益的大方向不会改变，我们也希望双方的融合能够开创一个生态环境、企业效益与农业发展共赢的良好局面。

CSP收到挑战信息后,根据获得的数据并利用式(6)计算认证标签u和σ。然后,CSP将证据P*=(u,σ)发送给TPA。

4)验证阶段

TPA接收到证据后,首先运用公钥pk和证据σ计算Enc(pk,σ),然后验证式(7)是否成立。若成立,证明数据完整性没有被破坏;否则,证明数据完整性遭到破坏。

qs·Enc(pk,σ)=u

(7)

在本文方案中,用户也可以进行数据完整性验证,具体过程为:

1)用户随机选取chal={csi*}(i*=1,2,…,c)作为一个挑战信息,发送给CSP。

3)用户接收到(u*,σ*)后,计算Dec(sk,u*)。

4)验证等式Dec(sk,u*)=σ*是否成立,若等式成立,表明存储的数据完整;否则,表明数据遭到破坏。

4.2 算法的正确性与安全性

为验证用户存储数据的完整性,需要根据接收到的挑战信息chal={csi*,g}和CSP生成的证据P*=(u,σ)来验证qs·Enc(pk,σ)=u等式是否成立。运用格上的加密算法计算如下:

c1=e1A+pe2

(8)

(e1A+pe2,e1P+pe3+f[cs1])+

(e1A+pe2,e1P+pe3+f[cs2])+…+

可见,qs·Enc(pk,σ)=u等式成立,即可以证明数据的完整性。

2)用户验证的正确性

用户计算Dec(sk,u*):

c1[i]S+c2[i]=(e1A+pe2)S+e1P+pe3+u*=

(13)

可见,Dec(sk,u*)=σ*等式成立,即可以证明数据的完整性。

3)安全性分析

5 算法性质与效率分析

5.1 同态操作

在本文方案的验证阶段,运用格上的加密算法对数据块的和进行整体加密后,判断生成的证据u(u是对每个数据块分别加密再求和)是否与qs·Enc(pk,σ)相等。若相等,证明数据完整性没有遭到破坏;否则,证明数据完整性遭到破坏。同态加密过程如下。

1)用户对2个数据块f[1]和f[2]及属性块分别进行加密:

c1[1]=e1A+pe2,c2[1]=e1P+pe3+f[1]

c[1]=(c1[1],c2[1])

c1[2]=e1A+pe2,c2[2]=e1P+pe3+f[2]

c[2]=(c1[2],c2[2])

B1[1]=e1A+pe2,B2[1]=e1P+pe3+IDF‖1‖V1

B[1]=(B1[1],B2[1])

B1[2]=e1A+pe2,B2[2]=e1P+pe3+IDF‖2‖V2

B[2]=(B1[2],B2[2])

然后生成如下的数据块标签并发送给CSP:

T[1]=c[1]‖B[1],T[2]=c[2]‖B[2]

2)CSP先把加密后的2个数据块标签相加,然后计算认证标签u和σ并发送给TPA:

σ=f[1]+f[2]

(16)

3)TPA对2个数据块的和σ进行整体加密:

c1[σ]=e1A+pe2

c2[σ]=e1P+pe3+σ

c[σ]=(c1[σ],c2[σ])=c[1]+c[2]

最后得到qs·c[σ]=qs·(c[1]+c[2])=g(c[1]+c[2])=u。

通过这种同态加密算法,可以减少用户、CSP和TPA间的通信开销以及客户端的计算代价。

5.2 动态操作

为满足各方面的需求,用户会不定期地对储存在云服务器中的数据进行更新,因此,必须对数据块进行动态操作。该过程由CSP计算,包括删除、修改和插入3个步骤。

1)删除:在f[1],f[2],…,f[n]中删除一个数据块后,后面所有的数据块索引向前移动一位。若要删除位置j上的数据块,则用户向CSP发送一个删除询问,当CSP接收到删除询问后,在指针j处删除数据块以及该数据块在CSP上相应的标签。

2)修改:在f[1],f[2],…,f[n]上修改一个数据块后,其余所有数据块的索引不变。如果用户需要修改位置j上的数据块,则他向CSP发送一个修改询问,当CSP接收到修改询问后,修改指针j的数据块以及该数据块相应的标签。

3)插入:在f[1],f[2],…,f[n]的j位置插入一个数据块前,后面数据块的指针依次往后移动一位,数据块数目变为n+1后插入一个新数据块。当CSP接收到用户发出的插入询问后,在指针j处插入数据块以及该数据块在CSP上相应的标签。

5.3 批处理

批处理可以实现对多个用户的数据同时进行完整性验证,提高了完整性验证的效率。TPA验证CSP中来自K个不同用户的数据文件Fk(1≤k≤K)的具体步骤如下:

2)在挑战阶段,假定每个数据文件都分成n个数据块,当 TPA收到用户发给它的一个标签请求后,它将所需的标签返回,用户用私钥sk验证数字标签的合法性。TPA随机选取chal={csi*,g}(g=qs,i*=1,2,…,c)作为一个挑战信息,将其发送给CSP。

3)在证据生成阶段,CSP收到挑战信息后,根据获得的数据并运用以下公式计算认证标签uk和σk。

然后,CSP返回k个证据Pk*=(uk,σk)给TPA。

qs·Enc(pk,σ)=u

(19)

5.4 效率分析

对本文方案和其他文献方案进行性能对比分析,结果如表1所示。其中,Pro.表示概率性验证,Det.表示确定性验证,n是所有块的数量,c是取样块的数量,s是在一个块中区间的数量。由表1可以看出,相比其他方案,本文方案可以实现公开验证、批处理、动态操作、同态操作,具有可行性和高效性。

表1 不同方案性能对比

6 结束语

本文提出一种格上基于同态加密的数据完整性验证方案。方案的高效性体现在其主要运用的是线性运算,无需模指数运算与对运算,可以大幅减少运算量、提高算法效率;安全性体现在它是基于LWE困难问题的;抗量子攻击性体现在其运用格上小向量的线性运算加密,计算复杂度低、效率高。但该方案中用户的计算量较大,且其密钥长度比基于双线性对的方案长,因此,减少方案的用户计算量并尽可能地缩短密钥长度是下一步的研究方向。