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

杨丹 李文宇

摘 要：随着计算机网络的迅速发展，越来越多的政府、企业和个人开始把数据放到云服务器上，以节省存储空间和系统维护费用。安全性便成为云存储发展过程中的关键。当云端服务器不完全可信时，如何实现安全的关键字搜索成为一个难题，解决这一难题的可搜索加密方法成为近年的研究热点。可搜索加密主要包括对称可搜索加密和公钥可搜索加密。现有的公钥可搜索加密普遍利用双线性对实现，但双线性对的计算开销较大，所以提出一种利用不可区分混淆来构造公钥的可搜索加密方案。文中用不可区分混淆器封装一个安全的加密算法和用户私钥作为用户公钥，以加密文件和关键字，用带密钥的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.