對稱可搜索加密技術(shù)研究進(jìn)展

王贇玲; 陳曉峰

doi:10.11999/JEIT190890

對稱可搜索加密技術(shù)研究進(jìn)展

doi: 10.11999/JEIT190890

王贇玲,
陳曉峰^,

西安電子科技大學(xué)網(wǎng)絡(luò)與信息安全學(xué)院西安 710071

基金項目: 國家密碼發(fā)展基金(MMJJ20180110)

詳細(xì)信息

作者簡介:
王贇玲：女，1990年生，博士生，研究方向為密文檢索和數(shù)據(jù)安全

陳曉峰：男，1976年生，教授，研究方向為公鑰密碼學(xué)、云計算安全和數(shù)據(jù)安全

通訊作者:
陳曉峰　xfchen@xidian.edu.cn

中圖分類號: TN918
計量
- 文章訪問數(shù): 4153
- HTML全文瀏覽量: 665
- PDF下載量: 437
- 被引次數(shù): 0
出版歷程
- 收稿日期: 2019-11-07
- 修回日期: 2020-05-02
- 網(wǎng)絡(luò)出版日期: 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)

摘要

摘要: 云計算作為一種新型計算模式，具有海量資源、動態(tài)擴展、按需分配等特點。資源受限的用戶可以將計算任務(wù)外包給云服務(wù)器，在享受高質(zhì)量數(shù)據(jù)服務(wù)的同時大大降低了本地管理開銷。然而，數(shù)據(jù)外包導(dǎo)致數(shù)據(jù)所有權(quán)與管理權(quán)分離，如何保證數(shù)據(jù)的安全性成為云計算中亟待解決的關(guān)鍵問題。傳統(tǒng)的加密技術(shù)雖然可以保證數(shù)據(jù)的機密性，但是在密文中如何執(zhí)行有意義的檢索操作成為一個巨大的挑戰(zhàn)。為了保證數(shù)據(jù)機密性的同時實現(xiàn)密文數(shù)據(jù)的高效檢索，可搜索加密技術(shù)應(yīng)運而生。近年來，可搜索加密方案的設(shè)計日趨多樣化，旨在提高方案的實用性。該文主要圍繞目前可搜索加密方案的研究熱點，從4個方面展開闡述，具體包括：單關(guān)鍵詞檢索、多模式檢索、前/后向安全檢索和可驗證檢索。該文主要介紹和分析具有代表性的研究成果，總結(jié)最新研究進(jìn)展及提煉關(guān)鍵技術(shù)難點，最后對未來的研究方向進(jìn)行展望。
- 密文檢索 /
- 單關(guān)鍵詞檢索 /
- 多模式檢索 /
- 前/后向安全檢索 /
- 可驗證檢索
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方案系統(tǒng)模型

下載: 全尺寸圖片幻燈片

圖 2 Song等人的方案

下載: 全尺寸圖片幻燈片

圖 3 Goh方案

下載: 全尺寸圖片幻燈片

圖 4 Curtmola等人方案

下載: 全尺寸圖片幻燈片

圖 5 Cash等人方案

下載: 全尺寸圖片幻燈片

圖 6 Lai等人方案

下載: 全尺寸圖片幻燈片

圖 7 前向安全方案

下載: 全尺寸圖片幻燈片

圖 8 Wang等人方案

下載: 全尺寸圖片幻燈片

表 1 典型SSE方案的比較

方案	檢索復(fù)雜度	檢索類型	云計算模型	前/后向安全
Song等人方案^[1]	$O({\rm{DB)}}$	單關(guān)鍵詞	誠實且好奇	無
Goh方案^[10]	$O(d{\rm{)}}$	單關(guān)鍵詞	誠實且好奇	無
Curtmola等人方案^[14]	$O({\rm{DB(}}w{\rm{))}}$	單關(guān)鍵詞	誠實且好奇	無
Cash等人方案^[21]	$O({\rm{DB(}}{w_1}{\rm{))}}$	多關(guān)鍵詞	誠實且好奇	無
Lai等人方案^[22]	$O({\rm{DB(}}{w_1}{\rm{))}}$	多關(guān)鍵詞	誠實且好奇	無
Bost方案^[35]	$O({\rm{DB(}}w{\rm{))}}$	單關(guān)鍵詞	誠實且好奇	前向安全
Bost等人方案^[42]	$O({\rm{DB(}}w{\rm{))}}$	單關(guān)鍵詞	誠實且好奇	前/后向安全
Wang等人方案^[8]	$O({\rm{DB(}}{w_1}{\rm{))}}$	多關(guān)鍵詞	惡意	無
Zhang等人方案^[9]	$O({\rm{DB(}}w{\rm{))}}$	單關(guān)鍵詞	惡意	前向安全

下載: 導(dǎo)出CSV

參考文獻(xiàn)(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.

曹素珍, 郎曉麗, 劉祥震, 等. 抗關(guān)鍵詞猜測的授權(quán)可搜索加密方案[J]. 電子與信息學(xué)報, 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

孫瑾, 王小靜, 王尚平, 等. 支持屬性撤銷的可驗證多關(guān)鍵詞搜索加密方案[J]. 電子與信息學(xué)報, 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.

相關(guān)文章

施引文獻(xiàn)

資源附件(0)

訪問統(tǒng)計