Towards achieving flexible and verifiable search for outsourced database in cloud computing

The notion of outsourced database allows the data owner to outsource a database to the cloud service provider (CSP), and then anyone can enjoy database services provided by the CSP. Some new security and privacy concerns, e.g., query integrity, are inevitably raised because of losing physical control of data. Recently, some researchers present a verifiable data integrity auditing protocol for outsourced database, which satisfies both the correctness and completeness of search result even if the CSP intentionally returns an empty set. However, for each attribute column, the data owner needs to count the number of data tuples with the same value in advance. Any slight update operation may bring about huge computation and communication overhead. This makes it very hard to be applicable to dynamic outsourced database scenario. To address the above challenge, we propose a novel verifiable search scheme for outsourced database based on invertible Bloom filter (IBF), which can achieve verifiability of search result without the process of pre-counting. Furthermore, the proposed scheme is extended to multi-user setting by incorporating multi-party searchable encryption (MPSE), which can resist collusion attack between the CSP and any malicious users. Finally, security and efficiency evaluation show that the proposed construction can achieve the desired security properties, while providing a comparable computation and storage overhead.