Prime Inner Product Encoding for Effective Wildcard-Based Multi-Keyword Fuzzy Search
Qin Liu, Yu Peng, Shuyu Pei, Jie Wu, Tao Peng, Guojun Wang · IEEE Transactions on Services Computing · 2020
With the prevalence of cloud computing, a growing number of users are delegating clouds to host their sensitive data. To preserve user privacy, it is suggested that data is encrypted before outsourcing. However, data encryption makes keyword-based searches over ciphertexts extremely difficult. This is even challenging forfuzzy searchthat allows uncertainties or misspellings of keywords in a query. In this article, we propose a prime inner product encoding (PIPE) scheme, which makes use of theindecomposableproperty of prime numbers to provide efficient, highly accurate, and flexible multi-keyword fuzzy search. Our main idea is to encode either a query keyword or an index keyword into a vector filled with primes or reciprocals of primes, such that the result of vectors’ inner product is an integer only when two keywords are similar. Specifically, we first construct$\text{PIPE}_{0}$that is secure in the known ciphertext model. Unlike existing works that have difficulty supporting AND and OR semantics simultaneously,$\text{PIPE}_{0}$gives users the flexibility to specify different search semantics in their queries. Then, we construct$\text{PIPE}_{\text{S}}$that subtly adds random noises to a query vector to resist linear analyses. Both theoretical analyses and experiment results demonstrate the effectiveness of our scheme.