全密态数据库的搜索与查询

范围搜索

保序

模糊查询

一个很小的点，有两种？？？大概是对称和非对称可搜索加密吧

框架一：对称可搜索加密SSE————针对一对一，尝试一对多多对多

• 基本SSE

  • 基于扫描的SWP方案
  • 文件-关键词：文件为单位，例如ZINDX引入布隆过滤器,要遍历所有文件结构
  • 关键词-文件：SSE-Ⅰ/Ⅱ，以关键词为单位的数据结构-链表，查询起来O(1)，但是文件更新要重建索引。

• 多关键词检索

• 模糊关键词搜索（此处是正题）
  问题建模来源于[1]

  [1]Song XD, Wagner D, Perrig A. Practical techniques for searches on encrypted data. SS&P. IEEE.

  文献[13]采用编辑距离来定义和度量关键词间的相似度,并使用了基于通配符和基于克(gram)的两种模糊关键词集构造方法.关键词查询时,用户计算待查询关键词在编辑距离门限下的模糊陷门集合并交给服务器,服务器使用陷门集与存储的模糊关键词集进行一一匹配,返回可能包含 W 的密文文件集合.

  [13]Li J, Wang Q, Wang C, Cao N, Fuzzy keyword-basedongram.pdf.Fuzzy keyword search over encrypted data in cloud computing. In: Proc. of the 29th IEEE Int’l Conf. on Computer Communications (INFOCOM)

  2012 年,Wang 等人[14]进一步研究模糊关键词检索方案(searching tree,edit distance, subsets, ),并给出了形式化的安全性证明.

  [14]Wang C, Ren K, Yu SC.ObsProof.pdf Achieving usable and privacy-assured similarity search over outsourced cloud data. (INFOCOM)

  文献[15]提出包含通配符的关键词检索方法,类似于 Z-IDX[4],也将文件包含的关键词插入布隆过滤器.所不同的是,为避免关联攻击,该方法产生基于文件标识符的伪随机数,用以对布隆过滤器的二进制向量进行遮蔽.最后,在包含通配符的关键词检索功能的实现上,该方法通过预先为关键词生成所有通配检索形式……插入索引,从而将包含通配符的关键词检索转化为精确匹配检索.

  [15]Bösch C, Brinkman R, Hartel P, Jonker W. Fuzzy keyword based like ZINDX.pdf Conjunctive Wildcard Search over Encrypted Data.
  [4]E.-J. Goh, ZINDX,“Secure indexes,” Cryptology ePrint Archive, Report2003/216, 2003
  [7] Y.-C. Chang and M. Mitzenmacher, “Privacy preserving keyword searches on remote encrypted data,” 这上面两个都是精确搜索，作为[15]的motivation

• 查询结果优化

  原有的 SSE 方案仅支持布尔检索……目标文件可能只是其中单个或极少一部分,这就导致大量不必要的解密操作.因此,迫切需要优化查询结果,降低用户端后处理工作开销.
  一种可能的优化办法是:在返回结果中,按照关键词与文件的相关度对加密文件进行排序,并将排序结果返回给用户.这样,用户只需根据相关度解密少量密文即可获得目标文件.目前,关于此方面的研究包括: ………

框架二：非对称可搜索加密————针对多对一，

• PEKS方案
  提出者Boneh，但是公钥加密体系一直是计算开销大的

  [2]Boneh D, Di Crescenzo G, Ostrovsky R, Persiano G. Public key encryption with keyword search. In: Camenisch LJ, Cachin C, eds.

• 关键词猜测攻击
• 模糊搜索
  文献[39]使用 HVE[38]构造包含通配符的 PEKS 方案.HVE 中,每个密文 C 和密钥 K 都分别与一个二进制属性向量 X=(X1,X2,…,Xn)和 Y=(Y1,Y2,…,Yn)相关联,这里,Y 中的某个分量不存在时,记为‘’.K 可以用来解密 C 当且仅当 X 与 Y 在除‘’外的所有分量都相同.包含通配符的 PEKS 中,将每个关键词视为属性向量:发送者使用邮件包含的关键词作为公钥,对该邮件执行 HVE 加密;接收者发送给服务器的陷门是待检索关键词的解密密钥,服务器试图执行 HVE 解密,如果解密成功,说明两个关键词除‘*’外所有分量都相同,从而达到包含通配符的关键词检索的目的

  [38]Boneh D, Waters B. Conjunctive, subset, and range queries on encrypted data. In: Vadhan PS, ed. Proc. of the Theory of.基于IBE还有SymmetricEncryption有两种，其应用场景为在加密后的审计日志上进行关键字搜索,该方案的特点为需要服务器端对文件进行加密,而且用户在进行检索时需要访问服务器并自己承担搜索开销.

未来发展

1. 外包数据库计算
2. 云计算隐私数据共享，结合代理重加密以及PBE，实现高细粒度控制的云数据访问共享