Key management for multi-user encrypted databases

ABSTRACT

Database outsourcing is becoming increasingly popular introducing a new paradigm, called database-as-a-service (DAS), where an organization's database is stored at an external service provider. In such a scenario, access control is a very important issue, especially if the data owner wishes to publish her data for external use.In this paper, we first present our approach for the implementation of access control through selective encryption. The focus of the paper is then the presentation of the experimental results, which demonstrate the applicability of our proposal.

REFERENCES

• 1: Rakesh Agrawal , Jerry Kiernan , Ramakrishnan Srikant , Yirong Xu, Order preserving encryption for numeric data, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007632]
• 2: Selim G. Akl , Peter D. Taylor, Cryptographic solution to a problem of access control in a hierarchy, ACM Transactions on Computer Systems (TOCS), v.1 n.3, p.239-248, August 1983 [doi>10.1145/357369.357372]
• 3: D. Boneh, G. D. Crescenzo, R. Ostrovsky, and G. Persiano. Public-key encryption with keyword search. In Proc. of Eurocrypt 2004, Interlaken, Switzerland, May 2004.
• 4: Dan Boneh , Matthew K. Franklin, Identity-Based Encryption from the Weil Pairing, Proceedings of the 21st Annual International Cryptology Conference on Advances in Cryptology, p.213-229, August 19-23, 2001
• 5: C. Boyens and O. Gunter. Using online services in untrusted environments - a privacy-preserving architecture. In Proc. of the 11th European Conference on Information Systems (ECIS '03), Naples, Italy, June 2003.
• 6: R. Brinkman, J. Doumen, and W. Jonker. Using secret sharing for searching in encrypted data. In Proc. of the Secure Data Management Workshop, Toronto, Canada, August 2004.
• 7: Alberto Ceselli , Ernesto Damiani , Sabrina De Capitani Di Vimercati , Sushil Jajodia , Stefano Paraboschi , Pierangela Samarati, Modeling and assessing inference exposure in encrypted databases, ACM Transactions on Information and System Security (TISSEC), v.8 n.1, p.119-152, February 2005 [doi>10.1145/1053283.1053289]
• 8: Implementation of a Storage Mechanism for Untrusted DBMSs, Proceedings of the Second IEEE International Security in Storage Workshop, p.38, October 31-31, 2003
• 9: E. Damiani, S. De Capitani di Vimercati, S. Foresti, S. Jajodia, S. Paraboschi, and P. Samarati. Metadata management in outsourced encrypted databases. In Proc. of the 2nd VLDB Workshop on Secure Data Management (SDM'05), Trondheim, Norway, September 2005.
• 10: E. Damiani, S. De Capitani di Vimercati, S. Foresti, S. Jajodia, S. Paraboschi, and P. Samarati. Selective release of information in outsourced encrypted databases. Technical report, University of Milan, 2005.
• 11: Ernesto Damiani , S. De Capitani Vimercati , Sushil Jajodia , Stefano Paraboschi , Pierangela Samarati, Balancing confidentiality and efficiency in untrusted relational DBMSs, Proceedings of the 10th ACM conference on Computer and communications security, October 27-30, 2003, Washington D.C., USA [doi>10.1145/948109.948124]
• 12: George I. Davida , David L. Wells , John B. Kam, A database encryption system with subkeys, ACM Transactions on Database Systems (TODS), v.6 n.2, p.312-328, June 1981 [doi>10.1145/319566.319580]
• 13: E. Goh. Secure indexes. http://eprint.iacr.org/2003/216/.
• 14: Providing Database as a Service, Proceedings of the 18th International Conference on Data Engineering, p.29, February 26-March 01, 2002
• 15: H. Hacigümüs, B. Iyer, and S. Mehrotra. Ensuring the integrity of encrypted databases in the database-as-a-service model. In DBSec, pages 61--74, 2003.
• 16: H. Hacigümüs, B. Iyer, and S. Mehrotra. Efficient execution of aggregation queries over encrypted relational databases. In Proc. of the 9th International Conference on Database Systems for Advanced Applications, Jeju Island, Korea, March 2004.
• 17: Hakan Hacigümüş , Bala Iyer , Chen Li , Sharad Mehrotra, Executing SQL over encrypted data in the database-service-provider model, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564717]
• 18: H. Hacigümüs and S. Mehrotra. Performance-conscious key management in encrypted databases. In DBSec, pages 95--109, 2004.
• 19: L. Harn , H.-Y. Lin, A cryptographic key generation scheme for multilevel data security, Computers and Security, v.9 n.6, p.539-546, Oct. 1990 [doi>10.1016/0167-4048(90)90132-D]
• 20: B. Hore, S. Mehrotra, and G. Tsudik. A privacy-preserving index for range queries. In Proc. of the 30th VLDB Conference, Toronto, Canada, 2004.
• 21: Min-Shiang Hwang , Wei-Pang Yang, Controlling access in large partially ordered hierarchies using cryptographic keys, Journal of Systems and Software, v.67 n.2, p.99-107, 15 August 2003 [doi>10.1016/S0164-1212(02)00091-2]
• 22: Stephen J. MacKinnon , Peter D. Taylor , Henk Meijer , Selim G. Akl, An optimal algorithm for assigning cryptographic keys to control access in a hierarchy, IEEE Transactions on Computers, v.34 n.9, p.797-802, Sept. 1985 [doi>10.1109/TC.1985.1676635]
• 23: E. Mykletun, M. Narasimha, and G. Tsudik. Authentication and integrity in outsourced database. In Proc. of the 11th Annual Network and Distributed System Security Symposium, San Diego, CA, USA, February 2004.
• 24: Ravinderpal S. Sandhu, Cryptographic implementation of a tree hierarchy for access control, Information Processing Letters, v.27 n.2, p.95-98, February 29, 1988 [doi>10.1016/0020-0190(88)90099-3]
• 25: B. R. Waters, D. Balfanz, G. Durfee, and D. K. Smetters. Building an encrypted and searchable audit log. In Proc. of the 11th Annual Network and Distributed System Security Symposium, San Diego, CA, February 2004.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.1 Logical Design

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.7 Database Administration

General Terms:
Experimentation, Management, Security

Keywords:
encrypted/indexing databases, hierarchical key derivation schema, selective access