Anti-Tamper Database: Querying Encrypted Databases

Database Security, Database Research Group at Department of EECS, Case Western Reserve University

Advances in mobile computing, web technologies and Internet have elevated significance of data security in computer application systems. Emergence of the “databases-as-a-service” model allows users to retrieve data from anywhere throughout the Internet; as a result, protecting data privacy becomes an imminent challenge. Moreover, mobility of laptops as well as increased storage and power of laptops allows databases with sensitive data to travel everywhere, thus making them easy targets to capture physically, or to compromise by malicious users through bypassing access control or user authentication process in such systems. Especially, in an application service provider (ASP) environment where a database system is provided as a service, the owner of the data and the service provider may be different, and the database server may not be trustworthy; thus the data needs to be protected from the database service provider.

We propose anti-tamper databases and a query processing architecture with the following properties:
· The database DBE, called the anti-tamper database, resides at the anti-tamper site, and is encrypted a priori using an open-form or closed-form encryption function f() applied to database attribute values. Thus, if DBE becomes available to the adversary, its contents are devoid of semantics and, therefore not directly usable by the adversary.
· To the users, the encryption is transparent. That is, users think that they interact with the original, nonencrypted database DB, and pose their query Q against DB.
· We employ an intermediary software agent, called the (Encryption/Decryption) Agent, which we assume to be secure and, in this paper, residing at different site, called the agent site. That is, the adversary cannot capture the Agent code, and reverse-engineer its encryption/decryption algorithms. Agent rewrites Q(DB) into the SQL query QE(DBE) of the encrypted database, and submits it to DBE.
· The encryption function f() is chosen such that (i) it is a group homomorphism from the original database DB to the anti-tamper database DBE, (ii) information leakage is minimized, and (iii) inferences are controlled carefully when user have a priori knowledge of some database attribute values.
· The DBMS of the anti-tamper database is not aware of the encryption, and its query engine freely employs its query optimization techniques.
· For SQL queries that are expressible in relational algebra, there is no extra query processing cost except for the decryption of the final query output by the (secure) agent.

Faculty:
Gultekin Ozsoyoglu, EECS, Email: tekin@case.edu

Current Students:
Sun S. Chung, EECS, Email: ssc7@case.edu

Research & Publications

Anti-Tamper Databases - Part I: Querying Encrypted Databases
Sun Chung, David Singer, and Gultekin Ozsoyoglu, Submission to VLDB Journal On Privacy Preserving Data Management September 2005.

Querying Encrypted Databases - Part II: Processing Aggregate Queries
Sun Chung and Gultekin Ozsoyoglu, Submission to Journal Of Privacy Technology, 2005.

Anti-Tamper Database: Querying Encrypted Databases - Extended Work
Gultekin Ozsoyoglu, David Singer, and Sun Chung, in Book Chapter of Research Directions in Data and Application Security XVIII, Sabrina De Capitani di Vimercati et al., (eds), Kluwer Academic Publisher, Prague, Boston, 2004.

Anti-Tamper Database: Querying Encrypted Databases
Gultekin Ozsoyoglu, David Singer, and Sun Chung, in Proceedings of 17th IFIP 11.3 International Conference on Data and Application Security, Estate Park, Colorado, U.S.A., August, 2003

Processing Aggregate Queries Over Encrypted Databases- With Experimental Summary & Extended Work
Sun Chung and Gultekin Ozsoyoglu, Technical Report, Department of EECS, Case Western Reserve University, 2005.

Anti-Tamper Database: Querying Encrypted Databases- With Experimental Summary & Extended Work
Gultekin Ozsoyoglu and Sun Chung, Technical Report, Department of EECS, Case Western Reserve Universiry, 2003.

Proposals

PhD Proposal, Sun S. Chung
Security Proposal, Gultekin Ozsoyoglu, David Singer, and Sun Chung

Related Organizations

IFIP'03 on Data and Applications Security
IFIP