{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,3]],"date-time":"2026-09-03T15:44:48Z","timestamp":1788450288994,"version":"build-2803163510"},"reference-count":42,"publisher":"Association for Computing Machinery (ACM)","issue":"7","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2015,2]]},"abstract":"<jats:p>\n                    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 matching queries featuring\n                    <jats:italic>fast generation of constant-size proofs.<\/jats:italic>\n                    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\u03bcs to generate a proof for a pattern (mis)match of 10\n                    <jats:sup>2<\/jats:sup>\n                    characters in a text of 10\n                    <jats:sup>6<\/jats:sup>\n                    characters, once the query has been evaluated.\n                  <\/jats:p>","DOI":"10.14778\/2752939.2752944","type":"journal-article","created":{"date-parts":[[2015,5,12]],"date-time":"2015-05-12T11:37:52Z","timestamp":1431430672000},"page":"750-761","source":"Crossref","is-referenced-by-count":23,"title":["Practical authenticated pattern matching with optimal proof size"],"prefix":"10.14778","volume":"8","author":[{"given":"Dimitrios","family":"Papadopoulos","sequence":"first","affiliation":[{"name":"Boston University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Charalampos","family":"Papamanthou","sequence":"additional","affiliation":[{"name":"University of Maryland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Roberto","family":"Tamassia","sequence":"additional","affiliation":[{"name":"Brown University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Nikos","family":"Triandopoulos","sequence":"additional","affiliation":[{"name":"Boston University"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2015,2]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Crypto++ Library. http:\/\/www.cryptopp.com\/.  Crypto++ Library. http:\/\/www.cryptopp.com\/."},{"key":"e_1_2_1_2_1","unstructured":"DCLXVI Library. http:\/\/cryptojedi.org\/.  DCLXVI Library. http:\/\/cryptojedi.org\/."},{"key":"e_1_2_1_3_1","unstructured":"FLINT Library. http:\/\/www.flintlib.org\/.  FLINT Library. http:\/\/www.flintlib.org\/."},{"key":"e_1_2_1_4_1","unstructured":"PugiXML. http:\/\/pugixml.org\/.  PugiXML. http:\/\/pugixml.org\/."},{"key":"e_1_2_1_5_1","unstructured":"University of Washington XML data repository. http:\/\/www.cs.washington.edu\/research\/xmldatasets\/.  University of Washington XML data repository. http:\/\/www.cs.washington.edu\/research\/xmldatasets\/."},{"key":"e_1_2_1_6_1","unstructured":"XMark. http:\/\/www.xml-benchmark.org\/.  XMark. http:\/\/www.xml-benchmark.org\/."},{"key":"e_1_2_1_7_1","volume-title":"July","author":"Barker E.","year":"2012","unstructured":"E. Barker , W. Barker , W. Burr , W. Polk , and M. Smid . NIST recommendation for key management Part 1: General (revision 3) , July 2012 . E. Barker, W. Barker, W. Burr, W. Polk, and M. Smid. NIST recommendation for key management Part 1: General (revision 3), July 2012."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-40084-1_6"},{"key":"e_1_2_1_9_1","volume-title":"EUROCRYPT","author":"Benaloh J. C.","year":"1993","unstructured":"J. C. Benaloh and M. de Mare . One-way accumulators : A decentralized alternative to digital sginatures (extended abstract) . In EUROCRYPT , 1993 . J. C. Benaloh and M. de Mare. One-way accumulators: A decentralized alternative to digital sginatures (extended abstract). In EUROCRYPT, 1993."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2004.63"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00145-007-9005-7"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-11379-1_3"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2517349.2522733"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.5555\/646767.704437"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-54631-0_7"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.5555\/1062063.1062065"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-39212-2_48"},{"key":"e_1_2_1_18_1","volume-title":"Algorithm design - foundations, analysis and internet examples","author":"Goodrich M. T.","year":"2002","unstructured":"M. T. Goodrich and R. Tamassia . Algorithm design - foundations, analysis and internet examples . Wiley , 2002 . M. T. Goodrich and R. Tamassia. Algorithm design - foundations, analysis and internet examples. Wiley, 2002."},{"key":"e_1_2_1_19_1","volume-title":"An Introduction to Parallel Algorithms","author":"JaJa J.","year":"1997","unstructured":"J. JaJa . An Introduction to Parallel Algorithms . Addison Wesley , 1997 . J. JaJa. An Introduction to Parallel Algorithms. Addison Wesley, 1997."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-30115-8_22"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1880022.1880026"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.14778\/2047485.2047490"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-003-1076-8"},{"key":"e_1_2_1_24_1","volume-title":"CRYPTO","author":"Merkle R.","year":"1989","unstructured":"R. Merkle . A certified digital signature . In CRYPTO , 1989 . R. Merkle. A certified digital signature. In CRYPTO, 1989."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1137\/0220070"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.5555\/1884265.1884275"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-30574-3_19"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-27836-8_87"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.14778\/1453856.1453875"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.5555\/2033036.2033045"},{"key":"e_1_2_1_31_1","first-page":"1","volume-title":"Algorithmica","author":"Papamanthou C.","year":"2015","unstructured":"C. Papamanthou , R. Tamassia , and N. Triandopoulos . Authenticated hash tables based on cryptographic accumulators . Algorithmica , pages 1 -- 49 , 2015 . C. Papamanthou, R. Tamassia, and N. Triandopoulos. Authenticated hash tables based on cryptographic accumulators. Algorithmica, pages 1--49, 2015."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/SP.2013.47"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/2465351.2465359"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-39658-1_2"},{"key":"e_1_2_1_35_1","volume-title":"AMW","author":"Tamassia R.","year":"2010","unstructured":"R. Tamassia and N. Triandopoulos . Certification and authentication of data structures . In AMW , 2010 . R. Tamassia and N. Triandopoulos. Certification and authentication of data structures. In AMW, 2010."},{"key":"e_1_2_1_36_1","volume-title":"USENIX HotCloud","author":"Thaler J.","year":"2012","unstructured":"J. Thaler , M. Roberts , M. Mitzenmacher , and H. Pfister . Verifiable computation with massively parallel interactive proofs . In USENIX HotCloud , 2012 . J. Thaler, M. Roberts, M. Mitzenmacher, and H. Pfister. Verifiable computation with massively parallel interactive proofs. In USENIX HotCloud, 2012."},{"key":"e_1_2_1_37_1","volume-title":"Undergraduate Honors Thesis","author":"Tremel E.","year":"2013","unstructured":"E. Tremel . Real-world performance of cryptographic accumulators. Undergraduate Honors Thesis , Brown University , 2013 . E. Tremel. Real-world performance of cryptographic accumulators. Undergraduate Honors Thesis, Brown University, 2013."},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/SWAT.1973.13"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559845.1559849"},{"key":"e_1_2_1_40_1","volume-title":"FC","author":"Yavuz A. A.","year":"2012","unstructured":"A. A. Yavuz , P. Ning , and M. K. Reiter . Efficient, compromise resilient and append-only cryptographic schemes for secure audit logging . In FC , 2012 . A. A. Yavuz, P. Ning, and M. K. Reiter. Efficient, compromise resilient and append-only cryptographic schemes for secure audit logging. In FC, 2012."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/2523649.2523670"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/2660267.2660354"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/2752939.2752944","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T05:15:28Z","timestamp":1672204528000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/2752939.2752944"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,2]]},"references-count":42,"journal-issue":{"issue":"7","published-print":{"date-parts":[[2015,2]]}},"alternative-id":["10.14778\/2752939.2752944"],"URL":"https:\/\/doi.org\/10.14778\/2752939.2752944","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2015,2]]}}}