Tell me the truth: Practically public authentication for outsourced databases with multi-user modification

With the advent of cloud computing, outsourcing databases to remote cloud servers provide the elastic, flexible and affordable data management services for the Internet users. The cloud users can create, store, access and update the remote outsourced databases just as they are using the database system locally. However, unlike storing data in a fully-controlled local database, storing data in a remote cloud server raises data privacy and security concerns, i.e., the correctness and completeness of the query results. Although some solutions have been proposed to address this problem, they do not scale well when multiple users update the remote outsourced database for two major reasons. First, the existing schemes mainly use the authenticated data structure (ADS) to provide the verification service which incurs expensive computation cost, especially when modifications are made to the database. Second, the data owner has to remain online all the time to participate in generating signatures for the modified data. Consider the fact that the outsourced databases involve lots of heavy multi-user modification operations, the existing solutions are not practical from the efficiency perspective. To address the above concerns, in this paper, we first propose a novel and efficient signature scheme which features additive homomorphic operations. On top of that, we further propose a new and practical mechanism for correctness and completeness verification with the support of multi-user modifications and without requiring an always-online data owner. Finally, we prove the security of our scheme under the well-known Computational Diffie-Hellman assumption and conduct extensive experiments to evaluate the performance of our scheme. The experimental results show that our scheme outperforms the existing solutions.