Page 168 - 计算机技术与网络安全研究

计算机技术与网络安全研究
Computer Technology and Cyber Security Research

Li 等人提出了编辑距离上的模糊关键词可搜索加密，其方案考虑的是由于
插入、删除、替换操作所导致的关键词不精确性，在对关键词进行加密的同时也
对在某个编辑距离之内的所有单词进行加密，从而将模糊关键词匹配转换为多个
精确匹配，同时 Li 等人还提出一种更为高效的基于通配符的方案，但是数据使
用者每搜索一个关键词需要构造多个搜索令牌，上述两种方案的时间复杂度都较

高。Kutu 等人提出了一个通用的相似性搜索方案，其核心思想是结合 LSH 和 BF
的良好性质，将关键词表示成 n-grams，每个 n-gram 用 LSH 插入 BF 中，其距离
测量是 Jaccard 距离，该方案是一个两轮的交互协议。

上述方案都是针对单一关键词搜索的，但是这种搜索过于粗糙不能有效满
足用户的数据检索需求，同时搜索多个关键词更符合人们使用搜索引擎时的搜索
习惯。以加密邮件搜索为例，用户可能不仅仅想要来自“Alice”的邮件，而想要
搜索来自“Alice”、被标记为“紧急”并且邮件内容是关于“经济”的邮件。
尽管可以使用多轮单一关键词查询来实现这一功能，但是会泄露额外的信

息；如果通过一轮密文搜索后，对返回结果解密，在客户端进行进一步的搜索会
给用户带来极差的操作体验；而通过在服务器上存储额外的信息会占用指数级的
存储空间。为了解决这一问题，研究者提出了支持连接关键词搜索（conjunctive

keyword search）的对称密钥可搜索加密方案。Golle 等人提出了两种支持连接关
键词搜索的可搜索加密机制：GSW-1 和 GSW-2。在 Golle 等人的方案中，每个
文件与一个可搜索的索引相关联，其中 GSW-1 的搜索时间与存储的文件数量成
线性关系，GSW-2 搜索时间与字典中的关键词数量成线性关系。
在上述方案的搜索过程中需要执行求幂运算和双线性对运算。之后，Ballard

等人给出了一个计算效率和存储开销上都要优于上述两个方案的构造。Ryu 等人
的方案为了降低关键词加密过程中的复杂度，减少了加密过程中双线性对计算的
数量，从而大大提升了加密过程的效率。上述所有的连接关键词可搜索加密方

案都达不到搜索令牌不可关联性，因此不可信服务器能够实施统计攻击。最近
Moataz 等人为解决这个问题提出了一个两轮的交互方案，该方案能够达到关键词
机密性和搜索令牌不可关联性并能够保护查询请求中包含关键词的数量。
在关键词搜索中，上述方案返回给用户的搜索结果是没有经过排序的，数
据使用者需要在本地进行解密并对结果进行整理从而找出自己最感兴趣的文件。

Wang等人针对这个问题提出了一个单个关键词上的排序关键词可搜索加密方案。

160
160