Revealing information while preserving privacy

ABSTRACT

We examine the tradeoff between privacy and usability of statistical databases. We model a statistical database by an n-bit string d1,..,dn, with a query being a subset q ⊆ [n] to be answered by Σiεq di. Our main result is a polynomial reconstruction algorithm of data from noisy (perturbed) subset sums. Applying this reconstruction algorithm to statistical databases we show that in order to achieve privacy one has to add perturbation of magnitude (Ω√n). That is, smaller perturbation always results in a strong violation of privacy. We show that this result is tight by exemplifying access algorithms for statistical databases that preserve privacy while adding perturbation of magnitude Õ(√n).For time-T bounded adversaries we demonstrate a privacypreserving access algorithm whose perturbation magnitude is ≈ √T.

REFERENCES

• 1: J. O. Achugbue and F. Y. Chin, The effectiveness of output modification by rounding for protection of statistical databases, INFOR 17, 3: 209--218, 1979.
• 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: Dakshi Agrawal , Charu C. Aggarwal, On the design and quantification of privacy preserving data mining algorithms, Proceedings of the twentieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.247-255, May 2001, Santa Barbara, California, United States [doi>10.1145/375551.375602]
• 4: Rakesh Agrawal , Ramakrishnan Srikant, Privacy-preserving data mining, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.439-450, May 15-18, 2000, Dallas, Texas, United States
• 5: N. Alon and J. H. Spencer, The probabilistic method, Wiley-Interscience {John Wiley & Sons}, New York, second edition, 2000.
• 6: Leland L. Beck, A security machanism for statistical database, ACM Transactions on Database Systems (TODS), v.5 n.3, p.316-3338, Sept. 1980 [doi>10.1145/320613.320617]
• 7: F. Y. Chin and G. Ozsoyoglu, Auditing and infrence control in statistical databases, IEEE Trans. Softw. Eng., SE-8(6):113--139, April 1982.
• 8: Dorothy E. Denning , Peter J. Denning , Mayer D. Schwartz, The tracker: a threat to statistical database security, ACM Transactions on Database Systems (TODS), v.4 n.1, p.76-96, March 1979 [doi>10.1145/320064.320069]
• 9: Dorothy E. Denning, Secure statistical databases with random sample queries, ACM Transactions on Database Systems (TODS), v.5 n.3, p.291-315, Sept. 1980 [doi>10.1145/320613.320616]
• 10: Dorothy Elizabeth Rob Denning, Cryptography and Data Security, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1982
• 11: I. Fellegi, On the question of statistical con dentiality, Journal of the American Statistical Association, 1972, pp. 7--18.
• 12: O. Goldreich , S. Micali , A. Wigderson, How to play ANY mental game, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.218-229, January 1987, New York, New York, United States [doi>10.1145/28395.28420]
• 13: Venkatesan Guruswami , Madhu Sudan, Improved Decoding of Reed-Solomon and Algebraic-Geometric Codes, Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.28, November 08-11, 1998
• 14: Jon Kleinberg , Christos Papadimitriou , Prabhakar Raghavan, Auditing Boolean attributes, Proceedings of the nineteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.86-91, May 15-18, 2000, Dallas, Texas, United States [doi>10.1145/335168.335210]
• 15: Chong K. Liew , Uinam J. Choi , Chung J. Liew, A data distortion by probability distribution, ACM Transactions on Database Systems (TODS), v.10 n.3, p.395-411, Sept. 1985 [doi>10.1145/3979.4017]
• 16: Ezio Lefons , Alberto Silvestri , Filippo Tangorra, An Analytic Approach to Statistical Databases, Proceedings of the 9th International Conference on Very Large Data Bases, p.260-274, October 31-November 02, 1983
• 17: Steven P. Reiss, Practical data-swapping: the first steps, ACM Transactions on Database Systems (TODS), v.9 n.1, p.20-37, March 1984 [doi>10.1145/348.349]
• 18: Arie Shoshani, Statistical Databases: Characteristics, Problems, and some Solutions, Proceedings of the 8th International Conference on Very Large Data Bases, p.208-222, September 08-10, 1982
• 19: Madhu Sudan, Decoding of Reed Solomon codes beyond the error-correction bound, Journal of Complexity, v.13 n.1, p.180-193, March 1997 [doi>10.1006/jcom.1997.0439 ]
• 20: J. F. Traub , Y. Yemini , H. Woźniakowski, The statistical security of a statistical database, ACM Transactions on Database Systems (TODS), v.9 n.4, p.672-679, Dec. 1984 [doi>10.1145/1994.383392]
• 21: A. Yao, Protocols for Secure Computations (Extended Abstract), FOCS 1982: 160--164.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Statistical databases

Additional Classification:
  B. Hardware
  B.2 ARITHMETIC AND LOGIC STRUCTURES
      B.2.4 High-speed Arithmetic
          Subjects: Algorithms

  K. Computing Milieux
  K.4 COMPUTERS AND SOCIETY
      K.4.1 Public Policy Issues
          Subjects: Privacy

General Terms:
Algorithms, Management, Theory

Keywords:
data reconstruction, integrity and security, subset-sums with noise