Verifying completeness of relational query results in data publishing

TLDR

In data publishing, query satisfaction is delegated to a third‑party publisher, which may be untrusted or vulnerable to attacks that could produce incorrect results. The paper introduces a scheme that lets users verify that query results are complete—no qualifying tuples omitted—and authentic—values originate from the owner. The scheme supports range selection on key and non‑key attributes, as well as projection and join queries on relational databases. The proposed scheme complies with access control policies, is computationally secure, and can be implemented efficiently.

Abstract

In data publishing, the owner delegates the role of satisfying user queries to a third-party publisher. As the publisher may be untrusted or susceptible to attacks, it could produce incorrect query results. In this paper, we introduce a scheme for users to verify that their query results are complete (i.e., no qualifying tuples are omitted) and authentic (i.e., all the result values originated from the owner). The scheme supports range selection on key and non-key attributes, project as well as join queries on relational databases. Moreover, the proposed scheme complies with access control policies, is computationally secure, and can be implemented efficiently.