{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,28]],"date-time":"2025-09-28T20:48:53Z","timestamp":1759092533574,"version":"3.41.0"},"reference-count":40,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2008,3,1]],"date-time":"2008-03-01T00:00:00Z","timestamp":1204329600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100014790","name":"Singapore Management University","doi-asserted-by":"crossref","award":["C220\/MSS5C002"],"award-info":[{"award-number":["C220\/MSS5C002"]}],"id":[{"id":"10.13039\/501100014790","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Inf. Syst. Secur."],"published-print":{"date-parts":[[2008,3]]},"abstract":"The number of successful attacks on the Internet shows that it is very difficult to guarantee the security of online servers over extended periods of time. A breached server that is not detected in time may return incorrect query answers to users. In this article, we introduce authentication schemes for users to verify that their query answers from an online server are complete (i.e., no qualifying tuples are omitted) and authentic (i.e., all the result values are legitimate). We introduce a scheme that supports range selection, projection as well as primary key-foreign key join queries on relational databases. We also present authentication schemes for single- and multi-attribute range aggregate queries. The schemes complement access control mechanisms that rewrite queries dynamically, and are computationally secure. We have implemented the proposed schemes, and experiment results showed that they are practical and feasible schemes with low overheads.<\/jats:p>","DOI":"10.1145\/1330332.1330337","type":"journal-article","created":{"date-parts":[[2008,2,28]],"date-time":"2008-02-28T14:02:33Z","timestamp":1204207353000},"page":"1-50","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":35,"title":["Verifying Completeness of Relational Query Answers from Online Servers"],"prefix":"10.1145","volume":"11","author":[{"given":"Hweehwa","family":"Pang","sequence":"first","affiliation":[{"name":"Singapore Management University"}]},{"given":"Kian-Lee","family":"Tan","sequence":"additional","affiliation":[{"name":"National University of Singapore"}]}],"member":"320","published-online":{"date-parts":[[2008,5]]},"reference":[{"volume-title":"2nd International Workshop<\/it>","author":"Anderson R.","key":"e_1_2_1_1_1","unstructured":" Anderson , R. , Needham , R. , and Shamir , A . <\/scp> 1998. The Steganographic file system. In <it>Information Hiding , 2nd International Workshop<\/it> . Portland, OR. D. Aucsmith Ed. Anderson, R., Needham, R., and Shamir, A.<\/scp> 1998. The Steganographic file system. In <it>Information Hiding, 2nd International Workshop<\/it>. Portland, OR. D. Aucsmith Ed."},{"key":"e_1_2_1_2_1","volume-title":"<\/scp>","author":"Boneh D.","year":"2003","unstructured":" Boneh , D. , Gentry , C. , Lynn , B. , and Shacham , H . <\/scp> 2003 . Aggregate and verifiably encrypted signatures from bilinear maps. In <it>Proceedings of Advances in Cryptology (EUROCRYPT'03)<\/it>, E. Biham Ed., <it>Lecture Notes in Computer Science<\/it>, Springer-Verlag . 416--432. Boneh, D., Gentry, C., Lynn, B., and Shacham, H.<\/scp> 2003. Aggregate and verifiably encrypted signatures from bilinear maps. In <it>Proceedings of Advances in Cryptology (EUROCRYPT'03)<\/it>, E. Biham Ed., <it>Lecture Notes in Computer Science<\/it>, Springer-Verlag. 416--432."},{"key":"e_1_2_1_3_1","volume-title":"-L.<\/scp>","author":"Cheng W.","year":"2006","unstructured":" Cheng , W. , Pang , H. , and Tan , K . -L.<\/scp> 2006 . Authenticating multi-dimensional query results in data publishing. In <it>Proceedings of the 20th Annual IFIP WG 11.3 Working Conference on Data and Applications Security <\/it>. Cheng, W., Pang, H., and Tan, K.-L.<\/scp> 2006. Authenticating multi-dimensional query results in data publishing. In <it>Proceedings of the 20th Annual IFIP WG 11.3 Working Conference on Data and Applications Security<\/it>."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/129902.129907"},{"key":"e_1_2_1_5_1","volume-title":"-L.<\/scp>","author":"Chun S.-J.","year":"2001","unstructured":" Chun , S.-J. , Chung , C.-W. , Lee , J.-H. , and Lee , S . -L.<\/scp> 2001 . Dynamic update cube for range-sum queries. In <it>Proceedings of the International Conference on Very Large Data Bases (VLDB '01)<\/it>. 521--530. Chun, S.-J., Chung, C.-W., Lee, J.-H., and Lee, S.-L.<\/scp> 2001. Dynamic update cube for range-sum queries. In <it>Proceedings of the International Conference on Very Large Data Bases (VLDB'01)<\/it>. 521--530."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/11552338_2"},{"key":"e_1_2_1_7_1","volume-title":"<\/scp>","author":"Damiani E.","year":"2005","unstructured":" Damiani , E. , di Vimercati , S. D. C. , Foresti , S. , Samarati , P. , and Viviani , M . <\/scp> 2005 b. Measuring Inference Exposure in Outsourced Encrypted Databases. In <it>Proceedings of the 1st Workshop on Quality of Protection <\/it>. Damiani, E., di Vimercati, S. D. C., Foresti, S., Samarati, P., and Viviani, M.<\/scp> 2005b. Measuring Inference Exposure in Outsourced Encrypted Databases. In <it>Proceedings of the 1st Workshop on Quality of Protection<\/it>."},{"key":"e_1_2_1_8_1","volume-title":"<\/scp>","author":"Devanbu P.","year":"2000","unstructured":" Devanbu , P. , Gertz , M. , Martel , C. , and Stubblebine , S . <\/scp> 2000 . Authentic data publication over the Internet. In <it>14th IFIP Working Conference in Database Security <\/it>. 102--112. Devanbu, P., Gertz, M., Martel, C., and Stubblebine, S.<\/scp> 2000. Authentic data publication over the Internet. In <it>14th IFIP Working Conference in Database Security<\/it>. 102--112."},{"key":"e_1_2_1_9_1","volume-title":"<\/scp>","author":"Devanbu P.","year":"2003","unstructured":" Devanbu , P. , Gertz , M. , Martel , C. , and Stubblebine , S . <\/scp> 2003 . Authentic data publication over the Internet. <it>J. Comput. Secur . 11<\/it>, 291--314. Devanbu, P., Gertz, M., Martel, C., and Stubblebine, S.<\/scp> 2003. Authentic data publication over the Internet. <it>J. Comput. Secur. 11<\/it>, 291--314."},{"key":"e_1_2_1_10_1","unstructured":"DriveCrypt<\/scp>. Secure hard disk encryption. http:\/\/www.drivecrypt.com. DriveCrypt<\/scp>. Secure hard disk encryption. http:\/\/www.drivecrypt.com."},{"key":"e_1_2_1_11_1","unstructured":"DSS<\/scp>. 1991. Proposed federal information processing standard for digital signature standard (DSS). <it>Federal Register 56 169<\/it> 42980--42982. DSS<\/scp>. 1991. Proposed federal information processing standard for digital signature standard (DSS). <it>Federal Register 56 169<\/it> 42980--42982."},{"volume-title":"Encrypting file system for windows","year":"2000","key":"e_1_2_1_12_1","unstructured":"EFS<\/scp>. Encrypting file system for windows 2000 . http:\/\/www.microsoft.com\/windows2000\/techinfo\/howitworks\/security\/encrypt. asp. EFS<\/scp>. Encrypting file system for windows 2000. http:\/\/www.microsoft.com\/windows2000\/techinfo\/howitworks\/security\/encrypt. asp."},{"key":"e_1_2_1_13_1","volume-title":"<\/scp>","author":"Geffner S.","year":"2000","unstructured":" Geffner , S. , Agrawal , D. , and Abbadi , A. E . <\/scp> 2000 . The dynamic data cube. In <it>Proceedings of the International Conference on Extending Database Technology (EDBT '00)<\/it>. 237--253. Geffner, S., Agrawal, D., and Abbadi, A. E.<\/scp> 2000. The dynamic data cube. In <it>Proceedings of the International Conference on Extending Database Technology (EDBT'00)<\/it>. 237--253."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1009726021843"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/564691.564717"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/253260.253274"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1142473.1142488"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/11535706_6"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/11602897_32"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-003-1076-8"},{"volume-title":"A certified digital signature. In <it>Proceedings of Advances in Cryptology (Crypto'89), <\/it>Lecture Notes in Computer Science","author":"Merkle R.","key":"e_1_2_1_21_1","unstructured":" Merkle , R. <\/scp> 1989. A certified digital signature. In <it>Proceedings of Advances in Cryptology (Crypto'89), <\/it>Lecture Notes in Computer Science . vol. 0435 . 218--238. Merkle, R.<\/scp> 1989. A certified digital signature. In <it>Proceedings of Advances in Cryptology (Crypto'89), <\/it>Lecture Notes in Computer Science. vol. 0435. 218--238."},{"key":"e_1_2_1_22_1","volume-title":"<\/scp>","author":"Mykletun E.","year":"2004","unstructured":" Mykletun , E. , Narasimha , M. , and Tsudik , G . <\/scp> 2004 . Authentication and integrity in outsourced databases. In <it>Proceedings of the Network and Distributed System Security Symposium <\/it>. Mykletun, E., Narasimha, M., and Tsudik, G.<\/scp> 2004. Authentication and integrity in outsourced databases. In <it>Proceedings of the Network and Distributed System Security Symposium<\/it>."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/11733836_30"},{"key":"e_1_2_1_24_1","volume-title":"<\/scp>","author":"Neuman B.","year":"1994","unstructured":" Neuman , B. and Tso , T . <\/scp> 1994 . Kerberos : An authentication service for computer networks. <it>IEEE Comm . 32,<\/it> 9, 33--38. Neuman, B. and Tso, T.<\/scp> 1994. Kerberos: An authentication service for computer networks. <it>IEEE Comm. 32,<\/it> 9, 33--38."},{"key":"e_1_2_1_25_1","unstructured":"Oracle VPD<\/scp>. 2002. The virtual private database in Oracle9ir2: An Oracle technical white paper. http:\/\/otn.oracle.com\/deploy\/security\/oracle9ir2\/pdf\/vpd9ir2twp.pdf. Oracle VPD<\/scp>. 2002. The virtual private database in Oracle9ir2: An Oracle technical white paper. http:\/\/otn.oracle.com\/deploy\/security\/oracle9ir2\/pdf\/vpd9ir2twp.pdf."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1066157.1066204"},{"key":"e_1_2_1_27_1","volume-title":"<\/scp>","author":"Pang H.","year":"2004","unstructured":" Pang , H. and Tan , K . <\/scp> 2004 . Authenticating query results in edge computing. In <it>IEEE International Conference on Data Engineering <\/it>. 560--571. Pang, H. and Tan, K.<\/scp> 2004. Authenticating query results in edge computing. In <it>IEEE International Conference on Data Engineering<\/it>. 560--571."},{"key":"e_1_2_1_28_1","volume-title":"<\/scp>","author":"Pang H.","year":"2003","unstructured":" Pang , H. , Tan , K. , and Zhou , X . <\/scp> 2003 . StegFS: A Steganographic file system. In <it>Proceedings of the 19th International Conference on Data Engineering<\/it>. Bangalore, India , 657--668. Pang, H., Tan, K., and Zhou, X.<\/scp> 2003. StegFS: A Steganographic file system. In <it>Proceedings of the 19th International Conference on Data Engineering<\/it>. Bangalore, India, 657--668."},{"key":"e_1_2_1_29_1","volume-title":"<\/scp>","author":"Papadias D.","year":"2001","unstructured":" Papadias , D. , Kalnis , P. , Zhang , J. , and Tao , Y . <\/scp> 2001 . Efficient OLAP operations in spatial data warehouses. In <it>Proceedings of the 7th International Symposium on Spatial and Temporal Databases <\/it>. 443--459. Papadias, D., Kalnis, P., Zhang, J., and Tao, Y.<\/scp> 2001. Efficient OLAP operations in spatial data warehouses. In <it>Proceedings of the 7th International Symposium on Spatial and Temporal Databases<\/it>. 443--459."},{"key":"e_1_2_1_30_1","volume-title":"<\/scp>","author":"Papadias D.","year":"2002","unstructured":" Papadias , D. , Tao , Y. , Kalnis , P. , and Zhang , J . <\/scp> 2002 . Indexing spatio-temporal data warehouses. In <it>IEEE International Conference on Data Engineering <\/it>. 166--175. Papadias, D., Tao, Y., Kalnis, P., and Zhang, J.<\/scp> 2002. Indexing spatio-temporal data warehouses. In <it>IEEE International Conference on Data Engineering<\/it>. 166--175."},{"key":"e_1_2_1_31_1","unstructured":"PGPdisk<\/scp>. http:\/\/www.pgpi.org\/products\/pgpdisk\/. PGPdisk<\/scp>. http:\/\/www.pgpi.org\/products\/pgpdisk\/."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/958491.958521"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.17487\/RFC1321"},{"key":"e_1_2_1_34_1","volume-title":"<\/scp>","author":"Rivest R.","year":"2001","unstructured":" Rivest , R. and Shamir , A . <\/scp> 2001 . PayWord and MicroMint: Two simple micropayment schemes. In http:\/\/theory.lcs.mit.edu\/rivest\/RivestShamir-mpay.pdf. Rivest, R. and Shamir, A.<\/scp> 2001. PayWord and MicroMint: Two simple micropayment schemes. In http:\/\/theory.lcs.mit.edu\/rivest\/RivestShamir-mpay.pdf."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/359340.359342"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/582318.582321"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/356924.356930"},{"key":"e_1_2_1_38_1","volume-title":"<\/scp>","author":"Sandhu R.","year":"1994","unstructured":" Sandhu , R. and Samarati , P . <\/scp> 1994 . Access Control : Principles and Practice. <it>IEEE Comm . 32,<\/it> 9, 40--48. Sandhu, R. and Samarati, P.<\/scp> 1994. Access Control: Principles and Practice. <it>IEEE Comm. 32,<\/it> 9, 40--48."},{"key":"e_1_2_1_39_1","first-page":"180","article-title":"Secure hashing algorithm. National Institute of Science and Technology","year":"2001","unstructured":"SHA<\/scp>. 2001 . Secure hashing algorithm. National Institute of Science and Technology . FIPS 180 - 182 . SHA<\/scp>. 2001. Secure hashing algorithm. National Institute of Science and Technology. FIPS 180-2.","journal-title":"FIPS"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/543613.543629"}],"container-title":["ACM Transactions on Information and System Security"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1330332.1330337","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1330332.1330337","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T14:47:31Z","timestamp":1750258051000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1330332.1330337"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,3]]},"references-count":40,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2008,3]]}},"alternative-id":["10.1145\/1330332.1330337"],"URL":"https:\/\/doi.org\/10.1145\/1330332.1330337","relation":{},"ISSN":["1094-9224","1557-7406"],"issn-type":[{"type":"print","value":"1094-9224"},{"type":"electronic","value":"1557-7406"}],"subject":[],"published":{"date-parts":[[2008,3]]},"assertion":[{"value":"2006-06-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2007-08-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-05-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}