TY - GEN
T1 - Super-efficient verification of dynamic outsourced databases
AU - Goodrich, Michael T.
AU - Tamassia, Roberto
AU - Triandopoulos, Nikos
PY - 2008
Y1 - 2008
N2 - We develop new algorithmic and cryptographic techniques for authenticating the results of queries over databases that are outsourced to an untrusted responder. We depart from previous approaches by considering super-efficient answer verification, where answers to queries are validated in time asymptotically less that the time spent to produce them and using lightweight cryptographic operations. We achieve this property by adopting the decoupling of query answering and answer verification in a way designed for queries related to range search. Our techniques allow for efficient updates of the database and protect against replay attacks performed by the responder. One such technique uses an off-line audit mechanism: the data source and the user keep digests of the sequence of operations, yet are able to jointly audit the responder to determine if a replay attack has occurred since the last audit.
AB - We develop new algorithmic and cryptographic techniques for authenticating the results of queries over databases that are outsourced to an untrusted responder. We depart from previous approaches by considering super-efficient answer verification, where answers to queries are validated in time asymptotically less that the time spent to produce them and using lightweight cryptographic operations. We achieve this property by adopting the decoupling of query answering and answer verification in a way designed for queries related to range search. Our techniques allow for efficient updates of the database and protect against replay attacks performed by the responder. One such technique uses an off-line audit mechanism: the data source and the user keep digests of the sequence of operations, yet are able to jointly audit the responder to determine if a replay attack has occurred since the last audit.
UR - http://www.scopus.com/inward/record.url?scp=43149099270&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=43149099270&partnerID=8YFLogxK
U2 - 10.1007/978-3-540-79263-5_26
DO - 10.1007/978-3-540-79263-5_26
M3 - Conference contribution
AN - SCOPUS:43149099270
SN - 3540792627
SN - 9783540792628
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 407
EP - 424
BT - Topics in Cryptology - CT-RSA 2008 - The Cryptographers' Track at the RSA Conference 2008, Proceedings
T2 - Cryptographers' Track at the RSA Conference, CT-RSA 2008
Y2 - 8 April 2008 through 11 April 2008
ER -