基于混淆的公鑰可搜索加密方案

楊丹 李文宇

摘 要：隨著計(jì)算機(jī)網(wǎng)絡(luò)的迅速發(fā)展，越來越多的政府、企業(yè)和個(gè)人開始把數(shù)據(jù)放到云服務(wù)器上，以節(jié)省存儲(chǔ)空間和系統(tǒng)維護(hù)費(fèi)用。安全性便成為云存儲(chǔ)發(fā)展過程中的關(guān)鍵。當(dāng)云端服務(wù)器不完全可信時(shí)，如何實(shí)現(xiàn)安全的關(guān)鍵字搜索成為一個(gè)難題，解決這一難題的可搜索加密方法成為近年的研究熱點(diǎn)。可搜索加密主要包括對稱可搜索加密和公鑰可搜索加密。現(xiàn)有的公鑰可搜索加密普遍利用雙線性對實(shí)現(xiàn)，但雙線性對的計(jì)算開銷較大，所以提出一種利用不可區(qū)分混淆來構(gòu)造公鑰的可搜索加密方案。文中用不可區(qū)分混淆器封裝一個(gè)安全的加密算法和用戶私鑰作為用戶公鑰，以加密文件和關(guān)鍵字，用帶密鑰的Hash函數(shù)生成陷門信息。一個(gè)安全的不可區(qū)分混淆器可有效保證此方案的安全性。利用不可區(qū)分混淆構(gòu)造公鑰可搜索加密以簡化其算法，使得方案更容易實(shí)現(xiàn)并更好地保護(hù)隱私。

關(guān)鍵詞：可搜索加密;不可區(qū)分混淆;公鑰; Hash函數(shù)

中圖分類號(hào)：TP309.7文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：2095-1302（2019）02-00-03

0 引 言

隨著云計(jì)算的快速發(fā)展，眾多用戶已經(jīng)把本地?cái)?shù)據(jù)放到云服務(wù)器上，以節(jié)省本地的存儲(chǔ)空間和系統(tǒng)維護(hù)費(fèi)用。但由于數(shù)據(jù)脫離了用戶的物理控制而存儲(chǔ)在云端，因此云端服務(wù)器管理員和非法用戶（如黑客等不具有訪問權(quán)限的用戶）可以嘗試通過訪問數(shù)據(jù)來獲取數(shù)據(jù)所包含的信息，造成數(shù)據(jù)信息和用戶隱私的泄露[1]。為了保證云服務(wù)器上數(shù)據(jù)的私密性，用戶先用已有的加密體制對數(shù)據(jù)加密后再放到云服務(wù)器上。加密后，用戶在云服務(wù)器中檢索特定文件的難度大大增加。如果把文件下載到本地解密后再檢索，會(huì)為用戶增加巨大的負(fù)擔(dān)。為了解決這一問題，密碼學(xué)研究者提出可搜索加密技術(shù)，包括對稱可搜索加密方案[2-9]、公鑰可搜索加密方案[10-14]及增加特殊功能的可搜索加密方案[15-17]。1996年，Goldreich O

和Ostrovsky R首次提出隱藏用戶訪問模式的密文搜索技術(shù)，但是該技術(shù)要求用戶和服務(wù)器端進(jìn)行多重對數(shù)輪交互，這種方法在實(shí)際應(yīng)用中的效率并不高[18]。2000年，Song D，Wagner D和Perrig A提出一種基于對稱算法的可搜索加密方案機(jī)制，用戶進(jìn)行搜索時(shí)，生成關(guān)鍵字的密文發(fā)送給服務(wù)器，通過將密文關(guān)鍵字和密文文件進(jìn)行掃描比對，服務(wù)器可以確認(rèn)關(guān)鍵字是否存在[2]。在此之后，許多研究者提出支持多個(gè)關(guān)鍵字搜索的對稱可搜索加密方案，模糊關(guān)鍵字搜索方案等。2004年，Boneh D等人提出基于公鑰密碼學(xué)算法的可搜索加密機(jī)制[10]，Golle等人首次提出基于多關(guān)鍵字的可搜索加密概念[11]，為后來的研究者通過公鑰密碼學(xué)實(shí)現(xiàn)更加多樣的可搜索加密方案提供指導(dǎo)。

2001年，Barak等人開始正式研究程序的混淆，希望能夠?qū)崿F(xiàn)輸入一個(gè)程序，輸出另一個(gè)程序并且該程序與原始程序功能相同卻可以隱藏原始程序工作方式的目標(biāo)。同時(shí)他們給出兩個(gè)混淆的概念，分別是虛擬黑盒混淆和不可區(qū)分混淆，遺憾的是他們并未給出如何實(shí)現(xiàn)[19]。直到2013年，Gary等人給出第一個(gè)對于一般程序的有效的不可區(qū)分混淆的候選方案。此方案由多線性拼圖困難塊（Multilinear Jigsaw Puzzle）構(gòu)造[20]，并且給出如何利用不可區(qū)分混淆來構(gòu)造功能加密。隨后很多學(xué)者給出利用不可區(qū)分混淆構(gòu)造的其他方案。

公鑰可搜索加密方案更適用于多用戶體制以及不安全的網(wǎng)絡(luò)環(huán)境。該方案無需發(fā)送者和接收者事先協(xié)商密鑰，發(fā)送者可以直接使用對外公開的公鑰對關(guān)鍵字加密。公鑰可搜索加密方案普遍利用雙線性對實(shí)現(xiàn)，雖然雙線性對的特性使得一些支持更加復(fù)雜的搜索語句的方案得以發(fā)展，但雙線性對的計(jì)算開銷較大。利用不可區(qū)分混淆構(gòu)造可搜索加密可以簡化其算法，使方案更容易實(shí)現(xiàn)且更好地保護(hù)隱私。本文利用不可區(qū)分混淆器封裝一個(gè)安全的加密算法及用戶自己的私鑰作為用戶的公鑰，安全的不可區(qū)分混淆器可有效保證方案的安全。

1 基礎(chǔ)知識(shí)

1.1 不可區(qū)分混淆

作為一個(gè)新的密碼學(xué)原語，不可區(qū)分混淆未來的應(yīng)用極具吸引力。混淆的概念最初來源于計(jì)算機(jī)學(xué)科，之后回歸到密碼學(xué)。不可區(qū)分混淆是密碼學(xué)中的一個(gè)重要工具，它可以更方便地實(shí)現(xiàn)算法，并具有很好的安全性。很多密碼學(xué)研究學(xué)者應(yīng)用不可區(qū)分混淆構(gòu)造了許多密碼學(xué)方案，包括版權(quán)和軟件的保護(hù)、私鑰加密模式轉(zhuǎn)換為公鑰加密模式、同態(tài)加密、證據(jù)加密、否定加密、功能加密、多方密鑰交換等[21-25]。

定義1（不可區(qū)分混淆器）對于一個(gè)電路族{Cλ}，一個(gè)同類PPT（概率多項(xiàng)式時(shí)間圖靈機(jī)）是不可區(qū)分混淆器，如果滿足以下條件[20]：

（1）對于所有輸入x，安全參數(shù)λ∈N，C∈Cλ，則有

（2）對于任意的PPT區(qū)分器D，存在一個(gè)可忽略函數(shù)α，對于所有的電路對C0，C1∈Cλ，λ∈N，如果對于所有的輸入x都有C0（x）=C1（x），那么

1.2 公鑰可搜索加密

公鑰可搜索加密方案中最具有代表性的是由Boneh等提出的PEKS方案[10]，此方案允許文件或信息的發(fā)送者是任何可以獲得公鑰的人，但是生成陷門值必須使用接收者的私鑰才能完成。

定義2一個(gè)非交互式公鑰加密搜索體制包含如下四個(gè)概率多項(xiàng)式時(shí)間算法[10]：

（1）初始化（Setup）：輸入安全參數(shù)λ，輸出密鑰k和公鑰PK。

（2）公鑰可搜索加密（PEKS）：輸入消息m，關(guān)鍵字w，利用公鑰生成關(guān)于m和w的密文C。

（3）限門（Trapdoor）：輸入密鑰k和一個(gè)關(guān)鍵字w，計(jì)算關(guān)于w的陷門值τ。

（4）測試（Test）：輸入可搜索加密的一個(gè)陷門值τ，如果滿足搜索關(guān)系則輸出密文文件C，否則輸出終止符號(hào)。

2 方案構(gòu)造

2.1 初始化算法

輸入安全參數(shù)λ，系統(tǒng)生成Bob的私鑰k和公鑰PK，公鑰PK是對圖1 Public Key經(jīng)過混淆后生成的程序，PK=（Public Key）。

3 正確性及安全性分析

（1） 方案的正確性：當(dāng)云服務(wù)器收到陷門值τ后，計(jì)算s1是否等于s2τ。若s1=s2τ，則σ=τ，關(guān)鍵字匹配成功。計(jì)算過程：。

（2）文件密文的安全性：文件的安全性依賴于加密算法的安全性，因此為文件加密時(shí)需選用安全的加密算法。

（3）混淆器的安全性：文獻(xiàn)[20]中就有對不可區(qū)分混淆器安全性的描述，一個(gè)安全的不可區(qū)分混淆器可以確保混淆器中的數(shù)據(jù)不被泄漏。

（4）密鑰和陷門信息的安全性：密鑰的安全性不僅依賴于密鑰管理，更依賴于不可區(qū)分混淆器的安全性，如果是一個(gè)安全的不可區(qū)分混淆器，那么在混淆器中的密鑰就是安全的且不會(huì)被泄露。陷門信息通過使用帶密鑰的Hash函數(shù)對關(guān)鍵字加密生成。根據(jù)Hash函數(shù)的性質(zhì)，如果不知道密鑰k則無法生成陷門信息。

（5）關(guān)鍵字的安全性：每一個(gè)關(guān)鍵字先由隨機(jī)數(shù)r1，r2完成隨機(jī)化，每加密一次都會(huì)換一次隨機(jī)數(shù)，再經(jīng)過不可區(qū)分混淆器后攻擊者無法直接獲取關(guān)鍵字的任何信息。

4 結(jié) 語

目前的公鑰可搜索加密方案大多基于雙線性對實(shí)現(xiàn)，由于其計(jì)算開銷大、效率低、難以在實(shí)際中應(yīng)用，所以找到一種不用雙線性對且易實(shí)現(xiàn)的方案十分必要。本文利用不可區(qū)分混淆構(gòu)造公鑰可搜索加密方案以避免使用雙線性對，使算法變得更簡單。不足之處是目前不可區(qū)分混淆的效率并不高，此后應(yīng)將提高不可區(qū)分混淆的效率作為研究重點(diǎn)。

參 考 文 獻(xiàn)

[1] SHEN Z R，XUE W，SHU J W.Survey on the research and development of searchable encryption schemes[J].Journal of software，2014，25（4）：880-895.

[2] SONG D X，WAGNER D，PERRIG A.Practical techniques for searches on encrypted data[C]// Security and Privacy，2000 S&P 2000 Proceedings.2000 IEEE Symposium on.IEEE，2000：44-55.

[3] CHANG Y C，MITZENMACHER M.Privacy preserving keyword searches on remote encrypted data[C]// Applied Cryptography and Network Security.Springer Berlin Heidelberg，2005：442-455.

[4] CURTMOLA R，GARAY J，KAMARA S，et al.Searchable symmetric encryption： improved definitions and efficient constructions[C]// Proceedings of the 13th ACM Conference on Computer and Communications Security.ACM，2006：79-88.

[5] BALLARD L，KAMARA S，MONROSE F.Achieving efficient conjunctive keyword searches over encrypted data [C]// Information and Communications Security.Springer Berlin Heidelberg，2005： 414-426.

[6] CAO N，YANG Z，WANG C，et al.Privacy-preserving query over encrypted graph-structured data in cloud computing[C]// Distributed Computing Systems （ICDCS），2011 31st International Conference. IEEE，2011：393-402.

[7] WANG C，CAO N，LI J，et al.Secure ranked keyword search over encrypted cloud data[C]// Distributed Computing Systems （ICDCS），2010 IEEE 30th International Conference.IEEE，2010： 253-262.

[8] CHENG R，YAN J，GUAN C，et al.Verifiable searchable symmetric encryption from indistinguishability obfuscation[C]// Proceedings of the 10th ACM Symposium on Information，Computer and Communications Security.ACM，2015：621-626.

[9] LI J，WANG Q，WANG C，et al.Fuzzy keyword search over encrypted data in cloud computing[C]// INFOCOM，2010 Proceedings IEEE.IEEE，2010：1-5.

[10] BONEH D，CRESCENZO D G，OSTROVSKY R，et al.Public key encryption with keyword search[C]// Advances in Cryptology-Eurocrypt 2004.Springer Berlin Heidelberg，2004： 506-522.

[11] GOLLE P，STADDON J，WATERS B.Secure conjunctive keyword search over encrypted data[C]// Applied Cryptography and Network Security.Springer Berlin Heidelberg，2004：31-45.

[12] HWANG Y H，LEE P J.Public key encryption with conjunctive keyword search and its extension to a multi-user system[C]// Pairing-Based Cryptography–Pairing 2007.Springer Berlin Heidelberg，2007：2-22.

[13] DONG C，RUSSELLO G，DULAY N.Shared and searchable encrypted data for untrusted servers[C]// Data and Applications Security XXII.Springer Berlin Heidelberg，2008：127-143.

[14] KATZ J，SAHAI A，WATERS B.Predicate encryption supporting disjunctions，polynomial equations，and inner products[C]// Advances in Cryptology-EUROCRYPT 2008.Springer Berlin Heidelberg，2008：146-162.

[15] OKAMOTO T，TAKASHIMA K.Hierarchical predicate encryption for inner-products[C]// Advances in Cryptology-ASIACRYPT 2009.Springer Berlin Heidelberg，2009：214-231.

[16] SWAMINATHAN A，MAO Y，SU G M，et al.Confidentiality-preserving rank-ordered search[C]// Proceedings of the 2007 ACM workshop on Storage Security and Survivability.ACM，2007：7-12.

[17] CAO N，WANG C，LI M，et al.Privacy-preserving multi-keyword ranked search over encrypted cloud data[J].Parallel and distributed Systems，IEEE，2014，25（1）：222-233.

[18] GOLDREICH O，OSTROVSKY R.Software protection and simulation on oblivious RAMs[J].Journal of the ACM，1996，43（3）：431?473.

[19] BARAK B，GOLDREICH O，IMPAGLIAZZO R，et al.On the （im） possibility of obfuscating programs[C]// Advances in cryptology-CRYPTO 2001，Heidelberg： Springer，2001：1-18.

[20] GARG S，GENTRY C，HALEVI S，et al.Candidate indistinguishability obfuscation and functional encryption for all circuits[C]// Foundations of Computer Science （FOCS），2013：40-49.

[21] BARAK B，GOLDREICH O，IMPAGLIAZZO R，et al.On the （im） possibility of obfuscating programs[J].Journal of the ACM（JACM），2012，59（2）：6.

[22] SAHAI A，WATERS B.How to use indistinguishability obfuscation：Deniable encryption，and more[C]// Proceedings of the 46th Annual ACM Symposium on Theory of Computing，ACM，2014：475-484.

[23] BONEH D，ZHANDRY M.Multiparty key exchange，efficient traitor tracing，and more from indistinguishability obfuscation[C]// Advances in Cryptology-CRYPTO 2014，Heidelberg： Springer，2014：480-499.

[24] GARG S，GENTRY C，HALEVI S，et al.On the implausibility of differing-inputs obfuscation and extractable witness encryption with auxiliary input[C]// Advances in Cryptology-CRYPTO 2014，Heidelberg：Springer，2014：518-535.

[25] HOHENBERGER S，SAHAI A，WATERS B.Replacing a random oracle：Full domain hash from indistinguishability obfuscation[C]// Advances in Cryptology-EUROCRYPT 2014，Heidelberg： Springer，2014：201-220.