Alberto Ceselli
Ernesto Damiani
Sushil Jajodia
Stefano Paraboschi
Abstract
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.
- 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. Google Scholar
- 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. Google Scholar
- Boyens, C. and Günter, 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.Google Scholar
- Caprara, A., Kellerer, H., and Pferschy, U. 2000. A ptas for the multiple subset sum problem with different knapsack capacities. Inf. Process. Lett. 73, 111--118. Google ScholarDigital Library
- Caprara, A., Kellerer, H., and Pferschy, U. 2003. A 3/4-approximation algorithm for multiple subset sum. J. Heuristics 9, 99--111. Google ScholarCross Ref
- 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. Google Scholar
- 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.Google Scholar
- 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. Google Scholar
- 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.Google Scholar
- Davida, G., Wells, D., and Kam, J. 1981. A database encryption system with subkeys. ACM Trans. Database Syst. 6, 2 (June), 312--328. Google ScholarDigital Library
- Denning, D. 1982. Cryptography and Data Security. Addison-Wesley, Reading, MA. Google Scholar
- Domingo-Ferrer, J. 1996. A new privacy homomorphism and applications. Inf. Process. Lett. 60, 5 (Dec.), 277--282. Google Scholar
- Domingo-Ferrer, J. and Herrera-Joanconmartí, J. 1998. A privacy homomorphism allowing field operations on encrypted data. Jornades de Matemàtica Discreta i Algorísmica.Google Scholar
- Foggia, P. 2001. The vflib graph matching library, version 2.0. http://amalfi.dis.unina.it/graph/db/vflib-2.0/doc/vflib.html.Google Scholar
- Garey, M. and Johnson, D. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, New York. Google Scholar
- Hacigümüs, 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. Google Scholar
- Hacigümüs, 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. Google Scholar
- Hacigümüs, 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.Google Scholar
- Hacigümüs, 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.Google Scholar
- 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. Google Scholar
- Klein, S., Bookstein, A., and Deerwester, S. 1989. Storing text retrieval systems on CD-ROM: compression and encryption considerations. ACM Trans. Inf. Syst. 7, 3 (July), 230--245. Google ScholarDigital Library
- McKay, B. 1981. Practical graph isomorphism. Congressus Numerantium 30, 45--87.Google Scholar
- Pisinger, D. 1995. Algorithms for knapsack problems. Ph.D. thesis, DIKU, University of Copenhagen, Copenhagen, Denmark. Report 95/1.Google Scholar
- Rivest, R., Adleman, L., and Dertouzos, M. 1978. Data banks and privacy homomorphisms. In Foundations of Secure Computation. Academic Press, Orlando, FL. 169--179.Google Scholar
- Samarati, P. 2001. Protecting respondent's privacy in microdata release. IEEE Trans. Knowledge Data Eng. 13, 6 (Nov./Dec.), 1010--1017. Google ScholarDigital Library
- 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. Google Scholar
- Ullman, J. 1976. An algorithm for subgraph isomorphism. J. ACM 23, 31--42. Google ScholarDigital Library
- 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. Google Scholar
- 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. Google Scholar
- Whitney, H. 1932. Congruent graphs and the connectivity of graphs. Am. J. Math. 54, 150--168.Google ScholarCross Ref
Index Terms
- Modeling and assessing inference exposure in encrypted databases
Recommendations
Balancing confidentiality and efficiency in untrusted relational DBMSs
CCS '03: Proceedings of the 10th ACM conference on Computer and communications securityThe 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 ...
Practical verifiably encrypted signature based on Waters signatures
Waters proposed the first efficient signature scheme that is known to be existentially unforgeable based on the standard computational Diffie‐Hellman assumption without random oracles. Lu et al. then proposed the first verifiably encrypted signature (VES) ...
Public-Key encryption from ID-Based encryption without one-time signature
OTM'06: Proceedings of the 2006 international conference on On the Move to Meaningful Internet Systems: AWeSOMe, CAMS, COMINF, IS, KSinBIT, MIOS-CIAO, MONET - Volume Part IDesign a secure public key encryption scheme and its security proof are one of the main interests in cryptography In 2004, Canetti, Halevi and Katz [8] constructed a public key encryption (PKE) from a selective identity-based encryption scheme with a ...
Comments