电子邮件系统中指定服务器的关键字搜索加密方案

牛淑芬,杨平平,谢亚亚,王彩芬,杜小妮

(西北师范大学 a.计算机科学与工程学院; b.数学与统计学院,兰州 730070)

0 概述

近年来,随着云计算技术[1]的迅速发展,基于网上在线存储的云存储服务得到广泛关注。将本地数据迁移到云端服务器可以节省本地数据管理开销、降低系统开发及维护成本[2],但同时也产生了数据泄露、个人隐私信息无法得到有效保护等安全问题。此外,为了确保数据的机密性,数据拥有者在上传数据至云端服务器前会对其进行加密,导致数据使用者难以在加密文件中快速查找信息。

为解决上述问题,研究人员提出可搜索加密 (Searchable Encryption,SE)技术[3-5]。可搜索加密体制分为对称可搜索加密体制和公钥可搜索加密体制[3]。文献[4]提出对称可搜索加密方案,随后文献[6]提出公钥关键字搜索加密(Public Key Encryption with Keyword Search,PEKS)概念,并结合公钥加密技术设计出基于双线性对的构造方案。该方案以邮件路由为应用场景以便邮件服务器对邮件进行分发,数据发送者从待发送的电子邮件中通过检索关键字与使用数据接收者公钥对关键字和电子邮件进行加密,数据接收者生成陷门并向邮件存储服务器发送相应陷门,邮件存储服务器搜索与其匹配的关键字密文,并将包含关键字的邮件密文返回给数据接收者[3]。

在加密的电子邮件系统中,带关键字搜索的公钥加密方案是在不解密情况下搜索加密邮件的有效手段,但是其存在安全问题。文献[7]指出PEKS方案和结合域关键字搜索的公钥加密(Public Key Encryption with Conjunctive Field Keyword Search,PECKS)方案[8]中存在离线关键字猜测攻击(Keyword Guessing Attack,KGA)风险。恶意敌手能在离线状态下采用穷举法搜索候选关键字[9],并分别对其进行验证。研究人员通过实验发现,该攻击具有可行性。如果邮件服务器变得恶意,其可以通过离线启动KGA从用户邮件中恢复信息[10]。文献[11]研究了基于身份的关键字搜索加密(Identity Based Encryption with Keyword Search,IBEKS)方案,并对IBEKS方案进行定义。该文献指出,数据发送者使用基于身份的加密 (Identity-Based Encryption,IBE)方法对电子邮件进行加密,并使用IBEKS方案加密关键字,然后将加密的电子邮件和关键字上传到邮件存储服务器[12-13],数据接收者为检索包含某个关键字的电子邮件,委托邮件服务器提供陷门搜索加密的关键字,邮件服务器将与加密关键字关联的电子邮件返回给数据接收者作为搜索结果。但是由于IBEKS方案无法抵抗内部离线关键字猜测攻击[14],同时还隐藏了外部敌手搜索模式,因此文献[15]提出一种指定服务器的基于身份关键字搜索加密(designated Server Identity-Based Encryption with Keyword Search,dIBEKS)方案,然而文献[16]指出该方案不能满足关键字密文的不可区分性。

为提高dIBEKS方案的安全性,本文提出一种指定邮件服务器的基于身份认证关键字搜索加密(designated Server Identity-Based Authenticated Encryption with Keyword Search,dIBAEKS)方案。在未知数据发送者私钥的情况下,攻击者难以伪造数据发送者加密的关键字,从而无法进行离线关键字猜测攻击,对该方案适应性选择消息攻击的关键字密文不可区分性、陷门不可区分性和离线猜测攻击的安全性进行验证。

1 基础知识

1.1 双线性对

令(G1,+)和(G2,×)为2个阶均为大素数q的循环群,p是群G1的生成元。

定义1(双线性对[17]) 循环群上线性映射e:G1×G1→G2具有以下性质:

2)非退化性。存在P,Q∈G1,满足e(P,Q)≠1。

3)可计算性。对于任意P,Q∈G1,存在1个有效算法计算e(P,Q)。

1.2 困难性问题假设

本文方案采用双线性Diffie-Hellman计算(Computational Bilinear Diffie-Hellman,CBDH)假设[18]。

AdvCBDH(R)=Pr[R(P,aP,bP)=e(P,P)ab]

(1)

其中,e(P,P)ab的概率优势可以忽略。

2 系统模型和安全模型

2.1 系统模型

图1为dIBAEKS方案的电子邮件系统模型。该模型主要包括数据发送者A、数据接收者B、指定邮件服务器S[19]以及可信任的密钥生成中心(Private Key Generator,PKG)4个实体。其中:数据发送者A对数据文件进行加密,使用其私钥skA为加密的数据文件生成关键字索引Cw,并将数据密文与关键字索引Cw共同上传到指定邮件服务器S;数据接收者B用其私钥skB生成陷门Tw,并将陷门Tw发送给指定邮件服务器S进行搜索服务请求;指定邮件服务器S为加密的电子邮件提供存储服务并利用其私钥sks完成数据接收者B的搜索请求;可信任的密钥生成中心PKG主要负责生成主密钥s和系统公共参数Params,并根据用户身份信息生成用户密钥。

图1 dIBAEKS方案的电子邮件系统模型Fig.1 Email system model of dIBAEKS scheme

dIBAEKS方案由以下5个概率多项式时间算法组成:

1)系统建立算法Setup(λ):给定1个安全参数λ,产生PKG的主密钥s和系统公共参数Params。

2)密钥生成算法KeyGen(Params,s,IDA,IDB,IDS):输入系统公共参数Params、主密钥s和身份信息(IDA、IDB、IDS),PKG生成各身份对应的密钥(pkA,skA)、(pkB,skB)和(pkS,skS)。

3)关键字加密算法dIBAEKS(Params,w,skA,IDB,IDS):对于关键字w,数据发送者结合数据接收者的身份信息IDB和指定邮件服务器的身份信息IDS,计算生成密文Cw。

4)陷门生成函数dTrapdoor(Params,w′,IDA,IDS,skB):对于给定搜索的关键字w′,数据接收者使用自身私钥skB、数据发送者身份信息IDA以及指定邮件存储服务器身份信息IDS,生成相对应的搜索陷门Tw′,然后数据接收者将Tw′发送给指定邮件服务器进行搜索请求。

5)验证算法dTest(Params,skS,Cw,Tw′):指定邮件服务器利用自身私钥skS,与接收的Cw和Tw′进行验证,如果验证通过,则输出“True”并返回给数据接收者Cw所对应的加密邮件;否则,输出“False”。

2.2 安全模型

dIBAEKS方案的安全性由关键字密文不可区分性、陷门不可区分性以及抗离线关键字猜测攻击构成。

2.2.1 关键字密文不可区分性

以敌手A1和挑战者F的交互游戏1来定义dIBAEKS方案的关键字密文不可区分性。假设敌手A1是外部攻击者。

1)系统初始化。挑战者F执行Setup算法产生系统参数并发送给敌手A1。

2)询问1。外部攻击者A1向挑战者F进行以下询问:

(1)密钥询问。当敌手A1向挑战者F进行密钥询问时,挑战者F调用KeyGen算法并返回数据接收者私钥skB和指定邮件服务器私钥skS给敌手A1。

(2)陷门询问。敌手A1将数据发送者身份信息IDA、数据接收者身份信息IDB和关键字w发送给挑战者F,挑战者F调用dTrapdoor算法返回给敌手A1搜索陷门Tw。

4)询问2。敌手A1向挑战者F进行密钥询问,除不能对指定邮件服务器身份信息IDS进行公钥询问和测试询问以外,其他与询问阶段1一致。

5)猜测。敌手A1输出猜测值b′∈{0,1},如果b′=b,则挑战成功,敌手A1赢得游戏1的胜利。

定义游戏 1中敌手A1赢得游戏的优势AdvA1(λ)=

2.2.2 陷门不可区分性

以敌手A2和挑战者F的交互游戏2来定义dIBAEKS方案的陷门不可区分性。假设敌手A2是外部攻击者。

1)系统初始化。挑战者F执行Setup算法产生系统参数并发送给敌手A2。

2)询问1。外部攻击者A2向挑战者F进行以下询问:

(1)密钥询问。当敌手A2向挑战者F进行密钥询问时,挑战者F调用KeyGen算法并返回数据接收者的私钥skB和指定邮件存储服务器私钥skS给敌手A2。

(2)陷门询问。敌手A2将数据发送者身份信息IDA、数据接收者身份信息IDB和关键字w发送给挑战者F,并对其进行陷门询问。挑战者F调用dTrapdoor算法返回给敌手A2搜索陷门Tw。

4)询问2。敌手A2向挑战者F进行密钥询问,除不能对指定邮件服务器身份信息IDS、接收者的身份信息IDB进行公钥询问和测试询问以外,其他与询问阶段1一致。

5)猜测。敌手A2输出猜测值b′∈{0,1},如果b′=b,则挑战成功,敌手A2赢得游戏2的胜利。

定义游戏2中敌手A2,赢得游戏的优势AdvA2(λ)=

2.2.3 离线猜测关键字攻击

由于本文提出的dIBAEKS方案在满足适应性选择消息下的陷门不可区分性时,可抵御离线关键字猜测攻击[15],因此dIBAEKS方案能够抵御离线关键字猜测攻击。

3 具体方案

dIBAEKS方案具体算法如下:

2)KeyGen算法。以主密钥s和指定邮件服务器S的身份信息IDs∈{0,1}*为输入,PKG生成指定邮件服务器S的私钥skS=sH1(IDS),其中H1(IDS)为指定邮件服务器S的公钥。类似地,PKG根据数据发送者A身份信息IDA∈{0,1}*和数据接收者B身份信息IDB∈{0,1}*,生成数据发送者A的私钥skA=sH1(IDA)和数据接收者B的私钥skB=sH1(IDB),其中,H1(IDA)和H1(IDB)分别为数据发送者A和数据接收者B的公钥。

5)dTest算法。指定邮件服务器S利用自身私钥skS,与接收的C1、C2、T1、T2、T3进行验证,判断C2·T3是否与e(C1+T1+T2,skS)相等。若两者相等则输出“True”,并将Cw所对应的加密邮件发送给数据接收者B,否则输出“False”。

4 正确性、安全性证明与效率分析

4.1 正确性证明

本文方案的正确性证明如下:

C2T3=e(rH1(IDS),q1·Ppub)e((t+q2)Ppub,H1(IDS))=

e(rH1(IDS),q1·sp)e((t+q2)sp,H1(IDS))=

e(rpq1,sH1(IDS))e((t+q2)p,sH1(IDS))=

e(rpq1+(t+q2)p,sH1(IDS))=

e(rpq1+tp+q2p,sH1(IDS))=

e(C1+T1+T2,skS)

(2)

由于C2T3=e(C1+T1+T2,skS)等式成立,符合关键字w′等于w以及对数据接收者身份的验证,因此证明了本文提出方案的正确性。

4.2 安全性证明

本节证明dIBAEKS方案能满足在随机预言模型适应性选择消息攻击下的关键字密文不可区分性和陷门不可区分性,进而证明该方案可抵御离线关键字猜测攻击[11,16]。

4.2.1 关键字密文不可区分性的具体证明

定理1在计算双线性Diffie-Hellman是困难问题的情况下,对于游戏1的攻击者,dIBAEKS方案在随机预言模型下满足适应性选择关键字密文攻击时的不可区分性安全。

1)系统初始化。挑战者F通过运行Setup算法产生系统参数Params={G1,G2,e,q,p,Ppub,H1,H2}并发送给敌手A1,设Ppub=ap。

2)询问1。敌手A1向挑战者F进行以下询问:

5)猜测。敌手A1输出猜测值μ′∈{0,1},如果μ′=μ,则挑战成功,敌手A1赢得游戏1 的胜利。

4.2.2 陷门不可区分性的具体证明

定理2在计算双线性Diffie-Hellman是困难问题的情况下,对于游戏2的攻击者,dIBAEKS方案在随机预言模型下满足适应性选择消息攻击时的陷门不可区分性。

1)系统初始化。挑战者F通过运行Setup算法产生系统参数Params={G1,G2,e,q,p,Ppub,H1,H2}并发送给敌手A2,设Ppub=ap。

2)询问1。敌手A2向挑战者F进行以下询问:

(2)H2询问。具体过程与定理1一致。

(4)陷门询问。具体过程与定理1一致。

5)猜测。敌手A2输出猜测值μ′∈{0,1},如果μ′=μ,则挑战成功,敌手A2赢得游戏2 的胜利。

4.3 效率分析

本节通过理论对比和数值实验对dIBAEKS方案进行效率分析。

4.3.1 理论对比

将采用dIBAEKS方案与dIBEKS方案的关键字加密算法、陷门生成算法以及验证算法的计算效率进行对比,并以点乘运算(PM)、双线性运算(PB)和哈希运算(PH)的数量作为评估指标,结果如表1所示。可以看出:在关键字加密算法中,dIBAEKS方案比dIBEKS方案少1个点乘运算和2个哈希运算;在陷门生成算法中,dIBAEKS方案比dIBEKS方案多1个双线性运算和1个哈希运算;在验证算法中,dIBAEKS方案比dIBEKS方案少3个双线性运算和2个哈希运算。由上述可知,在关键字加密算法和验证算法中,dIBAEKS方案的计算效率均优于dIBEKS方案,因此从总体来看,dIBAEKS方案的计算效率更高。

表1 不同算法下2种方案的计算效率对比Table 1 Comparison of calculation efficiency of two schemes under different algorithms

4.3.2 数值实验分析

本文采用数值实验对dIBAEKS方案与dIBEKS方案在关键字加密和验证阶段的计算效率进行对比分析。实验环境如下:ASUS A455L型计算机,Inter®CoreTMi5-4210U处理器,4 GB内存,Win10操作系统,Linux虚拟机。使用C语言基于配对的密码学(Pairing-Based Cryptography,PBC)库[20],群G1、G2的长度为1 024 bit,利用A型椭圆曲线y2=x3+xmodq进行计算,且用户身份和关键字随机产生,实验参数设置如表2所示。

表2 数值实验参数设置Table 2 Parameter setting of numerical experiment

关键字数量决定dIBAEKS方案的执行时间。在数值实验中,关键字数量分别取100、200、300、400、500、600、700、800、900和1 000,取50次运算结果的平均值作为最终实验结果。图2和图3分别为2种方案在关键字加密和验证阶段的执行时间随关键字数量的变化情况。由图2和图3可以看出,随着当关键字数量的增加,dIBAEKS方案与dIBEKS方案的执行时间均延长;在关键字加密阶段,dIBAEKS方案的执行时间增幅略低于dIBEKS方案,其计算效率略高;在验证阶段,dIBAEKS方案和dIBEKS方案执行时间的增幅分别为0.9%和1.3%,dIBAEKS方案的计算效率明显高于dIBEKS方案。

图2 2种方案在关键字加密阶段执行时间随关键字数量的变化Fig.2 The change of execution time with the number of keywords in the keyword encryption phase of two schemes

图3 2种方案在验证阶段执行时间随关键字数量的变化Fig.3 The change of execution time with the number of keywords in the verification phase of two schemes

5 结束语

本文提出一种指定服务器的身份认证邮件关键字加密方案,通过在指定服务器上进行陷门搜索,并由指定数据发送者发出关键字密文,可避免离线关键字猜测攻击。理论分析和数值实验结果表明,该方案具有较高的计算效率和安全性。下一步将在本文工作的基础上,增加数据接收者对返回加密电子邮件的验证,以更准确地分辨服务器返回结果的真实性。