Certification and Authentication of Data Structures

Download Now
Provided by: Brown University
Topic: Security
Format: PDF
The authors study the design of secure protocols for efficiently verifying the results of queries on data structures that are outsourced to untrusted servers, where answers are processed over relational databases in the RAM model of computation. They introduce a new authentication framework that, by design and through the new concept of query certification, aims at verifying the validity of the answer, rather than each step of the algorithm that generates the answer. Their framework efficiently reduces the authentication of general queries to that of set-membership queries, and provides sufficient conditions for achieving super-efficient answer verification (in time asymptotically less than the time spent to answer the query).
Download Now

Find By Topic