Practical authenticated pattern matching with optimal proof size

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 integrity-checking tool built directly over a suffix tree, we design the first authenticated data structure for verifiable answers to pattern match-ing queries featuring fast generation of constant-size proofs. We present two main applications of our new construction to authen-ticate: (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 match-ing, and at most 243 bytes for exact path XML search, indepen-dently of the document or answer size. By design, our authentica-tion 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. 1