对称可搜索加密技术研究进展

王贇玲; 陈晓峰

doi:10.11999/JEIT190890

对称可搜索加密技术研究进展

doi: 10.11999/JEIT190890

王贇玲,
陈晓峰^,

西安电子科技大学网络与信息安全学院西安 710071

基金项目: 国家密码发展基金(MMJJ20180110)

详细信息

作者简介:
王贇玲：女，1990年生，博士生，研究方向为密文检索和数据安全

陈晓峰：男，1976年生，教授，研究方向为公钥密码学、云计算安全和数据安全

通讯作者:
陈晓峰　xfchen@xidian.edu.cn

中图分类号: TN918
计量
- 文章访问数: 3933
- HTML全文浏览量: 621
- PDF下载量: 428
- 被引次数: 0
出版历程
- 收稿日期: 2019-11-07
- 修回日期: 2020-05-02
- 网络出版日期: 2020-05-13
- 刊出日期: 2020-10-13

Research on Searchable Symmetric Encryption

Yunling WANG,
Xiaofeng CHEN^,

School of Cyber Engineering, Xidian University, Xi’an 710071, China

Funds: The National Cryptography Development Fund (MMJJ20180110)

摘要

摘要: 云计算作为一种新型计算模式，具有海量资源、动态扩展、按需分配等特点。资源受限的用户可以将计算任务外包给云服务器，在享受高质量数据服务的同时大大降低了本地管理开销。然而，数据外包导致数据所有权与管理权分离，如何保证数据的安全性成为云计算中亟待解决的关键问题。传统的加密技术虽然可以保证数据的机密性，但是在密文中如何执行有意义的检索操作成为一个巨大的挑战。为了保证数据机密性的同时实现密文数据的高效检索，可搜索加密技术应运而生。近年来，可搜索加密方案的设计日趋多样化，旨在提高方案的实用性。该文主要围绕目前可搜索加密方案的研究热点，从4个方面展开阐述，具体包括：单关键词检索、多模式检索、前/后向安全检索和可验证检索。该文主要介绍和分析具有代表性的研究成果，总结最新研究进展及提炼关键技术难点，最后对未来的研究方向进行展望。
- 密文检索 /
- 单关键词检索 /
- 多模式检索 /
- 前/后向安全检索 /
- 可验证检索
Abstract: Cloud computing, as a new computing paradigm, offers dynamically scalable and seemly unbounded storage and computation resources in a pay-as-you-go manner. In order to enjoy superior data services and reduce the local maintenance cost, more and more resource-constrained users prefer to outsource their data to the cloud server. However, outsourcing data to the remote server suffers from data security concerns, because the server may try to learn the information of the outsourced data as much as possible for commercial purpose. The traditional encryption technique can protect the confidentiality of users’ data, however, it leads to the loss of search ability over the encrypted data. Fortunately, searchable encryption, as a promising solution, enables the server to perform keyword-based search over encrypted data. Recently, the design of searchable encryption scheme is becoming more and more diversified, aiming to improve the practicability of the scheme. This paper focuses on the current research for searchable encryption scheme in four aspects, including single keyword search, multi-modal search, forward/ backward secure search and verifiable search. This paper mainly introduces and analyzes the representative research results, summarizes the latest research progress and key technical difficulties, and finally prospects the future research direction.
- Search over encrypted data /
- Single keyword search /
- Multi-modal search /
- Forward/backward secure search /
- Verifiable search

HTML全文

图 1 SSE方案系统模型

下载: 全尺寸图片幻灯片

图 2 Song等人的方案

下载: 全尺寸图片幻灯片

图 3 Goh方案

下载: 全尺寸图片幻灯片

图 4 Curtmola等人方案

下载: 全尺寸图片幻灯片

图 5 Cash等人方案

下载: 全尺寸图片幻灯片

图 6 Lai等人方案

下载: 全尺寸图片幻灯片

图 7 前向安全方案

下载: 全尺寸图片幻灯片

图 8 Wang等人方案

下载: 全尺寸图片幻灯片

表 1 典型SSE方案的比较

方案	检索复杂度	检索类型	云计算模型	前/后向安全
Song等人方案^[1]	$O({\rm{DB)}}$	单关键词	诚实且好奇	无
Goh方案^[10]	$O(d{\rm{)}}$	单关键词	诚实且好奇	无
Curtmola等人方案^[14]	$O({\rm{DB(}}w{\rm{))}}$	单关键词	诚实且好奇	无
Cash等人方案^[21]	$O({\rm{DB(}}{w_1}{\rm{))}}$	多关键词	诚实且好奇	无
Lai等人方案^[22]	$O({\rm{DB(}}{w_1}{\rm{))}}$	多关键词	诚实且好奇	无
Bost方案^[35]	$O({\rm{DB(}}w{\rm{))}}$	单关键词	诚实且好奇	前向安全
Bost等人方案^[42]	$O({\rm{DB(}}w{\rm{))}}$	单关键词	诚实且好奇	前/后向安全
Wang等人方案^[8]	$O({\rm{DB(}}{w_1}{\rm{))}}$	多关键词	恶意	无
Zhang等人方案^[9]	$O({\rm{DB(}}w{\rm{))}}$	单关键词	恶意	前向安全

下载: 导出CSV

参考文献(54)

SONG D X, WAGNER D, and PERRIG A. Practical techniques for searches on encrypted data[C]. 2000 IEEE Symposium on Security and Privacy, Berkeley, USA, 2000: 44–55. doi: 10.1109/SECPRI.2000.848445.

BONEH D, DI CRESCENZO G, OSTROVSKY R, et al. Public key encryption with keyword search[C]. International Conference on the Theory and Applications of Cryptographic Techniques, Interlaken, Switzerland, 2004: 506–522. doi: 10.1007/978-3-540-24676-3_30.

曹素珍, 郎晓丽, 刘祥震, 等. 抗关键词猜测的授权可搜索加密方案[J]. 电子与信息学报, 2019, 41(9): 2180–2186. doi: 10.11999/JEIT181103

CAO Suzhen, LANG Xiaoli, LIU Xiangzhen, et al. Delegate searchable encryption scheme resisting keyword guess[J]. Journal of Electronics &Information Technology, 2019, 41(9): 2180–2186. doi: 10.11999/JEIT181103

CURTMOLA R, GARAY J, KAMARA S, et al. Searchable symmetric encryption: Improved definitions and efficient constructions[C]. The 13th ACM Conference on Computer and Communications Security, Alexandria, USA, 2006: 79–88. doi: 10.1145/1180405.1180417.

KAMARA S, MOATAZ T, and OHRIMENKO O. Structured encryption and leakage suppression[C]. The 38th Annual International Cryptology Conference on Advances in Cryptology, Santa Barbara, USA, 2018: 339–370. doi: 10.1007/978-3-319-96884-1_12.

WANG Jianfeng, MA Hua, TANG Qiang, et al. Efficient verifiable fuzzy keyword search over encrypted data in cloud computing[J]. Computer Science and Information Systems, 2013, 10(2): 667–684. doi: 10.2298/CSIS121104028W

WANG Jianfeng, CHEN Xiaofeng, HUANG Xinyi, et al. Verifiable auditing for outsourced database in cloud computing[J]. IEEE Transactions on Computers, 2015, 64(11): 3293–3303. doi: 10.1109/TC.2015.2401036

WANG Jianfeng, CHEN Xiaofeng, SUN Shifeng, et al. Towards efficient verifiable conjunctive keyword search for large encrypted database[C]. The 23rd European Symposium on Research in Computer Security on Computer Security, Barcelona, Spain, 2018: 83–100. doi: 10.1007/978-3-319-98989-1_5.

ZHANG Zhongjun, WANG Jianfeng, WANG Yunling, et al. Towards efficient verifiable forward secure searchable symmetric encryption[C]. The 24th European Symposium on Research in Computer Security on Computer Security, Luxembourg, 2019: 304–321. doi: 10.1007/978-3-030-29962-0_15.

GOH E J. Secure indexes[J]. IACR Cryptology ePrint Archive, 2003, 2003: 216.

BLOOM B H. Space/time trade-offs in hash coding with allowable errors[J]. Communications of the ACM, 1970, 13(7): 422–426. doi: 10.1145/362686.362692

ISLAM M S, KUZU M, and KANTARCIOGLU M. Access pattern disclosure on searchable encryption: Ramification, attack and mitigation[C]. Annual Network and Distributed System Security Symposium, San Diego, USA, 2012.

CASH D, GRUBBS P, PERRY J, et al. Leakage-abuse attacks against searchable encryption[C]. The 22nd ACM SIGSAC Conference on Computer and Communications Security, Denver, USA, 2015: 668–679. doi: 10.1145/2810103.2813700.

LIU Chang, ZHU Liehuang, WANG Mingzhong, et al. Search pattern leakage in searchable encryption: Attacks and new construction[J]. Information Sciences, 2014, 265: 176–188. doi: 10.1016/j.ins.2013.11.021

GOLDREICH O and OSTROVSKY R. Software protection and simulation on oblivious RAMs[J]. Journal of the ACM, 1996, 43(3): 431–473. doi: 10.1145/233551.233553

CHEN Guoxing, LAI T H, REITER M K, et al. Differentially private access patterns for searchable symmetric encryption[C]. IEEE Conference on Computer Communications, Honolulu, USA, 2018: 810–818. doi: 10.1109/INFOCOM.2018.8486381.

MISHRA P, PODDAR R, CHEN J, et al. Oblix: An efficient oblivious search index[C]. 2018 IEEE Symposium on Security and Privacy, San Francisco, USA, 2018: 279–296. doi: 10.1109/SP.2018.00045.

WANG Yunling, SUN Shifeng, WANG Jianfeng, et al. Achieving searchable encryption scheme with search pattern hidden[J]. IEEE Transactions on Services Computing, To be published. doi: 10.1109/TSC.2020.2973139

孙瑾, 王小静, 王尚平, 等. 支持属性撤销的可验证多关键词搜索加密方案[J]. 电子与信息学报, 2019, 41(1): 53–60. doi: 10.11999/JEIT180237

SUN jin, WANG Xiaojing, WANG Shangping, et al. Verifiable multi-keyword search encryption scheme with attribute revocation[J]. Journal of Electronics &Information Technology, 2019, 41(1): 53–60. doi: 10.11999/JEIT180237

GOLLE P, STADDON J, and WATERS B. Secure conjunctive keyword search over encrypted data[C]. The 2nd International Conference on Applied Cryptography and Network Security, Yellow Mountain, China, 2004: 31–45. doi: 10.1007/978-3-540-24852-1_3.

CASH D, JARECKI S, JUTLA C, et al. Highly-scalable searchable symmetric encryption with support for Boolean queries[C]. The 33rd Annual Cryptology Conference on Advances in Cryptology, Santa Barbara, USA, 2013: 353–373. doi: 10.1007/978-3-642-40041-4_20.

LAI Shangqi, PATRANABIS S, SAKZAD A, et al. Result pattern hiding searchable encryption for conjunctive queries[C]. 2018 ACM SIGSAC Conference on Computer and Communications Security, Toronto, Canada, 2018: 745–762. doi: 10.1145/3243734.3243753.

SUN Shifeng, LIU J K, SAKZAD A, et al. An efficient non-interactive multi-client searchable encryption with support for boolean queries[C]. The 21th European Symposium on Computer Security, Heraklion, Greece, 2016: 154–172. doi: 10.1007/978-3-319-45744-4_8.

WANG Yunling, WANG Jianfeng, SUN Shifeng, et al. Towards multi-user searchable encryption supporting Boolean query and fast decryption[J]. The Journal of Universal Computer Science, 2019, 25(3): 222–244.

KAMARA S and MOATAZ T. Boolean searchable symmetric encryption with worst-case sub-linear complexity[C]. The 36th Annual International Conference on the Theory and Applications of Cryptographic Techniques on Advances in Cryptology, Paris, France, 2017: 94–124. doi: 10.1007/978-3-319-56617-7_4.

LI Jin, WANG Qian, WANG Cong, et al. Fuzzy keyword search over encrypted data in cloud computing[C]. 2010 Proceedings IEEE INFOCOM, San Diego, USA, 2010: 441–445. doi: 10.1109/INFCOM.2010.5462196.

KUZU M, ISLAM M S, and KANTARCIOGLU M. Efficient similarity search over encrypted data[C]. The 28th IEEE International Conference on Data Engineering, Washington, USA, 2012: 1156–1167. doi: 10.1109/ICDE.2012.23.

WANG Cong, CAO Ning, REN Kui, et al. Enabling secure and efficient ranked keyword search over outsourced cloud data[J]. IEEE Transactions on Parallel and Distributed Systems, 2012, 23(8): 1467–1479. doi: 10.1109/TPDS.2011.282

CAO Ning, WANG Cong, LI Ming, et al. Privacy-preserving multi-keyword ranked search over encrypted cloud[C]. 2011 Proceedings IEEE INFOCOM, Shanghai, China, 2011: 829–837. doi: 10.1109/INFCOM.2011.5935306.

SUN Wenhai, WANG Bing, CAO Ning, et al. Verifiable privacy-preserving multi-keyword text search in the cloud supporting similarity-based ranking[J]. IEEE Transactions on Parallel and Distributed Systems, 2014, 25(11): 3025–3035. doi: 10.1109/TPDS.2013.282

FABER S, JARECKI S, KRAWCZYK H, et al. Rich queries on encrypted data: Beyond exact matches[C]. The 20th European Symposium on Research in Computer Security on Computer Security, Vienna, Austria, 2015: 123–145. doi: 10.1007/978-3-319-24177-7_7.

POPA R A, REDFIELD C M S, ZELDOVICH N, et al. CryptDB: Protecting confidentiality with encrypted query processing[C]. The 23rd ACM Symposium on Operating Systems Principles, Cascais, Portugal, 2011: 85–100. doi: 10.1145/2043556.2043566.

ZHANG Yupeng, KATZ J, and PAPAMANTHOU C. All your queries are belong to us: The power of file-injection attacks on searchable Encryption[C]. USENIX Security Symposium, Austin, USA, 2016: 707–720.

STEFANOV E, PAPAMANTHOU C, and SHI E. Practical dynamic searchable encryption with small leakage[C]. Annual Network and Distributed System Security Symposium, NDSS, San Diego, USA, 2014.

BOST R. ∑oφoç: Forward secure searchable encryption[C]. The 2016 ACM SIGSAC Conference on Computer and Communications Security, Vienna, Austria, 2016: 1143–1154. doi: 10.1145/2976749.2978303.

SONG Xiangfu, DONG Changyu, YUAN Dandan, et al. Forward private searchable symmetric encryption with optimized I/O efficiency[J]. IEEE Transactions on Dependable and Secure Computing, 2020, 17(5): 912–927. doi: 10.1109/TDSC.2018.2822294

KIM K S, KIM M, LEE D, et al. Forward secure dynamic searchable symmetric encryption with efficient updates[C]. The 2017 ACM SIGSAC Conference on Computer and Communications Security, Dallas, USA, 2017: 1449–1463. doi: 10.1145/3133956.3133970.

ZUO Cong, SUN Shifeng, LIU J K, et al. Dynamic searchable symmetric encryption schemes supporting range queries with forward (and backward) security[C]. 23rd European Symposium on Research in Computer Security on Computer Security, Barcelona, Spain, 2018: 228–246. doi: 10.1007/978-3-319-98989-1_12.

WU Zhiqiang and LI Kenli. VBTree: Forward secure conjunctive queries over encrypted data for cloud computing[J]. The VLDB Journal, 2019, 28(1): 25–46. doi: 10.1007/s00778-018-0517-6

HU Chengyu, SONG Xiangfu, LIU Pengtao, et al. Forward secure conjunctive-keyword searchable encryption[J]. IEEE Access, 2019, 7: 35035–35048. doi: 10.1109/ACCESS.2019.2902855

WANG Yunling, WANG Jianfeng, SUN Shifeng, et al. Toward forward secure SSE supporting conjunctive keyword search[J]. IEEE Access, 2019, 7: 142762–142772. doi: 10.1109/ACCESS.2019.2944246

BOST R, MINAUD B, and OHRIMENKO O. Forward and backward private searchable encryption from constrained cryptographic primitives[C]. 2017 ACM SIGSAC Conference on Computer and Communications Security, Dallas, USA, 2017: 1465–1482. doi: 10.1145/3133956.3133980.

GREEN M D and MIERS I. Forward secure asynchronous messaging from puncturable encryption[C]. 2015 IEEE Symposium on Security and Privacy, San Jose, USA, 2015: 305–320. doi: 10.1109/SP.2015.26.

SUN Shifeng, YUAN Xingliang, LIU J K, et al. Practical backward-secure searchable encryption from symmetric puncturable encryption[C]. 2018 ACM SIGSAC Conference on Computer and Communications Security, Toronto, Canada, 2018: 763–780. doi: 10.1145/3243734.3243782.

CHAMANI J G, PAPADOPOULOS D, PAPAMANTHOU C, et al. New constructions for forward and backward private symmetric searchable encryption[C]. 2018 ACM SIGSAC Conference on Computer and Communications Security, Toronto, Canada, 2018: 1038–1055. doi: 10.1145/3243734.3243833.

WANG X S, NAYAK K, LIU Chang, et al. Oblivious data structures[C]. 2014 ACM SIGSAC Conference on Computer and Communications Security, Scottsdale, USA, 2014: 215–226. doi: 10.1145/2660267.2660314.

STEFANOV E, VAN DIJK M, SHI E, et al. Path ORAM: An extremely simple oblivious RAM protocol[J]. Journal of the ACM, 2018, 65(4): 18. doi: 10.1145/3177872

DEVANBU P, GERTZ M, MARTEL C, et al. Authentic data publication over the internet[J]. Journal of Computer Security, 2003, 11(3): 291–314. doi: 10.3233/JCS-2003-11302

MYKLETUN E, NARASIMHA M, and TSUDIK G. Authentication and integrity in outsourced databases[C]. The Network and Distributed System Security Symposium, San Diego, USA, 2004.

PANG H, JAIN A, RAMAMRITHAM K, et al. Verifying completeness of relational query results in data publishing[C]. The 2005 ACM SIGMOD International Conference on Management of Data, Baltimore, USA, 2005: 407–418. doi: 10.1145/1066157.1066204.

PANG H, ZHANG Jilian, and MOURATIDIS K. Scalable verification for outsourced dynamic databases[J]. The VLDB Endowment, 2019, 2(1): 802–813. doi: 10.14778/1687627.1687718

YUAN Jiawei and YU Shucheng. Flexible and publicly verifiable aggregation query for outsourced databases in cloud[C]. 2013 IEEE Conference on Communications and Network Security, National Harbor, USA, 2013: 520–524. doi: 10.1109/CNS.2013.6682770.

AZRAOUI M, ELKHIYAOUI K, ÖNEN M, et al. Publicly verifiable conjunctive keyword search in outsourced databases[C]. 2015 IEEE Conference on Communications and Network Security, Florence, Italy, 2015: 619–627. doi: 10.1109/CNS.2015.7346876.

SUN Wenhai, LIU Xuefeng, LOU Wenjing, et al. Catch you if you lie to me: Efficient verifiable conjunctive keyword search over large dynamic encrypted cloud data[C]. 2015 IEEE Conference on Computer Communications, Hong Kong, China, 2015: 2110–2118. doi: 10.1109/INFOCOM.2015.7218596.

施引文献

资源附件(0)

访问统计