System and Method for Optimal Verification of Operations on Dynamic Sets

A system and method for cryptographically checking the correctness of outsourced set operations performed by an untrusted server over a dynamic collection of sets that are owned (and updated) by a trusted source is disclosed. The system and method provides new authentication mechanisms that allow any entity to publicly verify a proof attesting the correctness of primitive set operations such as intersection, union, subset and set difference. Based on a novel extension of the security properties of bilinear-map accumulators as well as on a primitive called accumulation tree, the system and method achieves optimal verification and proof complexity, as well as optimal update complexity, while incurring no extra asymptotic space overhead. The method provides an efficient proof construction, adding a logarithmic overhead to the computation of the answer of a set-operation query. Applications of interest include efficient verification of keyword search and database queries.