无安全信道的高效可搜索公钥加密方案*

李士强, 杨 波, 王 涛, 周彦伟

1.陕西师范大学计算机科学学院, 西安710119

2.密码科学技术国家重点实验室, 北京100878

3.中国科学院信息工程研究所信息安全国家重点实验室, 北京100093

1 引言

云计算自出现以来, 便迅速得到了人们的广泛关注.当云计算系统运算和处理大量的数据存储与管理时, 云计算系统便转变为一个云存储系统.简而言之, 云存储就是将存储资源放在云上供用户存取的一种新兴方案, 且使用者可以在任何时间、任何地点, 通过网络访问云上所存储的数据.在云存储带来巨大便利的同时, 数据的隐私安全问题成为了用户使用云的主要顾虑, 文献[1,2]对云计算中的安全需求进行了细致全面的分析和阐释.大多数用户是以明文的形式将数据上传到云服务器, 那么如果这部分数据被黑客截获, 或云端的管理员进行了违反职业道德的操作, 文件泄漏等安全隐患便不可避免.出于对数据隐私安全的保护诉求, 用户通常将数据加密后再上传至云端保存.然而, 由于现有的加密原语缺乏对密文相关操作的研究, 用户只能从云端下载加密数据, 对其解密后再进行搜索操作, 该方式不仅冗杂还造成了计算资源和网络带宽的浪费.

为了解决存储数据的保密性与搜索的高效性之间的矛盾, 2004年, Boneh 等人[3]提出了公钥可搜索加密(public key encryption with keyword search, PEKS)的概念.在PEKS 中, 用户让网关检索原始邮件中是否含有关键词, 与此同时, 网关不能得到邮件的任何信息.换句话说, 邮件网关可以搜索需要的关键词, 但是不会得到除关键词之外的任何信息.PEKS 具有广泛的实际应用价值, 如邮件路由[3,4]、电子健康记录系统[5,6]等相关工作.

在Boneh 等人的开创性工作之后, Water 等人[7]展示了PEKS 可以用来构造可搜索的加密审计日志.Golle 等人[8]提出了一种基于连接关键词的可搜索加密方案, 实现了对多个关键词进行搜索的功能.Boneh 和Waters[9]将PEKS 方案对关键词的搜索扩展到连接、子集和范围比较搜索, 支持对复杂逻辑结构进行搜索.此外, 相关文献[10,11]研究了如何将公钥可搜索加密与公钥加密进行安全的组合.由于关键词空间过小, 而且用户会频繁使用常见的关键词进行搜索, 所以文献[12–15]对PEKS 的关键词离线猜测攻击做出了研究.

然而, Boneh 等人[3]的方案存在着接收者与服务器之间需要由安全信道来传送陷门的缺陷, 安全信道的使用造成了计算资源上的浪费, 但若没有安全信道, 攻击者截获陷门便可进行搜索操作, 进而可以区分出与陷门匹配的加密消息.为解决此问题, Baek 等人[16]提出了无安全信道的公钥可搜索加密(secure-channel free public key encryption with keyword search, SCF-PEKS)方案.2007年, Gu 等人[17]基于双线性对运算给出了一个有趣的PEKS 方案, 该方案在加密过程中没有进行双线性对运算.之后, 他们进一步探究了安全信道的问题, 给出了一个高效的SCF-PEKS 方案.Rhee 等人[18]给出了新的方案, 增强了Baek 等人[16]方案的安全性模型, 允许攻击者获得非挑战密文与陷门的关系.后来Fang 等人[19]给出了首个在标准模型下安全的SCF-PEKS 方案, 但该方案检测算法过于复杂, 不够高效.Emura等人[20]展示了由匿名的IBE (identity-based encryption)机制可以构造通用的自适应的SCF-PEKS 方案.随后, Emura 和Rahman 等人拓展了Emura 等人[20]的工作, 使用划分密文结构的IBE 构造了更加高效的SCF-PEKS 方案[21].Rhee 等人[22]也提出两种转换模式, 用两个并行的或依次的IBE 机制来构造SCF-PEKS 方案.徐磊等人[23]基于静态假设提出了一个合数阶群下的PEKS 方案, 跟上述方案相比, 提升了现有方案的安全性能.

本文给出了一个在标准模型下安全的高效的SCF-PEKS 方案, 跟Fang 等人[19]在标准模型下构造的方案相比, 本文方案具有更简洁的构造, 且在静态假设下证明了安全性, 有着更好的安全性能.同文献[23]相比, 本文方案有着更小的陷门尺寸, 而且不需要安全信道的参与.基于判定性子群假设和DBDH假设(decisional bilinear Diffie-Hellman assumption), 我们证明了该方案在选择关键词的攻击下是安全的.

2 预备知识

2.1 合数阶双线性群

令G 表示双线性群生成算法, 该算法以安全参数λ 作为输入, 输出元组(N = p1p2p3,G,GT,e), 其中p1,p2,p3是三个互不相同的素数.

定义1 (合数阶双线性群)设G 和GT是阶为N =p1p2p3的循环群, g 是G 的生成元.e:G×G →GT是双线性映射, 满足下列性质:

(1)双线性: 对于任意g,h ∈G, a,b ∈ZN, 有e(ga,hb)=e(g,h)ab;

(2)非退化性: 存在g ∈G, 使得e(g,g)在GT中的阶是N.

进一步要求群G 和GT中的运算以及双线性运算e 都可以在多项式时间内完成.令G=Gp1Gp2Gp3,其中Gp1, Gp2和Gp3分别是群G 中阶为p1, p2和p3的子群.此外, 用表示Gpi{1}.注意到,若ij, hi∈Gpi, hj∈Gpj, 则e(hi,hj)是群GT中的单位元.

2.2 判定性子群假设

(1)给定一个群生成器G, 定义如下分布：

假设1若对于公开元组D, 存在一个任意概率多项式时间的敌手A, 那么敌手A 区分T0与T1的优势:=|Pr[A(D,T0)=1]−Pr[A(D,T1)=1]| 关于λ 是可忽略的.

(2)给定一个群生成器G, 定义如下分布：

假设2若对于公开元组D, 存在一个任意概率多项式时间的敌手A, 那么敌手A 区分T0与T1的优势:=|Pr[A(D,T0)=1]−Pr[A(D,T1)=1]| 关于λ 是可忽略的.

2.3 DBDH 假设

设G1和G2是阶为素数q 的循环群, g 是G1的生成元.设e:G1×G1→G2是双线性映射.定义敌手A 区分e(g,g)abc与e(g,g)r的优势为:

其中a,b,c,r ∈Zp是随机选取的.

2.4 核心引理

引理1[24]确定一个素数q 并定义那么对任意可进行最多q 次询问的敌手A, 我们有

其中RF:Zp→Zp为真随机函数.

2.5 SCF-PEKS 的概念

图1 SCF-PEKS 安全模型Figure 1 Security model of SCF-PEKS

如图1 所示, SCF-PEKS 的参与者主要涉及三方: 发送者(数据拥有者)、接收者R (数据使用者)、云服务器S.发送者生成和发送加密关键词.接收者对目标文件的关键词生成陷门, 并发送到云服务器.云服务器接收到发送者的加密关键词和接收者的陷门, 执行搜索操作, 最终将匹配的文件发送给接收者.

SCF-PEKS 的基本思想是令服务器保管它的公私钥对.为了生成PEKS 密文, 发送者同时使用服务器和接收者的公钥进行加密.然后, 接收者发送陷门去检索与加密关键词相关的数据, 但是在这个过程中,陷门可以通过公共信道发送.在接收到陷门后, 服务器使用它的私钥去检测与陷门匹配的PEKS 密文.下面我们定义这个模型.

定义2一个无安全信道的公钥可搜索加密(SCF-PEKS)方案由下列几个算法组成:

GlobalSetup(λ): 输入安全参数λ, 生成全局参数GP.

KeyGenServer(GP): 输入全局参数GP, 生成服务器S 的公私钥对(pkS,skS).

KeyGenReceiver(GP): 输入GP, 生成接收者R 的公私钥对(pkR,skR).

SCF-PEKS(GP,pkS,pkR,w): 输入GP, 接收者的公钥pkR, 服务器的公钥pkS以及关键词w, 生成关于关键词w 的PEKS 密文C.

Trapdoor(GP,skR,w): 输入GP, 接收者的私钥skR以及关键词w, 生成陷门Tw.

Test(GP,Tw,skS,C): 输入GP, 陷门Tw, 服务器的私钥skS以及w′的PEKS 密文C, 若w =w′,输出“yes”, 否则, 输出“no”.

2.6 安全性定义及攻击游戏的描述

定义3IND-SCF-CKA (indistinguishability of SCF-PEKS against chosen keyword attack)游戏.

设λ 为安全参数, A 为多项式时间敌手.我们考虑关于敌手A 和模拟者B 的两个游戏模型:

GameX: 假设A 是服务器.

Setup : 运行系统初始化算法GlobalSetup(λ), KeyGenServer(GP)和KeyGenReceiver(GP), 生成系统公共参数GP, 接收者和服务器的公私钥对(pkR,skR)、(pkS,skS).然后, B 将(pkS,skS)和pkR发送给A.

Queryphase1 : A 自适应的向模拟者B 询问关键词w ∈KSw的陷门, 然后, B 计算Tw=Trapdoor(GP,skR,w), 并返回给A.

Challenge: 一旦A 决定phase1 结束, 他向B 发送挑战关键词对(w0,w1), 唯一的要求是w0和w1不能出现在phase1 的讯问过程中.B 随机选取b ∈{0,1}, 并计算C∗= SCF-PEKS(GP,pkS,pkR,wb)作为挑战密文返回给A.

Queryphase2: A 继续进行关键词的陷门询问, 但是不能询问w0和w1.

Guess: A 输出猜测b′.如果b′=b, A 获得胜利.否则, A 失败.

定义A 攻破GameX 的优势为:

GameY: 假设A 是外部攻击者(包括接收者).

Setup : 运行系统初始化算法GlobalSetup(λ), KeyGenServer(GP)和KeyGenReceiver(GP), 生成系统公共参数GP, 接收者和服务器的公私钥对(pkR,skR)、(pkS,skS).然后, B 将(pkR,skR)和pkS发送给A.

Challenge:A 向B 发送目标关键词对(w0,w1).B 随机选取b ∈{0,1}, 并计算挑战密文C∗=SCFPEKS(GP,pkS,pkR,wb)返回给A.

Guess: A 输出猜测b′.如果b′=b, A 获得胜利.否则, A 失败.

定义A 攻破GameY 的优势为:

3 新的SCF-PEKS 方案

在本节中, 本文采用合数阶双线性对在标准模型下基于Wee[25]的IBE 方案构造SCF-PEKS 方案.

3.1 我们的构造

GlobalSetup(λ): 设λ 为安全参数, (N,G,GT,e)为双线性映射参数.选取一个抗碰撞单向哈希函数H :{0,1}∗→ZN, 令关键词空间为KSw=ZN.设全局参数为GP =(N,G,GT,e,H,KSw).

KeyGenServer(GP): 从中选择大于1 的随机数x, h ∈Gp1, 计算X =Y = e(X,h).输出pkS=(g1,h,Y), skS=x, 分别作为服务器的公私钥.

KeyGenReceiver(GP): 随机选取y ∈ZN, u ∈Gp1, g3∈输出pkR= (g1,e(g1,u)),skR=(y,u,g3), 分别作为接收者的公私钥.

SCF-PEKS(GP,pkS,pkR,w): 随机选取r,s ∈ZN, 计算U =t=H(e(X,h)s), V =W =e(g1,u)r.输出密文C =(U,V,W).

Trapdoor(GP,skR,w): 随机选取R3∈Gp3, 计算Tw=u1/(y+w)R3.返回Tw.

Test(GP,Tw,skS,C): 计算t=H(e(U,h)x), 检验e(Vt,Tw)=W.若等式成立, 输出“yes”, 否则,输出“no”.

方案正确性:

3.2 安全性证明

定理1如果判定性子群假设和DBDH 假设是困难的, 那么3.1 节方案是IND-SCF-CKA 安全的.

引理2如果判定性子群假设是困难的, 那么我们的方案在内部敌手的游戏中是语义安全的.

证明:设任意敌手A 至多可进行q 次询问, 存在与A 运行时间一致的敌手A1、A2, 使得

接下来我们进行一系列游戏, 并使用Advi表示敌手A 在Gamei中的优势.

Game0这是定义2 的真实攻击游戏.不失一般性, 我们做出如下假设:

(1)我们不会遇到这样一个关键词w, 使得w = y mod p1, 因为这样的关键词能直接构成的离散对数, 使判定性子群假设不成立.

(2)敌手的询问w1,··· ,wq∈ZN是不同的, 因此给定g3我们可以完美的随机化陷门Tw=u1/(y+w)R3.

(3)w1,··· ,wq在mod p2下是不同的; 给定wiwy∈ZN使得wi= wymod p2, 通过计算gcd(wi−wj,N)可以分解N.

我们将上述假设整合为一个整体, 从Game1 开始, 如果违背了第一个或第三个条件就中断游戏, 并且使用随机化处理重复的关键词询问.

Game1对(U0,V0,W0)←PEKS(pkS,pkR,w∗)做出如下改变:

随机选取C ∈Gp1, 输出(U0,V0,W0)=(U0,C,e(C,Tw∗)).

因为Game1 的改变对游戏成立的优势是不产生影响的, 所以,

其中negl(λ)是可忽略函数.

Game2将C 的分布由C ∈Gp1变为C ∈Gp1Gp2.构造一个攻击假设1 的敌手A1.

A1输入(g1,g3,C), 其中C ∈Gp1或者C ∈Gp1Gp2, 模拟敌手A 在Game1 中的实验: 诚实地运行KeyGenReceiver, 得到(y,u), 然后使用(y,u)回答所有的陷门询问, 同(U0,C,e(C,Tw∗))一样计算(U0,V,W0).

由2.2 节假设1 可知

Game3将Tw分布中的u1/(y+w)R3变为其中r1,···,rq+1,y1,···,yq+1∈ZN.然后进行一系列的子游戏, 定义为sub-game3.j.0 和sub-game3.j.1, j =1,2,··· ,q+1, 具体过程描述如下:

(1)在sub-game3.j.0 中, Tw的分布为

(2)在sub-game3.j.1 中, Tw的分布为

可以看出, Game2 对应着sub-game3.0.1,Game3 对应着sub-game3.q+1.1.

首先, 可以观察到, 在给定pkR和挑战密文下, y mod p2是完全隐藏的, 因此我们可以用yimod p2代替y mod p2.于是有

接下来, 对于j =1,··· ,q+1, 我们构造敌手A2.

A2输入(G,g1,g{2,3},g3,C,T), 其中C ∈Gp1Gp2, T = uR3∈Gp1Gp3或T =∈Gp1Gp2Gp3, 模拟敌手A 在Game3 中的实验:

(1)随机选取y ∈ZN, 公布pkR=(g1,e(g1,T),H), 其中e(g1,T)=e(g1,u);

(2)随机选取r1,··· ,rj−1,y1,··· ,yj−1∈ZN;

(3)模拟Trapdoor 输入w, 随机选取R′3∈Gp3, 输出

(4)用C 计算(U0,V0,W0).

观察到, 如果T = uR3, 那么这是sub-game3.j −1.1; 如果T =那么这是sub-game3.j.0.由2.2 节假设2 可得,

因此可以得到

Game4用RF(w)替换Tw中的其中RF : ZN→Zp2是真随机函数; 也就是说, Tw现在为由引理1 很容易得到

Game5用W0∈GT替换W0=e(C,Tw∗).

因此,

由以上游戏可得, 我们的方案在内部敌手的游戏中是语义安全的.

引理3如果DBDH 问题是困难的, 那么我们的方案在外部敌手的游戏中是语义安全的.

证明:假设存在多项式时间敌手A 可以攻击我们的方案, 我们构造一个可以进行DBDH 游戏的模拟者B.模拟过程如下:

挑战者设置阶为p1的群以及双线性映射其中分别为合数阶群G、GT的素数阶子群.输出DBDH 实例给B, B 的目标是要区分T =e(g1,g1)abc还是GT中的随机元素.

B 和A 进行以下游戏：

Setup : 设λ 为安全参数,(N,G,GT,e)为双线性映射参数.选取一个抗碰撞单向哈希函数H :{0,1}∗→ZN, 令关键词空间为KSw=ZN.设全局参数为GP =(N,G,GT,e,H,KSw).

Challenge : A 输出关键词对(w0,w1).作为回应, B 随机选取b ∈{0,1}, 设挑战关键词为w∗= wb, 随机选取r ∈ZN, U∗=t∗= H(T), V∗= g(y+w∗)r/t∗1, W∗= e(g1,u)r.挑战密文C∗=(U∗,V∗,W∗), 将C∗发送给A.

Guess : A 输出猜测b′.若b′= b 返回1, 意味着T = e(g1,g1)abc; 否则返回0, 意味着T 是GT中的随机元素.

容易看出, 若敌手A 能够攻破我们的方案, 那么模拟者B 便能攻破DBDH 假设, 所以我们的方案在外部敌手的游戏中是语义安全的.

由以上两个游戏可知, 我们的方案是IND-SCF-CKA 安全的.

4 性能对比

我们在下面列举了一些经典的可搜索加密方案, 配合本文方案进行性能对比.表1 中给出了各方案的安全模型、有无安全信道以及采用的困难性假设等信息.图2 给出了在Inter(R)Core(TM)i5-2450M CPU 2.5 GHz 4.00 GB RAM 的计算机下, 利用JPBC 库实现各算法所需要的平均时间.

表1 一些PEKS 方案对比分析数据表Table 1 Comparisons among various PEKS schemes

图2 方案每个算法的平均运行时间Figure 2 Average run time of each algorithm

我们发现, Gu 等人[17]的方案需要在随机谕言机模型下证明安全性, Gu 等人[17]和Fang 等人[19]的方案构造于素数阶群, 计算开销更少, 但是安全性证明采用了假设性较强的非静态假设.相较于素数阶的方案, 徐磊等人[23]和我们的方案在尽量少的损耗搜索速度的情况下, 实现了静态假设下的安全性, 有着更好的安全性能.与徐磊等人的方案相比, 我们的方案不需要安全信道的参与, 而且明显提升了陷门生成效率.

5 总结

在本文中, 我们讨论了云存储上的数据检索方法, 并提出了一个高效的SCF-PEKS 方案, 基于判定性子群假设和DBDH 假设, 该方案在标准模型下是IND-SCF-CKA 安全的.我们的方案保证了一定的搜索效率, 同时极大地提高了安全性能, 适用于实际中需要高安全性的云存储环境.下一阶段, 我们将基于静态假设在素数阶群下构造新的SCF-PEKS 方案, 在保证安全性能的基础上实现更高的计算效率.