Please wait a minute...
设为首页 | 加入收藏  
通信与信息网络学报  2016 Issue (4)    DOI: 10.11959/j.issn.2096-1081.2016.043
  本期目录 | 过刊浏览 | 高级检索 |
Secure searchable encryption: a survey
Yunling WANG1(),Jianfeng WANG1,2(),Xiaofeng CHEN1()
1 State Key Laboratory of Integrated Service Networks (ISN), Xidian University, Xian 710071, China
2 Guangxi Cooperative Innovation Center of Cloud Computing and Big Data, Guilin University of Electronic Technology, Guilin 541004, China
全文: PDF(796 KB)   HTML     XML
输出: BibTeX | EndNote (RIS)  
E-mail Alert

Cloud computing facilitates convenient and on-demand network access to a centralized pool of resources.Currently, many users prefer to outsource data to the cloud in order to mitigate the burden of local storage.However, storing sensitive data on remote servers poses privacy challenges and is currently a source of concern.SE (Searchable Encryption) is a positive way to protect users sensitive data, while preserving search ability on the server side.SE allows the server to search encrypted data without leaking information in plaintext data.The two main branches of SE are SSE (Searchable Symmetric Encryption) and PEKS (Public key Encryption with Keyword Search).SSE allows only private key holders to produce ciphertexts and to create trapdoors for search, whereas PEKS enables a number of users who know the public key to produce ciphertexts but allows only the private key holder to create trapdoors.This article surveys the two main techniques of SE: SSE and PEKS.Different SE schemes are categorized and compared in terms of functionality, efficiency, and security.Moreover, we point out some valuable directions for future work on SE schemes.

Key wordscloud storage    encrypted data    searchable encryption    searchable symmetric encryption    public key encryption with keyword search
出版日期: 2017-04-05
Figure1   Model of SSE schemes
Figure2   Encryption procedure
scheme search time index size security dynamism
Song, et al.[2] O(n/p) N/A CPA static
Goh[3] O(n/p) O(n) IND1-CKA dynamic
Curtmola, et al.[1](SSE-1) O(r) O(m+n) CKA1 static
Curtmola, et al.[1](SSE-2) O(r) O(mn) CKA2 static
Van Liesdonk, et al.[5] O(r) O(mn) CKA2 dynamic
Kamara, et al.[6] O(r) O(m+n) CKA2 dynamic
Kamara, et al.[7] O((r/p)logn) O(mn) CKA2 dynamic
Table1   Comparison of several SSE schemes
Figure3   Model of PEKS schemes
scheme search time index size security assumption
Boneh, et al.[46] nvp nv(2e+p) PK-CKA2 BDH
Baek, et al.[53](PEKS-1) nvp nv(3e+p) PK-CKA2 CDH
Baek, et al.[53](PEKS-2) nvp nv(e+2p) PK-CKA2 BDH
Crescenzo and Saraswat[50] 4nlJ 4nvlJ PK-CKA2 QIP
Khader[52] 4nve 5+3nve PK-CKA2 DDH
Rhee, et al.[54] nv(e + p) 2nve+(7+nv)p PK-CKA2 BDH, 1-BDHI
Rhee, et al.[59] nv(2e + p) 2nve+nvp PK-CKA2 BDH, 1-BDHI
Table2   Comparison of several PEKS schemes
[1] CURTMOLA R , GARAY J , KAMARA S ,et al. Searchable symmetric encryption:improved definitions and efficient constructions[C]// Proceedings of the 13th ACM Conference on Computer and Communications Security,Alexandria,USA, 2016: 79-88.
[2] SONG D X , WAGNER D , PERRIG A . Practical techniques for searches on encrypted data[C]// 2000 IEEE Symposium on Security and Privacy,Berkeley,California,USA, 2000: 44-55.
[3] GOH E J . Secure indexes[J].IACR cryptology eprint archive, 2003:216.
[4] BLOOM, B H . Space/time trade-offs in hash coding with allowable errors[J]. Communications of the ACM, 1970,131(5): 451-459.
[5] VAN LIESDONK P , SEDGHI S , DOUMEN J ,et al. Computationally efficient searchable symmetric encryption[C]// Proceedings of the 7th VLDB Workshop on Secure Data Management,Singapore, 2010: 87-100.
[6] KAMARA S , PAPAMANTHOU C , ROEDER T . Dynamic searchable symmetric encryption[C]// The ACM Conference on Computer and Communications Security,Raleigh,USA, 2012:965-976.
[7] KAMARA S , PAPAMANTHOU C . Parallel and dynamic searchable symmetric encryption[C]// The 17th International Conference on Financial Cryptography and Data Security,Okinawa,Japan, 2013: 258-274.
[8] STEFANOV E , PAPAMANTHOU C , SHI E . Practical dynamic searchable encryption with small leakage[C]// The 21st Annual Network and Distributed System Security Symposium,California,USA, 2014: 23-26.
[9] CASH D , JAEGER J , JARECKI S ,et al. Dynamic searchable encryption in very-large databases:data structures and implementation[J].,2014:853.IACR cryptology eprint archive, 2014:853
[10] NAVEED M , PRABHAKARAN M , GUNTER C A . Dynamic searchable encryption via blind storage[C]// 2014 IEEE Symposium on Security and Privacy,Berkeley,USA, 2014: 639-654.
[11] HAHN F , KERSCHBAUM F . Searchable encryption with secure and efficient updates[C]// Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security,Scottsdale,USA, 2014: 310-320.
[12] GAJEK S , . Dynamic symmetric searchable encryption from constrained functional encryption[C]// The Cryptographers Track at the RSA Conference,San Francisco,USA, 2016: 75-89.
[13] CASH D , GRUBBS P , PERRY J ,et al. Leakage-abuse attacks against searchable encryption[C]// Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security,Denver,USA, 2015: 668-679.
[14] ZHANG Y , KATZ J , PAPAMANTHOU C . All your queries are belong to us:the power of file-injection attacks on searchable encryption[C]// The 25th USENIX Security Symposium,Austin,USA, 2016:707-720.
[15] ISHAI Y , KUSHILEVITZ E , LU S ,et al. Private large-scale databases with distributed searchable symmetric encryption[C]// Cryptographers Track at the RSA Conference,San Francisco,USA, 2016: 90-107.
[16] KAMARA S , MOATAZ T . SQL on structurally-encrypted databases[R]. Cryptology ePrint Archive,Report 2016/453, 2016.
[17] ASHAROV G , NAOR M , SEGEV G ,et al. Searchable symmetric encryption:optimal locality in linear space via two-dimensional balanced allocations[C]// Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing,Cambridge,USA, 2016: 1101-1114.
[18] LI J , WANG Q , WANG C ,et al. Fuzzy keyword search over encrypted data in cloud computing[C]// The 29th IEEE International Conference on Computer,San Diego,USA, 2010: 441-445.
[19] KUZU M , ISLAM M S , KANTARCIOGLU M . Efficient similarity search over encrypted data[C]// The 28th IEEE International Conference on Data Engineering,Washington,USA, 2012: 1156-1167.
[20] WANG J , MA H , TANG Q ,et al. Efficient verifiable fuzzy keyword search over encrypted data in cloud computing[J]. Computer science and information systems, 2013,10(2): 667-684.
[21] ADJEDJ M , BRINGER J , CHABANNE H ,et al. Biometric identification over encrypted data made feasible[C]// The 5th International Conference on Information Systems Security,Kolkata,India, 2009: 86-100.
[22] WANG C , REN K , YU S ,et al. Achieving usable and privacyassured similarity search over outsourced cloud data[C]// Proceedings of the IEEE INFOCOM,Orlando,USA, 2012: 451-459.
[23] GOLLE P , STADDON J , 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.
[24] BALLARD L , KAMARA S , MONROSE F . Achieving e_cient conjunctive keyword searches over encrypted data[C]// The 7th International Conference on Information and Communications Security,Beijing,China, 2005: 414-426.
[25] CASH D , JARECKI S , JUTLA C ,et al. Highly-scalable searchable symmetric encryption with support for Boolean queries[C]// The 33rd Annual Cryptology Conference (CRYPTO),Santa Barbara,USA, 2013: 353-373.
[26] 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,Vienna,Austria, 2015: 123-145.
[27] BYUN J W , LEE D H , LIM J . Efficient conjunctive keyword search on encrypted data storage system[C]// The 3rd European Public Key Infrastructure Workshop on Theory and Practice,Turin,Italy, 2006: 184-196.
[28] WANG P , WANG H , PIEPRAYK J . Keyword field-free conjunctive keyword searches on encrypted data and extension for dynamic groups[C]// The 7th International Conference on Cryptology and Network Security,Hong-Kong,China, 2008: 178-195.
[29] SWAMINATHAN A , MAO Y , SU G M ,et al. Confidentialitypreserving rank-ordered search[C]// Proceedings of the 2007 ACM Workshop on Storage Security and Survivability,Alexandria,USA, 2007: 7-12.
[30] ZERR S , OLMEDILLA D , NEJDL W ,et al. Zerber+ r:Top-k retrieval from a confidential index[C]// Proceedings of the 12th International Conference on Extending Database Technology:Advances in Database Technology,Saint Petersburg,Russia, 2009: 439-449.
[31] WANG C , CAO N , LI J ,et al. Secure ranked keyword search over encrypted cloud data[C]// 2010 International Conference on Distributed Computing Systems,Genova,Italy, 2010: 253-262.
[32] WANG C , CAO N , REN K ,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.
[33] CAO N , WANG C , LI M ,et al. Privacy preserving multi-keyword ranked search over encrypted cloud data[C]// The 30th International Conference on Computer Communications,Shanghai,China, 2011: 829-837.
[34] SUN W , WANG B , CAO N ,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.
[35] XIA Z , WANG X , SUN X ,et al. A secure and dynamic multikeyword ranked search scheme over encrypted cloud data[J]. IEEE transactions on parallel and distributed systems, 2016,27(2): 340-352.
[36] CHEN C , ZHU X , SHEN P ,et al. An efficient privacy-preserving ranked keyword search method[J]. IEEE Transactions on Parallel and Distributed Systems, 2016,27(4): 951-963.
[37] ORENCIK C , KANTARCIOGLU M , SAVAS E . A practical and secure multi-keyword search method over encrypted cloud data[C]// The 6th IEEE International Conference on Cloud Computing,Santa Clara,USA, 2013: 390-397.
[38] ZHANG W , XIAO S , LIN Y ,et al. Secure ranked multi-keyword search for multiple data owners in cloud computing[C]// The 44th Annual IEEE/IFIP International Conference on Dependable Systems and Networks,Atlanta,USA, 2014: 276-286.
[39] BOUABANA-TEBIBEL T , KACI A . Parallel search over encrypted data under attribute based encryption on the Cloud Computing[J]. Computers & security, 2015,54: 77-91.
[40] PANG H H , TAN K L . Authenticating query results in edge computing[C]// Proceedings of the 20th International Conference on Data Engineering,Boston,USA, 2004: 560-571.
[41] LI F , HADJILEFTHERIOU M , KOLLIOS G ,et al. Authenticated index structures for outsourced databases[M]. Handbook of database security-applications and trends,Springer US, 2008:115-136.
[42] MOURATIDIS K , SACHARIDIS D , PANG H H . Partially materialized digest scheme:an efficient verification method for outsourced databases[J]. The International journal on very large data bases, 2009,18(1): 363-381.
[43] KUROSAWA K , OHTAKI Y . UCsecure searchable symmetric encryption[C]// International Conference on Financial Cryptography and Data Security,Kralendijk,Bonaire, 2012: 285-298.
[44] CHAI Q , GONG G . Verifiable symmetric searchable encryption for semi-honest but-curious cloud servers[C]// Proceedings of IEEE International Conference on Communications,Ottawa,Canada, 2012: 917-922.
[45] WANG J , CHEN X , HUANG X ,et al. Verifiable auditing for outsourced database in cloud computing[J]. IEEE transactions on computers, 2015,64(11): 3293-3303.
[46] 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.
[47] BONEH D , FRANKLIN M . Identity-based encryption from the Weil pairing[J]. SIAM journal on computing, 2003,32(3): 586-615.
[48] SHAMIR A , . Identity-based cryptosystems and signature schemes[C]// Workshop on the Theory and Application of Cryptographic Techniques Santa,Barbara,California,USA, 1984: 47-53.
[49] ABDALL M , BELLARE M , CATALANO D ,et al. Searchable encryption revisited:consistency properties,relation to anonymous IBE,and extensions[J]. Journal of cryptology, 2008,21(3): 350-391.
[50] DI CRESCENZO G , SARASWAT V . Public key encryption with searchable keywords based on Jacobi symbols[C]// International Conference on Cryptology in India,Chennai,India, 2007: 282-296.
[51] COCKS C , . An identity based encryption scheme based on quadratic residues[C]// The 8th IMA International Conference on Cryptography and Coding,Cirencester,UK, 2001: 360-363.
[52] KHADER D , . Public key encryption with keyword search based on k-resilient IBE[C]// International Conference on Computational Science and Its Applications,Kuala Lumpur,Malaysia, 2007:1086-1095.
[53] BAEK J,SAFAVI-NAINI R , SUSILO W . Public key encryption with keyword search revisited[C]// International conference on Computational Science and Its Applications,Perugia,Italy, 2008: 1249-1259.
[54] RHEE H S , PARK J H , AUSILO W ,et al. Improved searchable public key encryption with designated tester[C]// Proceedings of the 4th International Symposium on Information,Computer,and Communications Security,Sydney,Australia, 2009: 376-379.
[55] EMURA K , MIYAJI A , RAHMAN M S ,et al. Generic constructions of secure channel free searchable encryption with adaptive security[J]. Security and communication networks, 2015,8(8): 1547-1560.
[56] BYUN J W , RHEE H S , PARK H A ,et al. O_-line keyword guessing attacks on recent keyword search schemes over encrypted data[C]// The 3rd VLDB Workshop on Secure Data Management. Springer Berlin Heidelberg, 2006: 75-83.
[57] YAU W C , HENG S H , GOI B M . O_-line keyword guessing attacks on recent public key encryption with keyword search schemes[C]// International Conference on Autonomic and Trusted Computing,Seoul,Korea, 2008: 100-105.
[58] BAEK J,SAFAVI-NAINI R , SUSILO W . On the integration of public key data en cryption and public key encryption with keyword search[C]// The 9th International Conference on Information Security,Samos Island,Greece, 2006: 217-232.
[59] RHEE H S , PARK J H , SUSILO W ,et al. Trapdoor security in a searchable publickey encryption scheme with a designated tester[J]. Journal of systems and software, 2010,83(5): 763-771.
[60] FANG L , SUSILO W , GE C ,et al. Public key encryption with keyword search secure against keyword guessing attacks without random oracle[J]. Information sciences, 2013,238: 221-241.
[61] JEONG I R , KWON J O , HONG D ,et al. Constructing PEKS schemes secure against keyword guessing attacks is possible?[J]. Computer communications, 2009,32(2): 394-396.
[62] XU P , JIN H , WU Q ,et al. Public-key encryption with fuzzy keyword search:a provably secure scheme under keyword guessing attack[J]. IEEE transactions on computers, 2013,62(11): 2266-2277.
[63] CHEN R , MU Y , YANG G ,et al. Dual-server public-key encryption with keyword search for secure cloud storage[J]. IEEE transactions on information forensics and security, 2016,11(4): 789-798.
[64] PARK D J , KIM K , LEE P J . Public key encryption with conjunctive field keyword search[C]// The 5th International Workshop on Information Security Applications,Jeju Island,Korea, 2004: 73-86.
[65] BONEH D , WATERS B . Conjunctive,subset,and range queries on encrypted data[C]// The 4th Theory of Cryptography Conference,Amsterdam,Netherlands, 2007: 535-554.
[66] SHI E , BETHENCOURT J , CHAN T H H ,et al. Multi-dimensional range query over encrypted data[C]// 2007 IEEE Symposium on Security and Privacy (SP'07). Oakland,California,USA, 2007: 350-364.
[67] HWANG Y H , LEE P J . Public key encryption with conjunctive keyword search and its extension to a multi-user system[C]// The 1st International Conference on Pairing- Based Cryptography,Tokyo,Japan, 2007: 2-22.
[68] KATZ J , SAHAI A , WATERS B . Predicate encryption supporting disjunctions,polynomial equations,and inner products[C]// The 27th Annual International Conference on the Theory and Applications of Cryptographic Techniques,Istanbul,Turkey, 2008: 146-162.
[69] LAI J , ZHOU X , DENG R H ,et al. Expressive search on encrypted data[C]// The 8th ACM symposium on Information,computer and communications security,Hangzhou,China, 2013: 243-252.
[70] LEWKO A , OKAMOTO T , SAHAI A ,et al. Fully secure functional encryption:Attribute-based encryption and (hierarchical) inner product encryption[C]// The 29th Annual International Conference on the Theory and Applications of Cryptographic Techniques,French Riviera, 2010: 62-91.
[71] BRINGER J , CHABANNE H , KINDARJI B . Error-tolerant searchable encryption[C]// 2009 IEEE International Conference on Communications,Dresden,Germany, 2009: 1-6.
[72] INDYK P , MOTWANI R . Approximate nearest neighbors:towards removing the curse of dimensionality[C]// Proceedings of the 30th annual ACM symposium on Theory of computing,Dallas,Texas,USA, 1998: 604-613.
[73] BONEH D , KUSHILEVITZ E , OSTROVSKY R ,et al. Public key encryption that allows PIR queries[C]// The 27th Annual International Cryptology Conference,Santa Barbara,USA, 2007: 50-67.
[74] ZHENG Q , XU S , ATENIESE G . VABKS:verifiable attribute-based keyword search over outsourced encrypted data[C]// 2014 IEEE Conference on Computer Communications,Toronto,Canada, 2014: 522-530.
[75] LIU P , WANG J , MA H ,et al. Efficient verifiable public key encryption with keyword search based on KP-ABE[C]// The 9th International Conference on Broadband and Wireless Computing,Communication and Applications (BWCCA),Guangdong,China, 2014: 584-589.
No related articles found!


版权所有 © 2015 《通信与信息网络学报》编辑部