{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,25]],"date-time":"2026-02-25T16:44:50Z","timestamp":1772037890458,"version":"3.50.1"},"reference-count":37,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2006,5,1]],"date-time":"2006-05-01T00:00:00Z","timestamp":1146441600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Storage"],"published-print":{"date-parts":[[2006,5]]},"abstract":"<jats:p>In the Outsourced Database (ODB) model, entities outsource their data management needs to a third-party service provider. Such a service provider offers mechanisms for its clients to create, store, update, and access (query) their databases. This work provides mechanisms to ensure data integrity and authenticity for outsourced databases. Specifically, this article provides mechanisms that assure the querier that the query results have not been tampered with and are authentic (with respect to the actual data owner). It investigates both the security and efficiency aspects of the problem and constructs several secure and practical schemes that facilitate the integrity and authenticity of query replies while incurring low computational and communication costs.<\/jats:p>","DOI":"10.1145\/1149976.1149977","type":"journal-article","created":{"date-parts":[[2006,10,18]],"date-time":"2006-10-18T18:11:32Z","timestamp":1161195092000},"page":"107-138","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":186,"title":["Authentication and integrity in outsourced databases"],"prefix":"10.1145","volume":"2","author":[{"given":"Einar","family":"Mykletun","sequence":"first","affiliation":[{"name":"University of California, Irvine, Irvine, CA"}]},{"given":"Maithili","family":"Narasimha","sequence":"additional","affiliation":[{"name":"University of California, Irvine, Irvine, CA"}]},{"given":"Gene","family":"Tsudik","sequence":"additional","affiliation":[{"name":"University of California, Irvine, Irvine, CA"}]}],"member":"320","published-online":{"date-parts":[[2006,5]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Proceedings of the Eurocrypt Conference","volume":"1403","author":"Bellare M.","unstructured":"Bellare , M. , Garay , J. , and Rabin , T . 1998. Fast batch verification for modular exponentiation and digital signatures . In Proceedings of the Eurocrypt Conference , vol. 1403 , 191--204.]] Bellare, M., Garay, J., and Rabin, T. 1998. Fast batch verification for modular exponentiation and digital signatures. In Proceedings of the Eurocrypt Conference, vol. 1403, 191--204.]]"},{"key":"e_1_2_1_2_1","volume-title":"Lecture Notes in Computer Science","volume":"2442","author":"Bellare M.","unstructured":"Bellare , M. and Palacio , A . 2002. Gq and Schnorr identification schemes: Proofs of security against impersonation under active and concurrent attacks. In Advances in Cryptology---CRYPTO, M. Yung, ed . Lecture Notes in Computer Science , vol. 2442 , Springer-Verlag, Berlin Germany, 162--177.]] Bellare, M. and Palacio, A. 2002. Gq and Schnorr identification schemes: Proofs of security against impersonation under active and concurrent attacks. In Advances in Cryptology---CRYPTO, M. Yung, ed. Lecture Notes in Computer Science, vol. 2442, Springer-Verlag, Berlin Germany, 162--177.]]"},{"key":"e_1_2_1_3_1","volume-title":"Proceedings of the 1st ACM Conference on Computer and Communications Security. 62--73","author":"Bellare M.","unstructured":"Bellare , M. and Rogaway , P . 1993. Random oracles are practical: A paradigm for designing efficient protocols . In Proceedings of the 1st ACM Conference on Computer and Communications Security. 62--73 .]] 10.1145\/168588.168596 Bellare, M. and Rogaway, P. 1993. Random oracles are practical: A paradigm for designing efficient protocols. In Proceedings of the 1st ACM Conference on Computer and Communications Security. 62--73.]] 10.1145\/168588.168596"},{"key":"e_1_2_1_4_1","doi-asserted-by":"crossref","unstructured":"Boneh D. Gentry C. Lynn B. and Shacham H. 2003. Aggregate and verifiably encrypted signatures from bilinear maps. In Advances in Cryptology---EUROCRYPT E. Biham ed. LNCS Springer-Verlag Berlin.]]  Boneh D. Gentry C. Lynn B. and Shacham H. 2003. Aggregate and verifiably encrypted signatures from bilinear maps. In Advances in Cryptology---EUROCRYPT E. Biham ed. LNCS Springer-Verlag Berlin.]]","DOI":"10.1007\/3-540-39200-9_26"},{"key":"e_1_2_1_5_1","doi-asserted-by":"crossref","unstructured":"Boyd C. and Pavlovski C. 2000. Attacking and repairing batch verification schemes. In Asiacrypt. 58--71.]]   Boyd C. and Pavlovski C. 2000. Attacking and repairing batch verification schemes. In Asiacrypt. 58--71.]]","DOI":"10.1007\/3-540-44448-3_5"},{"key":"e_1_2_1_6_1","volume-title":"Group signature schemes and paymen systems based on the discrete logarithm problem","author":"Camenisch J.","unstructured":"Camenisch , J. 1998. Group signature schemes and paymen systems based on the discrete logarithm problem , vol. 2 , ETH-Series in Information Security and Cryptography. Hartung-Gorre Verlag , Konstanz, Germany.]] Camenisch, J. 1998. Group signature schemes and paymen systems based on the discrete logarithm problem, vol. 2, ETH-Series in Information Security and Cryptography. Hartung-Gorre Verlag, Konstanz, Germany.]]"},{"key":"e_1_2_1_7_1","volume-title":"Advances in Cryptology---CRYPTO","volume":"1294","author":"Camenisch J.","unstructured":"Camenisch , J. and Stadler , M . 1997. Efficient group signature schemes for large groups . In Advances in Cryptology---CRYPTO , vol. 1294 , Springer-Verlag, Berlin Germany. 410--424.]] Camenisch, J. and Stadler, M. 1997. Efficient group signature schemes for large groups. In Advances in Cryptology---CRYPTO, vol. 1294, Springer-Verlag, Berlin Germany. 410--424.]]"},{"key":"e_1_2_1_8_1","volume-title":"Tech. Rep. TR CS0917, Technion","author":"Chor B.","year":"1997","unstructured":"Chor , B. , Gilboa , N. , and Naor , M . 1997 . Private information retrieval by keywords. Tech. Rep. TR CS0917, Technion , University .]] Chor, B., Gilboa, N., and Naor, M. 1997. Private information retrieval by keywords. Tech. Rep. TR CS0917, Technion, University.]]"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/293347.293350"},{"key":"e_1_2_1_10_1","volume-title":"Proceedings of the 14th IFIP 11.3 Working Conference in Database Security, 101--112","author":"Devanbu P.","unstructured":"Devanbu , P. , Gertz , M. , Martel , C. , and Stubblebine , S. G . 2000. Authentic third-party data publication . In Proceedings of the 14th IFIP 11.3 Working Conference in Database Security, 101--112 .]] Devanbu, P., Gertz, M., Martel, C., and Stubblebine, S. G. 2000. Authentic third-party data publication. In Proceedings of the 14th IFIP 11.3 Working Conference in Database Security, 101--112.]]"},{"key":"e_1_2_1_11_1","doi-asserted-by":"crossref","unstructured":"Fiat A.\n     and \n      Shamir A\n  . \n  1987\n  . How to prove yourself: practical solutions to identification and signature problems. In Advances in Cryptology---CRYPTO '86 A. M. Odlyzko ed Lecture Notes in Computer Science vol. \n  263 Springer-Verlag Berlin Germany Santa 186--194.]]   Fiat A. and Shamir A. 1987. How to prove yourself: practical solutions to identification and signature problems. In Advances in Cryptology---CRYPTO '86 A. M. Odlyzko ed Lecture Notes in Computer Science vol. 263 Springer-Verlag Berlin Germany Santa 186--194.]]","DOI":"10.1007\/3-540-47721-7_12"},{"key":"e_1_2_1_12_1","volume-title":"Batch RSA. In Advances in Cryptology---CRYPTO '89","volume":"435","author":"Fiat A.","year":"1990","unstructured":"Fiat , A. 1990 . Batch RSA. In Advances in Cryptology---CRYPTO '89 , G. Brassard, ed. Lecture Notes in Computer Science , vol. 435 , Springer-Verlag, Berlin Germany, 175--185.]] Fiat, A. 1990. Batch RSA. In Advances in Cryptology---CRYPTO '89, G. Brassard, ed. Lecture Notes in Computer Science, vol. 435, Springer-Verlag, Berlin Germany, 175--185.]]"},{"key":"e_1_2_1_13_1","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1007\/s001459900021","article-title":"Batch RSA","volume":"10","author":"Fiat A.","year":"1997","unstructured":"Fiat , A. 1997 . Batch RSA . J. Cryptology 10 , 2, 75 -- 88 .]] Fiat, A. 1997. Batch RSA. J. Cryptology 10, 2, 75--88.]]","journal-title":"J. Cryptology"},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of the 30th Annual Symposium on Theory of Computing (STOC)","author":"Gertner Y.","unstructured":"Gertner , Y. , Ishai , Y. , Kushilevitz , E. , and Malkin , T . 1998. Protecting data privacy in private information retrieval schemes . In Proceedings of the 30th Annual Symposium on Theory of Computing (STOC) ( Dallas, TX).]] 10.1145\/276698.276723 Gertner, Y., Ishai, Y., Kushilevitz, E., and Malkin, T. 1998. Protecting data privacy in private information retrieval schemes. In Proceedings of the 30th Annual Symposium on Theory of Computing (STOC) (Dallas, TX).]] 10.1145\/276698.276723"},{"key":"e_1_2_1_15_1","unstructured":"Goh E.-J. 2003. Secure indexes for efficient searching on encrypted compressed data. Cryptology ePrint Archive Rep. 2003\/216 http:\/\/eprint.iacr.org\/2003\/216\/]]  Goh E.-J. 2003. Secure indexes for efficient searching on encrypted compressed data. Cryptology ePrint Archive Rep. 2003\/216 http:\/\/eprint.iacr.org\/2003\/216\/]]"},{"key":"e_1_2_1_16_1","volume-title":"Lecture Notes in Computer Science","volume":"403","author":"Guillou L.","unstructured":"Guillou , L. and Quisquater , J. J. 1988. A \u201cparadoxical\u201d identity-based signature scheme resulting from zero-knowledge. In Advances in Cryptology---CRYPTO, S. Goldwasser, ed . Lecture Notes in Computer Science , vol. 403 , Springer-Verlag, Berlin Germany.]] Guillou, L. and Quisquater, J. J. 1988. A \u201cparadoxical\u201d identity-based signature scheme resulting from zero-knowledge. In Advances in Cryptology---CRYPTO, S. Goldwasser, ed. Lecture Notes in Computer Science, vol. 403, Springer-Verlag, Berlin Germany.]]"},{"key":"e_1_2_1_17_1","volume-title":"Proceedings of the ACM SIGMOD Conference on Management of Data, 216--227","author":"Hacig\u00fcm\u00fc\u015f H.","unstructured":"Hacig\u00fcm\u00fc\u015f , H. , Iyer , B. , Li , C. , and Mehrotra , S . 2002. Executing SQL over encrypted data in the database-service-provider model . In Proceedings of the ACM SIGMOD Conference on Management of Data, 216--227 .]] 10.1145\/564691.564717 Hacig\u00fcm\u00fc\u015f, H., Iyer, B., Li, C., and Mehrotra, S. 2002. Executing SQL over encrypted data in the database-service-provider model. In Proceedings of the ACM SIGMOD Conference on Management of Data, 216--227.]] 10.1145\/564691.564717"},{"key":"e_1_2_1_18_1","volume-title":"Proceedings of the International Workshop on Certification and Security in E-Services (CSES IFIP WCC).]]","author":"Hacig\u00fcm\u00fc\u015f H.","unstructured":"Hacig\u00fcm\u00fc\u015f , H. , Iyer , B. , and Mehrotra , S . 2002a. Encrypted database integrity in database service provider model . In Proceedings of the International Workshop on Certification and Security in E-Services (CSES IFIP WCC).]] Hacig\u00fcm\u00fc\u015f, H., Iyer, B., and Mehrotra, S. 2002a. Encrypted database integrity in database service provider model. In Proceedings of the International Workshop on Certification and Security in E-Services (CSES IFIP WCC).]]"},{"key":"e_1_2_1_19_1","volume-title":"Proceedings of the International Conference on Data Engineering.]]","author":"Hacig\u00fcm\u00fc\u015f H.","unstructured":"Hacig\u00fcm\u00fc\u015f , H. , Iyer , B. , and Mehrotra , S . 2002b. Providing database as a service . In Proceedings of the International Conference on Data Engineering.]] Hacig\u00fcm\u00fc\u015f, H., Iyer, B., and Mehrotra, S. 2002b. Providing database as a service. In Proceedings of the International Conference on Data Engineering.]]"},{"key":"e_1_2_1_20_1","doi-asserted-by":"crossref","first-page":"4","DOI":"10.1049\/el:19950203","article-title":"DSA-Type secure interactive batch verification protocols","volume":"31","author":"Harn L.","year":"1995","unstructured":"Harn , L. 1995 . DSA-Type secure interactive batch verification protocols . Electron. Lett. 31 , 4 (Feb.), 257--258.]] Harn, L. 1995. DSA-Type secure interactive batch verification protocols. Electron. Lett. 31, 4 (Feb.), 257--258.]]","journal-title":"Electron. Lett."},{"key":"e_1_2_1_21_1","first-page":"9","article-title":"Batch verifying multiple DSA-Type digital signatures","volume":"34","author":"Harn L.","year":"1998","unstructured":"Harn , L. 1998 a. Batch verifying multiple DSA-Type digital signatures . Electron. Lett. 34 , 9 (Apr.), 870--871.]] Harn, L. 1998a. Batch verifying multiple DSA-Type digital signatures. Electron. Lett. 34, 9 (Apr.), 870--871.]]","journal-title":"Electron. Lett."},{"key":"e_1_2_1_22_1","first-page":"12","article-title":"Batch verifying RSA signatures","volume":"34","author":"Harn L.","year":"1998","unstructured":"Harn , L. 1998 b. Batch verifying RSA signatures . Electron. Lett. 34 , 12 (Apr.), 1219--1220.]] Harn, L. 1998b. Batch verifying RSA signatures. Electron. Lett. 34, 12 (Apr.), 1219--1220.]]","journal-title":"Electron. Lett."},{"key":"e_1_2_1_23_1","unstructured":"Joux A. and Nguyen K. 2001. Separating decision Diffie-Hellman from Diffie-Hellman in cryptographic groups. In Cryptology ePrint Archive. Number Rep. 2001\/003.]]  Joux A. and Nguyen K. 2001. Separating decision Diffie-Hellman from Diffie-Hellman in cryptographic groups. In Cryptology ePrint Archive. Number Rep. 2001\/003.]]"},{"key":"e_1_2_1_24_1","unstructured":"Law P. 1996. The health insurance portability and accountability act of 1996 (HIPAA). http:\/\/www.cms.hhs.gov\/hipaa\/]]  Law P. 1996. The health insurance portability and accountability act of 1996 (HIPAA). http:\/\/www.cms.hhs.gov\/hipaa\/]]"},{"key":"e_1_2_1_25_1","unstructured":"Menezes A. J. Van Oorschot P. C. and Vanstone S. A. 1997. Handbook of Applied Cryptography. CRC Press.]]   Menezes A. J. Van Oorschot P. C. and Vanstone S. A. 1997. Handbook of Applied Cryptography. CRC Press.]]"},{"key":"e_1_2_1_26_1","volume-title":"Proceedings of the IEEE Symposium on Research in Security and Privacy.]]","author":"Merkle R.","year":"1980","unstructured":"Merkle , R. 1980 . Protocols for public key cryptosystems . In Proceedings of the IEEE Symposium on Research in Security and Privacy.]] Merkle, R. 1980. Protocols for public key cryptosystems. In Proceedings of the IEEE Symposium on Research in Security and Privacy.]]"},{"key":"e_1_2_1_27_1","unstructured":"Miracl Library. 2006 http:\/\/indigo.ie\/~mscott]]  Miracl Library. 2006 http:\/\/indigo.ie\/~mscott]]"},{"key":"e_1_2_1_28_1","volume-title":"Proceedings of the Symposium on Network and Distributed Systems Security (NDSS).]]","author":"Mykletun E.","unstructured":"Mykletun , E. , Narasimha , M. , and Tsudik , G . 2004a. Authentication and integrity in outsourced databases . In Proceedings of the Symposium on Network and Distributed Systems Security (NDSS).]] Mykletun, E., Narasimha, M., and Tsudik, G. 2004a. Authentication and integrity in outsourced databases. In Proceedings of the Symposium on Network and Distributed Systems Security (NDSS).]]"},{"key":"e_1_2_1_29_1","volume-title":"Proceedings of the European Symposium on Research in Computer Security (ESORICS).]]","author":"Mykletun E.","unstructured":"Mykletun E. , Narasimha M. , and Tsudik G . 2004b. Signature 'Bouquets': Immutability of Aggregated Signatures , In Proceedings of the European Symposium on Research in Computer Security (ESORICS).]] Mykletun E., Narasimha M., and Tsudik G. 2004b. Signature 'Bouquets': Immutability of Aggregated Signatures, In Proceedings of the European Symposium on Research in Computer Security (ESORICS).]]"},{"key":"e_1_2_1_30_1","doi-asserted-by":"crossref","unstructured":"Naccache D. M'Ra\u00efhi D. Raphaeli D. and \n      Vaudenay S\n  . \n  1994\n  . Can DSA be improved: Complexity trade-offs with the digital signature standard. In Advances in Cryptology---EUROCRYPT Lecture Notes in Computer Science Springer-Verlag Berlin Germany 85--94.]]  Naccache D. M'Ra\u00efhi D. Raphaeli D. and Vaudenay S. 1994. Can DSA be improved: Complexity trade-offs with the digital signature standard. In Advances in Cryptology---EUROCRYPT Lecture Notes in Computer Science Springer-Verlag Berlin Germany 85--94.]]","DOI":"10.1007\/BFb0053426"},{"key":"e_1_2_1_31_1","volume-title":"Proceedings of the ACM Conference on Information and Knowledge Management.]] 10","author":"Narasimha M.","unstructured":"Narasimha , M. and Tsudik , G . 2005. DSAC: Integrity of outsourced databases with signature aggregation and chaining . In Proceedings of the ACM Conference on Information and Knowledge Management.]] 10 .1145\/1099554.1099604 Narasimha, M. and Tsudik, G. 2005. DSAC: Integrity of outsourced databases with signature aggregation and chaining. In Proceedings of the ACM Conference on Information and Knowledge Management.]] 10.1145\/1099554.1099604"},{"key":"e_1_2_1_32_1","unstructured":"OpenSSL Project. 2006. http:\/\/www.openssl.org]]  OpenSSL Project. 2006. http:\/\/www.openssl.org]]"},{"key":"e_1_2_1_33_1","volume-title":"Proceedings of the International Conference on Data Engineering, 560--571","author":"Pang H.","unstructured":"Pang , H. and Tan , K . -L. 2004. Authenticating query results in edge computing . In Proceedings of the International Conference on Data Engineering, 560--571 .]] Pang, H. and Tan, K.-L. 2004. Authenticating query results in edge computing. In Proceedings of the International Conference on Data Engineering, 560--571.]]"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/359340.359342"},{"key":"e_1_2_1_35_1","volume-title":"Proceedings of the IEEE Symposium on Security and Privacy.]]","author":"Song D.","unstructured":"Song , D. , Wagner , D. , and Perrig , A . 2000. Practical techniques for searches on encrypted data . In Proceedings of the IEEE Symposium on Security and Privacy.]] Song, D., Wagner, D., and Perrig, A. 2000. Practical techniques for searches on encrypted data. In Proceedings of the IEEE Symposium on Security and Privacy.]]"},{"key":"e_1_2_1_36_1","volume-title":"Sarbanes-Oxley act of","author":"United States Code. 2002.","year":"2002","unstructured":"United States Code. 2002. Sarbanes-Oxley act of 2002 , HR 3763, PL 107-204, 116 Stat 745. Codified in sections 11, 15, 18, 28, and 29 USC. ]] United States Code. 2002. Sarbanes-Oxley act of 2002, HR 3763, PL 107-204, 116 Stat 745. Codified in sections 11, 15, 18, 28, and 29 USC.]]"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/12.392857"}],"container-title":["ACM Transactions on Storage"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1149976.1149977","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1149976.1149977","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T16:08:27Z","timestamp":1750262907000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1149976.1149977"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,5]]},"references-count":37,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2006,5]]}},"alternative-id":["10.1145\/1149976.1149977"],"URL":"https:\/\/doi.org\/10.1145\/1149976.1149977","relation":{},"ISSN":["1553-3077","1553-3093"],"issn-type":[{"value":"1553-3077","type":"print"},{"value":"1553-3093","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006,5]]},"assertion":[{"value":"2006-05-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}