Files and links (1)
Published, Version of Record (VoR)CC BY-NC-ND V4.0, Open
Journal article
Practical Authenticated Pattern Matching with Optimal Proof Size
Proceedings of the VLDB Endowment, v 8(7), pp 750-761
01 Mar 2015
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 mu s to generate a proof for a pattern (mis) match of 10(2) characters in a text of 10(6) characters, once the query has been evaluated.
Metrics
13 Record Views
Details
- Title
- Practical Authenticated Pattern Matching with Optimal Proof Size
- Creators
- Dimitrios Papadopoulos - Boston UniversityCharalampos Papamanthou - University of Maryland, College ParkRoberto Tamassia - Brown UniversityNikos Triandopoulos - Boston University
- Publication Details
- Proceedings of the VLDB Endowment, v 8(7), pp 750-761
- Publisher
- Assoc Computing Machinery
- Number of pages
- 12
- Grant note
- 1012798; 1012910; 1228485 / U.S. National Science Foundation under CNS
- Resource Type
- Journal article
- Language
- English
- Academic Unit
- Mathematics
- Web of Science ID
- WOS:000362281700005
- Scopus ID
- 2-s2.0-85013652480
- Other Identifier
- 991020531841304721
InCites Highlights
Data related to this publication, from InCites Benchmarking & Analytics tool:
- Collaboration types
- Domestic collaboration
- Web of Science research areas
- Computer Science, Information Systems
- Computer Science, Theory & Methods