{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,8]],"date-time":"2026-04-08T08:55:24Z","timestamp":1775638524218,"version":"3.50.1"},"reference-count":49,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2010,12,1]],"date-time":"2010-12-01T00:00:00Z","timestamp":1291161600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000144","name":"Division of Computer and Network Systems","doi-asserted-by":"publisher","award":["CNS-0831281"],"award-info":[{"award-number":["CNS-0831281"]}],"id":[{"id":"10.13039\/100000144","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000144","name":"Division of Computer and Network Systems","doi-asserted-by":"publisher","award":["CNS-0831278"],"award-info":[{"award-number":["CNS-0831278"]}],"id":[{"id":"10.13039\/100000144","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Inf. Syst. Secur."],"published-print":{"date-parts":[[2010,12]]},"abstract":"<jats:p>Query authentication is an essential component in Outsourced DataBase (ODB) systems. This article introduces efficient index structures for authenticating aggregation queries over large datasets. First, we design an index that features good performance characteristics for static environments. Then, we propose more involved structures for the dynamic case. Our structures feature excellent performance for authenticating queries with multiple aggregate attributes and multiple selection predicates. Furthermore, our techniques cover a large number of aggregate types, including distributive aggregates (such as SUM, COUNT, MIN, and MAX), algebraic aggregates (such as the AVG), and holistic aggregates (such as MEDIAN and QUANTILE). We have also addressed the issue of authenticating aggregation queries efficiently when the database is encrypted to protect data confidentiality. Finally, we implemented a working prototype of the proposed techniques and experimentally validated the effectiveness and efficiency of our methods.<\/jats:p>","DOI":"10.1145\/1880022.1880026","type":"journal-article","created":{"date-parts":[[2010,12,29]],"date-time":"2010-12-29T14:32:48Z","timestamp":1293633168000},"page":"1-35","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":68,"title":["Authenticated Index Structures for Aggregation Queries"],"prefix":"10.1145","volume":"13","author":[{"given":"Feifei","family":"Li","sequence":"first","affiliation":[{"name":"Florida State University"}]},{"given":"Marios","family":"Hadjieleftheriou","sequence":"additional","affiliation":[{"name":"AT&amp;T Labs Research"}]},{"given":"George","family":"Kollios","sequence":"additional","affiliation":[{"name":"Boston University"}]},{"given":"Leonid","family":"Reyzin","sequence":"additional","affiliation":[{"name":"Boston University"}]}],"member":"320","published-online":{"date-parts":[[2010,12]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007568.1007632"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1066157.1066187"},{"key":"e_1_2_1_3_1","volume-title":"Proceedings of the Information Security Conference (ISC). 379--393","author":"Anagnostopoulos A."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2008.4497478"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2004.63"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.5555\/3127142.3127147"},{"key":"e_1_2_1_7_1","unstructured":"Dai W. Crypto++ Library. http:\/\/www.eskimo.com\/~weidai\/cryptlib.html. Dai W. Crypto++ Library. http:\/\/www.eskimo.com\/~weidai\/cryptlib.html."},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of the IFIP Workshop on Database Security (DBSec). 101--112","author":"Devanbu P."},{"key":"e_1_2_1_9_1","volume-title":"Proceedings of the International Conference on Very Large Databases (VLDB). 519--530","author":"Ge T."},{"key":"e_1_2_1_10_1","volume-title":"Proceedings of the Cryptographer\u2019s Track at the RSA Conference (CT-RSA). 407--424","author":"Goodrich M. T."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/3118748.3118939"},{"key":"e_1_2_1_12_1","volume-title":"Proceedings of the Cryptographer\u2019s Track at the RSA Conference (CT-RSA). 295--313","author":"Goodrich M. T."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/564691.564717"},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of the International Conference on Database Systems for Advanced Applications (DASFAA). 125--136","author":"Hacig\u00fcm\u00fcs H."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/253260.253274"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/SSDM.1999.787623"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/170088.170403"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.14778\/1453856.1453876"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/375663.375718"},{"key":"e_1_2_1_20_1","unstructured":"Levitte R. Henson S. and etal OpenSSL. http:\/\/www.openssl.org. Levitte R. Henson S. and et al. OpenSSL. http:\/\/www.openssl.org."},{"key":"e_1_2_1_21_1","unstructured":"Li F. Hadjieleftheriou M. Kollios G. and Reyzin L. 2006a. Authenticated index sturctures for aggregation queries in outsourced databases. Tech. rep. 2006-011 Computer Science Department Boston University. http:\/\/www.cs.bu.edu\/techreports Li F. Hadjieleftheriou M. Kollios G. and Reyzin L. 2006a. Authenticated index sturctures for aggregation queries in outsourced databases. Tech. rep. 2006-011 Computer Science Department Boston University. http:\/\/www.cs.bu.edu\/techreports"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1142473.1142488"},{"key":"e_1_2_1_23_1","volume-title":"Proceedings of the International Conference on Very Large Databases (VLDB). 147--158","author":"Li F."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-003-1076-8"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/SP.1980.10006"},{"key":"e_1_2_1_26_1","doi-asserted-by":"crossref","unstructured":"Miklau G. 2005. Confidentiality and integrity in data exchange. Ph.D. thesis University of Washington. Miklau G. 2005. Confidentiality and integrity in data exchange. Ph.D. thesis University of Washington.","DOI":"10.1007\/978-3-540-30073-1_4"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-008-0108-z"},{"key":"e_1_2_1_28_1","volume-title":"Proceedings of the Annual Network and Distributed System Security Symposium (NDSS).","author":"Mykletun E."},{"key":"e_1_2_1_29_1","volume-title":"Proceedings of the European Symposium on Research in Computer Security (ESORICS). 160--176","author":"Mykletun E."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.5555\/3127142.3127149"},{"key":"e_1_2_1_31_1","volume-title":"Proceedings of the USENIX Security Symposium.","author":"Naor M."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/1099554.1099604"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/1066157.1066204"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.14778\/1453856.1453875"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687627.1687718"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2009.187"},{"key":"e_1_2_1_37_1","volume-title":"Proceedings of the International Conference on Very Large Databases (VLDB). 135--146","author":"Papadopoulos S."},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/1455770.1455826"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/1353343.1353402"},{"key":"e_1_2_1_40_1","volume-title":"Proceedings of the International Conference on Very Large Databases (VLDB). 601--612","author":"Sion R.","year":"2005"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/11523468_13"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-72738-5_23"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2004.93"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/237661.237705"},{"key":"e_1_2_1_45_1","volume-title":"Proceedings of the International Conference on Very Large Databases (VLDB). 782--793","author":"Xie M."},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/1353343.1353384"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2008.4497517"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559845.1559849"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-008-0113-2"}],"container-title":["ACM Transactions on Information and System Security"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1880022.1880026","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1880022.1880026","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T10:52:15Z","timestamp":1750243935000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1880022.1880026"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,12]]},"references-count":49,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2010,12]]}},"alternative-id":["10.1145\/1880022.1880026"],"URL":"https:\/\/doi.org\/10.1145\/1880022.1880026","relation":{},"ISSN":["1094-9224","1557-7406"],"issn-type":[{"value":"1094-9224","type":"print"},{"value":"1557-7406","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,12]]},"assertion":[{"value":"2008-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2010-02-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2010-12-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}