A Privacy-Preserving Multi-Pattern Matching Scheme for Searching Strings in Cloud Database

Searching encrypted database is an important topic as more users want to leverage a third-party cloud system to store and process their data in encrypted form. Despite a lot of wonderful results, there are still a number of unsolved problems. In particular, the problems of pattern matching (not keyword search), e.g. with wildcards, that supports secure boolean queries and how to determine the value of k automatically of a top-k search for different queries on encrypted data are not properly addressed. In this paper, we provide solutions to solve these problems. Also, most existing secure databases employ different encryption functions to support different operators. The only exception is SDB (SIGMOD'2014) that was designed to support data interoperability between integers with a unified encryption scheme so that sophisticated queries can be answered by the database. However, SDB does not support string matching queries. We show that our solutions can be made compatible with SDB to fill this gap. To the best of our knowledge, we are the first to investigate these problems. We prove that our scheme is secure against chosen query attack. We have evaluated the performance of our scheme on large (10
⁵
strings) real-world datasets, and showed that our scheme can achieve a high search quality of 99.9% recall and 98.6% accuracy with reasonable response time.