Certification and authentication of data structures

Roberto Tamassia, Nikos Triandopoulos

Research output: Contribution to journalConference articlepeer-review

1 Scopus citations

Abstract

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).

Original languageEnglish
JournalCEUR Workshop Proceedings
Volume619
StatePublished - 2010
Event4th Alberto Mendelzon International Workshop on Foundations of Data Management, AMW 2010 - Buenos Aires, Argentina
Duration: 17 May 201020 May 2010

Fingerprint

Dive into the research topics of 'Certification and authentication of data structures'. Together they form a unique fingerprint.

Cite this