基于身份的抗内部猜测攻击的关键字搜索方案

郭丽峰,李智豪

(山西大学 计算机与信息技术学院,山西 太原 030006)

0 引言

随着信息和网络的发展,由于云计算提供给用户便利的数据存储和高效的处理服务,越来越多的个人和企业趋向将数据上传到云服务器,由其来处理数据。但是云服务器并不完全可信。在通信过程中,恶意的云服务器可能非法窃取用户的隐私,导致信息泄露。所以数据拥有者需要将数据加密后再上传到云平台,以密文的形式保障数据的安全性,但同时也加大了数据搜索的难度。

Boneh等[1]在2004年第一次提出了带关键字搜索的公钥加密方案(public key encryption with keyword search,PEKS),它的思想主要是发送者首先加密数据和关键字,并上传至云服务器。此后接收者发送一个由关键字生成的陷门给云服务器,最后云服务器执行关键字密文和陷门的匹配算法,成功后再将密文数据发送给接收方,此过程云服务器不能获得关键字和密文数据的任何信息。但是在该过程中需要建立接收者和服务器之间的安全信道。Baek等[2]人提出了无安全信道的可搜索加密方案(secure-channel free PEKS,SCF-PEKS),其方法是通过引入服务器的公私钥对来消除安全信道,只有指定的服务器才能够对关键字密文与陷门进行匹配。此后Rhee等[3-5]提高了Baek的安全模型,并提出了一系列指定检验者的关键字搜索方案(designated test PEKS,dPEKS)。此前的方案都是在随机谕言模型下证明安全的。Fang等[6]基于Gentry[7]的基于身份加密方案构造了标准模型下的带关键字搜索方案。

2006年,Byun等[8]第一次提出离线的关键字猜测攻击(KGA)的概念,并对Boneh的方案进行了攻击,他的攻击依据是关键字个数相对比较有限(约有225 000个),可以使用穷举搜索的方法来进行攻击。Rhee等[5]提出了陷门不可区分性,证明陷门不区分性是抵抗关键字猜测攻击的充分条件,并提出了一个具体的方案。Fang等[9]在非对称双线性映射下构造出一个可抵抗外部敌手进行关键字猜测攻击的方案,并在标准模型下证明安全性。

2015年,Shao等[10]在Fang等[9]的方案中引入了发送者的身份,并通过RSA算法对身份进行签名,其不允许非法生成的密文进行匹配测试,之后,接收者通过认证机构认证身份信息。此方案抵抗了内部的关键字猜测攻击,但该方案依赖与签名技术和认证机构。2017年,Huang等[11]、Lu等[12]、Sun等[13]引入了发送者的公私钥,恶意的服务器和外部的攻击者因无法掌握发送者的私钥而不能生成合法的关键字密文,但是它们的方案有个共同的问题,增加了发送者的计算负担。

1 基础知识

定义1双线性映射

设p是一素数,G1和G2是两个阶为p的循环群,g是G1上的一个生成元,双线性映射e:G1×G1→G2,若e满足如下的性质:

(1) 双线性:对于∀a,b∈Zp,有e(ga,gb)=e(g,g)ab成立;

(2) 非退化性:∃h∈G1,使得e(h,h)≠1G2,其中1G2是G2中的单位元;

(3) 可计算性:对于∀g,h∈G1,存在一个有效的算法计算e(g,h)。

定义2判定Bilinear Diffie-Hellman Inversion(BDHI)问题

给定一个三元组(g,gx,Z),其中随机选取x∈Zp,g是G1中的一个生成元,要求判断Z=e(g,g)1/x是否成立。

定义3判定Bilinear Diffie-Hellman(DBDH)问题

给定一个五元组(g,gx,gy,gz,Z),其中随机选取x,y,z∈Zp,g是G1中的一个生成元,要求判断Z=e(g,g)xyz是否成立。

定义4判定Division Diffie-Hellman(DDH)问题

给定一个四元组(g,gx,gy,Z),其中随机选取x,y∈Zp,g是G1中的一个生成元,要求判断Z=gx/y是否成立。

2 无安全信道的关键字搜索方案分析

2.1 Baek等[2]的模型描述

(1)Setup(1k)→{GP}:输入安全参数k,产生全局参数GP。

(2)KeyGenS(GP)→{pkS,skS}:输入全局参数GP,产生服务器的公私钥pkS,skS。

(3)KeyGenR(GP)→{pkR,skR}:输入全局参数GP,产生接收者的公私钥pkR,skR。

(4)PEKS(GP,pkS,pkR,w)→CT:发送者对关键字w进行加密产生密文CT,并发送给云服务器。

(5)Trapdoor(GP,w,skR,pkS)→Tw:接受者对关键字w进行加密产生陷门Tw,并发送给云服务器。

(6)Test(GP,CT,Tw,pkR,sks)→yes,no:云服务器进行匹配算法,判断密文CT和陷门Tw是否包含相同的关键字。

2.2 内部的关键字猜测攻击分析

当敌手是一个恶意的云服务器时,它可以执行匹配算法。想要抵抗内部的关键字猜测攻击需要满足两个条件,一是陷门本身不能泄露关键字的信息,二是服务器自己不能产生合法的密文。Shao等[10]在Fang等[9]的方案的基础上进行了改进,通过对发送者的身份进行数字签名达到服务器不能产生合法密文的目的。但是Lu等[12]指出Fang等[9]的方案陷门本身会泄露关键字的信息,即当敌手是恶意的云服务器时,Fang等[9]的方案不满足陷门不可区分性。在Huang等[11]的方案中,在产生关键字密文时引入了发送者的私钥,进行授权加密,但是在其方案中,陷门是固定的,不具有随机性。且发送者也可以计算出该陷门,他们的方案虽然可以抵抗服务器进行关键字猜测攻击,但是引入了一个新的敌手——发送者。

为了抵抗服务器进行关键字猜测攻击,大部分的方案都增加了发送者的计算量,我们引入了一个身份管理服务器对发送者的身份和关键字进行重加密来减轻发送者的计算量,另外,在接收者计算陷门时,包含了身份管理服务器的公钥来保障了陷门不可区分性。

3 基于身份的抗内部关键字猜测攻击的关键字搜索方案

3.1 系统模型

基于身份的关键字搜索方案有四个实体,如图1,分别是数据发送者(DS),身份管理服务器(MS),云存储服务器(CS),数据接收者(DR)。

DS首先对明文数据和关键字w进行加密。随后把加密的明文数据发送给CS,把预加密的关键字

发送给MS。

MS首先对发送者进行身份认证,若发送者身份是合法的。则对关键字和发送者身份id进行重加密,并将结果发送给CS。

DR对关键字和发送者的身份id进行加密生成陷门,并发送给CS。

CS进行匹配算法,若成功则把关键字对应的密文发送给DR。

在此过程中,MS,CS都不会得到关于关键字的任何信息。

3.2 方案的构造

在我们设计的基于身份的关键字搜索方案中,只关注关键字加密的部分,具体方案如下:

(1)Setup(1k)→{GP}:参数生成算法进行如下设置:选择两个阶为p的两个循环群G1和GT,双线性映射e:G1×G1→GT,g是G1中的一个生成元,选择抗碰撞的哈希函数H1:{0,1}*→G1,H2:{0,1}*→G1,H3:G2→{0,1}λ。输出全局参数GP={G1,GT,p,g,H1,H2,H3}。

图1 系统模型Fig.1 System model

3.3 计算一致性验证

H3[e(H1(w),gt)e(H1(id)yβ,gα)]=

H3[ct2e(H2(id)skMβ,pkS)]=C4。

4 安全性证明

我们的安全目标是要求身份管理服务器,云存储服务器,外部的攻击者都不能获得关于关键字的任何信息,包括进行选择关键字攻击(IND-CKA)和关键字猜测攻击(IND-KGA)。

引理1 假设1-BDHI问题是困难的,当敌手是一个恶意云服务器,我们的方案是抵抗选择关键字攻击(IND-CKA)安全的。

证明假设敌手A1是云存储服务器时,它最多进行qT次陷门询问,且有ε的优势去攻击方案,则我们可以构造一个算法B有忽略的优势ε/eqT去解决1-BDHI问题。

(1)敌手A1首先宣布一个想要挑战的身份id*。

作为陷门进行回复。

(7)猜测。敌手A1输出它的猜测δ′∈{0,1},如果δ′=δ,输出1,即Z=e(g,g)1/x。否则输出0。

则

Pr[δ′=δ]=Pr[δ′=δ∧abt]+

Pr[δ′=δ∧abt]=

Pr[δ′=δ|abt]Pr[abt]+

Pr[δ′=δ|abt]Pr[abt]=

引理2 假设DBDH问题是困难的,当敌手是一个外部攻击者(包括一个恶意的接收者),则我们的方案是抵抗选择关键字攻击(IND-CKA)安全的。

证明假设敌手A2是一个,它有ε的优势去攻击方案。我们可以构造一个算法B也有ε的优势去解决DBDH问题。

(1)敌手A2首先宣布一个想要挑战的身份id*。

(4)密文询问1。敌手A2对任意的关键字和任意身份(wi,idj)进行密文询问。算法B运行加密算法产生密文CT并发送给敌手A2。

(7)猜测。敌手A2输出它的猜测δ′∈{0,1},如果δ′=δ,输出1,即Z=e(g,g)abc。否则输出0。

引理3 假设DDH问题是困难的,当敌手是一个恶意的云存储服务器时,则我们的方案是抵抗关键字猜测攻击(IND-KGA)安全的。

证明假设敌手A3是一个,它最多进行qT次陷门询问,且有ε的优势去攻击方案。我们可以构造一个算法B有ε/eqT的优势去解决DDH问题。

(1)敌手A3首先宣布一个想要挑战的身份id*。

(7)猜测。敌手A3输出它的猜测δ′∈{0,1},如果δ′=δ,输出1,即Z=gab。否则输出0。

概率分析 和定理1的情况类似,我们可得算法B也有ε/eqT的优势去解决DDH问题。

引理4 假设1-BDHI问题是困难的,当敌手是一个恶意的身份管理服务器,则我们的方案是抵抗选择关键字攻击(IND-CKA)安全的。

5 性能分析

本文实现了可抵抗内部关键字猜测攻击的关键字搜索方案。我们和引入发送者公私钥的方案[12]进行比较,如表1所示。其中P表示指数运算,E表示双线性对运算,H代表Hash运算,n是关键字w的二进制展开位数。在表一中,预加密关键字过程是发送者执行的,在我们的方案中,发送者只需要计算2个指数运算,1个双线性对运算和1个Hash运算,对比文献[12],效率得到很大的提高。

表1 方案性能对比

6 结论

本文对原有的带关键字搜索的公钥加密方案进行改进,引入发送者的身份和一个身份管理服务器,身份管理服务器对所有发送者的身份进行授权,一个抵抗恶意的云存储服务器因其不能产生合法的密文从而不能进行关键字猜测攻击和选择关键字攻击。此外,我们还给出了完整的安全性证明,下一步的工作是把方案部署到云平台上,使其应用到医疗和金融等领域。