LAUSR

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 for fuzzy search that allows uncertainties or misspellings of keywords in a query. In this paper, we propose a prime inner product encoding (PIPE) scheme, which makes use of the indecomposable property 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 PIPE0 that is secure in the known ciphertext model. Unlike existing works that have difficulty supporting AND and OR semantics simultaneously, PIPE0 gives users the flexibility to specify different search semantics in their queries. Then, we construct PIPES 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.