Auditing Boolean Attributes Jon M. Kleinberg, Christos H. Papadimitriou, and Prabhakar Raghavan   View Paper (PDF)   Return to Award Talks Abstract We study the problem of auditing databases which support statistical sum queries to protect the security of sensitive information; we focus on the special case in which the sensitive information is Boolean. Principles and techniques developed for the security of statistical database in the case of continuous attributes do not apply here. We prove certain strong complexity results suggesting that there is no general efficient solution for the auditing problem in this case. We propose two efficient algorithms: The first is applicable when the sum queries are one-dimensional range queries (we prove that the problem is NP-hard even in the two-dimensional case). The second is an approximate algorithm that maintains security, although it may be too restrictive. Finally, we consider a "dual" variant, with continuous data but an aggregate function that is combinatorial in nature. Specifically, we provide algorithms for two natural definitions of the auditing condition when the aggregate function is MAX. References Note: References link to DBLP on the Web. [1] Nabil R. Adam , John C. Wortmann : Security-Control Methods for Statistical Databases: A Comparative Study. ACM Computing Surveys 21(4) : 515-556(1989) [2] Leland L. Beck : A Security Mechanism for Statistical Databases. TODS 5(3) : 316-338(1980) [3] Francis Y. Chin : Security in Statistical Databases for Queries with Small Counts. TODS 3(1) : 92-104(1978) [4] Francis Y. Chin , Gultekin Özsoyoglu : Statistical Database Design. TODS 6(1) : 113-139(1981) [5] Francis Y. Chin , Gultekin Özsoyoglu : Auditing and Inference Control in Statistical Databases. TSE 8(6) : 574-582(1982) [6] ... [7] Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest : Introduction to Algorithms. The MIT Press and McGraw-Hill Book Company 1989, ISBN 0-262-03141-8 and 0-07-013143-0 [8] ... [9] David P. Dobkin , Anita K. Jones , Richard J. Lipton : Secure Databases: Protection Against User Influence. TODS 4(1) : 97-106(1979) [10] Theodore D. Friedman , Lance J. Hoffman : Towards a Fail-Safe Approach to Secure Databases. IEEE Symposium on Security and Privacy 1980 : 18-21 [11] Chong K. Liew , Uinam J. Choi , Chung J. Liew : A Data Distortion by Probability Distribution. TODS 10(3) : 395-411(1985) [12] Gultekin Özsoyoglu , Francis Y. Chin : Enhancing the Security of Statistical Databases with a Question-Answering System and a Kernel Design. TSE 8(3) : 223-234(1982) [13] Steven P. Reiss : Practical Data-Swapping: The First Steps. TODS 9(1) : 20-37(1984) [14] Neil C. Rowe : Diophantine Inferences from Statistical Aggregates on Few-Valued Attributes. ICDE 1984 : 107-110 [15] ... [16] J. F. Traub , Yechiam Yemini , H. Wozniakowski : The Statistical Security of a Statistical Database. TODS 9(4) : 672-679(1984) BIBTEX @inproceedings{DBLP:conf/pods/KleinbergPR00,   author    = {Jon M. Kleinberg and                 Christos H. Papadimitriou and                 Prabhakar Raghavan},    title     = {Auditing Boolean Attributes},    booktitle = {Proceedings of the Nineteenth ACM SIGMOD-SIGACT-SIGART Symposium                 on Principles of Database Systems, May 15-17, 2000, Dallas, Texas,                 USA},    publisher = {ACM},    year      = {2000},    isbn      = {1-58113-214-X},    pages     = {86-91},    crossref  = {DBLP:conf/pods/00},    bibsource = {DBLP, http://dblp.uni-trier.de} } }, DiSC'01 Copyright ©2002 ACM Inc.