TY - JOUR
T1 - Practical authenticated pattern matching with optimal proof size
AU - Papadopoulos, Dimitrios
AU - Papamanthou, Charalampos
AU - Tamassia, Roberto
AU - Triandopoulos, Nikos
N1 - Publisher Copyright:
© 2015 VLDB Endowment 2150-8097/15/03.
PY - 2015
Y1 - 2015
N2 - We address the problem of authenticating pattern matching queries over textual data that is outsourced to an untrusted cloud server. By employing cryptographic accumulators in a novel optimal integritychecking tool built directly over a suffix tree, we design the first authenticated data structure for verifiable answers to pattern matching queries featuring fast generation of constant-size proofs. We present two main applications of our new construction to authenticate: (i) pattern matching queries over text documents, and (ii) exact path queries over XML documents. Answers to queries are verified by proofs of size at most 500 bytes for text pattern matching, and at most 243 bytes for exact path XML search, independently of the document or answer size. By design, our authentication schemes can also be parallelized to offer extra efficiency during data outsourcing. We provide a detailed experimental evaluation of our schemes showing that for both applications the times required to compute and verify a proof are very small-e.g., it takes less than 10μs to generate a proof for a pattern (mis)match of 102 characters in a text of 106 characters, once the query has been evaluated.
AB - We address the problem of authenticating pattern matching queries over textual data that is outsourced to an untrusted cloud server. By employing cryptographic accumulators in a novel optimal integritychecking tool built directly over a suffix tree, we design the first authenticated data structure for verifiable answers to pattern matching queries featuring fast generation of constant-size proofs. We present two main applications of our new construction to authenticate: (i) pattern matching queries over text documents, and (ii) exact path queries over XML documents. Answers to queries are verified by proofs of size at most 500 bytes for text pattern matching, and at most 243 bytes for exact path XML search, independently of the document or answer size. By design, our authentication schemes can also be parallelized to offer extra efficiency during data outsourcing. We provide a detailed experimental evaluation of our schemes showing that for both applications the times required to compute and verify a proof are very small-e.g., it takes less than 10μs to generate a proof for a pattern (mis)match of 102 characters in a text of 106 characters, once the query has been evaluated.
UR - http://www.scopus.com/inward/record.url?scp=85013652480&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85013652480&partnerID=8YFLogxK
U2 - 10.14778/2752939.2752944
DO - 10.14778/2752939.2752944
M3 - Conference article
AN - SCOPUS:85013652480
VL - 8
SP - 750
EP - 761
JO - Proceedings of the VLDB Endowment
JF - Proceedings of the VLDB Endowment
IS - 7
T2 - 41st International Conference on Very Large Data Bases, VLDB 2015
Y2 - 31 August 2015 through 4 September 2015
ER -