可搜索加密机制研究与进展

 

    1、灵活高效的搜索语句的设计。灵活的搜索语句不仅能够让用户可以更加精确地定位到所需要的数据文件，同时也可以让用户能够更加灵活地表述搜索需求。SE机制从研究初期的支持单词搜索，到后来逐渐发展为支持连接关键字搜索，再到支持区间搜索和子集搜索等复杂的逻辑语句。其研究难点在于：如何达到支持复杂的搜索请求的效果，以及如何寻找到适合的困难假设来证明其安全性，同时使得该机制又具有可以接受的性能。随着云计算的发展，在海量用户和海量数据的应用场景下，提供安全灵活高效的SE机制将是研究者所极力追求的目标之一。

    2、模糊搜索和基于相似度排序的模糊搜索。由于用户表述不精确或者输入错误等各种原因，造成精确匹配搜索将有可能无法找到用户所真正所需要的文件，因此模糊搜索的引入能够智能地寻找与用户所输入的搜索词相关的文件。由于数据存储形式为密文且基于安全需求的考虑，目前在明文上所广泛应用的模糊搜索方法无法直接运用到密文上的搜索中，因此设计支持模糊搜索和基于相似度排序的模糊搜索的可搜索加密机制是一个亟待研究的内容之一。

    3、在不同现实场景中对SE机制的应用。自从SE机制提出后，针对其所能部署的应用场景得到了研究者的关注。从SE机制提出初期的数据所有者独享数据[8,10,15,26]，到后来数据所有者将搜索的能力共享给其他用户[12,13,21,22,28]，以及云存储环境下的一些特殊场景中用户私密数据的管理[14,12,21]等。针对不同的应用场景需要相应的SE机制来支持，因此设计适合目的应用场景的SE机制是应用密码学领域的研究方向之一。

 

    现今众多的SE机制的设计可以根据其构造算法的不同而分为两类，即基于对称密码学算法（symmetric key cryptography based）的SE机制[8,9,10,12,13,15,21,22,26,32]，以及基于公钥密码学算法（public key cryptography based）的SE机制[9,11,14,16,20,23,24,29,30]。前者主要是使用一些伪随机函数生成器(pseudorandom function generator)、伪随机数生成器(pseudorandom number generator)、哈希算法和对称加密算法构建而成，而后者主要是使用双线性映射等代数工具，并将安全性建立在一些复杂性问题的难解性之上。这两种方法区别是：首先，由于大部分基于公钥密码学算法的SE机制都是基于双线性映射之上构造，在搜索的过程中需要进行群元素之间和双线性对的计算，因此它们的开销要远高于基于对称密码学算法的SE机制。其次，基于对称密码学的SE机制更加适用于单用户创造数据并与多用户共享的应用场景，而基于公钥密码学的SE机制则允许除数据所有者之外的用户使用可搜索加密机制来产生数据密文并生成加密后的索引表。

 

    2.1 SE机制的主要算法

    由于现今SE机制的构造方法众多，其形式化描述方法各不相同。基本的SE机制主要包括四个算法，分别是：Setup[20]、GenToken[20]、BuildIndex[20]和Query[20]。

    1、Setup：该算法主要由权威机构或者数据所有者进行并生成密钥。在基于公钥密码学的SE机制中，该算法会根据输入的安全参数(security parameter)来产生公钥和私钥；在基于对称密码学的SE机制中，运行该算法后会产生一些私钥，例如伪随机函数的密钥等。

    2、GenToken：该算法以根据用户需要搜索的关键字为输入，产生相应的搜索凭证。算法的执行者主要是由应用场景决定，可以由数据所有者、用户或者权威机构来执行（具体场景部分将在第4节中进行讨论）。

    3、BuildIndex：该算法由数据所有者执行。在这个算法中，数据所有者将根据文件内容，选出相应关键字集合，并使用可搜索加密机制建立索引表。在基于公钥密码学的SE机制中，数据所有者会使用公钥对每个文件的关键字集进行加密；在基于对称密码学的SE机制中，数据所有者会使用对称密钥或者使用基于密钥的哈希算法对关键字集进行加密。而文件内容主体将会使用对称加密算法进行加密。

    4、Query：该算法是由服务器端进行。服务器将以接收到的搜索凭证和每个文件中的索引表为输入，进行协议所预设的计算，并最后通过输出结果是否与协议预设的结果相同来判断该文件是否满足搜索请求。服务器最后将搜索结果返回。

    最后，用户在获得返回的文件密文之后，再使用相应的对称密钥对数据密文进行解密。

 

    2.2基于对称密码学的SE机制

    对称密码学算法指的是加密的密钥和解密的密钥都是衍生于同一个密钥，它们或者相等或者之间需要一些简单的转换[36]。对称密码学算法的优点是计算开销小，适用于大块数据的加密，缺点则是加密方和解密方需要在事先实现密钥的协商，而密钥则需要通过安全信道传输。

    而基于对称密码学的SE机制是采用伪随机函数、伪随机置换以及哈希算法(或者散列算法)对关键字按照一些步骤进行处理，当需要对关键字进行搜索时，首先将关键字随机化处理，然后让服务器端照着协议所预设的计算方式进行关键字的匹配，如果最后的结果是某种特定的格式，则说明匹配成功。例如在文献[8]的工作中，当服务器端将关键字的密文和服务器端的密文C进行异或运算后，需要判断结果的前(n-m)位的哈希值是否是后m位；在文献[9]的工作中，需要判断最后的结果是否是(flag|K)格式。基于对称密码学的SE机制在运算性能上较基于公钥密码学的SE机制高效，但是在支持搜索语句的灵活性上，现今的基于对称密码学的SE机制只能支持单个关键字或者是连接关键字的搜索，而且搜索凭证的大小需要与所搜索的关键字数目呈线性关系。

 

    2.3基于公钥密码学的SE机制

    现今应用比较普遍的基于公钥密码学的SE机制大部分是构建于双线性对（bilinear pairing）之上，其安全性都是基于不同安全假设。下面先给出关于双线性对的定义，以及一些应用较为普遍的困难问题。

定义1[16]：（双线性对定义）对于双线性映射e=G1×G1→G2, 其需要满足以下条件：(1)双线性(bilinear)：；(2)非退化性(Non-degenerate)；(3) 可计算性(Computable)：群中的运算以及双线性映射e运算在多项式时间内可解。

定义2[11]：(DDH，离散Diffie-Hellman问题)。假设G是一个素数阶p的群，其中g是G的生成元，随机从{0,…,p-1}中选择元素a,b,c，给定元组，判断gc是否等于gab。

定义3[16,20]：(BDH，双线性Diffie-Hellman问题)。对于群G及其生成元g，给定ga,gb,gc，计算eg(abc)。

    基于公钥密码学的SE机制由于涉及到群元素之间的运算，开销较大。同时正是由于双线性对的特性和复杂性假设的存在，使得一些支持更加复杂的搜索语句的工作得以发展。另外，基于公钥密码学的SE机制更加适用于一些不安全的网络中，它不需要加密方和解密方事先协商密钥。用户可以直接使用对外公开的公钥对关键字集合进行加密，而数据所有者可以使用私钥产生搜索凭证进行密文上的关键字搜索。

 

3. SE机制搜索效果分析

    搜索语句是用户搜索兴趣的表现，灵活的搜索语句不仅可以让用户能够更加准确地描述自己的搜索意愿，同时也能够更加精确地定位到用户需要的文件。在本节中，根据SE机制支持的搜索语句，分为单词字搜索、连接关键字搜索和复杂逻辑结构语句三类。

 

    3.1支持单词搜索的SE机制

    支持单词搜索指的是用户一次只能对一个关键字进行搜索，云端服务器通过该凭证搜索到包含该词的文件，然后将最后满足条件的结果返回给用户。早期的SE机制研究主要考虑的应用场景是：数据所有者为了节省本地存储空间将数据以密文形式存储在远端服务器，并在带宽受限的环境下进行关键字搜索操作。在该情况下所衍生出的SE机制主要是以基于对称密码学算法为主。

    文献[8]于2000年提出了一种基于对称密码学算法的实用SE方案，具体如图2所示。在这个方案中，伪随机函数F和f公开。在对数据加密时，文件内容被分割为固定大小的文件块，经过加密后的文件块被分为两个部分，分别是Li和Ri，同时数据所有者利用伪随机位(pseudorandom bits)Si生成(SiFk(Si))，并与Li,Ri经过异或运算生成密文Ci，其中Li和Si长度分别为(n-m)位（或m位）。当用户需要搜索关键字的时候，数据所有者将EWi和Ki发给服务器端。服务器端将密文Ci与EWj进行异或运算，然后判断得到的结果是不是满足(S,Fki（S）)的形式，如果满足，则说明匹配成功，并将该文件返回。这种方法虽然能够基本实现单词搜索，但是存在着一些缺陷：云端服务器需要对每个文件的内容进行扫描，看密文内容是否存在给定的关键字的密文形式相匹配的内容，造成的计算开销将同文件大小呈线性关系，在海量数据环境下，该方法效率不佳，同时服务器端可以通过统计攻击的方法，获得一些额外的用户隐私信息，例如通过得到的搜索凭证来判断用户前后搜索的关键字是否相同等。

 

Fig.2 The final scheme in reference [8]

图2  文献[8]中的最终机制

    针对文献[8]中搜索效率低下等缺点，文献[10]提出了使用安全索引的方法来快速实现对海量密文数据的搜索。这种搜索机制是建立在Bloom filter[37]之上，即每个文件都有对应的一些独立的哈希函数和Bloom filter数据结构。在文件加密之前，需要对文件中的关键字使用私钥加密，再使用哈希函数映射到filter之上并记录，最后将映射后的filter和文件的密文上传到服务器中。当用户需要进行密文搜索时，需要将关键字的密文发送给云端服务器，再由云端服务器使用每个文件的哈希函数进行关键字到filter的映射。如果映射到的位置之前都有记录的痕迹，则说明这个关键字有很大的概率是在该文件中，最后云端服务器将得到的匹配文件发给用户。这种方法的优点是能够利用哈希函数计算快速的特点，快速地查找关键字所在的密文文件，但是它也继承了Bloom filter存在错误率的特点，有可能导致一些文件本来并不包含关键字，最后却能够通过哈希函数的检测，而被云端作为结果返回给用户，给用户带来一些额外的带宽开销和计算开销。

    由于之前的SE机制都是基于对称密码学算法，文献[16]给出了基于公钥密码下的可搜索加密机制PEKS的构造方法，他们主要考虑的应用场景是：用户Alice掌握着私钥(Private Key)，并将相对应的公钥(Public Key)公开，为了让电子邮件网关(Email gateway)分拣接收到的邮件，Alice会事先将一些特定关键字的陷门(Trapdoor)发送给电子邮件网关，使得它能够通过判断邮件中是否包含关键字W来选择接受设备。与此同时，电子邮件网关在判断的过程中无法获得关于关键字和邮件内容的有效信息。在PEKS机制的加密算法中使用到了两个哈希算法，用户使用哈希算法将每个关键字映射到群中，然后选取随机数r和双线性映射将关键字W随机化映射到群中。这样即使是相同的关键字，所生成的密文也将不同，并将r的信息以形式保存，最后生成密文。当需要生成搜索凭证时，使用将关键字映射到中，并选取随机数a，将发给服务器端，使得即使是相同的关键字，由于随机数a的作用，所产生的搜索凭证也将不同。最后，服务器端利用双线性映射的性质进行关键字的匹配判断。该方法的优点是支持数据接收者对多个发送者所加密的密文中进行搜索的应用场景，而且由于随机数的作用，系统的加密效果为非确定性加密，导致了服务器端无法通过密文是否相同来判断索引表（或搜索凭证）中是否具有相同的关键字。缺点是计算开销因为双线性对的引进而加大，特别是对操作(pairing operation)的计算开销较大，使得该方法在海量数据处理场景中的应用性受到一定的限制，另外，PEKS的安全性是在随机语言机模型(random oracle model)下成立，并不适合现实应用。

    文献[9]分别基于对称密码学和基于身份加密(identity based encryption，简称IBE)给出了两种SE机制的设计方法来实现在加密后的审计日志上进行关键字的搜索。在基于对称密码学的设计中，审计日志服务器(audit log server)首先从数据中萃取出具有代表性的关键字，然后使用带有密钥的伪随机函数和一个随机位串r，计算得到密文。用户需要向审计代理(audit escrow agent)请求搜索关键字w操作，审计代理根据每个审计日志服务器的密钥，使用伪随机函数生成搜索凭证(search capability)并发给用户。用户持有该搜索凭证并利用r对密文进行XOR运算，如果结果满足某种特定的格式，则说明搜索成功。而在基于IBE的设计中，审计日志服务器以关键字为公钥，对(flag|K)使用IBE的加密算法进行加密。当收到搜索关键字w的请求后，审计代理通过计算得到w的私钥作为搜索凭证发给用户。用户使用对密文使用IBE中的解密算法进行解密，若得到的结果是(flag|K)形式，则说明解密成功。与其他SE机制的应用场景不同，该方法需要审计日志服务器对日志进行加密，同时要求用户访问服务器进行搜索，需要用户自己承担搜索开销。

    文献[15]则考虑了两种应用场景，分别是当用户拥有足够的空间存储生成关键字的字典，以及当用户所拥有的存储空间无法存放字典的情况，所谓的字典就是用来表示每个关键字的、长度为d的二元组合。在第一种情况中，用户需要为每个文件j建立二进制位串索引，并使用伪随机函数将该文件包含的每个关键字的id使用伪随机置换函数进行置换，并将置换结果所在的位置1，并使用另一个随机位串对进行异或运算，隐藏中每一位的值。在第二种情况中，用户将字典用伪随机置换函数随机化后存储在服务器端。当需要进行关键字的搜索时，则需要与服务器端进行两轮的交互，第一轮是从服务器中取出想要搜索关键字的二进制串表示，第二轮中则是计算出关键字的陷门并发给服务器端。

    针对之前的SE机制只是假设攻击者(adversary)并不会考虑搜索的陷门(trapdoor)和以前搜索结果的特点，文献[22]提出了一种更强的自适应(adaptive)攻击者模型，在该模型中，攻击者会根据之前搜索过的陷门和搜索结果为参照，来决定下一次的查询语句。在他们的工作中提出了两种设计方案，第一种设计方案是在假设攻击者是non-adaptive情况下保证安全，并使用了连接表(linked list)、数组和查找表等数据结构将不同文件中的相同关键字连接起来，提高了搜索的性能。而在第二种方案中则保证了自适应的语义安全(adaptive semantic security)。同时，针对以前基于公钥密码学算法中只有掌握私钥的用户才能对用公钥加密的数据进行搜索的限制，这篇文章采用了广播加密(broadcast encryption)的方法，在共享用户群中共享密钥r，使得该共享用户群也能够对这些密文数据进行搜索。

    之前的SE机制只是简单地将满足关键字的搜索结果返回却缺乏对搜索结果进行整理，而用户需要在本地对结果进行整理并找出最相关的结果。文献[12]针对搜索结果进行了一些优化，提出了一个在云数据中实现安全排序的方法，这种方法不仅能够使云端服务器进行关键字的密文搜索，同时还能够对搜索的结果对于关键字的相关性程度进行排序，最后将前k个最相关的文件返回给用户，这种操作更加有利于用户更快地找出自己所感兴趣的数据，节省了用户的开销。为了实现排序的效果，首先需要文件所有者在上传文件之前，针对每个关键字在文件中出现的次数，根据相关性分数模型计算该文件对于每个关键字的相关性得分，然后在本地构建一个关键字和文件的倒排索引表，每个表格的数据则是该关键字和文件的相关性分数，然后再将索引表加密，同时使用保序加密(order-preserving encryption[38])对相关性分数加密，当用户需要搜索密文关键字时，云端服务器再根据每个文件对该关键字相关性分数的密文结果进行排序，并将经过排序后的前k个文件返回给用户。这种方法的优点是在每次搜索的过程中，用户可以得到在相关性分数模型下对该关键字最为相关的文件，提高了用户体验，并节省了一定的带宽和因为解密带来的计算开销，但是云端服务器也掌握了每个文件对于某个关键字相关性程度的信息。

    针对有可能发生的印刷错误以及用户由于疏忽导致精确匹配无法发生作用的情景，文献[13]则考虑了在云计算中实现密文上的模糊关键字搜索的应用场景。在他们的设计中，主要考虑了三种情况下的模糊搜索，分别是插入、删除和替换操作。他们使用了编辑距离(edit distance)的概念，对于某个单词，他们将在某个编辑距离之内的所有单词都加密，然后上传到云端服务器。当用户需要搜索某个单词时，可以定位到距离该单词某个编辑距离的所有单词，然后将包含这些单词的文件返回给用户。该方法虽然可以实现对于关键字的模糊搜索，但是带来的代价是需要存储的可能数据量过于庞大，而且用户虽然可以得到近似的结果，但是结果的不精确性也将给用户带来极大地网络开销和计算开销。

 

    3.2支持连接关键字搜索(conjunctive keyword search)的可搜索加密机制

    由于支持单词的SE机制只允许用户一次只能发送一个单词的搜索凭证，这极不符合现实生活中多词搜索的应用需求，特别是当单词无法精确定位到用户所想要的文件时，单词搜索的限制可能需要用户使用不同关键字多轮搜索，或者是经过一轮密文搜索后，对返回结果解密，通过在明文上进行搜索来寻找目标文件，而这样的结果将给用户带来极差的操作体验。针对这些不足，支持连接关键字搜索的可搜索加密机制开始得到研究者广泛的关注和研究。

    文献[11]针对之前的搜索机制中只能使用单词搜索的不足，提出了两种支持连接关键字搜索的SE机制。在他们的方案中，每个文件都有固定的数量的关键字域，每个域中都有特定的关键字来表征这些文件的特性。例如在邮件中具有关键字域“主题，发送方，接收方”，而在“主题”域中可能具有关键值“会议”等。第一种机制能够达到固定的在线网络开销，所谓的固定，指的是用户数据所有者进行在线交互的网络开销是依赖于每个文件中的关键字域数量，在这个方案中，用户需要发送两个部分的搜索凭证，第一个部分可以在高速网络中离线发送到服务器端，称为“原型凭证(proto-capability)”，其大小和存储在服务器端的文件数量线性相关，第二个部分称为“查询部分(query part)”，需要用户同数据所有者进行在线交互而得到。当用户将查询部分发给服务器端时，服务器端会将其与原型凭证整合成完整的搜索凭证，并进行搜索。该机制的安全性是建立在DDH(Decisional Diffie-Hellman)问题的复杂性之上。针对第一种机制可能导致网络开销过大的情况，在第二种机制中使用了固定网络开销的搜索凭证，即搜索凭证对于文件数量而言是固定的，但是依然与关键字域数量线性相关。

    文献[26]分别是基于对称密码学和公钥密码学提出了两种实现连接关键字搜索的高效SE机制，但是需要保证没有重复的关键字。在基于对称密码学的SE机制中，首先对关键字采用伪随机函数进行加密，当用户需要搜索m个关键字时，就使用秘密共享(secret sharing)中的recover算法，将这m个关键字的密文作为输入，并将结果作为陷门发给服务器端。服务器端也调用secret sharing中的recover算法，对于每个文件进行判断，如果结果等于陷门，则说明该文件包含了所有的关键词。但是该方案要求陷门的大小和文件数量呈线性关系。针对这个问题，文中提出了基于公钥密码学的SE机制，该使用了双线性映射使得陷门的大小固定，其中它的安全性则是建立在DDH、XDH和MXDH复杂性之上。

    之前的基于公钥密码学机制要么只能支持“多个发送者-单个接受者”的应用场景，要么密文过于庞大的情况，文献[24]针对这种情况提出了一种基于公钥密码学的SE机制。其核心思想是，通过使用多接受者公钥加密方法(multi-receiver public key encryption)将所有接受者的公钥对关键字集合进行加密，通过支持连接关键字的公钥加密方法，实现了支持每个接受者只需要使用自己的私钥就能对连接关键字进行搜索，实现了在“单个发送者-多个接受者”场景下支持密文搜索的效果。

    作为文献[12]的工作的拓展，文献[21]的工作能够让服务器对用户所请求搜索的多个关键字，根据每个文件对于所请求关键字的得分排序，并将排名最高的k个文件返回给用户，服务器端将无法获得用户搜索的关键字信息、文件是否包含某个关键字信息以及最后每个文件的得分信息。其核心思想是采用了kNN[39]的思想，首先生成两个二进制位串，分别称为文件的数据向量(data vector)和用户的查询向量(query vector)。这两个向量中的每个位都分别与关键字进行一一对应，并以该位的值来表示该文件以及用户的查询请求是否包含某个关键字，然后使用两个互逆的矩阵的分别对这两个位串加密，保证文件包含关键字的信息和用户查询语句对云端服务器不可见。在计算得分的时候，还需要对两个位串的乘积通过加入随机数来进行随机化处理。这种方法和前面的连接关键字搜索不同之处在于，普通的连接关键字搜索是返回的文件需要保证包含每个域上的关键字，而在这里的多词搜索中，即使某个文件没有全部包含所请求的关键字，只要其得分位列于前k中，依然可以被返回。另外，随机数的引入也导致了最终得分的不精确性，根据该文中的描述，当引入随机变量的正态分布标准差时，最后结果的不准确度最高可达到20%。该机制的安全性建立于文献[39]之上，能够抵御已知明文攻击 (known-plaintext attack)。

    除了在普通数据上进行搜索之外，文献[32]也尝试对加密后的图结构数据（graph-structure data）上进行搜索的机制，他们遵循“过滤和确认(filtering-and-verification)”原则，即在过滤步骤里，预先为每个图建立一个基于特征的索引(feature-based index)，其中特征(feature)是原图的子图，而在确认阶段，则需要判断每个图像的特征是否与请求相同构，由于特征集合的大小和整个图像集合相比更小，因此这种操作减轻了比较的工作量。同文献[21]不同的是，为了让云端服务器无法通过相关性得分来判断在一次搜索中所匹配的关键字数量这一信息，该文放弃了在每个图形索引中使用二进制位串中的每一位的值来表征是否包含特征，而是分别从一个随机数串S和一个随机数矩阵M取值来表    征，其中。如果图形包含特征，则相应的索引表取值为，否则取值为，为了保证索引表对云端服务器不可见，使用了一对互逆的矩阵分别对图形索引表和查询语句中的数据向量(data vector)和查询向量(query vecotr)进行隐藏。最后在搜索的时候，数据所有者会将搜索预期值作为搜索凭证的一部分发给用户，而云端服务器在计算相关性得分时，如果某个图形的相关性得分等于该预期值，则说明该图形包含所有的特征；反之，如果得分小于预期值，则说明该图不满足所有的特征，但是云端服务器无法在不满足的图形中获取它们包含特征数量多少的信息。该机制能够抵御已知明文攻击。

 

    3.3支持复杂逻辑结构的可搜索加密机制

    另外，近年来逐渐发展的谓词加密(predicate encryption)是一种涵盖面比较广泛的密码学原语(cryptographic primitive)，它涵盖了基于属性加密机制(attribute-based encryption scheme[40,41])和基于身份加密机制(identity-based encryption scheme[42])。在谓词加密中，每个密文和刻画其性质的属性相联系(其中是所有属性集合)，而对应着谓词的私钥(secret key)记作。如果和I满足，则能够解密与I相联系的密文。谓词加密可以被运用于密文搜索中，其中每个密文的属性可以用该文件含有的典型关键字来刻画，谓词可被认为是用户的查询语句，私钥可看做是根据用户查询语句生成的搜索凭证，可认为密文的关键字满足用户的查询语句。

    文献[30]提出了支持析取子句、多项式方程和内积形式的谓词加密构造方法。通过在复合阶群(composite order group)上构建向量(vector)来表示析取范式、合取范式和多项式方程等复杂逻辑结构。虽然该方法支持多种逻辑结构，但是由于建立在复合阶群之上的双线性对的计算开销大约是素数阶群的50倍[43,44]，因此该方法的性能不是很理想。在该方法的实现中，虽然可以使用一些预处理来加速双线性对计算[45]，但是总的效率依然远低于其他建立在素数阶群之上的SE机制。另外，支持内积的谓词加密也可    以适用于子集和区间的关键字搜索，可以将判断是否属于子集和区间的关系式转换为以“或”关系连接的子句，例如对于判断语句“”，可以转换为“(x=1) (x=2)  (x=3)”，然后再将该子句转换为内积形式。针对谓词加密的代理，文献[12]考虑了文献[20]中的代理问题，并提出了实现的方案。另外文献[25]还考虑了谓词的隐私性问题，他们构造了一个实现谓词隐私保护的密码学原语，该构造是建立在一个复合群之上，其中该复合群可以表示成四个子群的直积。该方法能够达到更高强度的属性隐藏安全(attribute-hiding security)，意味着除了用户通过密钥获得的额外信息之外，每个密文所关联的属性信息都将被隐藏。

    文献[29]构造出了基于DPVS(dual pairing vector space)的分级谓词加密方案(hierarchical predicate encryption, HPE)，其中DPVS是n个素数阶群的直积所展成的空间，并且DPVS上的双线性运算相当于在n个素数阶群上进行双线性运算。通过在DPVS上构造出单位正交向量,将向量用于构造密文，将向量用于生成密钥。使得用户可以根据自己的私钥将部分权限代理给其他用户，假设用户Alice能够解密的文件集合为，而当Alice将部分权限代理给Bob后，Bob所能解密的文件集合应该满足。该方案能够在RDSP和IDSP假设下，对选择性明文攻击(chosen plaintext attack)达到选择性属性隐藏(selective attribute-hiding)安全

    文献[17]考虑了网络入侵检测的问题而提出了MRQED机制，在不可信的远端服务器中存放网络审计日志的密文形式并进行搜索，当网络入侵发生时，审计者(auditor)可以通过被授权的key来查找在某个特定区间中的网络流信息。在他们的工作中提出多维区间查询(multi-dimensional range query)机制，其中在每个维度上支持区间查询，并定义了两种安全模型，分别是匹配保护安全(match-concealing security)和匹配泄露安全(match-revealing security)，最后证明了所提出的方案在这两种安全模型下能够达到选择性安全(selective secure)。另外，他们的工作可以防止串谋攻击(collusion attack)。

    文献[14]考虑了在加密后的个人健康记录(PHR, personal health record)上进行授权搜索的应用场景，并利用分级的谓词加密(HPE, hierarchical predicate encryption)支持灵活的搜索语句。在他们的设计中，用户首先在本地产生合取范式形式(CNF，conjunctive normal form)的查询语句，首先需要向本地的LTA申请，本地的LTA认证用户的请求并先将合取范式的查询语句转换为谓词向量(predicate vector和属性向量(attribute vector来表示，最后LTA将转换成的谓词向量作为输入，使用分级谓词加密方法中的代理算法(delegation algorithm)产生相应搜索凭证(search capability)并颁发给用户。为了保证查询语句的隐私，他们引入了一个代理服务器(proxy server)对密文进行再处理，使得云端服务器无法达到通过公钥遍历生成密文来试探搜索语句的内容的效果。由于该机制是建立在文献[29]之上，因此其安全性能够达到文献[29]所提出的方案的安全性。

 

    3.4 小结

    从以上的分析可以看出，随着研究者们对SE机制的研究和发展，以及为了满足一些特定的应用需求，SE机制在搜索效果上得到迅速的发展。首先，从对搜索语句的支持上，SE机制的搜索效果从简单的单词搜索，逐步发展成灵活复杂的查询语句，不仅支持合取范式和析取范式等查询语句，而且在每个维度上支持相同匹配(equality)，子集(subset)和区间(range)查询，这将更加有利于用户描述自己的搜索意愿。其次，从对搜索结果的优化处理上看，SE机制的搜索结果从只满足用户搜索请求，逐步发展成支持返回与用户搜索关键字相关的前k个文件，以及支持容错的密文搜索等，这将更加有利于用户能够更快找到自己所需要的文件。表1对一些SE机制在所基于的算法、查询语句支持等方面进行总结，其中对于一些基于公钥密码学的SE机制，还归纳了它们所基于的安全性假设。

表2. 一些基于公钥密码学的SE机制的对比 

 

4. SE机制的应用模型

    近年来，SE机制已经被广泛地考虑应用于实际场景中。SE机制中可以根据应用场景分为三类：第一类是数据所有者并不将数据共享给其他用户，而是独自拥有对数据的搜索的权利；第二类是数据所有者允许其他经过认证后的用户对其数据进行搜索；第三类是多个数据所有者允许某个特定的用户对数据进行搜索，例如邮件处理场景。

 

    4.1数据独享场景

    在早期的SE机制中，数据所有者独享搜索权限是主要考虑的应用场景如图3所示。用户将数据上传到服务器端，并不是出于同其他用户共享的目的，而是为了节省本地存储空间和管理开销，同时希望能够在低带宽的网络环境下对数据进行访问。由用户独享搜索权限的数据可以是用户的私密数据，例如电子病历、邮件等涉及到个人隐私和公司内部事务等。在文献[8]、文献[26]和文献[10]的工作中，主要考虑了当用户Alice在保留搜索能力的前提下，将个人数据的密文存放在不可信的服务器上，在带宽受限的环境中，需要对其数据进行搜索的应用场景。在文献[15]的工作中主要考虑两种应用场景。第一种是当用户在使用家中的电脑存储的字典产生搜索凭证，并发给远端服务器的密文搜索。第二种应用场景是当用户使用存储空间小的手机时，需要将字典存放在远端服务器，然后经过同服务器端两轮交互，对服务器端的密文数据进行搜索。

Fig.3 The scenario that data are searched by the owner only

图3. 数据只由数据所有者独享

 

    4.2 数据共享场景

    这种情况主要适用于数据所有者将自己的一些数据同其他用户共享的场景。当数据所有者允许经过认证后的用户对其数据进行搜索时，则有三种方式使得其他用户能够根据自己感兴趣的关键字获取到搜索凭证，分别是：由数据所有者生成搜索凭证；或者数据所有者将一部分密钥信息发布给授权的用户，由授权用户在本地产生搜索凭证；或者将分发搜索凭证的责任交由信任的第三方权威机构来执行。这三种方法各有所适用的应用场景。

Fig.4 The scenario that data are shared between multiple users. (a)The data owner generates search capabilities and distributes them to users; (b)The user generates search capability at local machine; (c) The trusted audit agent answers users’ search requests and responses with search capabilities.

图4. 数据在多用户之间共享的场景。(a)数据所有者产生搜索凭证并发给用户；(b)用户在本地产生搜索凭证；(c)可信审计机构处理用户请求并分发搜索凭证.

 4.2.1 由数据所有者生成搜索凭证

4.2.3 由可信审计机构生成搜索凭证

    在多数据所有者和多用户的环境中，由于服务器端的数据归属复杂，数据所有者可以将分发搜索凭证的责任交由可信审计机构执行，具体如图4(c)所示。由可信审计机构生成搜索凭证可以不要求数据所有者时刻在线，并利用可信审计机构强大的计算能力来承担产生搜索凭证的计算负担，同时达到对用户的搜索请求进行授权目的。但是这也要求数据所有者对其完全信任，并将数据的控制权限交给该机构。其中基于公钥密码学的SE机制较为适用于这种应用场景。

    文献[14]考虑了用户在加密的电子病历上进行搜索的应用场景，其中电子病历有可信的第三方机构TA进行保存管理。论文提出了使用TA/LTA对用户的搜索权限进行认证并颁发搜索凭证的系统框架。每个LTA都被赋予了一些属性密钥，这些属性密钥决定了该LTA对数据的访问权限。当认证用户的搜索请求时，LTA使用自己的属性密钥对用户的请求进行代理操作(delegation operation)，即经过认证后的用户请求能够检索到的文件不能超过该LTA的权限。这种方法能够缓解TA成为整个系统的性能瓶颈的情况，并提高了系统的可扩展性。但是在该系统框架中，由于TA拥有了最高的权限，造成数据的明文信息将完全曝光在TA的视线之中，而数据所有者丧失了对数据的完全控制能力。

    在文献[9]的工作构造了两种机制，在第一种机制中，每个调查者(investigator)在搜索之前都需要将所要搜索的词w发给审计代理机构，以此获取搜索凭证(Search Capability)，是以为密钥的哈希函数。在第二种机制中，审计代理使用IBE中的哈希函数以及随机数，调用IBE中密钥生成算法得到。

    在文献[17]的工作中主要考虑审计者在网络入侵发生后，对网络流量进行审计并找出入侵者的应用场景。审计者需要向权威机构进行申请，并获得搜索凭证。

 

    4.3 邮件处理场景

    这种情况主要使用于基于公钥密码学的SE机制。邮件发送者使用公钥对邮件进行加密，邮件接收者利用私钥对一些感兴趣的关键字生成搜索凭证，并发给网关，让网关根据感兴趣的关键字对邮件进行分拣。

    在文献[16]的工作中，主要考虑邮件接收者对其他用户利用其公钥加密的邮件进行判断的场景。邮件接受者针对感兴趣的关键字使用私钥生成搜索凭证并发给网关，网关根据搜索凭证来判断邮件中是否有接受者所制定的关键字，并以此来判断邮件的紧急程度，从而选择其最终的接受设备。在文献[20]的另一份工作中，主要考虑的是邮件接受者根据感兴趣的谓词条件生成搜索凭证P并发给网关，使其根据搜索凭证来判断邮件是否满足谓词条件P，以此来决定接受的设备。该谓词条件包括某个关键字是否属于某个区间，以及判断该关键字集合是否是某个集合的子集等。

    针对文献[16]和文献[20]所考虑的应用场景是多个用户发送给某个邮件接收者的情况，文献[24]考虑了其对偶问题，即当一个用户需要将一封邮件发送给多个接受者的情况，他们考虑的是使用多接受者的公钥加密方法对邮件进行处理，从而避免因为分别使用每个接受者的公钥对邮件加密而带来的重复加密开销，以及支持邮件接受者单独使用私钥生成搜索凭证对邮件进行搜索。

 

    4.4 小结

    本节主要对SE机制的应用场景和系统模型进行了介绍，分析了每种应用场景的特点。从以上的分析可以得出以下几个结论。首先，SE机制的研究和现实的需求紧密相关，其中具体体现在各个SE机制都能在一些特定的现实场景中为用户节省大量的开销和繁琐的操作。另外，对于每个应用的场景都有各自的威胁模型和系统模型的定义，而它们所关注和改善的目标都极为不同，而这些不同之处也产生了额外的问题，进而带来新的设计，例如如果需要减轻数据所有者的负担而给与用户生成搜索凭证的能力，则需要将相关的密钥分发给用户，同时保证授权用户不会将该密钥泄露。其次，现实中的一些特定的应用需求，也极大地凸显其与现有SE机制的不合之处，从而让研究者们开始分析和设计适应该需求下的SE机制，进而达到提高安全性的同时又在极大程度上保证其效率的效果。

 

 

5. 总结与展望

    本文针对可搜索加密机制的研究现状进行了较为全面的介绍和讨论，首先针对SE机制的研究内容进行介绍，其次对SE机制的构造算法、对搜索语句的支持程度以及其被考虑的应用场景进行了分析和讨论。从以上介绍中可以看出SE机制的研究逐渐成熟化，将逐渐成为云计算环境下用户对数据密文进行操作的有利工具。未来的一段时间，SE机制依然将被视为解决云计算中的安全问题的研究热点之一。随着越来越多的数据存储在云端服务器中，以及用户对数据安全和个人隐私的敏感程度越来越强，如何高效精确且安全地对存储在云端服务器中的密文进行搜索，将是研究者不断研究的方向。我们认为进一步的研究主要重点解决以下问题。

    第一，高效率且支持灵活查询语句的SE机制是未来重点研究方向之一。随着越来越多用户接受云的概念，同时在云端服务器存储的数据逐渐向海量级别发展，在这种条件下，如何给用户良好的搜索体验将极大考验SE机制的性能。基于对称密码学的SE机制在性能上较为优越，而一些基于公钥密码学的SE机制，虽然能够支持灵活的查询语句，但是由于其要么构造于复合群之上(例如文献[20]和文献[30]的工作)，要么是构建于多个素数群的直积之上(例如文献[29]的工作)。由于公钥密码学的计算开销约是对称密码学算法1000倍[46]，导致了它们的性能效果将难以适用于海量用户和海里数据的应用场景中，虽然一些能够提高群元素间运算速度的硬件[47]已经推出以及一些并行化技术的采用能够在一定程度上减轻搜索时所带来的时间等待，但是只有设计出高效的SE机制，才是在算法角度上根本解决加快现今搜索效率的有效方法。

    第二，支持模糊搜索(fuzzy search)和支持按相关性排序的可搜索加密机制依然是未来需要解决的问题。由于现今的大部分可搜索加密机制都是基于匹配搜索(equality search)，因此在密文上实现快速高效的支持按相关性排序搜索和模糊搜索之上的工作依然处于初始研究阶段。一些工作[21][48][13][49]虽然在一定程度上实现了基于相关性排序和模糊搜索，但是依然存在着一些不足，例如文献[13]中的方法存储开销较大且仅支持单词搜索等。

    第三，支持关系运算(>,<,==等)的可搜索加密机制依然未来需要研究的内容。现有的一些工作虽然能够实现区间查询(range query)和子集查询(subset query)，但是在支持关系运算的效果上依然不是很理想。在未来的一段时间里，支持关系运算的可搜索加密机制的研究依然是研究的一个热点，它的研究也将为加密数据库上的查询提供一些借鉴。

    第四，保留语义的SE机制依然是研究难点。加密虽然能够将明文信息隐藏，同时也破坏了明文中的语义关系，使得用户无法像在明文上通过机器学习等方法使得返回的密文能够越来越符合用户的需求。未来的SE机制研究成果或许能够达到像明文那样，不仅应该实现精确的关键字匹配，还应该能够洞悉用户的真正搜索请求，然后将最符合的结果返回给用户。

    最后，应用于实际场景中的SE机制得到业界的更多关注。SE机制起源于理论研究，但是由于其实现复杂度高等原因，一直无法在业界得到广泛应用。随着一些应用密码学工作的展开[21,9,12,13]，SE机制渐渐步入实际中的应用。由于云计算的逐步推广，相应的配套技术也将得到研究和部署，相信在未来的一段时间内，SE机制不仅只停留在理论研究框架之内，也将逐步在实际中接受用户们的检验。

 

附中文参考文献：

1、陈康,郑纬民.云计算:系统实例与研究现状.软件学报,2009,20(5):1337-1348. http://www.jos.org.cn/ch/reader/view_abstract.aspx?flag=1&file_no=3493&journal_id=jos

2、冯登国,张敏,张妍,徐震.云计算安全研究.软件学报,2011,22(1):71-83. http://www.jos.org.cn/ch/reader/view_abstract.aspx?flag=1&file_no=3958&journal_id=jos

3、苏金树, 曹丹, 王小峰, 孙一品, 胡乔林. 属性基加密机制. 软件学报, 2011, 22(6): 1299-1315. http://www.jos.org.cn/ch/reader/view_abstract.aspx?flag=1&file_no=3993&journal_id=jos