We propose a Parity-based Data Outsourcing(PDO) model in this paper. This model outsources a set of raw data by associating it with a set of parity data and then distributing both sets of data among a number of cloud servers that are managed independently by different service providers. Users query the servers for the data of their interest and are allowed to perform both authentication and correction. The former refers to the capability of verifying if the query result they receive is correct (i.e., all data items that satisfy the query condition are received, and every data item received is original from the data owner), whereas the latter, the capability of correcting the corrupted data, if any. A data item may be corrupted unintentionally (e.g, because of errors in systems and/or networking) or intentionally (e.g., by malicious service providers or because of systems being compromised by hackers). Existing techniques support only query authentication, but not error correction. Moreover, they all rely on complex cryptographic techniques and require the cloud server to build verification objects. In contrast, our approach achieves both without using any encryption. It does not require to install any additional software on a cloud server and thus can take advantage of the many cloud data management services available on the market today. We address the challenges of PDO implementation, including parity coding, database encoding, data retrieval, and database insertion and deletion, and evaluate the performance potential of PDO through analysis, simulation, and prototyping. Our results indicate its excellent performance in terms of storage, communication, and computation overhead.

Consider a database where each record represents a math function. A third party is in charge of processing queries over this database and we want to provide a mechanism for users to verify the correctness of their query results. Here each query, referred to as a Function Query (FQ), retrieves the functions whose computation results with user-supplied arguments satisfy certain conditions (e.g., within a certain range). We present authentication solutions that work on a variety of functions, including univariate linear function, multivariate linear function, and multivariate high degree function. Our solutions are based on the fact that the functions can be sorted in the subdomains defined by their intersections and thus can be chained to produce a signature mesh for query result verification. We study the performance of the proposed techniques through theoretical analysis, simulation and empirical study, and include the results in this paper.