OTKI-F: An efficient memory-secure multi-keyword fuzzy search protocol

Abstract

Many breakthroughs on security and privacy-preserving techniques have emerged to mitigate the trust loss of cloud hosting environment caused by various types of attacks. To enhance memory-level security of multi-keyword fuzzy search, a widely occurred query request, we take the initiative to apply Trusted Execution Environment (a.k.a TEE) technology to our protocol design which provides hardware-based tamper-proof enclaves. Then we propose the Edit Distance-based Obfuscation Mechanism to further protect the query process executed outside TEE against access pattern leakage. With concerns of practicality and performance, we also propose the two-layer fuzzy index structure and Trend-aware Cache. The former addresses the space limitation of TEE memory for searching large datasets, while the latter optimizes the cache utility of TEE with trend-aware coordinator to effectively reduce the communication overhead.

Keywords

Keyword Search Fuzzy Search Privacy Preservation Trusted Execution Environment Cloud Security

Get full access to this article

View all access options for this article.

References

ARM.com, ARM TrustZone. https://www.arm.com/products/security-on-arm/trustzone.

Aumasson and

Merino, SGX Secure Enclaves in Practice–Security and Crypto Review, Black Hat, 2016.

Bajaj and

Sion, Trusteddb: A trusted hardware-based database with privacy and data confidentiality, IEEE Transactions on Knowledge and Data Engineering 26(3) (2014), 752–765. doi:10.1109/TKDE.2013.38.

B.H.

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

Blum,

Feldman and

Micali, Non-interactive zero-knowledge and its applications, in: Providing Sound Foundations for Cryptography: On the Work of Shafi Goldwasser and Silvio Micali, 2019, pp. 329–349.

Boneh,

Di Crescenzo,

Ostrovsky and

Persiano, Public key encryption with keyword search, in: International Conference on the Theory and Applications of Cryptographic Techniques, Springer, 2004, pp. 506–522.

Bösch,

Brinkman,

Hartel and

Jonker, Conjunctive wildcard search over encrypted data, in: Workshop on Secure Data Management, Springer, 2011, pp. 114–127. doi:10.1007/978-3-642-23556-6_8.

Brasser,

Müller,

Dmitrienko,

Kostiainen,

Capkun and

A.-R.

Sadeghi, Software grand exposure: {SGX} cache attacks are practical, in: 11th USENIX Workshop on Offensive Technologies (WOOT 17), 2017.

J.W.

Byun,

H.S.

Rhee,

H.-A.

Park and

D.H.

Lee, Off-line keyword guessing attacks on recent keyword search schemes over encrypted data, in: Workshop on Secure Data Management, Springer, 2006, pp. 75–83. doi:10.1007/11844662_6.

10.

Cash,

Jarecki,

Jutla,

Krawczyk,

M.-C.

Roşu and

Steiner, Highly-scalable searchable symmetric encryption with support for Boolean queries, in: Annual Cryptology Conference, Springer, 2013, pp. 353–373.

11.

Chor,

Goldreich,

Kushilevitz and

Sudan, Private information retrieval, in: Foundations of Computer Science, 1995. Proceedings., 36th Annual Symposium on, IEEE, 1995, pp. 41–50.

12.

Chuah and

Hu, Privacy-aware bedtree based solution for fuzzy multi-keyword search over encrypted data, in: 2011 31st International Conference on Distributed Computing Systems Workshops, IEEE, 2011, pp. 273–281. doi:10.1109/ICDCSW.2011.11.

13.

Costan and

Devadas, Intel SGX explained, IACR Cryptology ePrint Archive 2016(086) (2016), 1–118.

14.

Curtmola,

Garay,

Kamara and

Ostrovsky, Searchable symmetric encryption: Improved definitions and efficient constructions, Journal of Computer Security 19(5) (2011), 895–934. doi:10.3233/JCS-2011-0426.

15.

Ding,

Li,

Zhang,

Chen,

Wang and

Xu, An efficient and privacy-preserving ranked fuzzy keywords search over encrypted cloud data, in: 2016 International Conference on Behavioral, Economic and Socio-Cultural Computing (BESC), IEEE, 2016, pp. 1–6.

16.

Eskandarian and

Zaharia, An oblivious general-purpose SQL database for the cloud, 2017, CoRR, arXiv:1710.00458.

17.

Fu,

Ren,

Shu,

Sun and

Huang, Enabling personalized search over encrypted outsourced data with efficiency improvement, IEEE transactions on parallel and distributed systems 27(9) (2015), 2546–2559. doi:10.1109/TPDS.2015.2506573.

18.

Fu,

Wu,

Guan,

Sun and

Ren, Toward efficient multi-keyword fuzzy search over encrypted outsourced data with accuracy improvement, IEEE Transactions on Information Forensics and Security 11(12) (2016), 2706–2716. doi:10.1109/TIFS.2016.2596138.

19.

Gentry, A fully homomorphic encryption scheme, Stanford University, 2009.

20.

Goldreich, Towards a theory of software protection and simulation by oblivious RAMs, in: Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing, ACM, 1987, pp. 182–194.

21.

Goldreich,

Micali and

Wigderson, Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems, Journal of the ACM (JACM) 38(3) (1991), 690–728. doi:10.1145/116825.116852.

22.

Han,

Hu and

Ye, ReFlat: A robust access pattern hiding solution for general cloud query processing based on K-isomorphism and hardware enclave, IEEE Transactions on Cloud Computing, 2021.

23.

He,

Prabhavalkar,

Rao,

Li,

Bakhtin and

McGraw, Streaming small-footprint keyword spotting using sequence-to-sequence models, in: 2017 IEEE Automatic Speech Recognition and Understanding Workshop (ASRU), IEEE, 2017, pp. 474–481. doi:10.1109/ASRU.2017.8268974.

24.

Hristidis,

Papakonstantinou and

Gravano, Efficient IR-style keyword search over relational databases, in: Proceedings 2003 VLDB Conference, Elsevier, 2003, pp. 850–861. doi:10.1016/B978-012722442-8/50080-X.

25.

Hu,

Chen and

Xu, VERDICT: Privacy-preserving authentication of range queries in location-based services, in: Proc. of the 29th IEEE International Conference on Data Engineering (ICDE ’13), IEEE, 2013, pp. 1312–1315.

26.

Hu,

Xu,

Pei,

Choi and

Zhou, Private search on key-value stores with hierarchical indexes, in: Proc. of the 30th IEEE International Conference on Data Engineering (ICDE ’14), IEEE, 2014, pp. 628–639.

27.

Huo,

Meng,

Wang,

Hao,

Zhao,

Zhai and

Li, Bluethunder: A 2-level Directional Predictor Based Side-Channel Attack against SGX, IACR Transactions on Cryptographic Hardware and Embedded Systems (2020), 321–347.

28.

IBM, IBM 4758 PCI Cryptographic Coprocessor General Information Manual, 2016. ftp://www6.software.ibm.com/software/cryptocards/4758gi.pdf.

29.

Ibrahim,

Jin,

A.A.

Yassin and

Zou, Secure rank-ordered search of multi-keyword trapdoor over encrypted cloud data, in: 2012 IEEE Asia-Pacific Services Computing Conference, IEEE, 2012, pp. 263–270. doi:10.1109/APSCC.2012.59.

30.

Indyk and

Motwani, Approximate nearest neighbors: Towards removing the curse of dimensionality, in: Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing, 1998, pp. 604–613.

31.

Intel, IntelR 64 and IA-32 Architectures Software Developer’s Manual, 2015, https://www.intel.com/content/www/us/en/developer/articles/technical/intel-sdm.html .

32.

Intel, Intel(r) Software Guard Extensions Remote Attestation End-to-End Example, 2016. https://software.intel.com/en-us/articles/intel-software-guard-extensions-remote-attestation-end-to-end-example.

33.

Intel, Intel(R) Software Guard Extensions (Intel(R) SGX). http://software.intel.com/en-us/sgx.

34.

Intel, Software Guard Extensions Programming Reference, 2014, https://www.intel.com/content/dam/develop/external/us/en/documents/329298-002-629101.pdf.

35.

Kim,

Jang,

Park,

Jeong,

Kim,

Choi and

B.B.

Kang, SGX-LEGO: Fine-grained SGX controlled-channel attack and its countermeasure, computers & security 82 (2019), 118–139. doi:10.1016/j.cose.2018.12.001.

36.

Kulkarni,

Chapuis and

Garbinato, Privacy-preserving location-based services by using intel sgx, in: Proceedings of the First International Workshop on Human-Centered Sensing, Networking, and Systems, 2017, pp. 13–18. doi:10.1145/3144730.3144739.

37.

Li,

Wang,

Cao,

Ren and

Lou, Fuzzy keyword search over encrypted data in cloud computing, in: 2010 Proceedings IEEE INFOCOM, IEEE, 2010, pp. 1–5.

38.

Li,

Yu,

Cao and

Lou, Authorized private keyword search over encrypted data in cloud computing, in: 2011 31st International Conference on Distributed Computing Systems, IEEE, 2011, pp. 383–392. doi:10.1109/ICDCS.2011.55.

39.

Luo,

Jia,

Duan,

Wang,

Xu and

Fu, pRide: Private ride request for online ride hailing service with secure hardware enclave, in: Proceedings of the International Symposium on Quality of Service, 2019, pp. 1–10.

40.

Mayzner, English Letter Frequency Counts: Mayzner Revisited or ETAOIN SRHLDCU, http://norvig.com/mayzner.html.

41.

Mishra,

Poddar,

Chen,

Chiesa and

R.A.

Popa, Oblix: An efficient oblivious search index, in: 2018 IEEE Symposium on Security and Privacy (SP), IEEE, 2018, pp. 279–296. doi:10.1109/SP.2018.00045.

42.

M.H.

Mofrad,

Lee and

S.L.

Gray, Leveraging Intel SGX to Create a Nondisclosure Cryptographic library, 2017, arXiv preprint arXiv:1705.04706.

43.

Raghavendra,

Geeta,

Shaila,

Buyya,

Venugopal,

Iyengar and

Patnaik, MSSS: Most significant single-keyword search over encrypted cloud data, in: Proceedings of the 6th Annual Intrernational Conference on ICT: BigData, Cloud and Security, 2015.

44.

Shen,

Shu and

Xue, Preferred keyword search over encrypted data in cloud computing, in: 2013 IEEE/ACM 21st International Symposium on Quality of Service (IWQoS), IEEE, 2013, pp. 1–6.

45.

Shen,

Shu and

Xue, Keyword search with access control over encrypted data in cloud computing, in: 2014 IEEE 22nd International Symposium of Quality of Service (IWQoS), IEEE, 2014, pp. 87–92. doi:10.1109/IWQoS.2014.6914304.

46.

Song,

Li,

Feng and

Zhou, Effective fuzzy keyword search over uncertain data, in: International Conference on Database Systems for Advanced Applications, Springer, 2009, pp. 66–70. doi:10.1007/978-3-642-00887-0_6.

47.

Stefanov,

Van Dijk,

Shi,

Fletcher,

Ren,

Yu and

Devadas, Path ORAM: An extremely simple oblivious RAM protocol, in: Proceedings of the 2013 ACM SIGSAC Conference on Computer & Communications Security, ACM, 2013, pp. 299–310.

48.

Sun,

Zhang,

Lou and

Y.T.

Hou, Rearguard: Secure keyword search using trusted hardware, in: IEEE INFOCOM 2018-IEEE Conference on Computer Communications, IEEE, 2018, pp. 801–809. doi:10.1109/INFOCOM.2018.8485838.

49.

Van Bulck,

Minkin,

Weisse,

Genkin,

Kasikci,

Piessens,

Silberstein,

T.F.

Wenisch,

Yarom and

Strackx, Foreshadow: Extracting the keys to the intel SGX kingdom with transient out-of-order execution, in: 27th USENIX Security Symposium (USENIX Security, Vol. 18, 2018, pp. 991–1008.

50.

Van Liesdonk,

Sedghi,

Doumen,

Hartel and

Jonker, Computationally efficient searchable symmetric encryption, in: Workshop on Secure Data Management, Springer, 2010, pp. 87–100.

51.

Wang,

Yu,

Lou and

Y.T.

Hou, Privacy-preserving multi-keyword fuzzy search over encrypted data in the cloud, in: IEEE INFOCOM 2014-IEEE Conference on Computer Communications, IEEE, 2014, pp. 2112–2120. doi:10.1109/INFOCOM.2014.6848153.

52.

Wang,

Ma,

Tang,

Li,

Zhu,

Ma and

Chen, Efficient verifiable fuzzy keyword search over encrypted data in cloud computing, Computer science and information systems 10(2) (2013), 667–684. doi:10.2298/CSIS121104028W.

53.

Wang,

Yu and

Zhao, Privacy-preserving ranked multi-keyword fuzzy search on cloud encrypted data supporting range query, Arabian Journal for Science and Engineering 40(8) (2015), 2375–2388. doi:10.1007/s13369-015-1737-3.

54.

Wang,

Liu,

Su,

Ma,

Wang,

Yang,

Shen,

Li,

Zhang and

Dong, CryptSQLite: Protecting Data Confidentiality of SQLite with Intel SGX, in: Networking and Network Applications (NaNA), 2017 International Conference on, IEEE, 2017, pp. 303–308.

55.

Weibo, WEIBO-INDEX, 2019, https://data.weibo.com/index.

56.

Xu,

Hu and

M.-H.

Au, When query authentication meets fine-grained access control: A zero-knowledge approach, in: Proc. of the 2018 ACM SIGMOD International Conference on Management of Data, ACM, 2018, pp. 147–162.

57.

Zhang,

Hadjieleftheriou,

B.C.

Ooi and

Srivastava, Bed-tree: An all-purpose index structure for string similarity search based on edit distance, in: Proceedings of the 2010 ACM SIGMOD International Conference on Management of Data, 2010, pp. 915–926. doi:10.1145/1807167.1807266.

58.

Zheng,

X.-M.

Shu and

H.-Y.

Yuan, Hot spot information auto-detection method of network public opinion, Computer Engineering 36(3) (2010), 4–6.

59.

Zheng and

Zhou, An efficient attack on a fuzzy keyword search scheme over encrypted data, in: 2013 IEEE 10th International Conference on High Performance Computing and Communications & 2013 IEEE International Conference on Embedded and Ubiquitous Computing, IEEE, 2013, pp. 1647–1651.