CS732: Topics in Database Systems

CS732 is a PhD level seminar course in database systems. In this semester, we will discuss classical and recent research papers in data security and privacy. We plan to cover the following topics:

Security in statistical databases
Access control
Databases as a service
Database watermarking
Secure information sharing
Privacy-preserving data mining
Hippocratic databases

Instructor

Johannes Gehrke
Office: 4105B Upson Hall
Email: johannes@cs.cornell.edu

Location and Hours

Lectures: Fridays, 3:30-5:30pm (with an occasional lecture on Wednesdays, 4:30-6pm).
Location: 484 Rhodes

Course Schedule

We will discuss one or two papers each class, and you are expected to have read these papers before class. The papers under the heading "Additional readings" are optional reading except for the presenters that day who are expected to read all papers relevant to her lecture.

Date	Topic and Papers	Presenter
9/24	Introduction and overview	Johannes
Wednesday 10/1	Security-Control in Statistical Databases: Query Restriction, Data Perturbation, and Answer Perturbation Nabil R. Adam, John C. Wortmann: Security-Control Methods for Statistical Databases: A Comparative Study. ACM Computing Surveys 21(4): 515-556 (1989). Surveys methods for protecting statistical databases against disclosure of confidential information. Additional reading: I. Fellegi. On the question of statistical confidentiality. Journal of the American Statistical Assoc., 67(337):7--18, March 1972. Gives conditions how to check for residual disclosure of sensitive information given a set of query answer. Francis Y. L. Chin: Security in Statistical Databases for Queries with Small Counts. TODS 3(1): 92-104 (1978). Several early results on query-set size control, including results on how the database can be compromised if the user has some prior knowledge. Dorothy E. Denning, Peter J. Denning, Mayer D. Schwartz: The Tracker: A Threat to Statistical Database Security. TODS 4(1): 76-96(1979). Shows that controlling query-set sizes can be easily compromised. Francis Y. L. Chin, Gultekin Özsoyoglu: Statistical Database Design. TODS 6(1): 113-139 (1981). Introduces a conceptual model for data security in statistical databases.	Johannes
10/3	Access Control Elisa Bertino, Sushil Jajodia, Pierangela Samarati: Database Security: Research and Practice. IS 20(7): 537-556 (1995)	Ashwin
Wednesday 10/08	XML Access Control Ting Yu, Divesh Srivastava, Laks V. S. Lakshmanan, H. V. Jagadish: Compressed Accessibility Map: Efficient Access Control for XML. VLDB 2002: 478-489	Chavdar
10/10	No class
10/17	Databases as a Service Dawn Xiaodong Song, David Wagner, Adrian Perrig: Practical Techniques for Searches on Encrypted Data. IEEE Symposium on Security and Privacy 2000: 44-55 (Prakash) Additional reading Hakan Hacigümüs, Sharad Mehrotra, Balakrishna R. Iyer: Providing Database as a Service. ICDE 2002: 29-	Prakash
10/24	No class
10/31	Databases as a Service (Continued) Hakan Hacigümüs, Balakrishna R. Iyer, Chen Li, Sharad Mehrotra: Executing SQL over encrypted data in the database-service-provider model. SIGMOD Conference 2002: 216-227 (Cristi) Authenticated Data Structures M. T. Goodrich, R. Tamassia, N. Triandopoulos and R. Cohen, Authenticated Data Structures for Graph and Geometric Searching, Technical Report, Center for Geometric Computing, Brown University, 2002. Additional reading Distributed Data Authentication (Brown University)	Cristi Shai
11/07	No class
11/14	Digital Signatures Ralph C. Merkle: A Certified Digital Signature. CRYPTO 1989: 218-238. To print this paper, go to to the DBLP Entry for Ralph Merkle, and then click on the electronic edition link which brings you to a Springer website from which you can download the paper. M. Naor, K. Nissim. Certificate Revocation and Certificate Update. (abstract) Proc. 7th USENIX Security Symposium, 1998. Journal version IEEE Journal on Selected Areas in Communications (JSAC) Vol. 18 no. 4, April 2000.	Shai
11/21	Guest lecture on Software Licensing XrML: A popular language for writing software licenses. Check out: MPEG-21 Rights Expression Language Language FCD (local copy). http://www.xrml.org.	Vicky
11/28	Thanksgiving -- no class.
12/5	More on XML Access Control: XML Access Control (XACL). http://www.trl.ibm.com/projects/xml/xacl/ (Kevin)	Kevin

Future papers:

XML Access Control

E. Damiani, S. De Capitani di Vimercati, S. Paraboschi, P. Samarati, "Securing XML Documents," in Proc. of the 2000 International Conference on Extending Database Technology (EDBT2000), Konstanz, Germany, March 27-31, 2000. (Abhinandan)

Database Watermarking

Rakesh Agrawal, Jerry Kiernan: Watermarking Relational Databases. 155-166, VLDB 2002 (Abhinandan)

Database Fingerprinting

Saul Schleimer, Daniel Shawcross Wilkerson, Alexander Aiken: Winnowing: Local Algorithms for Document Fingerprinting. SIGMOD 2002, 76-85. (Kevin)

Hippocratic databases

Rakesh Agrawal, Jerry Kiernan, Ramakrishnan Srikant, Yirong Xu: Hippocratic Databases. 143-154, VLDB 2002

Enforcing Access Control with Cryptography

Gerome Miklau, Dan Suciu: Controlling Access to Published Data Using Cryptography. VLDB 2003, 898-909 (Mirek)

Privacy standards

R. Agrawal, J. Kiernan, R. Srikant and Y. Xu, "Implementing P3P using Database Technology", Proc. of the 19th Int'l Conference on Data Engineering, Bangalore, India, March 2003. (Mingsheng)
R. Agrawal, J. Kiernan, R. Srikant and Y. Xu, "An XPath-based Preference Language for P3P", Proc. of the Twelfth Int'l World Wide Web Conference, Budapest, Hungary, May 2003. (Fan)
Platform for Privacy Preferences (P3P): http://www.w3.org/P3P/

Secure Information Sharing

Rakesh Agrawal, Alexandre V. Evfimievski, Ramakrishnan Srikant: Information Sharing Across Private Databases. SIGMOD Conference 2003: 86-97