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

楊丹 李文宇

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

關鍵詞：可搜索加密;不可區分混淆;公鑰; Hash函數

中圖分類號：TP309.7文獻標識碼：A文章編號：2095-1302（2019）02-00-03

0 引 言

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

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

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

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

1 基礎知識

1.1 不可區分混淆

作為一個新的密碼學原語，不可區分混淆未來的應用極具吸引力。混淆的概念最初來源于計算機學科，之后回歸到密碼學。不可區分混淆是密碼學中的一個重要工具，它可以更方便地實現算法，并具有很好的安全性。很多密碼學研究學者應用不可區分混淆構造了許多密碼學方案，包括版權和軟件的保護、私鑰加密模式轉換為公鑰加密模式、同態加密、證據加密、否定加密、功能加密、多方密鑰交換等[21-25]。

定義1（不可區分混淆器）對于一個電路族{Cλ}，一個同類PPT（概率多項式時間圖靈機）是不可區分混淆器，如果滿足以下條件[20]：

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

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

1.2 公鑰可搜索加密

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

定義2一個非交互式公鑰加密搜索體制包含如下四個概率多項式時間算法[10]：

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

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

（3）限門（Trapdoor）：輸入密鑰k和一個關鍵字w，計算關于w的陷門值τ。

（4）測試（Test）：輸入可搜索加密的一個陷門值τ，如果滿足搜索關系則輸出密文文件C，否則輸出終止符號。

2 方案構造

2.1 初始化算法

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

3 正確性及安全性分析

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

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

（3）混淆器的安全性：文獻[20]中就有對不可區分混淆器安全性的描述，一個安全的不可區分混淆器可以確保混淆器中的數據不被泄漏。

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

（5）關鍵字的安全性：每一個關鍵字先由隨機數r1，r2完成隨機化，每加密一次都會換一次隨機數，再經過不可區分混淆器后攻擊者無法直接獲取關鍵字的任何信息。

4 結 語

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

參 考 文 獻

[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.