We study the problem of authenticating outsourced set operations performed by an untrusted server over a dynamic collection of sets that are owned by a trusted source. We present efficient methods for authenticating fundamental set operations, such as union and intersection so that the client can verify the correctness of the received answer. Based on a novel extension of the security properties of bilinear-map accumulators, our authentication scheme is the first to achieve optimality in several critical performance measures:
Updates and queries are also efficient at the server. In contrast, existing schemes entail high bandwidth and verification costs or high storage usage since they recompute the query over authentic data or precompute answers to all possible queries.
We also show applications of our techniques to the authentication of keyword searches on outsourced document collections (e.g., inverted-index queries) and of queries in outsourced databases (e.g., equi-join queries). Since set intersection is heavily used in these applications, we obtain new authentication schemes that compare favorably to existing approaches.
(Joint work with Charalampos Papamanthou and Nikos Triandopoulos.)