Detecting privacy violations in database publishing using disjoint queries

ABSTRACT

We present a new method of detecting privacy violations in the context of database publishing. Our method defines a published view V to preserve the privacy of a secret query Q if V and Q return no tuples in common, over all possible database instances. We then establish necessary and sufficient conditions that characterize when V preserves the privacy of Q in terms of the projected inequalities in the queries, both for conjunctive queries and queries with negation. We also show that integrity constraints have an effect on privacy, and derive a test for ensuring privacy preservation in the presence of FD constraints. The issue of privacy preservation in the presence of multiple views is investigated, and we show that it can reduced to the single view case for a suitably chosen view.

REFERENCES

• 1: Serge Abiteboul , Richard Hull , Victor Vianu, Foundations of Databases: The Logical Level, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
• 2: Nabil R. Adam , John C. Worthmann, Security-control methods for statistical databases: a comparative study, ACM Computing Surveys (CSUR), v.21 n.4, p.515-556, Dec. 1989 [doi>10.1145/76894.76895]
• 3: Antova, L., Koch, C.: On API's for probabilistic databases. In: Workshop on management of Uncertain Data (2008)
• 4: Silvana Castano , Maria Grazia Fugini , Giancarlo Martella , Pierangela Samarati, Database security, ACM Press/Addison-Wesley Publishing Co., New York, NY, 1995
• 5: Chawla, S., Dwork, C., McSherry, F., Smoth, A., Wee, H.: Towards privacy in public databases. In: TCC, pp. 363--385 (2005)
• 6: Nilesh Dalvi , Dan Suciu, Management of probabilistic data: foundations and challenges, Proceedings of the twenty-sixth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.1-12, June 11-13, 2007, Beijing, China [doi>10.1145/1265530.1265531]
• 7: Dalvi, N., Miklau, G., D. Suciu: Asymptotic conditional probabilities for conjunctive queries. In: ICDT, pp. 289--305 (2005)
• 8: Deutsch, A., Papakonstantinou, Y.: Privacy in database publishing. In: ICDT, pp. 230--245 (2006)
• 9: Irit Dinur , Kobbi Nissim, Revealing information while preserving privacy, Proceedings of the twenty-second ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.202-210, June 09-11, 2003, San Diego, California [doi>10.1145/773153.773173]
• 10: Dwork, C.: Ask a better question, get a better answer: a new approach to private data analysis. In: ICDT, pp. 18--27 (2007)
• 11: C. Elkan, A decision procedure for conjunctive query disjointness, Proceedings of the eighth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.134-139, March 1989, Philadelphia, Pennsylvania, United States [doi>10.1145/73721.73735]
• 12: Charles Elkan, Independence of logic database queries and update, Proceedings of the ninth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.154-160, April 02-04, 1990, Nashville, Tennessee, United States [doi>10.1145/298514.298557]
• 13: Fan, W.: XML publishing: Bridging theory and practice. In: DBPL, pp. 1--16 (2007)
• 14: Simson Garfinkel, Database nation: the death of privacy in the 21st century, O'Reilly & Associates, Inc., Sebastopol, CA, 2001
• 15: Gupta, A., Mumick, I.: Maintenance of materialized views: Problems, techniques, and applications. Data Engineering Bulletin 18(2), 1--16 (1995)
• 16: Gupta, A., Mumick, I. S.: Materialized Views. MIT Press (1999)
• 17: Halevy, A., Ives, Z., Suciu, D., Tatarinov, I.: Schema mediation in peer data management systems. In: ICDE, pp. 505-- (2003)
• 18: Daniel Kifer , Johannes Gehrke, Injecting utility into anonymized datasets, Proceedings of the 2006 ACM SIGMOD international conference on Management of data, June 27-29, 2006, Chicago, IL, USA [doi>10.1145/1142473.1142499]
• 19: Alon Y. Levy , Yehoshua Sagiv, Queries Independent of Updates, Proceedings of the 19th International Conference on Very Large Data Bases, p.171-181, August 24-27, 1993
• 20: Ashwin Machanavajjhala , Johannes Gehrke, On the efficiency of checking perfect privacy, Proceedings of the twenty-fifth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 26-28, 2006, Chicago, IL, USA [doi>10.1145/1142351.1142375]
• 21: Ashwin Machanavajjhala , Johannes Gehrke , Daniel Kifer , Muthuramakrishnan Venkitasubramaniam, \ell -Diversity: Privacy Beyond \kappa -Anonymity, Proceedings of the 22nd International Conference on Data Engineering, p.24, April 03-07, 2006 [doi>10.1109/ICDE.2006.1]
• 22: Gerome Miklau , Dan Suciu, Controlling access to published data using cryptography, Proceedings of the 29th international conference on Very large data bases, p.898-909, September 09-12, 2003, Berlin, Germany
• 23: Gerome Miklau , Dan Suciu, A formal analysis of information disclosure in data exchange, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007633]
• 24: Gerome Miklau , Dan Suciu, A formal analysis of information disclosure in data exchange, Journal of Computer and System Sciences, v.73 n.3, p.507-534, May, 2007 [doi>10.1016/j.jcss.2006.10.004]
• 25: Ng, W. S., Ooi, B. C., Tan, K. L., Zhou, A.: PeerDB: a P2P based system for distributed data sharing. In: ICDE, pp. 633--644 (2003)
• 26: Vibhor Rastogi , Dan Suciu , Sungho Hong, The boundary between privacy and utility in data publishing, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
• 27: Latanya Sweeney, k-anonymity: a model for protecting privacy, International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems, v.10 n.5, p.557-570, October 2002 [doi>10.1142/S0218488502001648]