Efficient Searchable Symmetric Encryption Scheme for Size Pattern Protection

doi:10.3969/j.issn.1671-1122.2024.06.003

Abstract

Abstract:

In recent years, with the popularity of cloud services and the increasing demand for data security protection, dynamic searchable symmetric encryption (DSSE) has attracted widespread attention from academia due to its ability to update and query in encrypted databases. Due to considerations of search and update efficiency, DSSE often needs to disclose some information, mainly search pattern, access pattern, and size pattern. At present, the main use of oblivious random access machine (ORAM) is to protect search and access pattern, but ORAM cannot guarantee the security of size pattern leakage. The article explained the harm of size pattern leakage to security and extended the existing DSSE privacy concept to achieve protection of size patterns, namely proposing strong forward backward privacy. Based on this enhanced security objective, the article proposed an efficient searchable symmetric encryption scheme for size pattern protection named Eurus, aiming to solve the size pattern leakage problem in existing solutions. By combining multi-server ORAM architecture, update slot mechanism and fine tree path elimination technology, Eurus provided strong forward and reversed privacy protection to prevent the disclosure of sensitive keywords and file information. Multi-server ORAM hided search and access patterns, update slots confuse file identifiers, and fine tree path elimination techniques disrupted the actual order of files. The experimental results show that Eurus improves the search and update efficiency while maintaining privacy, improving the search performance by about 46% compared with the existing scheme, and improving the update performance by 4.73 times.

Key words: searchable encryption, size pattern, ORAM

CLC Number:

TP309

LI Qiang, SHEN Yuanhai, LIU Tianxu, HUANG Yanyu, SUN Jianguo. Efficient Searchable Symmetric Encryption Scheme for Size Pattern Protection[J]. Netinfo Security, 2024, 24(6): 843-854.

Figures/Tables 5

References 39

[1]	SONG Xiaoding, WAGNER D, PERRIG A. Practical Techniques for Searches on Encrypted Data[C]// IEEE. 2000 IEEE Symposium on Security and Privacy. New York: IEEE, 2000: 44-55.
[2]	HAHN F, KERSCHBAUM F. Searchable Encryption with Secure and Efficient Updates[C]// ACM. 2014 ACM SIGSAC Conference on Computer and Communications Security. New York: ACM, 2014: 310-320.
[3]	STEFANOV E, PAPAMANTHOU C, SHI E. Practical Dynamic Searchable Encryption with Small Leakage[EB/OL]. (2014-02-23)[2024-01-13]. https://eprint.iacr.org/2013/832.
[4]	CURTMOLA R, GARAY J, KAMARA S, et al. Searchable Symmetric Encryption: Improved Definitions and Efficient Constructions[J]. Computer Security, 2011, 19(5): 895-934.
[5]	ISLAM M, KUZU M, KANTARCIOGLU M. Access Pattern Disclosure on Searchable Encryption: Ramification, Attack and Mitigation[EB/OL]. (2012-02-06)[2024-01-13]. https://personal.utdallas.edu/-mxk055100/publications/ndss2012.pdf.
[6]	CASH D, GRUBBS P, PERRY J, et al. Leakage-Abuse Attacks against Searchable Encryption[C]// ACM. The 22nd ACM SIGSAC Conference on Computer and Communications Security. New York: ACM, 2015: 668-679.
[7]	ZHANG Yupeng, KATZ J, PAPAMANTHOU C. All Your Queries are Belong to Us: The Power of File-Injection Attacks on Searchable Encryption[C]// ACM. The 25th USENIX Conference on Security Symposium. New York: ACM, 2016: 707-720.
[8]	NING Jianting, XU Jia, ZHANG Fan, et al. Passive Attacks against Searchable Encryption[J]. IEEE Transactions on Information Forensics and Security, 2018, 14(3): 789-802.
[9]	POULIOT D, WRIGHT C V. The Shadow Nemesis: Inference Attacks on Efficiently Deployable, Efficiently Searchable Encryption[C]// ACM. 2016 ACM SIGSAC Conference on Computer and Communications Security. New York: ACM, 2016: 1341-1352.
[10]	KORNAROPOULOS E M, PAPAMANTHOU C, TAMASSIA R. The State of the Uniform: Attacks on Encrypted Databases Beyond the Uniform Query Distribution[C]// IEEE. 2020 IEEE Symposium on Security and Privacy (SP). New York: IEEE, 2020: 118-131.
[11]	MARKATOU E A, TAMASSIA R. Full Database Reconstruction with Access and Search Pattern Leakage[C]// ACM. Information Security:22nd International Conference (ISC 2019). New York: ACM, 2019: 25-43.
[12]	BOST R. ∑oφoς: Forward Secure Searchable Encryption[C]// ACM. The 2016 ACM SIGSAC Conference on Computer and Communications Security. New York: ACM, 2016: 1143-1154.
[13]	LAI R W F, CHOW S S M. Forward-Secure Searchable Encryption on Labeled Bipartite Graphs[C]// Springer. 2017 International Conference on Applied Cryptography and Network Security (ACNS 2017). Heidelberg: Springer, 2017: 478-497.
[14]	ETEMAD M, KUPCU A, PAPAMANTHOU C, et al. Efficient Dynamic Searchable Encryption with Forward Privacy[C]// ACM. The Twelfth ACM Conference on Data and Application Security and Privacy. New York: ACM, 2018: 312-323.
[15]	BOSY R, MINAUD B, OHRIMENKO O. Forward and Backward Private Searchable Encryption from Constrained Cryptographic Primitives[C]// ACM. The 2017 ACM SIGSAC Conference on Computer and Communications Security. New York: ACM, 2017: 1465-1482.
[16]	GHAREH J, PAPADOPOULOS D, PAPAMANTHOU C, et al. New Constructions for Forward and Backward Private Symmetric Searchable Encryption[C]// ACM. The 2018 ACM SIGSAC Conference on Computer and Communications Security. New York: ACM, 2018: 1038-1055.
[17]	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.
[18]	LI Jin, HUANG Yanyu, YU Wei, et al. Searchable Symmetric Encryption with Forward Search Privacy[J]. IEEE Transactions on Dependable and Secure Computing, 2021, 18(1): 460-474.
[19]	GARG S, MOHASSEL P, PAPAMANTHOU C. TWORAM: Efficient Oblivious RAM in Two Rounds with Applications to Searchable Encryption[C]// Springer. 36th Annual International Cryptology Conference (CRYPTO 2016). Heidelberg: Springer, 2016: 563-592.
[20]	HOANG T, OZKAPTAN C D, YAVUZ A A, et al. S³ORAM: A Computation-Efficient and Constant Client Bandwidth Blowup ORAM with Shamir Secret Sharing[C]// ACM. 2017 ACM SIGSAC Conference on Computer and Communications Security. New York: ACM, 2017: 491-505.
[21]	WANG Xiao, CHAN H, SHI E. Circuit ORAM: On Tightness of the Goldreich-Ostrovsky Lower Bound[C]// ACM. 22nd ACM SIGSAC Conference on Computer and Communications Security. New York: ACM, 2015: 850-861.
[22]	DEVADAS S, VAN D M, FLETCHER C W, et al. Onion ORAM: A Constant Bandwidth Blowup Oblivious RAM[C]// Springer. 2016 Theory of Cryptography Conference (TCC 2016). Heidelberg: Springer, 2016: 145-174.
[23]	REN Ling, FLETCHER C, KWON A, et al. Constants Count: Practical Improvements to Oblivious {RAM}[C]// USENIX. 24th USENIX Security Symposium (USENIX Security 15). Berlin:USENIX, 2015: 415-430.
[24]	STEFANOV E, VAN D M, SHI E, et al. Path ORAM: An Extremely Simple Oblivious RAM Protocol[C]// ACM. 2013 ACM SIGSAC Conference on Computer & Communications Security. New York: ACM, 2013: 299-310.
[25]	MISHRA P, PODDAR R, CHIESA A, et al. Oblix: An Efficient Oblivious Search Index[C]// IEEE. 2018 IEEE Symposium on Security and Privacy (SP). New York: IEEE, 2018: 279-296.
[26]	NAVEED M. The Fallacy of Composition of Oblivious RAM and Searchable Encryption[EB/OL]. (2015-07-05)[2024-01-13]. https://eprint.iacr.org/2015/668.pdf.
[27]	SHAFIEE A, BALASUBRAMONIAN R, TIWARI M, et al. Secure DIMM: Moving ORAM Primitives Closer to Memory[C]// IEEE. IEEE International Symposium on High Performance Computer Architecture (HPCA). New York: IEEE, 2018: 428-440.
[28]	GARG S, MOHASSEL P, PAPAMANTHOU C. TWORAM: Efficient Oblivious RAM in Two Rounds with Applications to Searchable Encryption[C]// Springer. 36th Annual International Cryptology Conference (CRYPTO 2016). Heidelberg: Springer, 2016: 563-592.
[29]	BLACKSTONE L, KAMARA S, MOATAZ T. Revisiting Leakage Abuse Attacks[EB/OL]. (2019-10-10)[2024-01-13]. https://eprint.iacr.org/2019/1175.
[30]	KELLARIS G, KOLLIOS G, NISSIM K, et al. Generic Attacks on Secure Outsourced Databases[C]// ACM. 2016 ACM SIGSAC Conference on Computer and Communications Security. New York: ACM, 2016: 1329-1340.
[31]	GRUBBS P, MINAUD B, PATERSON K G. Pump up the Volume: Practical Database Reconstruction from Volume Leakage on Range Queries[C]// ACM. 2018 ACM SIGSAC Conference on Computer and Communications Security. New York: ACM, 2018: 315-331.
[32]	GUI Zichen, JOHNSON O, WARINSCHI B. Encrypted Databases: New Volume Attacks against Range Queries[C]// ACM. 2019 ACM SIGSAC Conference on Computer and Communications Security. New York: ACM, 2019: 361-378.
[33]	PODDAR R, WANG S, LU Jianan, et al. Practical Volume-Based Attacks on Encrypted Databases[C]// IEEE. 2020 IEEE European Symposium on Security and Privacy (EuroS&P). New York: IEEE, 2020: 107-123.
[34]	SHAMIR A. How to Share a Secret[J]. Communications of the ACM, 1979, 22(11): 612-613.
[35]	LEE J, JANG J, JANG Y, et al. Hacking in Darkness: Return Oriented Programming against Secure Enclaves[C]// USENIX. The 26th USENIX Conference on Security Symposium. Berlin:USENIX, 2017: 523-539.
[36]	GOTZFRIED J, ECKERT M, SCHINZEL S, et al. Cache Attacks on Intel SGX[C]// ACM. The 10th European Workshop on Systems Security. New York: ACM, 2017: 101-106.
[37]	CHEN Hao, CHILLOTTI I, REN Lin. Onion Ring ORAM: Efficient Constant Bandwidth Oblivious RAM from (Leveled) TFHE[C]// ACM. The 2019 ACM SIGSAC Conference on Computer and Communications Security. New York: ACM, 2019: 345-360.
[38]	BINDSCHAEDLER V, NAVEED M, PAN X, et al. Practicing Oblivious Access on Cloud Storage: the Gap, the Fallacy, and the New Way Forward[C]// ACM. The 22nd ACM SIGSAC Conference on Computer and Communications Security. New York: ACM, 2015: 837-849.
[39]	CHOR B, GOLDREICH O, KUSHILEVITZ E, et al. Private Information Retrieval[C]// IEEE. Proceedings of IEEE 36th Annual Foundations of Computer Science. New York: IEEE, 1995: 41-50.

测试次数/次	搜索时间/s		更新时间/s
测试次数/次	SPS14	本文方案	本文方案	GOSSE
1	750	35740	172668	46867
2	682	36540	161435	44174
3	743	35344	232788	64278
4	800	36450	212527	57373
5	754	36193	228534	64643