一種可驗(yàn)證的公鑰可搜索加密方案

劉鵬亮,俎龍輝,白翠翠,馬 華

(西安電子科技大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院,西安710071)

一種可驗(yàn)證的公鑰可搜索加密方案

劉鵬亮,俎龍輝,白翠翠,馬 華

(西安電子科技大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院,西安710071)

公鑰可搜索加密能實(shí)現(xiàn)基于密文的信息檢索,適用于云計(jì)算環(huán)境。但現(xiàn)有公鑰可搜索加密方案普遍依賴于雙線性對(duì),并且無(wú)法對(duì)服務(wù)器返回的搜索結(jié)果進(jìn)行驗(yàn)證,效率和安全性較低。為此,基于ElGamal加密算法提出一種可驗(yàn)證的公鑰可搜索加密方案。該方案使用ElGamal加密算法替代雙線性對(duì)運(yùn)算,與傳統(tǒng)算法相比具有較低的計(jì)算復(fù)雜度,并且易于實(shí)現(xiàn)。在密文關(guān)鍵詞及加密文件生成算法中,采用ElGamal簽名算法對(duì)關(guān)鍵詞的哈希值進(jìn)行數(shù)字簽名。當(dāng)收到服務(wù)器返回的搜索結(jié)果后,用戶可以通過(guò)計(jì)算得到發(fā)送者的公鑰,并對(duì)相應(yīng)的簽名值進(jìn)行驗(yàn)證,從而有效防止服務(wù)器返回錯(cuò)誤結(jié)果。

可搜索加密;公鑰;密文關(guān)鍵詞;驗(yàn)證;關(guān)鍵詞搜索;ElGamal加密

1 概述

隨著云計(jì)算技術(shù)越來(lái)越流行,大量的私密信息被存儲(chǔ)在云端［1-2］。因此,云端數(shù)據(jù)的安全性引起了廣泛關(guān)注。加密技術(shù)保護(hù)了數(shù)據(jù)的機(jī)密性和隱私性,卻給加密數(shù)據(jù)的檢索帶來(lái)了很大的困難。檢索加密數(shù)據(jù)的一種方法是用戶將所有密文全部下載,逐一解密尋找自己想要的文件,確保了不會(huì)泄露任何信息給服務(wù)器。這是一項(xiàng)非常耗時(shí)且需要很大存儲(chǔ)空間的任務(wù),對(duì)資源受限的用戶來(lái)說(shuō),尋找特定文件是不現(xiàn)實(shí)的。為使用戶在不解密密文的情況下快速找到自己想要的文件,研究者提出了可搜索加密方法［3］,主要分為公鑰可搜索加密［4-5］和對(duì)稱可搜索加密［6-7］。目前許多公鑰可搜索加密方案相繼被提出,如文獻(xiàn)［8-9］通過(guò)利用改變傳統(tǒng)陷門信息解決了公鑰可搜索加密中存在的陷門攻擊問(wèn)題,增強(qiáng)了方案的安全性。但其方案都是基于計(jì)算量大且難以實(shí)現(xiàn)的雙線性對(duì)。針對(duì)這一缺陷,文獻(xiàn)［10］基于K-容忍的身份加密技術(shù)提出了一種新的公鑰可搜索加密方案,方案中運(yùn)用多項(xiàng)式和異或運(yùn)算代替雙線性對(duì),提高了計(jì)算效率。文獻(xiàn)［11］提出了一種基于大整數(shù)分解的公鑰可搜索加密方案。然而,上述方案都存在著一個(gè)共同的問(wèn)題:均沒(méi)有對(duì)搜索結(jié)果進(jìn)行正確性驗(yàn)證。而與公鑰相對(duì)應(yīng)的對(duì)稱可搜索加密中已經(jīng)實(shí)現(xiàn)了對(duì)搜索結(jié)果的驗(yàn)證。文獻(xiàn)［6-7］分別提出了對(duì)稱可搜索加密中確定性和模糊性關(guān)鍵詞搜索結(jié)果的驗(yàn)證方案,確保了用戶對(duì)服務(wù)器返回結(jié)果的正確性和完整性的驗(yàn)證。

針對(duì)公鑰可搜索加密中缺少驗(yàn)證這一問(wèn)題,本文基于離散對(duì)數(shù)問(wèn)題,運(yùn)用ELGamal算法構(gòu)造一種可驗(yàn)證的公鑰可搜索加密方案。

2 預(yù)備知識(shí)

2.1 ELGamal加密算法

ELGamal加密算法不是一個(gè)確定性算法,其加密結(jié)果依賴于消息、公鑰和一個(gè)隨機(jī)選擇的數(shù),算法具體過(guò)程如下:

(2)加密:若加密明文消息為M,發(fā)送者選擇隨機(jī)整數(shù)k(1≤k≤p-1),并且gcd(k,p-1)=1。計(jì)算y1=gk,y2=Myk=Mgxk,則密文為C=〈y1,y2〉。

2.2 ELGamal簽名算法

ELGamal簽名算法的具體過(guò)程如下:

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

(2)簽名:對(duì)明文消息M,進(jìn)行如下操作:

選擇隨機(jī)整數(shù)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)驗(yàn)證:當(dāng)接收者收到簽名消息(M,r,s)后進(jìn)行如下計(jì)算:1)驗(yàn)證是否有1≤r≤p-1,如果不是,則拒絕簽名;2)計(jì)算v=gM和w=yrrs;3)如果v=w成立,則接受簽名,否則拒絕。

3 方案構(gòu)造

公鑰可搜索加密方案模型如圖1所示。發(fā)送者(Alice)利用接收者(Bob)的公鑰生成密文關(guān)鍵詞并將密文存儲(chǔ)于服務(wù)器。Bob用自己的私鑰生成陷門發(fā)送給服務(wù)器,然后服務(wù)器檢測(cè)密文關(guān)鍵詞和陷門是否是由同一個(gè)關(guān)鍵詞生成。如果相同,服務(wù)器就發(fā)送密文給接收者。否則,返回空值。

圖1 公鑰可搜索加密模型

本文基于ELGamal加密和簽名算法構(gòu)造了一種新可驗(yàn)證的公鑰可搜索加密方案。新方案不僅實(shí)現(xiàn)了關(guān)鍵詞的檢索,而且Bob可以對(duì)服務(wù)器返回的搜索結(jié)果的正確性進(jìn)行驗(yàn)證。新方案包括 5個(gè)算法:

(1)參數(shù)生成算法

(2)密文關(guān)鍵詞及加密文件生成算法

若Alice要發(fā)送含有關(guān)鍵詞w的文件M給Bob。Alice計(jì)算關(guān)鍵詞W的哈希值H(W),選取2個(gè)隨機(jī)數(shù)r1,r2∈Z*p,計(jì)算S1=r1rH(w)2modp,S2=r1

H(w)-1r2modp,則密文關(guān)鍵詞為S=〈S1,S2〉。

Alice用Bob的公鑰(p2,g2,y2)對(duì)文件M進(jìn)行加密:選擇隨機(jī)整數(shù)k(1≤k≤p2-1),且gcd(k,p2-1)= 1,計(jì)算y11=gk2mod(p2-1),y12=Myk2mod(p2-1)=Mgx2k2mod(p2-1),密文為C1=〈y11,y12〉。

Alice用自己的私鑰x1對(duì)H(w)進(jìn)行簽名:選擇隨機(jī)整數(shù)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)陷門生成算法

當(dāng)Bob要檢索一個(gè)含有關(guān)鍵詞w1的文件時(shí),他首先計(jì)算A=H(w1),然后用服務(wù)器的公鑰(p,g,y)對(duì)其進(jìn)行加密。選擇隨機(jī)整數(shù)α(1≤α≤p-1)。計(jì)算y31=gαmodp;y32=Agαmodp;TW=Enc(A)=〈y31,y32〉。Bob將Tw發(fā)給服務(wù)器,作為對(duì)關(guān)鍵詞w的搜索請(qǐng)求。

(4)檢測(cè)算法

當(dāng)服務(wù)器接收到來(lái)自Bob的搜索請(qǐng)求后,首先解密獲取陷門信息。如果S1=SH(w1)2,服務(wù)器返回D=〈C1,sig,C2〉發(fā)送給Bob。否則,返回空值。

(5)驗(yàn)證算法

當(dāng)Bob收到服務(wù)器返回的結(jié)果D后并將其分成C1,sig和C23個(gè)部分,首先對(duì)身份密文C2進(jìn)行解密,確認(rèn)發(fā)送者身份。然后再用其公鑰對(duì)關(guān)鍵詞的簽名進(jìn)行驗(yàn)證,若驗(yàn)證成功再對(duì)C1進(jìn)行解密。否則,丟棄。

方案正確性驗(yàn)證過(guò)程如下:

(1)Alice計(jì)算:

(3)若Bob收到服務(wù)器返回的D=〈C1,sig,C2〉,首先進(jìn)行身份驗(yàn)證:

1)對(duì)C2進(jìn)行解密計(jì)算,確認(rèn)發(fā)送者的身份:

2)若上步身份驗(yàn)證是Alice時(shí),用其公鑰進(jìn)行簽名驗(yàn)證:

①驗(yàn)證是否有1≤r≤p1-1,如果不是,則拒絕該簽名;

3)解密:簽名驗(yàn)證成功后Bob用自己的私鑰對(duì)加密文件進(jìn)行解密:

通過(guò)以上分析,可以證明此方案是正確的。

4 安全性及效率分析

本文方案采用的是ELGamal加密和簽名算法,接下來(lái)從3個(gè)方面對(duì)其安全性進(jìn)行分析:

(1)文件密文和陷門信息安全性:對(duì)文件和陷門信息的加密都采用ELGamal加密算法,該算法基于求解離散對(duì)數(shù)困難問(wèn)題。攻擊者要通過(guò)求解離散對(duì)數(shù)得到解密密鑰,而求解過(guò)程非常復(fù)雜。因此,保證了密文和陷門信息的安全性。

(2)簽名安全性:對(duì)關(guān)鍵詞w,同樣采用基于求解離散對(duì)數(shù)困難問(wèn)題的ELGamal簽名算法。每次選取不同的隨機(jī)數(shù)k1實(shí)施簽名。這樣即使同樣的文件,得到的簽名結(jié)果是不一樣的,防止了重復(fù)攻擊,提高了系統(tǒng)的安全性。另外,對(duì)密文關(guān)鍵詞w的簽名實(shí)質(zhì)是對(duì)H(w)的簽名,所選取哈希函數(shù)是抗碰撞的,因此,對(duì)一個(gè)消息的簽名偽造是不可能實(shí)現(xiàn)的。

(3)密文關(guān)鍵詞安全性

關(guān)鍵詞的密文形式S=〈S1,S2〉。其中:

對(duì)每一個(gè)關(guān)鍵詞w的加密都隨機(jī)選取r1,r2,攻擊者無(wú)法直接獲取有關(guān)關(guān)鍵詞的任何信息。

文獻(xiàn)［4,8-9］方案主要基于雙線性對(duì)進(jìn)行大量運(yùn)算,這會(huì)耗費(fèi)大量時(shí)間和存儲(chǔ)資源。文獻(xiàn)［10-11］基于大整數(shù)分解實(shí)現(xiàn)了公鑰可搜索加密,提高了效率,卻未對(duì)服務(wù)器的返回結(jié)果進(jìn)行驗(yàn)證。本文基于ELGamal算法提出了一種新的可驗(yàn)證的公鑰可搜索加密方案,利用ELGamal簽名算法對(duì)搜索結(jié)果的正確性進(jìn)行了驗(yàn)證。各種方案的比較如表1所示。

表1 方案性能對(duì)比

5 結(jié)束語(yǔ)

目前對(duì)公鑰可搜索加密方案的研究較多,但多數(shù)方案中對(duì)服務(wù)器返回的搜索結(jié)果卻未實(shí)現(xiàn)驗(yàn)證,而與之對(duì)應(yīng)的對(duì)稱可搜索加密已經(jīng)實(shí)現(xiàn)了高效的驗(yàn)證。本文基于ELGamal算法構(gòu)造了一種新的可驗(yàn)證的公鑰可搜索加密方案,對(duì)服務(wù)器返回的結(jié)果的正確性進(jìn)行了驗(yàn)證,并對(duì)方案從效率和安全性上進(jìn)行了分析。下一步將研究如何對(duì)公鑰可搜索加密中服務(wù)器返回的搜索結(jié)果進(jìn)行更廣泛的驗(yàn)證。

［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］ 聶規(guī)劃,佘其平,陳冬林.客戶云需求波動(dòng)下的多實(shí)例組合決策研究［J］.計(jì)算機(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］ 方黎明.帶關(guān)鍵字搜索公鑰加密的研究［D］.南京:南京航空航天大學(xué),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

國(guó)家自然科學(xué)基金資助項(xiàng)目(61100229);中央高校基本科研業(yè)務(wù)費(fèi)專項(xiàng)基金資助項(xiàng)目(K5051270003);信息安全國(guó)家重點(diǎn)實(shí)驗(yàn)室開(kāi)放基金資助項(xiàng)目(GW0704127001);陜西省教育廳科研計(jì)劃基金資助項(xiàng)目(12JK0852)。

劉鵬亮(1988-),男,碩士研究生,主研方向:網(wǎng)絡(luò)與信息安全;俎龍輝、白翠翠,碩士研究生;馬 華,教授。

2013-12-23

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

中文引用格式:劉鵬亮,俎龍輝,白翠翠,等.一種可驗(yàn)證的公鑰可搜索加密方案［J］.計(jì)算機(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.