高级搜索

留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

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

王贇玲 陈晓峰

王贇玲, 陈晓峰. 对称可搜索加密技术研究进展[J]. 电子与信息学报, 2020, 42(10): 2374-2385. doi: 10.11999/JEIT190890
引用本文: 王贇玲, 陈晓峰. 对称可搜索加密技术研究进展[J]. 电子与信息学报, 2020, 42(10): 2374-2385. doi: 10.11999/JEIT190890
Yunling WANG, Xiaofeng CHEN. Research on Searchable Symmetric Encryption[J]. Journal of Electronics and Information Technology, 2020, 42(10): 2374-2385. doi: 10.11999/JEIT190890
Citation: Yunling WANG, Xiaofeng CHEN. Research on Searchable Symmetric Encryption[J]. Journal of Electronics and Information Technology, 2020, 42(10): 2374-2385. doi: 10.11999/JEIT190890

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

doi: 10.11999/JEIT190890
基金项目: 国家密码发展基金(MMJJ20180110)
详细信息
    作者简介:

    王贇玲:女,1990年生,博士生,研究方向为密文检索和数据安全

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

    通讯作者:

    陈晓峰 xfchen@xidian.edu.cn

  • 中图分类号: TN918

Research on Searchable Symmetric Encryption

Funds: The National Cryptography Development Fund (MMJJ20180110)
  • 摘要: 云计算作为一种新型计算模式,具有海量资源、动态扩展、按需分配等特点。资源受限的用户可以将计算任务外包给云服务器,在享受高质量数据服务的同时大大降低了本地管理开销。然而,数据外包导致数据所有权与管理权分离,如何保证数据的安全性成为云计算中亟待解决的关键问题。传统的加密技术虽然可以保证数据的机密性,但是在密文中如何执行有意义的检索操作成为一个巨大的挑战。为了保证数据机密性的同时实现密文数据的高效检索,可搜索加密技术应运而生。近年来,可搜索加密方案的设计日趋多样化,旨在提高方案的实用性。该文主要围绕目前可搜索加密方案的研究热点,从4个方面展开阐述,具体包括:单关键词检索、多模式检索、前/后向安全检索和可验证检索。该文主要介绍和分析具有代表性的研究成果,总结最新研究进展及提炼关键技术难点,最后对未来的研究方向进行展望。
  • 图  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
  • [1] 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.
    [2] 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.
    [3] 曹素珍, 郎晓丽, 刘祥震, 等. 抗关键词猜测的授权可搜索加密方案[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
    [4] 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.
    [5] 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.
    [6] 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
    [7] 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
    [8] 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.
    [9] 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.
    [10] GOH E J. Secure indexes[J]. IACR Cryptology ePrint Archive, 2003, 2003: 216.
    [11] 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
    [12] 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.
    [13] 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.
    [14] 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
    [15] 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
    [16] 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.
    [17] 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.
    [18] 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
    [19] 孙瑾, 王小静, 王尚平, 等. 支持属性撤销的可验证多关键词搜索加密方案[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
    [20] 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.
    [21] 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.
    [22] 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.
    [23] 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.
    [24] 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.
    [25] 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.
    [26] 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.
    [27] 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.
    [28] 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
    [29] 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.
    [30] 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
    [31] 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.
    [32] 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.
    [33] 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.
    [34] 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.
    [35] 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.
    [36] 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
    [37] 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.
    [38] 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.
    [39] 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
    [40] 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
    [41] 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
    [42] 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.
    [43] 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.
    [44] 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.
    [45] 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.
    [46] 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.
    [47] 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
    [48] 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
    [49] 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.
    [50] 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.
    [51] 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
    [52] 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.
    [53] 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.
    [54] 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.
  • [1] 陈昌红, 彭腾飞, 干宗良.  基于深度哈希算法的极光图像分类与检索方法, 电子与信息学报. doi: 10.11999/JEIT190984
    [2] 王瑞霞, 彭国华.  n-words模型下Hesse稀疏表示的图像检索算法, 电子与信息学报. doi: 10.11999/JEIT150617
    [3] 杨娟, 李永福, 汪荣贵, 薛丽霞, 张清杨.  基于双广义高斯模型和多尺度融合的纹理图像检索方法, 电子与信息学报. doi: 10.11999/JEIT160181
    [4] 易运晖, 朱畅华, 裴昌幸, 权东晓.  偏振旋转的量子私有信息检索方案, 电子与信息学报. doi: 10.3724/SP.J.1146.2012.00242
    [5] 张雪源, 贺前华, 李艳雄, 叶婉玲.  一种基于倒排索引的音频检索方法, 电子与信息学报. doi: 10.3724/SP.J.1146.2012.00510
    [6] 陈慧中, 陈永光, 景宁, 陈荦.  遥感影像检索中高维特征的快速匹配, 电子与信息学报. doi: 10.3724/SP.J.1146.2011.00074
    [7] 涂岩恺, 陈庆虎, 邓伟.  计算机激光打印文档鉴别与检索, 电子与信息学报. doi: 10.3724/SP.J.1146.2010.00230
    [8] 陈星星, 张荣.  基于多尺度相位特征的图像检索方法, 电子与信息学报. doi: 10.3724/SP.J.1146.2008.00297
    [9] 王桂婷, 郭志芳, 焦李成.  基于区域色彩纹理特征描述和DPF匹配的图像检索, 电子与信息学报. doi: 10.3724/SP.J.1146.2006.01588
    [10] 徐小龙, 王汝传.  基于智能Agent的多维权值信息检索模型, 电子与信息学报. doi: 10.3724/SP.J.1146.2006.01341
    [11] 王磊, 杜利民, 王劲林.  基于音频的电视新闻节目的主题检索和聚类, 电子与信息学报. doi: 10.3724/SP.J.1146.2006.00272
    [12] 赵珊, 崔江涛, 周利华.  基于位平面分布熵的图像检索算法, 电子与信息学报. doi: 10.3724/SP.J.1146.2006.00009
    [13] 邓丽, 金立左, 费树岷.  基于组合相似性的视频检索, 电子与信息学报. doi: 10.3724/SP.J.1146.2006.00165
    [14] 徐艳, 王加俊.  使用拼贴误差直方图的分形图像检索, 电子与信息学报.
    [15] 刘远超, 王晓龙, 刘秉权, 钟彬彬.  信息检索中的聚类分析技术, 电子与信息学报.
    [16] 倪林, 苗原.  一种JPEG2000压缩域图像检索方法, 电子与信息学报.
    [17] 杨守义, 罗韦雄.  一种分形域基于内容的图像检索方法, 电子与信息学报.
    [18] 陈添丁, 刘济林.  结合判别函数的分形IFS图像检索, 电子与信息学报.
    [19] 高永英, 章毓晋, 罗云.  基于目标语义特征的图像检索系统, 电子与信息学报.
    [20] 李勍, 章毓晋.  基于特征元素的图像检索方法, 电子与信息学报.
  • 加载中
  • 图(8) / 表ll (1)
    计量
    • 文章访问数:  11
    • HTML全文浏览量:  0
    • PDF下载量:  7
    • 被引次数: 0
    出版历程
    • 收稿日期:  2019-11-07
    • 修回日期:  2020-05-02
    • 网络出版日期:  2020-05-13
    • 刊出日期:  2020-10-13

    目录

      /

      返回文章
      返回

      官方微信,欢迎关注