基于多线性映射的可搜索加密方案

冯金明 田有亮 刘田天

摘 要：可搜索加密技术为云环境下数据的使用提供了技术支持，针对可搜索的关键字数量及用户模式提出了一种基于多线性映射的可搜索加密方案。首先，提出了基于多线性映射的可搜索加密方案，多线性映射提高了方案的安全性，加强了数据拥有者的权限，使得数据拥有者可以灵活地增加和刪除用户。其次，利用消息认证码技术验证数据的完整性，提高了存储数据的安全性。最后，在标准模型下证明方案是满足选择明文攻击下不可区分安全，且方案安全性归约于多线性计算Diffie-Hellman（MCDH）问题。此外，与相关方案进行了性能分析，分析结果表明该方案的安全性高。

关键词：云计算；可搜索加密；多线性映射；可证明安全

中图分类号：TP309.7

文献标识码： A

伴随着网络技术的迅速发展，云计算在近些年也快速兴起，越来越多的企业、政府公共领域和个人开始使用云相关的技术[1]。如何解决数据加密和数据搜索之间的冲突已经成为亟需解决的重要问题[2]。为了有效的搜索数据，需要一个可以直接作用于加密数据的搜索机制[3]，可搜索加密因此而诞生。其目标就是在不影响数据检索功能的条件下，保护用户外包数据的安全与查询隐私[4]。

可搜索加密的概念是由SONG等[5]在2000年首次提出，其指出用户将自己的加密数据存储到不可信的云服务器上，在给定关键词陷门信息的情况下，服务器可以为用户搜索包含特定关键词的加密文件，而不能获得关于明文的信息。2003年，GOH[6]提出了一种新方案，该方案利用Bloom过滤器来建立文件索引，以达到降低开销的目的。2004年，DAN等[7]提出了基于关键词的可搜索加密算法，开启了密文搜索的新纪元。2005年，CHANG等[8]利用随机比特建立关键字的索引，并在搜索时通过恢复索引的部分信息来匹配关键字。2006年，CURTMOLA等[9]提出了在整个文件集合上建立加密关键字的Hash索引，搜索令牌由关键字陷门和文件拥有者的身份信息组成，从而通过关键字陷门与关键字密文的匹配来产生搜索结果。此后，可搜索加密机制的研究迅速发展。2010年，LI等[10]提出了模糊关键字搜索方案，使用编辑距离来定义关键字的相似度，并且提出了基于克和基于通配符的两种模糊集的构造方法。2011年，CHAI等[11]提出了一个可验证的对称可搜索加密方案，他们在其方案中使用了一种更强的安全模型——半可信但好奇的服务器，在这种模型下，服务器为了节省自己的带宽及计算量不一定按照协议执行操作，从而可能只是执行部分搜索操作或者返回部分搜索结果。2012年，WANG等[12]进一步研究了模糊关键字的搜索方案，并且给出了关于方案的安全性证明；SUN等[13]提出了可验证的多关键词排序搜索方案。此外，RHEE等[14]于2013年提出多线性映射的概念，并利用多线性映射构造了无需随机预言机下的聚合和可验证的加密签名方案。随后，GARG等[15]将椭圆曲线对拓展到多线性映射上，首次在理想格上构造了一个实用的多线性映射。2014年，张敏情等[16]基于多线性映射与强不可伪造签名提出一种可公开验证加密方案，该方案是选择密文安全的，与基于双线性对构造的方案相比具有明显优势。2015年，于志敏等[17]利用多线性映射构造了一种环签密广播方案，各个环成员代表环群体匿名签密并广播给接收者，从而实现两个用户群之间环签密通信的功能。2017年，彭巧等[18]利用多线性映射构造了一种信息率可以达到m/（m+1）的秘密共享方案。从而发现多线性映射是构造加密和签名方案的一种非常实用的工具。因此，将多线性映射应用到可搜索加密方案的构造具有很好的前景。

本文针对大数据环境下数据加密搜索机制提出了一种解决方案。

（1）提出了一种基于多线性映射的可搜索加密方案。相比于传统的可搜索加密方案，该方案在大数据环境下具有更大的应用场景。

（2）动态权限分配。由数据拥有者自己定义自身的文档权限，可以进行实时更新，只需将对应的权限发送给服务器，而不需要重新上传索引表。进一步解决了多用户将数据共享在云端的安全问题。

（3）本方案支持多个数据共享者及数据拥有者，避免了传统的单用户对资源共享的限制，使方案更具有实用性。

（4）支持多关键词查询服务，可以更全面的返回用户需要的文件。

1 基础知识

1.1 消息认证码

定义1 消息认证码是指消息被一密钥控制的公开函数所作用后产生的，用作认证符的，固定长度的数值，也被称为密码校验和。

假设通信双方A与B拥有一个共享密钥K，用户A想给用户B发送的消息为M，则用户A先计算MAC=CK（M），其中CK（·）是密钥控制的公开函数，然后用户A给用户B发送M‖MAC，B收到A发送的消息后也做与A相同的操作得到一新的MAC，然后比较两个MAC，就可以知道信息有没有被篡改。

MAC函数与加密算法类似，差别主要在于MAC函数具有不可逆性，因此不易被攻破。

1.2 多线性映射

BONEH等在2003年提出了多线性映射[19]的概念，多线性映射是对双线性映射的推广。相对于双线性映射，多线性映射将更多的循环群关联到目标循环群。

2 基于多线性映射的可搜索加密方案

2.1 方案描述

在基于多线性映射的可搜索加密方案中，包含以下三个实体：云服务器（CSP）、数据拥有者（Data Owner）及数据使用者（Data Users）。本文提出的方案模型如图1所示。

其中，云服务器是诚实但好奇的。一方面，服务器会诚实地执行与用户之间的协议；另一方面，服务器会通过交互过程获得用户的额外信息。在本方案中，每个用户既可以是数据拥有者，也可以是数据使用者。任何用户都可以向数据库上传添加自己的加密数据，且任何授权的用户都可以检索并解密接受需要的密文。

2.2 方案構造

一个基于多线性映射的可搜索加密方案由系统建立、数据加密上传、增删权限、陷门生成、数据查询、验证、数据下载解密等7个算法构成。

（5）加密文档Encrypt（Fi）。 具体实施过程：

数据拥有者选择一种安全的对称加密方案SKE，该对称加密方案的加解密密钥为K，将加解密算法公开，任何授权的用户均可以使用此加密方案加密自己的数据，数据使用者也可以使用约定的密钥生成陷门，从而向服务器发送搜索请求，最终解密服务器返回的数据。

3 方案分析

3.1 正确性分析

3.1.1 协商共享密钥的正确性

3.1.2 解密算法的正确性

3.2 安全性分析

从表1可以看到，本方案与其他方案相比具有以下优势：首先，本方案以多线性映射为工具，提高了方案的安全性；其次，本方案能够满足对搜索结果的可验证性，以防止存储的数据被服务器篡改；另外，本方案可以支持多用户，数据拥有者不仅可以灵活地删除失去权限的用户，还能重新添加新增的授权用户；最后，与其他方案相比，本方案能够支持多关键字检索，为用户的搜索提供更便捷、高效的服务。

4 结语

基于多线性映射的MCDH问题，本文提出了一种标准模型下选择明文攻击安全的可搜索加密方案。 一方面，利用多线性映射提高了数据拥有者的权限，使得数据拥有者可以动态地分配权限；另一方面，方案能够实现多关键词查询，通过支持多用户的搜索，提高数据共享的效率。最后，通过安全性与效率分析，该方案的数据拥有者对数据的管理权限得到了显著地提高，有助于存储数据的安全性，能满足云存储环境中数据的安全、高效和可验证的要求。下一步还需要深入研究大数据环境下支持模糊查询的可搜索加密方案，通过构造模糊集以实现关键字的模糊查询，扩大搜索范围。

参考文献：

[1]刘全明， 赵宝， 高富强.基于属性的可搜索加密方案[J].山西大学学报（自然科学版）， 2016， 39（4）：593-600.

[2]程小燕.具有关键字搜索性质的云存储加密方案[J].聊城大学学报（自然科学版）， 2014， 27（2）：92-94.

[3]杨旸， 杨书略， 蔡圣暐，等.排序可验证的语义模糊可搜索加密方案[J].四川大学学报（工程科学版）， 2017， 49（4）：119-128.

[4]钟晗， 郭飞.基于词嵌入的云存储可搜索加密方案[J].重庆师范大学学报（自然科学版）， 2017（4）：70-74.

[5]SONG D， WAGNER D， PERRIG A. Practical techniques for searches on encrypted data[C]//Procceeding of the IEEE Symposium on Security and Privacy. Berkeley：IEEE Press， 2000：44-55.

[6]GOH E J.Secure indexes[C]//DIMACS Workshop on Privacy Preserving Data-Mining， USA：United Technology Corporation，2003：216-235.

[7]DANG B， CRESCENZO G D， OSTROVSKY R， et al. Public Key Encryption with Keyword Search[J]. Eurocrypt， 2004， 3027（16）：506-522.

[8]CHANG Y C， MITZENMACHER M. Privacy Preserving Keyword Searches on Remote Encrypted Data[C]//Applied Cryptography and Network Security （ACNS 2005）， Berlin：Springer-Verlag， 2005：442-455.

[9]CURTMOLA R， GARAY J， KAMARA S， et al. Searchable Symmetric Encryption： Improved Definitions and Efficient Constructions[C]//ACM Conf. Computer and Comm. Security （ACM CCS2006）， New York： ACM Digital Library， 2006：376-379.

[10]LI J， WANG Q， WANG C， et al. Fuzzy keyword search over encrypted data in cloud computing[C]//Procceeding of the 29th IEEE international Conference on Computer Communications（INFOCOM′10）， San Diego， CA， USA：IEEE Press， 2010： 441-445.

[11]CHAI Q， GONG G. Verifiable symmetric searchable encryption for semi honest but curious cloud servers[C]//Proccceeding of the IEEE Int'l Conf. on Communications. Ottawa， ON， Canada：IEEE Press， 2012：917-922.

[12]WANG C， REN K， YU S， et al. Achieving usable and privacy-assured similarity search over outsourced cloud data[C]// IEEE INFOCOM. Orlando， FL， USA： IEEE， 2012：451-459.

[13]SUN W， WANG B， CAO N， et al. Verifiable privacy preserving multi-keyword text search in the cloud supporting similarity-based ranking[J].IEEE Transactions on Parallel and Distributed Systems， 2013， 99（11）：1-11.

[14]RHEE H S， PARK J H， SUSILO W， et al. Improved Searchable Public Key Encryption with Designated Tester [C]//Proceedings of the 4th International Symposium on Information， Computer， and Communications Security. Sydney， Australia：ACM Press， 2009： 376-379.

[15]GARG S， GENTRY C， HALEVI S. Candidate Multilinear Maps from Ideal Lattices[C]// International Conference on the Theory and Applications of Cryptographic Techniques.Berlin， Heidelberg：Springer，2013：1-17.

[16]张敏情， 张腾飞， 王绪安. 基于多线性映射的可公开验证加密方案[J].武汉大学学报（理学版）， 2014， 60（6）： 507-512.

[17]于志敏， 景征骏， 古春生. 基于多线性映射的环签密广播公钥方案[J]. 计算机科学， 2015， 42（3）： 106-110.

[18]彭巧， 田有亮. 基于多线性Diffie-Hellman问题的秘密共享方案[J].电子学报， 2017， 45（1）： 200-205.

[19]BONEH D， SILVERBERG A. Applications of multilinear forms to cryptography[J].Contemporary Mathematics， 2003， 324（1）： 71-90.

[20]ZHAO Y， CHEN X， MA H， 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.

[21]YANG H M， XU C X， ZHAO H T. An Efficient Public Key Encryption with Keyword Scheme Not Using Pairing[C]// First International Conference on Instrumentation， Measurement， Computer， Communication and Control. Washington， DC， USA：IEEE Computer Society， 2011：900-904.

[22]LUO W， TAN J. Public Key Encryption with Keyword Search Based on Factoring [ C ]//Proceedings of CCIS' 12. Hangzhou：IEEE Press， 2012： 1245-1247.

[23]BAEK J， SAFAVINAINI 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.

（責任编辑：周晓南）