背景及概述

目前，云计算飞速发展，许多用户更喜欢将数据上传到云上，以减轻本地存储的负担。

然而，在远程服务器上存储敏感数据会带来隐私方面的挑战，这是一个令人担忧的问题。Searchable Encryption（可搜索加密）是一种保护用户敏感数据的积极方法，同时保留了服务器端的搜索能力。

SE允许服务器搜索加密数据，但不会泄漏明文数据中的信息。SE的两个主要分支是SSE（可搜索对称加密，Symmetric Searchable Encryption）和PEKS（带有关键字搜索的公钥加密，Public key Encryption with Keyword Search）。

  1. SSE只允许私钥持有者生成密文并为搜索创建陷门，
  2. PEKS允许多个拥有公钥的用户生成密文，但只允许私钥持有者创建陷门。

本文综述了SE的两种主要技术：SSE和PEKS，根据功能、效率和安全性对不同的SE方案进行分类和比较，此外，我们指出了一些有价值的方向，阐述了SE的方案，以及未来可以开展工作的方向。

可搜索的加密方案角色包括三方：

  1. 可信的数据所有者
  2. 半可信的服务器
  3. 被授权搜索的用户集合

各方的任务如下：

  1. 数据所有者：一个数据所有者想要把一组文档存到云存储上，包括一些关键字，数据所有者需要以特定的方式对文档和关键字进行加密，以便以后方便地搜索它们，然后将密文上传到服务器。
  2. 数据用户：如果授权用户想要搜索包含特定关键字的文档，Ta必须向服务器提交该查询关键字的陷门。搜索之后，服务器将包含该关键字的文档返回给用户。
  3. 服务器：服务器执行搜索任务。当服务器从用户处接收到查询关键字的陷门时，它搜索密文，然后将相关文档返回给用户。我们假设服务器是诚实的，这意味着服务器将正确遵循协议，但它可能会分析收到的数据并尝试获取一些附加信息。

可搜索的对称加密方案（Symmetric Searchable Encryption，SSE）

一种通用的可搜索对称加密方案包含四个多项式时间算法：

  1. Keygen(1^k)：这是一个由数据所有者运行的密钥生成算法，它以安全参数k作为输入，然后输出密钥k。
  2. BuildIndex(K, D)：由数据所有者运行的关键字索引生成算法，它以密钥K和一组文档D作为输入，然后输出关键字索引的结果I。
  3. Trapdoor(K, w)：由用户运行的关键字Trapdoor（陷门）生成算法，它以密钥K和查询关键字w作为输入，并输出关键字w的Trapdoor（陷门）Tw。
  4. Search(I, Tw)：由服务器运行的关键字搜索算法，它以关键字索引I和Trapdoor（陷门）Tw作为输入，并输出一组包含查询关键字w的文档D(w)。

SSE的几类方案分别如下

单一关键字搜索

1） 顺序扫描的SSE方案

在该方案中，通过顺序扫描整个密文来执行搜索。该方案的基本思想是通过将明文中的每个关键字与伪随机比特序列进行异或运算来获得密文。因此，允许直接在密文上搜索。

该方案包括3个步骤，分别是：加密、搜索和解密。

alt

在该方案中，明文和查询关键字的隐私得到了保护。但是，它的搜索效率较低，搜索时间与文档集合的长度成线性关系，因为服务器在确定文档中是否包含某个关键字时，需要扫描文档的整个密文。

2） 具有安全索引的SSE方案

  • 基于文档的索引

为了提高搜索效率而采用伪随机函数和布隆过滤器的安全索引结构，使用布隆过滤器，可以快速确定一个元素是否属于一个集合。在这个方案中，伪随机函数被应用于文档中的每个关键词两次。然后，输出被映射到布隆过滤器。有了Bloom filter的知识，确定一个文档是否包含某个关键字就容易多了。

这种方案的优点是服务器只需要搜索索引，而不是扫描整个密文。结果，提高了搜索效率，但服务器还必须搜索每个索引，并且查询的搜索工作与文档数量成线性关系，即使只有一个文档包含查询关键字。

  • 基于关键字的索引

另一种安全索引，称为基于关键字的安全索引。

在这种基于关键字的安全索引中，一个关键字对应许多文档标识符。在该方案中，查询关键词的搜索时间与包含该查询关键词的文档数量成线性关系。因此，与基于文档的索引相比，基于关键字的索引在搜索查询时更有效。然而，当在集合中添加、删除或修改文档时，更新基于关键字的索引是困难的。

3） 动态SSE方案

这是一种能够处理文档更新的动态SSE方案。

在该方案中，服务器中存储的关键字的搜索时间是对数的。基本方案扩展到两个方案，这两个方案均支持文档更新。第一个方案是交互式的，而第二个方案是无交互式的。

模糊关键词搜索的方案

在SSE方案中，用户向服务器提交查询关键字的Trapdoor（陷门），服务器返回包含查询关键字的文档。但是，如果查询关键字与预设的关键字不匹配，如“campus”和“compus”，关键字搜索将失败。幸运的是，模糊关键字搜索可以处理这个问题，因为它可以容忍轻微的打字错误和格式不一致。

联合关键字搜索

联合关键字搜索允许用户在单个查询期间获得包含几个关键字的文档。

它比单一关键字搜索更高效，更适合实际应用。

一个简单的过程是分别对每个关键字执行单个关键字搜索，然后处理结果。但是，它的效率很低，并且会向服务器泄露一些信息。

现存的一些联合关键字搜索，往往通信成本与文档数量成线性关系，但主要工作可以离线完成；另外的方案只需要不断的交流，不需要离线做任何事情。此外，还有基于非标准shamir秘密共享技术方案实现的方案，也有基于双线性对实现的方案。也有学者提出支持范围、子串、通配符和短语查询的方案。

排名和可验证的关键字搜索

排名关键字搜索可以通过返回最相关的文档来优化搜索结果，这可以减少网络流量并增强系统可用性。

有学者提出了一种具有“索引匹配”度量的多关键字排序搜索方案。然而，他们的搜索结果是根据匹配关键词的数量进行排名的，而没有考虑不同关键词的重要性。也有人提出了一种使用“余弦度量”技术的多关键字排序搜索方案。他们的方案以牺牲搜索精度为代价获得了比线性搜索更好的效率。

最近有学者提出了一个动态的多关键字排序搜索方案，原理是使用一个安全树，也有学者提出基于层次聚类索引的多关键字排序搜索方案，以提高搜索效率。在他们的方案中，当数据集合的大小呈指数增长时，搜索时间呈线性增长。

带有关键字搜索的公钥加密（Public key Encryption with Keyword Search，PEKS）

PEKS的几类方案分别如下

单一关键字搜索

第一个PEKS方案由Boneh等人提出，它是基于IBE(基于身份的加密)，由三个阶段组成。

首先，消息发送者用接收者的公钥加密Ta的消息和关键字方式。 密文为EApub(M)，PEKS(Apub，W1)，…，PEKS(Apub，Wk)，其中M为消息内容，Apub是接收方的公钥。

然后，接收者向服务器发送查询关键字W的陷门Tc。

最后，服务器搜索密文并确定某个关键字是否在特定的密文中。

该方案需要两个素数阶为p 的群G1 G2，这由安全参数以及一个双线性映射e确定。该方案需要两个哈希函数H1和H2。

在构造PEKS方案方面，学术界已经进行了许多研究，根据其安全性将其分为三类。

1）传统的PEKS

传统的PEKS，其原理有将匿名IBE方案转换为PEKS方案的通用解决方案，也有不是基于双线性映射对的PEKS方案（但具有很高的存储和通信开销），也有基于k-resilient IBE的PEKS方案，该算法方案效率较低，并且需要计算四次指数运算来测试某个关键字是否在密文中。

2）无需安全信道的PEKS

第一个PEKS方案具有限制，即需要安全信道来传输陷门；因此，只有服务器可以学习Trapdoor（陷门），然而，这是不实际的，因为建立一个安全通道的成本是昂贵的。

Baek等人提出了SCF-PEKS(无安全通道的PEKS)，它不需要安全通道。这个新的PEKS方案增加了服务器公钥/私钥对；因此，只有服务器可以搜索密文。Rhee等人随后增强了Beak等人的模型的安全性。在他们的安全增强模型中，攻击者可以获得密文和陷门之间的关系。也有学者将SCF-PEKS方案的安全性扩展为基于匿名IBE的自适应SCF-PEKS方案，该模型允许攻击者自适应地测试查询关键字。

3）针对关键词猜测攻击

Byun等人首先提出了离线KGA（关键词猜测攻击），因为关键词的空间很小，他们还指出，Boneh等人的方案容易受到离线关键字猜测攻击。

Yau等人也断言SCF-PEKS和PKE/PEKS方案也容易受到这种攻击。外部对手可以从公共信道（KGA之外）捕获陷门；而内部对手，如恶意服务器，可以从公共或安全信道捕获陷门。

Rhee等人提出了一个针对外部KGA的方案，该方案在陷门计算中引入了一个随机变量，以使陷门不可区分。

fang等人提出了针对以外地区的具体SCF-PEKS。

对于内KGA，zheng等人表明当可能的关键字的数量由某个多项式限定时，构造一个安全的和一致的抗KGA的PEKS方案是不可能的。

Xu等人提出了一个支持模糊关键字搜索的PEKS方案。在他们的方案中，多个关键词共享同一个模糊关键词陷门，使得服务器不能学习确切的关键词。然而，他们的方案在安全性和效率方面有局限性。

Chen等人提出了一个新的PEKS框架，称为双服务器PEKS，它在内部是安全的。

联合关键字搜索

Park等人在公钥系统中构造了两个支持联合关键字搜索的方案，其中计算开销是有效的，陷门大小是恒定的。

然而，第一种方案需要多个双线性配对映射，并且私有关键字的数量与关键字字段的大小成线性关系。

Boneh和Waters提出了一个基于隐藏向量加密的公钥方案，它支持比较查询、子集查询和任意合取查询。解密后属性值不会泄露。然而，由于使用了复合阶双线性群，密文的大小很大。此外，它在公钥大小和加密操作方面具有很高的成本。幸运的是，解密密钥大小和解密成本被最小化。

Shi等人提出了一种支持对加密数据进行多维范围查询的方案，该方案可用于共享网络审计日志。但是，解密后会泄漏属性值。Hwang和Lee改进了密文和私钥的大小。

Kaze等人构建了一个PEKS方案，支持基于内积谓词加密的析取关键字搜索。然而，密文大小和私钥大小受到一些超多项式的限制。

Lai等人介绍了一种支持任意单调布尔谓词的有效PEKS方案，该方案基于密钥策略属性的加密（KP-ABE）。

模糊关键词搜索

Bringer等人提出了一种基于LSH（本地敏感哈希）和BFS（带存储的布隆过滤器）函数的公钥环境下的容错可搜索加密。LSH 函数可用于减少相似项目之间的差异，而BFS函数用于回答集合成员资格查询。

如果两个关键字足够相似，LSHs输出的哈希值是相同的。将LSH值输入到BFS中实现了容错搜索。

他们的方案已经被证明是PK-CKA2安全的，并且使用PIR技术保护搜索模式。

可验证的关键字搜索

假设服务器是半诚实的，这样它可能只返回一部分搜索结果，甚至是不准确的结果。

zheng等人用一种称为VABKS（可验证的基于属性的关键字搜索）的基于属性的加密方案解决了这个问题。在该方案中，只有满足数据所有者访问控制策略的用户才被允许执行搜索和验证操作。然而，验证搜索结果的正确性是昂贵的。此外，该方案也很脆弱因为对手可以容易地获得关键字密文和搜索令牌。

liu等人提出了一个新的VABKS方案，其中安全信道是不必要的。他们提出的方案在验证搜索结果的正确性和完整性方面也相对高效。

结论

自从SSE和PEKS分别在2000年和2004年提出以来，可搜索加密研究领域受到了极大的关注，并在以下三个主要方向取得了进展。

1）查询表现力

对于查询表达能力的扩展已经进行了大量的研究。为了使方案更加实用，不仅支持精确的单一关键字搜索，还支持模糊关键字搜索、范围搜索和子集搜索，查询结果也得到了优化。

例如，排序关键字搜索找到最相关的结果，可验证关键字搜索验证结果的正确性和完整性。然而，许多方案以牺牲效率或安全性为代价来提高查询表达能力。因此，未来的研究应该注意查询表达性和效率或安全性之间的权衡。

2）效率

从SSE的角度来看，搜索在一些方案中，复杂性与存储在服务器上的文档数量成线性关系。

此外，一些方案实现了次线性搜索时间，其中搜索复杂度与所有文档中的关键词数量成对数关系。

此外，一些方案实现了最优的搜索时间，其中搜索复杂度与包含查询关键词的文档数量成线性关系。

随着大数据时代的到来，大规模数据现在需要存储在服务器上。因此，如何高效地处理大规模数据的问题是进一步工作的方向。此外，文件不能灵活更新，因为搜索索引与关键字相关。

因此，如何构造一个有效的动态SSE方案是未来工作的另一个方向。从PKES的角度来看，大量的方案都是基于配对地图的。结果，这些方案是低效的，因为配对映射是低效的算法。因此，构建实用的PEKS方案也是未来工作的一个方向。

3）安全

一方面，尽管几乎所有的SE方案都是可证明安全的，但是它们没有使用一个通用的安全模型。

也就是说，不同的方案在不同的假设下使用不同的安全模型。因此，总是很难比较它们的安全性。

因此，为SE方案提出一个标准的安全模型是未来工作的一个方向。

此外，大多数方案在搜索模式和访问模式上折衷。因此，构建一个不泄漏搜索模式和访问模式的高效方案是未来工作的另一个方向。

未来

未来的工作还应该关注如何应用SE的基本思想来处理其他类型的数据。

例如：

  • 如何搜索包含图像数据或视频数据的加密媒体数据；
  • 如何搜索包含关系数据库或非关系数据库的加密数据库；
  • 以及如何搜索结构化的社交网络数据。