云环境下一种排序非对称的可搜索加密方案

林 楠，费益军，王宇飞，彭凝多

（1.国家电网公司信息通信分公司，北京100761；2.国家电网公司江苏省电力公司，南京210024；3.南京南瑞集团公司北京中电普华信息技术有限公司，北京100192；4.电子科技大学计算机科学与工程学院，成都611731）

云环境下一种排序非对称的可搜索加密方案

林 楠1，费益军2，王宇飞3，彭凝多4

（1.国家电网公司信息通信分公司，北京100761；2.国家电网公司江苏省电力公司，南京210024；3.南京南瑞集团公司北京中电普华信息技术有限公司，北京100192；4.电子科技大学计算机科学与工程学院，成都611731）

可搜索加密算法的基本功能之一是对搜索结果进行排序并返回最佳匹配文件。为使该功能在非对称可搜索加密算法中实现，将非对称加密结构转换为对称加密结构，并结合保序加密算法，提出一种在非对称可搜索加密算法上实现排序查询功能的方案，进行混合加密密文的检索。实验结果表明，与传统的只支持对称可搜索加密结构排序方法相比，该方法支持非对称加密，具有较好的检索效率，并且应用性强。

可搜索加密；排序加密；保序加密；云存储；非对称加密

1 概述

云存储为用户提供了弹性、高可靠、易使用与价格便宜的数据存储服务。随着云计算的发展，该类数据外包方式受到越来越广泛的应用［1-2］。然而，数据外包存在着天然的安全隐患，因为敏感的数据（例如用户的隐私数据、商业数据等）如果放在云上，云服务提供商将能够直接读取与使用该数据，从而导致可能侵犯用户的隐私与破坏数据的安全［3-5］。对大多数人而言，假定云服务提供商是“绝对可信”是不可能的，因此需要从技术层面为用户提供隐私与数据保护，且在安全性保证的前提下尽可能保障用户的正常操作功能（例如用关键字检索文件）。目前，用户隐私的保护与用户数据的安全也成为了制约数据外包模式是否能被更广泛应用的瓶颈。

可搜索加密技术是一种在不影响数据检索功能的条件下，保护用户数据安全与查询隐私的重要技术手段。对称可搜索加密方案（Symmetric Searchable Encryption，SSE）［6-10］基于对称加密技术，加密者可以对远程密文进行安全的检索。基于公钥机制的非对称可搜索加密方案（Asymmetric Search-able Encryption，ASE）［11-13］是可搜索加密算法中的另一类加密方案，其应用更灵活，适用面更广泛，因此在近几年得到了较快发展，其应用场景为：数据外包者使用公钥加密数据放在云端，用户使用私钥生成安全的查询并提交给服务器，最后服务器返回满足条件的相应文件。而在所有的过程中，服务器无法得知外包的数据内容与用户查询的内容信息。

支持对返回的文件按关键字匹配度进行排序，是可搜索加密算法中的标准应用之一。文献［14］在对称加密的结构中设置了关键字相关性，且为了保证安全进行了随机化，使得可以近似地返回最相关的文档。文献［15］将相关性用保序加密（Order Preserving Encryption，OPE）算法加密，使得可以精确返回最相关的文档。文献［16］基于两轮协议，在第一轮操作中返回加密的相关性，这样用户可以自行选择最佳匹配文档。然而，这一系列的方案均基于对称加密技术。如何在非对称加密应用场景中，用户用私钥生成的令牌来排序用公钥生成的相关性（此处安全前提是公钥生成的相关性无法直接排序，否则会泄漏加密的文件信息）成为一个挑战性的难题。

本文基于非对称加密结构到对称加密结构的转化思路，并结合基于对称加密的保序加密算法，以实现排序查询功能在非对称可搜索加密算法中的应用。

2 方案构造

排序查询功能指所有匹配的文档会根据一个标准进行排序，最终仅返回给用户最相关的k个文档。该功能的查询SQL格式为“ORDERED BY‘keyword'”。文献［15］介绍了一种相关性评分的计算方法，并提出了基于保序加密算法（OPE）的分数大小比较方案。采用同样的保序加密算法为基础，排序功能组件可以先记录加密的相关分数，并构造一个索引记录“令牌，分数”数据对，从而使得功能组件可以在计算时间复杂度为O（1）的条件下获取分数并比较大小进行排序。

为了存储索引记录，本文采用基于稀疏矩阵的间接寻址方案［17］构造一个2维索引表A，记录数据对＜关键字，相关性分数＞。所有数据均加密。当查询时，服务器查找所有匹配文档的相关性分数，并找出最佳k个文档。为了安全地使用保序加密算法，加密数据前需要一个预处理过程。构造一个保序加密表（OPE Table）来预处理所有的明文，并按如下步骤存储加密的相关性分数：

（1）给定一个文档集D=（d1，d2，…，dn），对文档集中的每一个文档dk（1≤k≤n）扫描其中的ok个关键字W。对于dk中的每一个关键字，根据关键字出现的频率计算相关性分数（1≤i≤ok），并记录一个对应于dk的ok×3矩阵。该矩阵的第i行记录，其中，为第1个在文档中出现的位置。

（2）对于所有文档，配置OPE加密的数据量N= o1+o2+…+on，编号依次为s1，s2，…，sN。对每一个数据sj（1≤j≤N），其保序加密结果为ej。将之前的矩阵转换成为一个保序加密表，表的第i行记录，其中，是的保序加密结果。

（3）对于一个文档，至多包含|d|/2+1个关键字（注意每个关键字后包含一个分隔符，否则该关键字无法被识别）。因此，索引表在最后填充到|d|/ 2+1个数据项，从而保障文档内容与数据项数量无关。

为了应用非对称可搜索加密算法的相关功能，这里引用非对称可搜索加密算法的部分内容如下：

定义s←PEKS（Kpub，w）为非对称可搜索加密算法中的可搜索结构的构造子算法。输入公钥Kpub与一个关键字w，输出可搜索结构s。算法由用户执行，生成的可搜索结构s链接到加密的消息（单个文档）后提交给服务器。

定义c←Enc（Kpub，d）为非对称可搜索加密算法中的文档加密子算法。输入公钥Kpub与消息d（单个文档），输出密文c。算法由数据发送者执行，密文c连同多个可搜索结构发送给服务器。

定义一个哈希函数：fh：｛0，1｝*→｛0，1｝l，其中，l为映射的长度（根据选择的哈希函数）。例如，如果采用MD5作为fh，则l为128 bit。

可排序非对称可搜索加密算法包括构造算法Build与过滤算法Filter两部分，分别用于加密时的功能结构的构造与检索时的文件查询，具体方案如算法所示。

算法 可排序加密查询的构造与过滤算法

算法Build的主要流程是从文档中抽取关键字，并基于保序加密方案，结合非对称可搜索加密算法的数据结构，构造索引表。算法Filter的主要流程是根据每个加密文档对应的加密索引表，对查询结果进行排序，并返回排序结果，从而返回最匹配用查询的文档。

3 安全性证明

非正式而言，排序查询功能的安全性保障模型为：给定2个大小相同的文档集D1与D2。挑战者随机投掷一个公平的硬币b并用LSE加密Db（密文的顺序需要随机化）。敌手可以查询一个关键字并获得排序的文档子集，但无法分辨挑战者是从哪个文档集中选择的子集。

基于文献［8］提出的抗非自适应选择关键字攻击模型，并结合文献［18］提出的保序概念（这里定义为可排序），正式定义抗非自适应选择排序攻击安全模型如下。

定义（抗非自适应选择排序攻击） 令∑为排序查询功能组件，k∈ℕ为安全参数。考虑以下的概率实验，其中，A为敌手，Sim为模拟器：

（1）Real∑，A（k）：挑战者执行密钥生成算法Gen（1k）产生密钥K。敌手产生一个文档集D=（d1，d2，…，dn）（每个文档的大小固定），从挑战者处接收到加密的文档C=（c1，c2，…，cn）与功能结构L=（L1，L2，…，Ln）（随机顺序）。敌手提交一个查询w，其中，w∈d1∩d2∩…∩dn，并从挑战者处接收到映射v。最终，A返回一个值b（1或0）作为实验的输出。

（2）Simulate∑，A，Sim（k）：给定文档数量n，每个文档的大小与映射的大小，Sim生成C*，L*， v*并发送结果给敌手A。最终，A返回一个值b（1或0）作为实验的输出。

称排序查询功能组件是CRKA安全的，当且仅当对于所有多项式时间敌手A，存在一个模拟器Sim满足：|Pr［Real∑，A（k）=1］-Pr［Simulate∑，A，Sim（k）= 1］|≤negl（k）其概率取决于密钥生成算法Gen（1k）。

定理 如果LSE的接口具有CPA安全性，底层封装的OPE算法具有POPF-CCA安全性，则排序查询功能组件具有CRKA安全性。

证明：模拟器以如下方式产生C*，L*，v*：对于C*，模拟器产生n个随机字符串，每个字符串大小为。对于L*，令m=|d|/2+1，模拟器产生m个随机字符串V*=，每个字符串长度为。模拟器构造一个m×n矩阵，其中，每个元素为一个随机数。则对每一个文档而言，模拟器产生索引项=。对于v*，模拟器随机选择。

现在证明没有一个多项式分辨器可以分辨（C，L，v）与（C*，L*，v*）。由于密钥K对于敌手是保密的，因此接口的CPA安全性直接保障C与C*间不可分辨。同时，该安全性保障v与v*间也不可分辨。当接收到v=vi∈V或后，敌手可以调用Filter（C，L，v）或者Filter（C*，L*，v*）来获取r1= L1［vi］=e1，e2，…，rn=Ln［vi］=en或者得到。POPFCCA安全性保障集合（r1，r2，…，rn）与集合间不可分辨，即敌手无法分辨OPE的加密结果与一个随机保序函数的输出结果。由此，L与L*间不可分辨。

4 性能分析

算法由C++语言编码，并在一台虚拟机上运行。虚拟机的配置为64位的双核2.1 GHz CPU，4 GB内存，运行Centos操作系统。每一个文档设置为固定的10 KB，其内容为从一个字典随机抽取的单词组合。查询也是随机关键字（数量也是随机的）。过滤算法的运行结果如图1所示。

图1 文档检索执行效率

从图1中可以看出，可排序的非对称可搜索加密方案运行效率较高，其根本原因是在加密时将非对称加密结构间接转化成了对称加密结构，从而实现了传统仅在对称加密算法中支持的功能，并且达到了和对称可搜索加密算法等同的效率。令n表示需要进一步过滤的文档数量。对于排序查询，其主要的操作为从索引表中获得相关性分数，该表由稀疏矩阵的间接地址技术维护（压缩存储），因此总查询时间复杂度为O（n）。另外需要从最终结果中比较分数，选择出最佳k个匹配的文档，其总计算复杂度为O（n）。由于该索引的压缩方案并不是唯一的，这里增加非压缩的索引方案，以此作为检索时间的下限作为参考。

5 结束语

本文提出了一种在非对称可搜索加密算法上实现排序查询功能的方案，弥补了非对称可搜索加密算法功能较单一的不足。此外该方案本质上是对称加密算法在非对称加密结构中的混合应用，因此可以扩展到其他基于对称加密的数据结构上，从而丰富非对称可搜索加密方案的功能与应用。

［1］ Fox A，Griffith R，Joseph A，et al.Above the Clouds：A Berkeley View of Cloud Computing［D］.Berkeley，USA：Department of Electrical Engineering and Computing Sciences，University of California，2009.

［2］ Chakraborty R，Ram ireddy S，Raghu T S，et al.The Information Assurance Practices of Cloud Computing Vendors［J］.IT Professional，2010，12（4）：29-37.

［3］ Takabi H，Joshi B D，Ahn G J.Security and Privacy Challenges in Cloud Computing Environments［J］.IEEE Security&Privacy，2010，8（6）：24-31.

［4］ Subashini S，Kavitha V.A Survey on Security Issues in Service Delivery Models of Cloud Computing［J］. Journal of Network and Computing Applications，2011，34（1）：1-11.

［5］ Popovic K，Hocenski Z.Cloud Computing Security Issues and Challenges［C］//Proceedings of IEEE MIPRO'10.Washington D.C.，USA：IEEE Press，2010：344-349.

［6］ Song D X，Wagner D，Perrig A.Practical Techniques for Searches on Encrypted Data［C］//Proceedings of IEEE Symposium on Security and Privacy.Washington D.C.，USA：IEEE Press，2000：44-55.

［7］ 沈志荣，薛 巍，舒继武.可搜索加密机制研究与进展［J］.软件学报，2014，25（4）：880-895.

［8］ Curtm ola R，Garay J，Kamara S，et al.Searchable Symmetric Encryption：Improved Definitions and Efficient Constructions［C］//Proceedings of the 13th ACM Conference on Computing and Communications Security.New Yrok，USA：ACM Press，2006：79-88.

［9］ Kamara S，Papamanthou C，Roeder T.CS2：A Searchable Cryptographic Cloud Storage System，TechReport：MSRTR-2011-58［R］.Redmond，USA：Microsoft Research，2011.

［10］ Chase M，Kamara S.Structured Encryption and Controlled Disclosure［C］//Proceedings of ASIACRYPT'10. Berlin，Germany：Springer，2010：577-594.

［11］ Boneh D，Di-Crescenzo G，Ostrovsky R，et al.Public Key Encryption with Keyword Search［C］//Proceedings of Advances in Cryptology-Eurocrypt'04.Berlin，Germ any：Springer，2004：506-522.

［12］ Abdalla M，Bellare M，Catalano D，et al.Searchable Encryption Revisited：Consistency Properties，Relation to Anonymous IBE，and Extensions［C］//Proceedings of Advances in Cryptology-CRYPTO'05.Berlin，Germany：Springer，2005：205-222.

［13］ Boneh D，Kushilevitz E，Ostrovsky R，et al.Public Key Encryption that Allows PIR Queries［C］//Proceedings of Advances in Cryptology-CRYPTO'07.Berlin，Germ any：Springer，2007：50-67.

［14］ Cao N，Wang C，Li M，et al.Privacy-preserving Multikeyword Ranked Search over Encrypted Cloud Data［J］. IEEE Transactions on Parallel and Distributed System s，2014，25（1）：222-233.

［15］ Wang C，Cao N，Li J，et al.Secure Ranked Keyword Search over Encrypted Cloud Data［C］//Proceedings of the 30th IEEE International Conference on Distributed Computing Systems.Washington D.C.，USA：IEEE Press，2010：253-262.

［16］ Swaminathan A，Mao Y，Su G M，et al.Confidentiality-preserving Rank-ordered Search［C］//Proceedings of 2007 ACM Workshop on Storage Security and Survivabi-lity.New Y rok，USA：ACM Press，2007：7-12.

［17］ Fredman M L，Komlós J，Szemerédi E.Storing a Sparse Table with O（1）Worst Case Access Time［J］.Journal of the ACM，1984，31（3）：538-544.

［18］ Boldyreva A，Chenette N，Lee Y，et al.Order-preserving Symmetric Encryption［C］//Proceedings of Advances in Cryptology-EUROCRYPT'09.Berlin，Germany：Springer，2009：224-241.

编辑 索书志

Ranked-order Asymmetric Searchable Encryption Scheme in Cloud Environment

LIN Nan1，FEIYijun2，WANG Yufei3，PENG Ningduo4
（1.Information&Telecommunication Branch，State Grid Corporation of China，Beijing 100761，China；
2.Jiangsu Electric Power Company，State Grid Corporation of China，Nanjing 210024，China；
3.Beijing China Power Information Technology Co.Ltd.，NARIGroup Corporation，Beijing 100192，China；
4.School of Computing Science and Engineering，University of Electronic Science and Technology of China，Chengdu 611731，China）

Ranking the search results and returning the most matched documents is an important and basic function for searchable encryption technique.In order to support such function in asymmetric searchable encryption，this paper proposes a method to transform the asymmetric structure to symmetric structure.Combining with the preserving-order encryption，searching in the mixed encrypted documents is realized.In comparison with prior works that only support symmetric encryption，the algorithm supports asymmetric encryption.Experimental results show that the new algorithm is efficient and practical.

searchable encryption；ranked-order encryption；preserving-order encryption；cloud storage；asymmetric encryption

林 楠，费益军，王宇飞，等.云环境下一种排序非对称的可搜索加密方案［J］.计算机工程，2015，41（11）：190-193.

英文引用格式：Lin Nan，Fei Yijun，Wang Yufei，et al.Ranked-order Asymmetric Searchable Encryption Scheme in Cloud Environment［J］.Computer Engineering，2015，41（11）：190-193.

1000-3428（2015）11-0190-04

A

TP309

10.3969/j.issn.1000-3428.2015.11.033

四川省科技支撑计划基金资助项目（2013JQ0005，2014JY0010）。

林 楠（1987-），男，硕士，主研方向：信息安全，云计算；费益军、王宇飞，硕士；彭凝多，博士研究生。

2014-11-17

2014-12-04 E-m ail：freedom.w ind@163.com