CS 269S, Winter 2011: Theory Seminar
Bren Hall, Room 3011, 3:00pm
16 Feb 2011:

Optimal Authentication of Operations on Dynamic Sets

Roberto Tamassia, Brown University

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:

  1. The verification overhead at the client is optimal, that is, the client can verify an answer in time proportional to the size of the query parameters and answer.
  2. The update overhead at the source is constant.
  3. The bandwidth consumption is optimal, namely constant between the source and the server and operation-sensitive between the client and the server (i.e., proportional only to the size of the query parameters and the answer).
  4. The storage usage is optimal, namely constant at the client and linear at the source and the server.

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.)