{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:18:45Z","timestamp":1750306725780,"version":"3.41.0"},"reference-count":39,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2014,12,30]],"date-time":"2014-12-30T00:00:00Z","timestamp":1419897600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"European Commission under ICT-FP7-LEADS-318809 (Large-Scale Elastic Architecture for Data-as-a-Service)"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2014,12,30]]},"abstract":"<jats:p>\n            We consider a\n            <jats:italic>stream outsourcing<\/jats:italic>\n            setting, where a data owner delegates the management of a set of disjoint data streams to an untrusted server. The owner authenticates his streams via signatures. The server processes continuous queries on the union of the streams for clients trusted by the owner. Along with the results, the server sends proofs of result correctness derived from the owner's signatures, which are verifiable by the clients. We design novel constructions for a collection of fundamental problems over streams represented as linear algebraic queries. In particular, our basic schemes authenticate dynamic vector sums, matrix products, and dot products. These techniques can be adapted for authenticating a wide range of important operations in streaming environments, including group-by queries, joins, in-network aggregation, similarity matching, and event processing. We also present extensions to address the case of sliding window queries, and when multiple clients are interested in different subsets of the data. These methods take advantage of a novel nonce chaining technique that we introduce, which is used to reduce the verification cost without affecting any other costs. All our schemes are lightweight and offer strong cryptographic guarantees derived from formal definitions and proofs. We experimentally confirm the practicality of our schemes in the performance-sensitive streaming setting.\n          <\/jats:p>","DOI":"10.1145\/2656336","type":"journal-article","created":{"date-parts":[[2015,1,5]],"date-time":"2015-01-05T13:27:09Z","timestamp":1420464429000},"page":"1-45","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Lightweight Query Authentication on Streams"],"prefix":"10.1145","volume":"39","author":[{"given":"Stavros","family":"Papadopoulos","sequence":"first","affiliation":[{"name":"Hong Kong University of Science and Technology"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Graham","family":"Cormode","sequence":"additional","affiliation":[{"name":"University of Warwick, Coventry, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Antonios","family":"Deligiannakis","sequence":"additional","affiliation":[{"name":"Technical University of Crete, Chania, Greece"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Minos","family":"Garofalakis","sequence":"additional","affiliation":[{"name":"Technical University of Crete, Chania, Greece"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2014,12,30]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-003-0095-z"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-01957-9_18"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/872757.872854"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/11818175_36"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/2008684.2008698"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807271"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-00468-1_27"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02927-1_20"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/2033036.2033048"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2090236.2090245"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.14778\/2047485.2047488"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/872757.872838"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/872757.872765"},{"volume-title":"Proceedings of the Conference on Innovative Data Systems Research (CIDR'07)","author":"Demers Alan J.","key":"e_1_2_2_14_1","unstructured":"Alan J. Demers , Johannes Gehrke , Biswanath Panda , Mirek Riedewald , Varun Sharma , and Walker M. White . 2007. Cayuga: A general purpose event monitoring system . In Proceedings of the Conference on Innovative Data Systems Research (CIDR'07) . 412--422. Alan J. Demers, Johannes Gehrke, Biswanath Panda, Mirek Riedewald, Varun Sharma, and Walker M. White. 2007. Cayuga: A general purpose event monitoring system. In Proceedings of the Conference on Innovative Data Systems Research (CIDR'07). 412--422."},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.5555\/876661.876663"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2007.368958"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.5555\/1881412.1881445"},{"volume-title":"The Foundations of Cryptography -","author":"Goldreich Oded","key":"e_1_2_2_18_1","unstructured":"Oded Goldreich . 2001. The Foundations of Cryptography - Volume 1 (Basic Techniques). Cambridge University Press . Oded Goldreich. 2001. The Foundations of Cryptography - Volume 1 (Basic Techniques). Cambridge University Press."},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374396"},{"volume-title":"Introduction to Modern Cryptography","author":"Katz Jonathan","key":"e_1_2_2_20_1","unstructured":"Jonathan Katz and Yehuda Lindell . 2007. Introduction to Modern Cryptography . Chapman and Hall\/CRC Press . Jonathan Katz and Yehuda Lindell. 2007. Introduction to Modern Cryptography. Chapman and Hall\/CRC Press."},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1142473.1142488"},{"key":"e_1_2_2_22_1","volume-title":"Proceedings of the 33rd International Conference on Very Large Data Bases (VLDB'07)","author":"Li Feifei","year":"2007","unstructured":"Feifei Li , Ke Yi , Marios Hadjieleftheriou , and George Kollios . 2007 . Proof-infused streams: Enabling authentication of sliding window queries on streams . In Proceedings of the 33rd International Conference on Very Large Data Bases (VLDB'07) . 147--158. Feifei Li, Ke Yi, Marios Hadjieleftheriou, and George Kollios. 2007. Proof-infused streams: Enabling authentication of sliding window queries on streams. In Proceedings of the 33rd International Conference on Very Large Data Bases (VLDB'07). 147--158."},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/844128.844142"},{"key":"e_1_2_2_24_1","volume-title":"Van Oorschot","author":"Menezes Alfred J.","year":"1996","unstructured":"Alfred J. Menezes , Scott A. Vanstone , and Paul C . Van Oorschot . 1996 . Handbook of Applied Cryptography. CRC Press , Boca Raton, FL. Alfred J. Menezes, Scott A. Vanstone, and Paul C. Van Oorschot. 1996. Handbook of Applied Cryptography. CRC Press, Boca Raton, FL."},{"key":"e_1_2_2_25_1","unstructured":"Microsoft. 2010. StreamInsight. http:\/\/msdn.microsoft.com\/en-us\/library\/ee362541.aspx.  Microsoft. 2010. StreamInsight. http:\/\/msdn.microsoft.com\/en-us\/library\/ee362541.aspx."},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/11733836_30"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1723028.1723074"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2013.6544852"},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559845.1559851"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1066157.1066204"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.5555\/977401.978163"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2465281"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2011.5767886"},{"key":"e_1_2_2_34_1","volume-title":"Proceedings of the 33rd International Conference on Very Large Data Bases (VLDB'07)","author":"Papadopoulos Stavros","year":"2007","unstructured":"Stavros Papadopoulos , Yin Yang , and Dimitris Papadias . 2007 . CADS: Continuous authentication on data streams . In Proceedings of the 33rd International Conference on Very Large Data Bases (VLDB'07) . 135--146. Stavros Papadopoulos, Yin Yang, and Dimitris Papadias. 2007. CADS: Continuous authentication on data streams. In Proceedings of the 33rd International Conference on Very Large Data Bases (VLDB'07). 135--146."},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.5555\/2033036.2033045"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.5555\/1754542.1754568"},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.5555\/1315451.1315477"},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559845.1559849"},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/1567274.1567277"}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2656336","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2656336","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T07:19:37Z","timestamp":1750231177000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2656336"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,12,30]]},"references-count":39,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2014,12,30]]}},"alternative-id":["10.1145\/2656336"],"URL":"https:\/\/doi.org\/10.1145\/2656336","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"type":"print","value":"0362-5915"},{"type":"electronic","value":"1557-4644"}],"subject":[],"published":{"date-parts":[[2014,12,30]]},"assertion":[{"value":"2013-10-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-07-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-12-30","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}