一种可验证的公钥可搜索加密方案

刘鹏亮,俎龙辉,白翠翠,马 华

(西安电子科技大学数学与统计学院,西安710071)

一种可验证的公钥可搜索加密方案

刘鹏亮,俎龙辉,白翠翠,马 华

(西安电子科技大学数学与统计学院,西安710071)

公钥可搜索加密能实现基于密文的信息检索,适用于云计算环境。但现有公钥可搜索加密方案普遍依赖于双线性对,并且无法对服务器返回的搜索结果进行验证,效率和安全性较低。为此,基于ElGamal加密算法提出一种可验证的公钥可搜索加密方案。该方案使用ElGamal加密算法替代双线性对运算,与传统算法相比具有较低的计算复杂度,并且易于实现。在密文关键词及加密文件生成算法中,采用ElGamal签名算法对关键词的哈希值进行数字签名。当收到服务器返回的搜索结果后,用户可以通过计算得到发送者的公钥,并对相应的签名值进行验证,从而有效防止服务器返回错误结果。

可搜索加密;公钥;密文关键词;验证;关键词搜索;ElGamal加密

1 概述

随着云计算技术越来越流行,大量的私密信息被存储在云端［1-2］。因此,云端数据的安全性引起了广泛关注。加密技术保护了数据的机密性和隐私性,却给加密数据的检索带来了很大的困难。检索加密数据的一种方法是用户将所有密文全部下载,逐一解密寻找自己想要的文件,确保了不会泄露任何信息给服务器。这是一项非常耗时且需要很大存储空间的任务,对资源受限的用户来说,寻找特定文件是不现实的。为使用户在不解密密文的情况下快速找到自己想要的文件,研究者提出了可搜索加密方法［3］,主要分为公钥可搜索加密［4-5］和对称可搜索加密［6-7］。目前许多公钥可搜索加密方案相继被提出,如文献［8-9］通过利用改变传统陷门信息解决了公钥可搜索加密中存在的陷门攻击问题,增强了方案的安全性。但其方案都是基于计算量大且难以实现的双线性对。针对这一缺陷,文献［10］基于K-容忍的身份加密技术提出了一种新的公钥可搜索加密方案,方案中运用多项式和异或运算代替双线性对,提高了计算效率。文献［11］提出了一种基于大整数分解的公钥可搜索加密方案。然而,上述方案都存在着一个共同的问题:均没有对搜索结果进行正确性验证。而与公钥相对应的对称可搜索加密中已经实现了对搜索结果的验证。文献［6-7］分别提出了对称可搜索加密中确定性和模糊性关键词搜索结果的验证方案,确保了用户对服务器返回结果的正确性和完整性的验证。

针对公钥可搜索加密中缺少验证这一问题,本文基于离散对数问题,运用ELGamal算法构造一种可验证的公钥可搜索加密方案。

2 预备知识

2.1 ELGamal加密算法

ELGamal加密算法不是一个确定性算法,其加密结果依赖于消息、公钥和一个随机选择的数,算法具体过程如下:

(2)加密:若加密明文消息为M,发送者选择随机整数k(1≤k≤p-1),并且gcd(k,p-1)=1。计算y1=gk,y2=Myk=Mgxk,则密文为C=〈y1,y2〉。

2.2 ELGamal签名算法

ELGamal签名算法的具体过程如下:

(1)密钥生成(同ELGamal加密算法):公钥为(p,g,y),私钥为x。

(2)签名:对明文消息M,进行如下操作:

选择随机整数k(1≤k≤p-2),这里k必须满足并且gcd(k,p-1)=1;r=gkmodp,s=k-1(M-rx)mod (p-1),则签名消息为(M,r,s)。

(3)验证:当接收者收到签名消息(M,r,s)后进行如下计算:1)验证是否有1≤r≤p-1,如果不是,则拒绝签名;2)计算v=gM和w=yrrs;3)如果v=w成立,则接受签名,否则拒绝。

3 方案构造

公钥可搜索加密方案模型如图1所示。发送者(Alice)利用接收者(Bob)的公钥生成密文关键词并将密文存储于服务器。Bob用自己的私钥生成陷门发送给服务器,然后服务器检测密文关键词和陷门是否是由同一个关键词生成。如果相同,服务器就发送密文给接收者。否则,返回空值。

图1 公钥可搜索加密模型

本文基于ELGamal加密和签名算法构造了一种新可验证的公钥可搜索加密方案。新方案不仅实现了关键词的检索,而且Bob可以对服务器返回的搜索结果的正确性进行验证。新方案包括 5个算法:

(1)参数生成算法

(2)密文关键词及加密文件生成算法

若Alice要发送含有关键词w的文件M给Bob。Alice计算关键词W的哈希值H(W),选取2个随机数r1,r2∈Z*p,计算S1=r1rH(w)2modp,S2=r1

H(w)-1r2modp,则密文关键词为S=〈S1,S2〉。

Alice用Bob的公钥(p2,g2,y2)对文件M进行加密:选择随机整数k(1≤k≤p2-1),且gcd(k,p2-1)= 1,计算y11=gk2mod(p2-1),y12=Myk2mod(p2-1)=Mgx2k2mod(p2-1),密文为C1=〈y11,y12〉。

Alice用自己的私钥x1对H(w)进行签名:选择随机整数k1,k1(1≤k1≤p1-1),r=g1k1mod(p1-1),s=k-11(H(w)-rx1)mod(p1-1),则签名为sig=〈H(w),r,s〉。

(3)陷门生成算法

当Bob要检索一个含有关键词w1的文件时,他首先计算A=H(w1),然后用服务器的公钥(p,g,y)对其进行加密。选择随机整数α(1≤α≤p-1)。计算y31=gαmodp;y32=Agαmodp;TW=Enc(A)=〈y31,y32〉。Bob将Tw发给服务器,作为对关键词w的搜索请求。

(4)检测算法

当服务器接收到来自Bob的搜索请求后,首先解密获取陷门信息。如果S1=SH(w1)2,服务器返回D=〈C1,sig,C2〉发送给Bob。否则,返回空值。

(5)验证算法

当Bob收到服务器返回的结果D后并将其分成C1,sig和C23个部分,首先对身份密文C2进行解密,确认发送者身份。然后再用其公钥对关键词的签名进行验证,若验证成功再对C1进行解密。否则,丢弃。

方案正确性验证过程如下:

(1)Alice计算:

(3)若Bob收到服务器返回的D=〈C1,sig,C2〉,首先进行身份验证:

1)对C2进行解密计算,确认发送者的身份:

2)若上步身份验证是Alice时,用其公钥进行签名验证:

①验证是否有1≤r≤p1-1,如果不是,则拒绝该签名;

3)解密:签名验证成功后Bob用自己的私钥对加密文件进行解密:

通过以上分析,可以证明此方案是正确的。

4 安全性及效率分析

本文方案采用的是ELGamal加密和签名算法,接下来从3个方面对其安全性进行分析:

(1)文件密文和陷门信息安全性:对文件和陷门信息的加密都采用ELGamal加密算法,该算法基于求解离散对数困难问题。攻击者要通过求解离散对数得到解密密钥,而求解过程非常复杂。因此,保证了密文和陷门信息的安全性。

(2)签名安全性:对关键词w,同样采用基于求解离散对数困难问题的ELGamal签名算法。每次选取不同的随机数k1实施签名。这样即使同样的文件,得到的签名结果是不一样的,防止了重复攻击,提高了系统的安全性。另外,对密文关键词w的签名实质是对H(w)的签名,所选取哈希函数是抗碰撞的,因此,对一个消息的签名伪造是不可能实现的。

(3)密文关键词安全性

关键词的密文形式S=〈S1,S2〉。其中:

对每一个关键词w的加密都随机选取r1,r2,攻击者无法直接获取有关关键词的任何信息。

文献［4,8-9］方案主要基于双线性对进行大量运算,这会耗费大量时间和存储资源。文献［10-11］基于大整数分解实现了公钥可搜索加密,提高了效率,却未对服务器的返回结果进行验证。本文基于ELGamal算法提出了一种新的可验证的公钥可搜索加密方案,利用ELGamal签名算法对搜索结果的正确性进行了验证。各种方案的比较如表1所示。

表1 方案性能对比

5 结束语

目前对公钥可搜索加密方案的研究较多,但多数方案中对服务器返回的搜索结果却未实现验证,而与之对应的对称可搜索加密已经实现了高效的验证。本文基于ELGamal算法构造了一种新的可验证的公钥可搜索加密方案,对服务器返回的结果的正确性进行了验证,并对方案从效率和安全性上进行了分析。下一步将研究如何对公钥可搜索加密中服务器返回的搜索结果进行更广泛的验证。

［1］ Wang Cong,Chow S S M,Wang Qian,et al.Privacy Preserving Public Auditing for Secure Cloud Storage［J］.IEEE Transactions on Computers,2013,62(2):362-375.

［2］ 聂规划,佘其平,陈冬林.客户云需求波动下的多实例组合决策研究［J］.计算机工程,2013,39(5):43-47.

［3］ Song X D,Wagner D,Perrig A.Practical Techniques for Searches on Encrypted Data［C］//Proceedings of 2000 IEEE Symposium on Security and Privacy.［S.l.］:IEEE Press,2000:44-55.

［4］ Baek J,Safiavi-Naini R,Susilo W.Public Key Encryption with Keyword Search Revisited［C］//Proceedings of International Conference on Computational Science and Its Applications.Perugia, Italy: Springer-Verlag, 2008: 1249-1259.

［5］ 方黎明.带关键字搜索公钥加密的研究［D］.南京:南京航空航天大学,2012.

［6］ Chai Qi,Gong Guang.Verifiable Symmetric Searchable Enryption for Semi-honest But-curious Servers［EB/OL］.［2013-12-25］.http://www.cacr.math.Uwater-loo.ca/ techreports/2011/cacr201122.

［7］ Li Jin,Wang Qian,Wang Cong,et al.Fuzzy Keyword Search over Encrypted Data in Cloud Computing［C］// Proceedings of IEEE INFOCOM'10.［S.l.］:IEEE Press,2010:1-5.

［8］ Rhee H S,Park J H,Susilo W,et al.Improved Searchable Public Key Encryption with Designated Tester［C］// Proceedings ofthe4th InternationalSymposium on Information,Computer,and CommunicationsSecurity.Sydney,Australia:ACM Press,2009:376-379.

［9］ Zhao Yuanjie,Chen Xiaofeng,Ma Hua,et al.A New Trapdoor-indistinguishable Public Key Encryption with Keyword Search［J］.Journal of Wireless Mobile Networks, Ubiquitous Computing,and Dependable Applications,2012, 3(1/2):72-81.

［10］ Yang Haomiao,Xu Chunxiang,Zhao Hongtian.An Efficient Public Key Encryption with Keyword Scheme Not Using Pairing［C］//Proceedings of the 1st International Conference on Instrumentation,Measurement,Computer,Communication and Control.Beijing,China:［s.n.］,2011: 900-904.

［11］ Luo W,Tan J.Public Key Encryption with Keyword Search Based on Factoring［C］//Proceedings of CCIS'12.［S.l.］:IEEE Press,2012:1245-1247.

编辑 金胡考

A Verifiable Public Key Searchable Encryption Scheme

LIU Pengliang,ZU Longhui,BAI Cuicui,MA Hua
(School of Mathematics and Statistics,Xidian University,Xi'an 710071,China)

As an attractive cryptographic primitive,the public key searchable encryption enables users to search on encrypted data,and hence is applicable to the setting of cloud computing.But most of the existing schemes have to adopt the bilinear pairing and fail to verify search results from the server.Accordingly,these schemes suffer drawbacks in terms of efficiency and security.Aiming at this problem,based on the ElGamal encryption algorithm,a new verifiable scheme is proposed.It has more desirable computation efficiency and is easy to implement in because it replaces the bilinear pairing with the ElGamal encryption.Especially,during the generation of encrypted keywords and encrypted files,the new scheme can generate the digital signature of the hash value of keywords based on the ElGamal signature algorithm.Upon receiving the search results from the server,users can obtain the public key of the sender,and then verify the ElGamal signature, which effectively prevents the server from returning wrong results.

searchable eneryption;public key;encrypted keyword;verification;keyword search;ElGamal encryption

1000-3428(2014)11-0118-03

A

TP309

10.3969/j.issn.1000-3428.2014.11.023

国家自然科学基金资助项目(61100229);中央高校基本科研业务费专项基金资助项目(K5051270003);信息安全国家重点实验室开放基金资助项目(GW0704127001);陕西省教育厅科研计划基金资助项目(12JK0852)。

刘鹏亮(1988-),男,硕士研究生,主研方向:网络与信息安全;俎龙辉、白翠翠,硕士研究生;马 华,教授。

2013-12-23

2014-01-19E-mail:ffgz112lpl@126.com

中文引用格式:刘鹏亮,俎龙辉,白翠翠,等.一种可验证的公钥可搜索加密方案［J］.计算机工程,2014,40(11):118-120.

英文引用格式:Liu Pengliang,Zu Longhui,Bai Cuicui,et al.A Verifiable Public Key Searchable Encryption Scheme［J］.Computer Engineering,2014,40(11):118-120.