Practical authenticated pattern matching with optimal proof size

Dimitrios Papadopoulos, Charalampos Papamanthou, Roberto Tamassia, Nikos Triandopoulos

Research output: Contribution to journalConference articlepeer-review

21 Scopus citations

Abstract

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.

Original languageEnglish
Pages (from-to)750-761
Number of pages12
JournalProceedings of the VLDB Endowment
Volume8
Issue number7
DOIs
StatePublished - 2015
Event41st International Conference on Very Large Data Bases, VLDB 2015 - Kohala Coast, United States
Duration: 31 Aug 20154 Sep 2015

Fingerprint

Dive into the research topics of 'Practical authenticated pattern matching with optimal proof size'. Together they form a unique fingerprint.

Cite this