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.
1. A computer implemented method of verifying set operations on a dynamic collection of sets performed by an untrusted server, comprising:
providing a dynamic collection 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 using the secret key and public key;
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;
returning the answer and proof to the client; and
verifying the answer by using the public key and digest to check the proof.
2. The method of claim 1 , wherein the client and trusted source are the same.
3. The method of claim 1 , wherein the client and trusted source are different.
4. The method of claim 1 , wherein the set operation query consisting essentially of the group selected from the primitive set operations of union, intersection, set difference, and subset.
5. The method of claim 1 , wherein the proof is returned in an accumulation tree representing the answer to the set operation query performed on the dynamic collection of sets.
6. The method of claim 5 , wherein the proof further contains subset witnesses.
7. The method of claim 5 , wherein the proof further contains completeness witnesses.
8. The method of claim 5 , wherein the proof further contains membership witnesses.
9. The method of claim 5 , wherein the proof further contains accumulation-value correctness witnesses.
10. The method of claim 1 , wherein the proof verifies the correctness of the answer with respect to the digest.
11. The method of claim 1 , wherein the set operation query is based on a keyword search on a collection of documents.
12. The method of claim 11 , wherein the keyword search comprises timestamps.
13. The method of claim 1 , wherein the set operation query is based on database records.
14. The method of claim 1 , wherein the digest is constructed by applying hierarchically over the dynamic collection of sets, an accumulator tree formed through bilinear-map accumulators and collision-resistant hashing.
15. 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.
16. The method of claim 15 , wherein the set operation query consisting essentially of the group selected from the primitive set operations of union, intersection, set difference, and subset.
17. The method of claim 15 , wherein the proof is returned in an accumulation tree representing the answer to the set operation query performed on the dynamic collection of sets.
18. The method of claim 17 , wherein the proof further contains subset witnesses.
19. The method of claim 17 , wherein the proof further contains completeness witnesses.
20. The method of claim 17 , wherein the proof further contains membership witnesses.
21. The method of claim 17 , wherein the proof further contains accumulation-value correctness witnesses.
22. The method of claim 15 , wherein the proof verifies the correctness of the answer with respect to the digest.
23. The method of claim 15 , wherein the set operation query is based on a keyword search on a collection of documents.
24. The method of claim 23 , wherein the keyword search comprises timestamps.
25. The method of claim 15 , wherein the set operation query is based on database records.
26. 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.
27. The system of claim 26 , wherein the trusted source is a plurality of synchronized trusted sources.
28. The system of claim 26 , wherein the client and trusted source are the same.
29. The system of claim 26 , wherein the client and trusted source are the different.
30. The system of claim 26 , wherein the server is configured and arranged to receive set operation queries consisting essentially of the group selected from the primitive set operations of union, intersection, set difference, and subset.
31. The system of claim 26 , wherein the proof is returned in an accumulation tree representing the answer to the set operation query performed on the dynamic collection of sets.
32. The system of claim 31 , wherein the proof further contains subset witnesses.
33. The system of claim 31 , wherein the proof further contains completeness witnesses.
34. The system of claim 31 , wherein the proof further contains membership witnesses.
35. The system of claim 31 , wherein the proof further contains accumulation-value correctness witnesses.
36. The system of claim 26 , wherein the set operation query is based on a keyword search on a collection of documents.
37. The system of claim 26 , wherein the keyword search comprises timestamps.
38. The system of claim 26 , wherein the set operation query is based on database records.
39. The system of claim 26 , wherein the digest is constructed by applying hierarchically over the dynamic collection of sets, an accumulator tree formed through bilinear-map accumulators and collision-resistant hashing.