Privacy-Preserving Fine-grained Correctness Verification of Query Results in Outsourced Databases

Adoption of data outsourcing to cloud servers is hindered by data integrity issues due to the lack of trust to the servers. Existing solutions to deal with the problem often require costly verification processes to build a verification object (VO) at the server side and to verify it at the client side, especially when the verification is to be performed at a low-level of granularity. This paper proposes an efficient and privacy-preserving solution, which verifies both the integrity and completeness of query results at the finest level of granularity — an individual attribute value. Outsourced data confidentiality is also preserved by securely dividing attribute values into several pieces. As a key novelty, our solution does not require building VOs at the server side for query results. Consequently, 1) no computation overhead is imposed on the server to construct VOs, 2) no change is required to the existing DBMS engines due to calculating VOs and accompanying them with the results, and 3) no information leakage occurs due to building or observing VOs by the server. Our theoretical and empirical analyses indicate the effectiveness of our solution compared to the existing solutions in terms of communication, query execution, and verification overheads.