Privacy-enhancing k-anonymization of customer data

ABSTRACT

In order to protect individuals' privacy, the technique of k-anonymization has been proposed to de-associate sensitive attributes from the corresponding identifiers. In this paper, we provide privacy-enhancing methods for creating k-anonymous tables in a distributed scenario. Specifically, we consider a setting in which there is a set of customers, each of whom has a row of a table, and a miner, who wants to mine the entire table. Our objective is to design protocols that allow the miner to obtain a k-anonymous table representing the customer data, in such a way that does not reveal any extra information that can be used to link sensitive attributes to corresponding identifiers, and without requiring a central authority who has access to all the original data. We give two different formulations of this problem, with provably private solutions. Our solutions enhance the privacy of k-anonymization in the distributed scenario by maintaining end-to-end privacy from the original customer data to the final k-anonymous results.

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: C. C. Aggarwal and P. S. Yu. A condensation approach to privacy preserving data mining. In Proceedings of 9th International Conference on Extending Database technology. Springer, 2004.
• 4: G. Aggarwal, T. Feder, K. Kenthapadi, R. Motwani, R. Panigrahy, D. Thomas, and A. Zhu. k-anonymity: Algorithms and hardness. Under review, 2004.
• 5: 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]
• 6: 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
• 7: William Aiello , Yuval Ishai , Omer Reingold, Priced Oblivious Transfer: How to Sell Digital Goods, Proceedings of the International Conference on the Theory and Application of Cryptographic Techniques: Advances in Cryptology, p.119-135, May 06-10, 2001
• 8: Roberto J. Bayardo , Rakesh Agrawal, Data Privacy through Optimal k-Anonymization, Proceedings of the 21st International Conference on Data Engineering (ICDE'05), p.217-228, April 05-08, 2005 [doi>10.1109/ICDE.2005.42]
• 9: 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]
• 10: Dan Boneh, The Decision Diffie-Hellman Problem, Proceedings of the Third International Symposium on Algorithmic Number Theory, p.48-63, June 21-25, 1998
• 11: F. Y. Chin and G. Ozsoyoglu. Auditing and inference control in statistical databases. IEEE Transactions on Software Engineering, SE-8(6):113--139, April 1982.
• 12: T. Dalenius. Finding a needle in a haystack-or identifying anonymous census record. Journal of Official Statistics, 2(3):329--336, 1986.
• 13: Yvo Desmedt , Yair Frankel, Threshold Cryptosystems, Proceedings of the 9th Annual International Cryptology Conference on Advances in Cryptology, p.307-315, August 20-24, 1989
• 14: 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]
• 15: Taher El Gamal, A public key cryptosystem and a signature scheme based on discrete logarithms, Proceedings of CRYPTO 84 on Advances in cryptology, p.10-18, August 1985, Santa Barbara, California, United States
• 16: Alexandre Evfimievski , Johannes Gehrke , Ramakrishnan Srikant, Limiting privacy breaches in privacy preserving data mining, Proceedings of the twenty-second ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.211-222, June 09-11, 2003, San Diego, California [doi>10.1145/773153.773174]
• 17: Alexandre Evfimievski , Ramakrishnan Srikant , Rakesh Agrawal , Johannes Gehrke, Privacy preserving mining of association rules, 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.775080]
• 18: R. Gennaro, S. Jarecki, H. Krawczyk, and T. Rabin. Secure applications of Pedersen's distributed key generation protocol. In CT-RSA 2003, volume 2612 of Lecture Notes in Computer Science, pages 373--390, 2003.
• 19: Oded Goldreich, Foundations of Cryptography: Volume 2, Basic Applications, Cambridge University Press, New York, NY, 2004
• 20: M. Kantarcioglu and C. Clifton. Privacy preserving distributed mining of association rules on horizontally partitioned data. In ACM SIGMOD Workshop on Research Issues in Data Mining and Knowledge Discovery, pages 639--644. ACM, 2002.
• 21: Hillol Kargupta , Souptik Datta , Qi Wang , Krishnamoorthy Sivakumar, On the Privacy Preserving Properties of Random Data Perturbation Techniques, Proceedings of the Third IEEE International Conference on Data Mining, p.99, November 19-22, 2003
• 22: 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]
• 23: Y. Lindell and B. Pinkas. Privacy preserving data mining. Journal of Cryptology, 15(3):177--206, 2002.
• 24: Adam Meyerson , Ryan Williams, On the complexity of optimal K-anonymity, Proceedings of the twenty-third ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 14-16, 2004, Paris, France [doi>10.1145/1055558.1055591]
• 25: 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]
• 26: 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 ]
• 27: Pierangela Samarati , Latanya Sweeney, Generalizing data to provide anonymity when disclosing information (abstract), Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.188, June 01-04, 1998, Seattle, Washington, United States [doi>10.1145/275487.275508]
• 28: Adi Shamir, How to share a secret, Communications of the ACM, v.22 n.11, p.612-613, Nov. 1979 [doi>10.1145/359168.359176]
• 29: 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
• 30: L. Sweeney. Guaranteeing anonymity when sharing medical data, the datafly system. In Proceedings, Journal of the American Medical Informatics Association, 1997.
• 31: Latanya Sweeney, Achieving k-anonymity privacy protection using generalization and suppression, International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems, v.10 n.5, p.571-588, October 2002 [doi>10.1142/S021848850200165X]
• 32: 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]
• 33: 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]
• 34: Jaideep Vaidya , Chris Clifton, Privacy preserving association rule mining in vertically partitioned data, 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.775142]
• 35: Jaideep Vaidya , Chris Clifton, Privacy-preserving k-means clustering over vertically partitioned data, Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2003, Washington, D.C. [doi>10.1145/956750.956776]