Super-Efficient Verification of Dynamic Outsourced Databases

@incollection{citeulike:3010788, abstract = {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.}, author = {Goodrich, Michael and Tamassia, Roberto and Triandopoulos, Nikos }, citeulike-article-id = {3010788}, doi = {http://dx.doi.org/10.1007/978-3-540-79263-5\_26}, journal = {Topics in Cryptology – CT-RSA 2008}, keywords = {accumulators, authentication, hash}, pages = {407--424}, posted-at = {2008-07-17 00:55:21}, priority = {2}, title = {Super-Efficient Verification of Dynamic Outsourced Databases}, url = {http://dx.doi.org/10.1007/978-3-540-79263-5\_26}, year = {2008} }

TY - CHAP ID - citeulike:3010788 L3 - citeulike-article-id:3010788 TI - Super-Efficient Verification of Dynamic Outsourced Databases JF - Topics in Cryptology – CT-RSA 2008 SP - 407 EP - 424 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. KW - accumulators KW - authentication KW - hash AU - Goodrich, Michael AU - Tamassia, Roberto AU - Triandopoulos, Nikos PY - 2008/// UR - http://dx.doi.org/10.1007/978-3-540-79263-5_26 ER -