Skip to content

简介

1. 研究的问题

可搜索加密 ，简单描述就是用户将自己的数据加密后上传到云服务器，为了方便搜索，用户还需要使用关键词对文件进行标记，这样用户只需要提供特定的关键词，云服务器便可以返回相应的结果。

SSE_model

2. 系统模型

从上图可以看出，可搜索加密中存在三类实体：

  1. 数据拥有者（Data Owner），负责上传数据；
  2. 云服务器（Cloud Server），负责保存加密数据以及提供搜索功能；
  3. 用户（Client），向云端发起搜索请求，得到搜索结果。

在这一过程中，需要保证云服务器：

  • 不能直接获取数据信息；
  • 不能知道用户查询的关键词信息；
  • 不能知道关键词与文件的具体对应关系。

3. 现有的研究

如果单纯从参与者的数量出发，可以分成四类：

  1. SW/SR，即 single-writer/single-reader
  2. MW/SR，即 multi-writer/single-reader
  3. SW/MR，即 single-writer/multi-reader
  4. MW/MR，即 multi-writer/multi-reader

如果按照研究的内容来分类的话，我们大概可以从这四个角度来看：

  1. 从单关键词到多关键词： 早期的工作只关注单关键词检索，从 2013 年 Cash 等人1 提出了高效的多关键词布尔查询机制之后，越来越多的方案开始考虑支持多关键词查询。多关键词的难点在于两个方面，首先考虑效率因素，不能直接套用单关键词搜索的方案（否则复杂度会线性上升）；其次是隐私保护方面，不能让服务器知道针对每一个关键词对应的文件索引（也就是服务器不能获得额外的信息）；
  2. 从准确搜索到模糊搜索： 早期工作对于给定的关键词只会返回其对应的结果。但考虑到现实中存在 typos，或只知道部分关键词的情况，这时就需要考虑模糊搜索。比如 2015 年 ESORICS 上的一篇工作就考虑了2 substring 搜索以及通配符搜索。最近也有工作认为单纯只考虑查询关键词的“形似”是不合理的，真正需要考虑的是语义上的相似，因此引申出了语义上的搜索。这一类工作需要考虑的是如何衡量关键词之间的距离，用到的有3 Locality-sensitive hashing，布隆过滤器这样的工具，复杂一点的用到了自然语言处理的 word2vec。如果考虑多用户场景的话，还需要保证即使模糊搜索，用户也不会得到超过其本身权限的文件信息；
  3. 从单用户到多用户： 在可搜索加密中，用户一般指代查询用户。一般的模型里数据拥有者就假定为一个，多用户指的就是查询用户有很多个。这个场景在现实中非常常见，在这种场景中需要考虑的就是数据拥有者对用户的授权问题（规定可搜索范围），服务器需要对用户进行认证，以及对用户的撤销操作。部分工作采用广播加密或基于属性的加密来为用户分配权限，但还存在效率方面的问题。Du 等人4 在 OXT 协议1的基础上使用了一个用户列表来记录每个用户的权限信息；
  4. 从静态到动态： 动态可搜索加密是可搜索加密中的难点，动态是指支持对加密数据集进行修改，而不需要有数据拥有者重新初始化再上传。为什么这个问题比较困难呢？是因为一旦有了更新，后面会引发一系列安全相关的问题，也就是前向安全和后向安全。近期有篇工作详细给出了在可搜索加密中前后向安全的定义，并设计了三个不同的动态可搜索加密机制。前向安全需要保证的是新的更新不能与之前的操作关联起来，而后向安全需要确保如果在查询关键词5 w 之前，包含关键词 w 的文档被删除，那么这次查询也不能暴露该删除文档的信息。从这篇文章里我想到另外一个问题，谁可以修改数据？一般意义上只能数据拥有者来修改，但如果考虑现实中情况的话，类似于多人协作的场景，数据查询者有时也需要被赋予修改的权限。

3.1 多关键词检索

狭义上的多关键词检索指的是连接关键词检索，也就是服务器返回包含所有查询关键词的文档。最简单的做法是服务器对每个关键词执行单关键词检索，之后对得到的结果取交集。多关键词连接查询可以直接参考OXT协议，此处不做赘述。

3.2 模糊检索

3.2.1 通配符检索

3.2.2 范围检索

  • Rich Queries on Encrypted Data: Beyond Exact Matches, ESORICS '15 2
  • CryptDB: Protecting Confidentiality with Encrypted Query Processing, SOSP '11 6
  • An Efficiently Searchable Encrypted Data Structure for Range Queries, ESORICS '197

3.3 多用户

多用户分为两种实现方式，一种基于ABE，另一种基于BE。

基于ABE的方案：

方案描述 特点 短板
TDSC'208 使用ABE加密文件标识和对称密钥 任何用户都可以上传文件 需要可信第三方；既然服务器返回的结果是已经筛选过的，那么为什么还需要在解密时使用ABE来解密呢？
JUCS'199 使用 Server-Side Match Anonymous ABE，即服务器可以筛选出符合用户权限的密文 服务器侧做匹配，减小通信开销，降低解密成本
TDSC'1910 用户需要与其他用户合作生成检索请求 防止服务器与用户共谋
WWW'2018

基于BE的方案：

方案描述 特点 短板
JISA'1812
TDSC'2013 使用two-keyword index，加入了可验证功能
EIDWT'1315

其他方案：

方案描述 特点 短板
TDSC'2011 使用集合限制的PRF
TSC'2114
IS'2016
TDSC'2017

一些核心问题：

  • 用户的权限改变会导致系统参数的变化
  • 用户的属性信息是需要隐私保护的

  1. D. Cash, S. Jarecki, C. Jutla, H. Krawczyk, M.-C. Roşu, and M. Steiner, “Highly-Scalable Searchable Symmetric Encryption with Support for Boolean Queries,” in Advances in Cryptology – CRYPTO 2013, Berlin, Heidelberg, 2013, pp. 353–373, doi: 10.1007/978-3-642-40041-4_20. ↩↩

  2. S. Faber, S. Jarecki, H. Krawczyk, Q. Nguyen, M. Rosu, and M. Steiner, “Rich Queries on Encrypted Data: Beyond Exact Matches,” in Computer Security -- ESORICS 2015, Cham, 2015, pp. 123–145, doi: 10.1007/978-3-319-24177-7_7. ↩↩

  3. W. Yang and Y. Zhu, “A Verifiable Semantic Searching Scheme by Optimal Matching Over Encrypted Data in Public Cloud,” IEEE Transactions on Information Forensics and Security, vol. 16, pp. 100–115, 2021, doi: 10.1109/TIFS.2020.3001728. ↩

  4. L. Du, K. Li, Q. Liu, Z. Wu, and S. Zhang, “Dynamic multi-client searchable symmetric encryption with support for boolean queries,” Information Sciences, vol. 506, pp. 234–257, Jan. 2020, doi: 10.1016/j.ins.2019.08.014. ↩

  5. I. Demertzis, J. G. Chamani, D. Papadopoulos, and C. Papamanthou, “Dynamic Searchable Encryption with Small Client Storage,” presented at the Network and Distributed System Security Symposium, San Diego, CA, 2020, doi: 10.14722/ndss.2020.24423. ↩

  6. R. A. Popa, C. M. S. Redfield, N. Zeldovich, and H. Balakrishnan, “CryptDB: protecting confidentiality with encrypted query processing,” in Proceedings of the Twenty-Third ACM Symposium on Operating Systems Principles, New York, NY, USA, Oct. 2011, pp. 85–100. doi: 10.1145/2043556.2043566. ↩

  7. F. Kerschbaum and A. Tueno, “An Efficiently Searchable Encrypted Data Structure for Range Queries,” in Computer Security – ESORICS 2019, Cham, 2019, pp. 344–364. doi: 10.1007/978-3-030-29962-0_17. ↩

  8. K. Zhang, M. Wen, R. Lu, and K. Chen, “Multi-client Sub-Linear Boolean Keyword Searching for Encrypted Cloud Storage with Owner-enforced Authorization,” IEEE Transactions on Dependable and Secure Computing, pp. 1–1, 2020, doi: 10.1109/TDSC.2020.2968425. ↩

  9. Y. Wang et al., “Towards multi-user searchable encryption supporting Boolean query and fast decryption,” JUCS-Journal of Universal Computer Science, vol. 25, p. 222, 2019. ↩

  10. S. Kasra Kermanshahi et al., “Multi-client Cloud-based Symmetric Searchable Encryption,” IEEE Transactions on Dependable and Secure Computing, pp. 1–1, 2019, doi: 10.1109/TDSC.2019.2950934. ↩

  11. S.-F. Sun et al., “Non-Interactive Multi-Client Searchable Encryption: Realization and Implementation,” IEEE Transactions on Dependable and Secure Computing, pp. 1–1, 2020, doi: 10.1109/TDSC.2020.2973633. ↩

  12. L. Sun, C. Xu, and Y. Zhang, “A dynamic and non-interactive boolean searchable symmetric encryption in multi-client setting,” Journal of Information Security and Applications, vol. 40, pp. 145–155, Jun. 2018, doi: 10.1016/j.jisa.2018.03.002. ↩

  13. X. Liu, G. Yang, Y. Mu, and R. H. Deng, “Multi-User Verifiable Searchable Symmetric Encryption for Cloud Storage,” IEEE Transactions on Dependable and Secure Computing, vol. 17, no. 6, pp. 1322–1332, Nov. 2020, doi: 10.1109/TDSC.2018.2876831. ↩

  14. Q. Gan, X. Wang, D. Huang, J. Li, D. Zhou, and C. Wang, “Towards Multi-client Forward Private Searchable Symmetric Encryption in Cloud Computing,” IEEE Transactions on Services Computing, pp. 1–1, 2021, doi: 10.1109/TSC.2021.3087155. ↩

  15. Z. Liu, Z. Wang, X. Cheng, C. Jia, and K. Yuan, “Multi-user Searchable Encryption with Coarser-Grained Access Control in Hybrid Cloud,” in 2013 Fourth International Conference on Emerging Intelligent Data and Web Technologies, Sep. 2013, pp. 249–255. doi: 10.1109/EIDWT.2013.48. ↩

  16. L. Du, K. Li, Q. Liu, Z. Wu, and S. Zhang, “Dynamic multi-client searchable symmetric encryption with support for boolean queries,” Information Sciences, vol. 506, pp. 234–257, Jan. 2020, doi: 10.1016/j.ins.2019.08.014. ↩

  17. Y. Yang, X. Liu, and R. H. Deng, “Multi-User Multi-Keyword Rank Search Over Encrypted Data in Arbitrary Language,” IEEE Transactions on Dependable and Secure Computing, vol. 17, no. 2, pp. 320–334, Mar. 2020, doi: 10.1109/TDSC.2017.2787588. ↩

  18. Q. Cao, Y. Li, Z. Wu, Y. Miao, and J. Liu, “Privacy-preserving conjunctive keyword search on encrypted data with enhanced fine-grained access control,” World Wide Web, vol. 23, no. 2, pp. 959–989, Mar. 2020, doi: 10.1007/s11280-019-00671-3. ↩