System and method for optimal verification of operations on dynamic sets

A computer implemented method of verifying set operations on a dynamic collection of sets performed by an untrusted server, comprising:

• providing a dynamic selection of sets from a trusted source stored on an untrusted server;
• providing a security parameter based on the dynamic selection of sets;
• calculating a secret key and a public key based on the security parameter;
• calculating a digest of the dynamic collection of sets containing a set of all possible sets in the dynamic collection of sets using the secret key and public key, said digest constructed by applying hierarchically over the dynamic collection of sets, an accumulator tree formed through bilinear-map accumulators and collision-resistant hashing;
• providing a public key and digest to a client;
• performing a set operation query on the dynamic collection of sets;
• determining an answer to the set operation query on the dynamic collection of sets;
• creating a proof of the answer to the set operation query, said proof having a polynomial representing the answer to the set operation query performed on the dynamic collection of sets, said polynomial stored as an accumulation tree of the answer;
• returning the answer and proof to the client;
• and
• verifying the answer by using the public key and digest to check the proof by calculating the coefficients of a polynomial by determining if the nodes of the accumulation tree in the answer are in the accumulation tree of the digest.

A system for verifying set operations on a dynamic collection of sets performed by an untrusted server, comprising:

• an untrusted server hosting a dynamic collection of sets, a digest of the dynamic collection of sets and a public key provided by a trusted source, said untrusted server configured and arranged to receive a set operation query for elements in the dynamic collection of sets, and further configured and arranged to construct and return an answer to the set operation query, a proof and a digest of the dynamic collection of sets;
• at least one client configured and arranged to transmit queries to the untrusted server for elements of the dynamic collection of sets, said client further configured and arranged to receive the answer, digest and a proof transmitted by the untrusted server, and further configured and arranged to verify the answer using the public key, digest and proof;
• said digest of the dynamic collection of sets calculated of the dynamic collection of sets, public key and secret key;
• and
• said secret key and public key calculated from a security parameter based on the dynamic collection of sets.