Toward High-Performance Privacy-Preserving Fuzzy Search Over Encrypted Data

With the development of information and communication technology, the Internet of Things (IoT) has gained significant popularity across various applications. As the number of devices surges and data generation accelerates, robust data security and accurate data retrieval have become increasingly important. Fuzzy keyword search provides an elegant way to allow retrieval over encrypted data. Privacy and accuracy are two important factors when applying fuzzy keyword search into cloud storage systems. State-of-the-art mechanisms cannot effectively balance privacy and accuracy, and they even compromise the access pattern. In this paper, we propose SeaPA, a fuzzy keyword search scheme with strong privacy and high accuracy. SeaPA is built on top of two non-colluding servers and integrated with secure multi-party computation. To construct SeaPA, we introduce a top-k document retrieval algorithm that conceals the similarity of search results from identical queries, preventing access pattern leakage. We implement a prototype system and conduct extensive experiments on the 20NewsGroups dataset. The results show that SeaPA achieves higher accuracy, with over <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$16\times$</tex-math></inline-formula> speedups in index encryption efficiency and over <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$9.3\times$</tex-math></inline-formula> speedups in search efficiency, compared to previous schemes.