TY - JOUR
T1 - Certification and authentication of data structures
AU - Tamassia, Roberto
AU - Triandopoulos, Nikos
PY - 2010
Y1 - 2010
N2 - We 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. We 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. Our 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).
AB - We 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. We 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. Our 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).
UR - http://www.scopus.com/inward/record.url?scp=84872246055&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84872246055&partnerID=8YFLogxK
M3 - Conference article
AN - SCOPUS:84872246055
SN - 1613-0073
VL - 619
JO - CEUR Workshop Proceedings
JF - CEUR Workshop Proceedings
T2 - 4th Alberto Mendelzon International Workshop on Foundations of Data Management, AMW 2010
Y2 - 17 May 2010 through 20 May 2010
ER -