{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T12:08:15Z","timestamp":1763467695311,"version":"3.41.0"},"reference-count":29,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2005,2,1]],"date-time":"2005-02-01T00:00:00Z","timestamp":1107216000000},"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. Inf. Syst. Secur."],"published-print":{"date-parts":[[2005,2]]},"abstract":"<jats:p>The scope and character of today's computing environments are progressively shifting from traditional, one-on-one client-server interaction to the new cooperative paradigm. It then becomes of primary importance to provide means of protecting the secrecy of the information, while guaranteeing its availability to legitimate clients. Operating online querying services securely on open networks is very difficult; therefore many enterprises outsource their data center operations to external application service providers. A promising direction toward prevention of unauthorized access to outsourced data is represented by encryption. However, data encryption is often supported for the sole purpose of protecting the data in storage while allowing access to plaintext values by the server, which decrypts data for query execution. In this paper, we present a simple yet robust single-server solution for remote querying of encrypted databases on external servers. Our approach is based on the use of indexing information attached to the encrypted database, which can be used by the server to select the data to be returned in response to a query without the need of accessing the plaintext database content. Our indexes balance the trade-off between efficiency requirements in query execution and protection requirements due to possible inference attacks exploiting indexing information. We investigate quantitative measures to model inference exposure and provide some related experimental results.<\/jats:p>","DOI":"10.1145\/1053283.1053289","type":"journal-article","created":{"date-parts":[[2005,8,3]],"date-time":"2005-08-03T08:30:55Z","timestamp":1123057855000},"page":"119-152","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":99,"title":["Modeling and assessing inference exposure in encrypted databases"],"prefix":"10.1145","volume":"8","author":[{"given":"Alberto","family":"Ceselli","sequence":"first","affiliation":[{"name":"Universit\u00e0 di Milano, Crema, Italy"}]},{"given":"Ernesto","family":"Damiani","sequence":"additional","affiliation":[{"name":"Universit\u00e0 di Milano, Crema, Italy"}]},{"given":"Sabrina De Capitani Di","family":"Vimercati","sequence":"additional","affiliation":[{"name":"Universit\u00e0 di Milano, Crema, Italy"}]},{"given":"Sushil","family":"Jajodia","sequence":"additional","affiliation":[{"name":"George Mason University, Fairfax, VA"}]},{"given":"Stefano","family":"Paraboschi","sequence":"additional","affiliation":[{"name":"Universit\u00e0 di Bergamo, Dalmine---Italy"}]},{"given":"Pierangela","family":"Samarati","sequence":"additional","affiliation":[{"name":"Universit\u00e0 di Milano, Crema, Italy"}]}],"member":"320","published-online":{"date-parts":[[2005,2]]},"reference":[{"volume-title":"Proceedings of the ACM SIGMOD 2004 Conference","author":"Agrawal R.","key":"e_1_2_1_1_1","unstructured":"Agrawal , R. , Kiernan , J. , Srikant , R. , and Xu , Y . 2004. Order-preserving encryption for numeric data . In Proceedings of the ACM SIGMOD 2004 Conference , Paris, France. ACM Press, New York. 10.1145\/1007568.1007632 Agrawal, R., Kiernan, J., Srikant, R., and Xu, Y. 2004. Order-preserving encryption for numeric data. In Proceedings of the ACM SIGMOD 2004 Conference, Paris, France. ACM Press, New York. 10.1145\/1007568.1007632"},{"volume-title":"Proceedings of the 28th International Conference on Very Large Data Bases","author":"Bouganim L.","key":"e_1_2_1_2_1","unstructured":"Bouganim , L. and Pucheral , P . 2002. Chip-secured data access: Confidential data on untrusted servers . In Proceedings of the 28th International Conference on Very Large Data Bases , Hong Kong, China. Morgan Kaufmann, San Mateo, CA, 131--142. Bouganim, L. and Pucheral, P. 2002. Chip-secured data access: Confidential data on untrusted servers. In Proceedings of the 28th International Conference on Very Large Data Bases, Hong Kong, China. Morgan Kaufmann, San Mateo, CA, 131--142."},{"volume-title":"Proceedings of the 11th European Conference on Information Systems (ECIS '03)","author":"Boyens C.","key":"e_1_2_1_3_1","unstructured":"Boyens , C. and G\u00fcnter , O . 2003. Using online services in untrusted environments---a privacy-preserving architecture . In Proceedings of the 11th European Conference on Information Systems (ECIS '03) , Naples, Italy. Boyens, C. and G\u00fcnter, O. 2003. Using online services in untrusted environments---a privacy-preserving architecture. In Proceedings of the 11th European Conference on Information Systems (ECIS '03), Naples, Italy."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(00)00010-7"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1022584312032"},{"volume-title":"Proceedings of the 10th International Conference on Image Analysis and Processing","author":"Cordella L.","key":"e_1_2_1_6_1","unstructured":"Cordella , L. , Foggia , P. , Sansone , C. , and Vento , M . 1999. Performance evaluation of the VF graph matching algorithm . In Proceedings of the 10th International Conference on Image Analysis and Processing , Venice, Italy. IEEE Computer Society Press, Los Alamitos, CA. Cordella, L., Foggia, P., Sansone, C., and Vento, M. 1999. Performance evaluation of the VF graph matching algorithm. In Proceedings of the 10th International Conference on Image Analysis and Processing, Venice, Italy. IEEE Computer Society Press, Los Alamitos, CA."},{"volume-title":"Proceedings of the 3rd IAPR TC-15 Workshop on Graph-Based Representations in Pattern Recognition","author":"Cordella L.","key":"e_1_2_1_7_1","unstructured":"Cordella , L. , Foggia , P. , Sansone , C. , and Vento , M . 2001. An improved algorithm for matching large graphs . In Proceedings of the 3rd IAPR TC-15 Workshop on Graph-Based Representations in Pattern Recognition , Ischia, Italy, J. Jolion, W. Kropatsch, and M. Vento, Eds. 149--159. Cordella, L., Foggia, P., Sansone, C., and Vento, M. 2001. An improved algorithm for matching large graphs. In Proceedings of the 3rd IAPR TC-15 Workshop on Graph-Based Representations in Pattern Recognition, Ischia, Italy, J. Jolion, W. Kropatsch, and M. Vento, Eds. 149--159."},{"volume-title":"Proceedings of the 10th ACM Conference on Computer and Communications Security","author":"Damiani E.","key":"e_1_2_1_8_1","unstructured":"Damiani , E. , De Capitani di Vimercati, S., Jajodia , S. , Paraboschi , S. , and Samarati , P . 2003. Balancing confidentiality and efficiency in untrusted relational dbmss . In Proceedings of the 10th ACM Conference on Computer and Communications Security , Washington, DC. ACM Press, New York. 10.1145\/948109.948124 Damiani, E., De Capitani di Vimercati, S., Jajodia, S., Paraboschi, S., and Samarati, P. 2003. Balancing confidentiality and efficiency in untrusted relational dbmss. In Proceedings of the 10th ACM Conference on Computer and Communications Security, Washington, DC. ACM Press, New York. 10.1145\/948109.948124"},{"key":"e_1_2_1_9_1","volume-title":"S., Paraboschi, S.","author":"Damiani E.","year":"2004","unstructured":"Damiani , E. , De Capitani di Vimercati , S., Paraboschi, S. , and Samarati, P. 2004 . Computing range queries on obfuscated data. In Proceedings of the Information Processing and Management of Uncertainty in Knowledge-Based Systems, Perugia, Italy . Damiani, E., De Capitani di Vimercati, S., Paraboschi, S., and Samarati, P. 2004. Computing range queries on obfuscated data. In Proceedings of the Information Processing and Management of Uncertainty in Knowledge-Based Systems, Perugia, Italy."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/319566.319580"},{"volume-title":"Cryptography and Data Security","author":"Denning D.","key":"e_1_2_1_11_1","unstructured":"Denning , D. 1982. Cryptography and Data Security . Addison-Wesley , Reading, MA . Denning, D. 1982. Cryptography and Data Security. Addison-Wesley, Reading, MA."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(96)00170-6"},{"key":"e_1_2_1_13_1","unstructured":"Domingo-Ferrer J. and Herrera-Joanconmart\u00ed J. 1998. A privacy homomorphism allowing field operations on encrypted data. Jornades de Matem\u00e0tica Discreta i Algor\u00edsmica.  Domingo-Ferrer J. and Herrera-Joanconmart\u00ed J. 1998. A privacy homomorphism allowing field operations on encrypted data. Jornades de Matem\u00e0tica Discreta i Algor\u00edsmica."},{"key":"e_1_2_1_14_1","unstructured":"Foggia P. 2001. The vflib graph matching library version 2.0. http:\/\/amalfi.dis.unina.it\/graph\/db\/vflib-2.0\/doc\/vflib.html.  Foggia P. 2001. The vflib graph matching library version 2.0. http:\/\/amalfi.dis.unina.it\/graph\/db\/vflib-2.0\/doc\/vflib.html."},{"key":"e_1_2_1_15_1","unstructured":"Garey M. and Johnson D. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman New York.   Garey M. and Johnson D. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman New York."},{"volume-title":"Proceedings of the ACM SIGMOD'2002","author":"Hacig\u00fcm\u00fcs H.","key":"e_1_2_1_16_1","unstructured":"Hacig\u00fcm\u00fcs , H. , Iyer , B. , Li , C. , and Mehrotra , S . 2002a. Executing SQL over encrypted data in the database-service-provider model . In Proceedings of the ACM SIGMOD'2002 , Madison, WI. ACM Press, New York. 10.1145\/564691.564717 Hacig\u00fcm\u00fcs, H., Iyer, B., Li, C., and Mehrotra, S. 2002a. Executing SQL over encrypted data in the database-service-provider model. In Proceedings of the ACM SIGMOD'2002, Madison, WI. ACM Press, New York. 10.1145\/564691.564717"},{"volume-title":"Proceedings of the 18th International Conference on Data Engineering","author":"Hacig\u00fcm\u00fcs H.","key":"e_1_2_1_17_1","unstructured":"Hacig\u00fcm\u00fcs , H. , Iyer , B. , and Mehrotra , S . 2002b. Providing database as a service . In Proceedings of the 18th International Conference on Data Engineering , San Jose, CA. IEEE Computer Society Press, Los Alamitos, CA. Hacig\u00fcm\u00fcs, H., Iyer, B., and Mehrotra, S. 2002b. Providing database as a service. In Proceedings of the 18th International Conference on Data Engineering, San Jose, CA. IEEE Computer Society Press, Los Alamitos, CA."},{"volume-title":"Proceedings of the 9th International Conference on Database Systems for Advanced Applications. Springer","author":"Hacig\u00fcm\u00fcs H.","key":"e_1_2_1_18_1","unstructured":"Hacig\u00fcm\u00fcs , H. , Iyer , B. , and Mehrotra , S . 2004. Efficient execution of aggregation queries over encrypted relational databases . In Proceedings of the 9th International Conference on Database Systems for Advanced Applications. Springer , Jeju Island, Korea. Hacig\u00fcm\u00fcs, H., Iyer, B., and Mehrotra, S. 2004. Efficient execution of aggregation queries over encrypted relational databases. In Proceedings of the 9th International Conference on Database Systems for Advanced Applications. Springer, Jeju Island, Korea."},{"volume-title":"Proceedings of the 18th Annual IFIP WG 11.3 Working Conference on Data and Applications Security","author":"Hacig\u00fcm\u00fcs H.","key":"e_1_2_1_19_1","unstructured":"Hacig\u00fcm\u00fcs , H. and Mehrotra , S . 2004. Performance-conscious key management in encrypted databases . In Proceedings of the 18th Annual IFIP WG 11.3 Working Conference on Data and Applications Security , Sitges, Catalonia, Spain. Kluwer Academic Publishers, Dordrecht. Hacig\u00fcm\u00fcs, H. and Mehrotra, S. 2004. Performance-conscious key management in encrypted databases. In Proceedings of the 18th Annual IFIP WG 11.3 Working Conference on Data and Applications Security, Sitges, Catalonia, Spain. Kluwer Academic Publishers, Dordrecht."},{"key":"e_1_2_1_20_1","volume-title":"Proceedings of the 9th Workshop on ACM SIGOPS European Workshop: Beyond the PC. New Challenges for the Operating System","author":"Jensen C.","year":"2000","unstructured":"Jensen , C. 2000 . Cryptocache: a secure sharable file cache for roaming users . In Proceedings of the 9th Workshop on ACM SIGOPS European Workshop: Beyond the PC. New Challenges for the Operating System , Kolding, Denmark. 73--78. 10.1145\/566726.566744 Jensen, C. 2000. Cryptocache: a secure sharable file cache for roaming users. In Proceedings of the 9th Workshop on ACM SIGOPS European Workshop: Beyond the PC. New Challenges for the Operating System, Kolding, Denmark. 73--78. 10.1145\/566726.566744"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/65943.65946"},{"key":"e_1_2_1_22_1","volume-title":"Congressus Numerantium 30","author":"McKay B.","year":"1981","unstructured":"McKay , B. 1981 . Practical graph isomorphism . Congressus Numerantium 30 , 45--87. McKay, B. 1981. Practical graph isomorphism. Congressus Numerantium 30, 45--87."},{"key":"e_1_2_1_24_1","unstructured":"Rivest R. Adleman L. and Dertouzos M. 1978. Data banks and privacy homomorphisms. In Foundations of Secure Computation. Academic Press Orlando FL. 169--179.  Rivest R. Adleman L. and Dertouzos M. 1978. Data banks and privacy homomorphisms. In Foundations of Secure Computation. Academic Press Orlando FL. 169--179."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/69.971193"},{"volume-title":"Proceedings of the 2000 IEEE Symposium on Security and Privacy","author":"Song D.","key":"e_1_2_1_26_1","unstructured":"Song , D. , Wagner , D. , and Perrig , A . 2000. Practical techniques for searches on encrypted data . In Proceedings of the 2000 IEEE Symposium on Security and Privacy , Oakland, CA. IEEE Computer Society Press, Los Alamitos, CA. 44--55. Song, D., Wagner, D., and Perrig, A. 2000. Practical techniques for searches on encrypted data. In Proceedings of the 2000 IEEE Symposium on Security and Privacy, Oakland, CA. IEEE Computer Society Press, Los Alamitos, CA. 44--55."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/321921.321925"},{"key":"e_1_2_1_28_1","volume-title":"Proceedings of the 30th Annual ACM SIGUCCS Conference on User Services","author":"Walton J.","year":"2002","unstructured":"Walton , J. 2002 . Developing an enterprise information security policy . In Proceedings of the 30th Annual ACM SIGUCCS Conference on User Services , Providence, RI. ACM Press, New York. 10.1145\/588646.588678 Walton, J. 2002. Developing an enterprise information security policy. In Proceedings of the 30th Annual ACM SIGUCCS Conference on User Services, Providence, RI. ACM Press, New York. 10.1145\/588646.588678"},{"key":"e_1_2_1_29_1","volume-title":"Proceedings of the Conference on File and Storage Technologies (FAST","author":"Ward J.","year":"2002","unstructured":"Ward , J. , O'Sullivan , M. , Shahoumian , T. , and Wilkes , J . 2002. Appia: Automatic storage area network fabric design . In Proceedings of the Conference on File and Storage Technologies (FAST 2002 ). The USENIX Association, Monterey, CA. Ward, J., O'Sullivan, M., Shahoumian, T., and Wilkes, J. 2002. Appia: Automatic storage area network fabric design. In Proceedings of the Conference on File and Storage Technologies (FAST 2002). The USENIX Association, Monterey, CA."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.2307\/2371086"}],"container-title":["ACM Transactions on Information and System Security"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1053283.1053289","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1053283.1053289","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T22:43:28Z","timestamp":1750286608000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1053283.1053289"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,2]]},"references-count":29,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2005,2]]}},"alternative-id":["10.1145\/1053283.1053289"],"URL":"https:\/\/doi.org\/10.1145\/1053283.1053289","relation":{},"ISSN":["1094-9224","1557-7406"],"issn-type":[{"type":"print","value":"1094-9224"},{"type":"electronic","value":"1557-7406"}],"subject":[],"published":{"date-parts":[[2005,2]]},"assertion":[{"value":"2005-02-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}