An Online Query Authentication System for Outsourced Databases

The cloud computing paradigm moves increasing amount of data across administrative domains to be managed by various outsourced database (ODB) service providers. There needs a means for a data owner to verify the correctness and completeness of query results returned from these ODB services. The process is called query authentication. This paper proposes to use independent observers for query authentication. This approach enables the data owner to maintain the data state using these observers and the query results can be verified by these observers without any additional information from the ODB. To preserve privacy to a certain degree, the data state is partitioned vertically among observers, therefore no observer has full knowledge about the data. We implement the method on top of a NoSQL database. Our evaluation results in Amazon EC2 show the effectiveness of the method in such kind of databases.