A formal analysis of information disclosure in data exchange

ABSTRACT

We perform a theoretical study of the following query-view security problem: given a view V to be published, does V logically disclose information about a confidential query S? The problem is motivated by the need to manage the risk of unintended information disclosure in today's world of universal data exchange. We present a novel information-theoretic standard for query-view security. This criterion can be used to provide a precise analysis of information disclosure for a host of data exchange scenarios, including multi-party collusion and the use of outside knowledge by an adversary trying to learn privileged facts about the database. We prove a number of theoretical results for deciding security according to this standard. We also generalize our security criterion to account for prior knowledge a user or adversary may possess, and introduce techniques for measuring the magnitude of partical disclosures. We believe these results can be a foundation for practical efforts to secure data exchange frameworks, and also illuminate a nice interaction between logic and probability theory.

REFERENCES

• 1: 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]
• 2: F. Bancilhon and N. Spyratos. Protection of information in relational data bases. In VLDB, 1977.
• 3: François Bancilhon , Nicolas Spyratos, Algebraic versus probabilstic independence in data bases, Proceedings of the fourth ACM SIGACT-SIGMOD symposium on Principles of database systems, p.149-153, March 25-27, 1985, Portland, Oregon, United States [doi>10.1145/325405.325424]
• 4: Elisa Bertino , Sushil Jajodia , Pierangela Samarati, Database security: research and practice, Information Systems, v.20 n.7, p.537-556, Nov. 1995 [doi>10.1016/0306-4379(95)00029-4]
• 5: José A. Blakeley , Neil Coburn , Per-:1Vke Larson, Updating derived relations: detecting irrelevant and autonomously computable updates, ACM Transactions on Database Systems (TODS), v.14 n.3, p.369-400, Sept. 1989 [doi>10.1145/68012.68015]
• 6: Dorothy Elizabeth Rob Denning, Cryptography and Data Security, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1982
• 7: 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]
• 8: R. Fagin. Probabilities on finite models. Notices of the Am. Math. Soc., October: A714, 1972.
• 9: R. Fagin, Probabilities on finite models. Journal of Symbolic Logic, 41(1), 1976.
• 10: C. Fortuin, P. Kasteleyn, and J. Ginibre. Correlation inequalities on some partially ordered sets. Comm. in Math. Physics, 22:89--103, 1971.
• 11: Lise Getoor , Benjamin Taskar , Daphne Koller, Selectivity estimation using probabilistic models, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.461-472, May 21-24, 2001, Santa Barbara, California, United States
• 12: Ashish Gupta , Yehoshua Sagiv , Jeffrey D. Ullman , Jennifer Widom, Constraint checking with partial information, Proceedings of the thirteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.45-55, May 24-27, 1994, Minneapolis, Minnesota, United States [doi>10.1145/182591.182597]
• 13: Alon Y. Halevy, Answering queries using views: A survey, The VLDB Journal — The International Journal on Very Large Data Bases, v.10 n.4, p.270-294, December 2001 [doi>10.1007/s007780100054]
• 14: Daphne Koller , Avi Pfeffer, Probabilistic frame-based systems, Proceedings of the fifteenth national/tenth conference on Artificial intelligence/Innovative applications of artificial intelligence, p.580-587, July 1998, Madison, Wisconsin, United States
• 15: 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
• 16: G. Miklau and D. Suciu. A formal analysis of information disclosure in data exchange. University of Washington Technical Report (TR 03-12-02), Dec 2003. www.cs.washington.edu/homes/gerome.
• 17: B. Schneier. Applied Cryptography, Second Edition. John Wiley and Sons, Inc., 1996.
• 18: C. E. Shannon. Communication theory of secrecy systems. In Bell System Technical Journal, 1949.
• 19: 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]