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

Article type: Research Article

Authors: Han, Ziyang | Ye, Qingqing | Hu, Haibo^{; *}

Affiliations: Department of Electronic and Information Engineering, Hong Kong Polytechnic University, Hong Kong SAR, China

Correspondence: [*] Corresponding author. E-mail: haibo.hu@polyu.edu.hk.

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

DOI: 10.3233/JCS-210145

Journal: Journal of Computer Security, vol. 31, no. 2, pp. 129-152, 2023