Hiding the presence of individuals from shared databases

ABSTRACT

Advances in information technology, and its use in research, are increasing both the need for anonymized data and the risks of poor anonymization. We present a metric, δ-presence, that clearly links the quality of anonymization to the risk posed by inadequate anonymization. We show that existing anonymization techniques are inappropriate for situations where δ-presence is a good metric (specifically, where knowing an individual is in the database poses a privacy risk), and present algorithms for effectively anonymizing to meet δ-presence. The algorithms are evaluated in the context of a real-world scenario, demonstrating practical applicability of the approach.

REFERENCES

• 1: A. D. Association. Direct and indirect costs of diabetes in the United States, 2006. http://www.diabetes.org/diabetes-statistics/cost-of-diabetes-in-us.jsp
• 2: Charu C. Aggarwal, On k-anonymity and the curse of dimensionality, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 3: G. Agrawal, T. Feder, K. Kenthapadi, S. Khuller,R. Panigrahy, D. Thomas., A. Zhu, Achieving anonymity via clustering. In: PODS '06: Proc. of the 25th ACMSIGMOD-SIGACT-SIGART symposium on Principles of database systems, Chicago, IL, USA, 2006.
• 4: M. Atzori. Weak k-anonymity: A low-distortion model for protecting privacy. In Proceedings of the 8th International Information Security Conference (ISC06), pages 60--71,2006.
• 5: R. Bayardo and R. Agrawal. Data privacy through optimalk-anonymization. In Proc. of the 21st Int'l Conf. on Data Engineering, 2005.
• 6: C. Blake and C. Merz. UCI repository of machine learning databases, 1998.
• 7: Standard for privacy of individually identifiable health information. Federal Register, 67(157):53181--53273, Aug.14 2002.
• 8: A. Ohrn and L. Ohno-Machado. Using boolean reasoning to anonymize databases. Artificial Intelligence in Medicine, 15(3):235--254, Mar. 1999.
• 9: Vijay S. Iyengar, Transforming data to satisfy privacy constraints, Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, July 23-26, 2002, Edmonton, Alberta, Canada [doi>10.1145/775047.775089]
• 10: Kristen LeFevre , David J. DeWitt , Raghu Ramakrishnan, Incognito: efficient full-domain K-anonymity, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066164]
• 11: Kristen LeFevre , David J. DeWitt , Raghu Ramakrishnan, Mondrian Multidimensional K-Anonymity, Proceedings of the 22nd International Conference on Data Engineering (ICDE'06), p.25, April 03-07, 2006 [doi>10.1109/ICDE.2006.101]
• 12: Ashwin Machanavajjhala , Johannes Gehrke , Daniel Kifer , Muthuramakrishnan Venkitasubramaniam, \ell -Diversity: Privacy Beyond \kappa -Anonymity, Proceedings of the 22nd International Conference on Data Engineering (ICDE'06), p.24, April 03-07, 2006 [doi>10.1109/ICDE.2006.1]
• 13: National Institute of Diabetes and Digestive and Kidney Diseases. National diabetes statistics fact sheet: general information and national estimates on diabetes in the United States. Technical Report NIH Publication No. 06-3892, U.S. Department of Health and Human Services, National Institute of Health, Bethesda, MD, Nov. 2005.
• 14: M. Ercan Nergiz , Chris Clifton, Thoughts on k-Anonymization, Proceedings of the 22nd International Conference on Data Engineering Workshops (ICDEW'06), p.96, April 03-07, 2006 [doi>10.1109/ICDEW.2006.147]
• 15: P. Samarati, Protecting Respondents' Identities in Microdata Release, IEEE Transactions on Knowledge and Data Engineering, v.13 n.6, p.1010-1027, November 2001 [doi>10.1109/69.971193]
• 16: 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]
• 17: Xiaokui Xiao , Yufei Tao, Anatomy: simple and effective privacy preservation, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea

INDEX TERMS

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

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

General Terms:
Algorithms, Legal Aspects, Security

Keywords:
delta presence, k-anonymity, medical databases, privacy