On Distributed k-Anonymization

• Autorzy: Zhong, S.
• Języki publikacji: EN

Abstrakty

EN

When a database owner needs to disclose her data, she can k-anonymize her data to protect the involved individuals’ privacy. However, if the data is distributed between two owners, then it is an open question whether the two owners can jointly k-anonymize the union of their data, such that the information suppressed in one owner's data is not revealed to the other owner. In this paper, we study this problemof distributed k-anonymization. We have two major results: First, it is impossible to design an unconditionally private protocol that implements any normal k-anonymization function, where normal k-anonymization functions are a very broad class of k-anonymization functions. Second, we give an efficent protocol that implements a normal k-anonymization function and show that it is private against polynomial-time adversaries. Our results have many potential applications and can be extended to three or more parties.

Słowa kluczowe

EN

k-anonymity; protocols; secure computation

• Czasopismo: Fundamenta Informaticae
• Rocznik: 2009
• Tom: Vol. 92, nr 4
• Strony: 411-431
• Opis fizyczny: Bibliogr. 38 poz., tab.

Twórcy

autor

Zhong, S.

• Computer Science and Engineering Department State University of New York at Buffalo Amherst, NY 14260, U. S. A.,

Bibliografia

• [1] Achugbue, J. O., Chin, F. Y.: The effectiveness of outputmodification by rounding for protection of statistical databases, INFOR, 17(3), 1979, 209-218.
• [2] Adam, N., Worthmann, J.: Security-control methods for statistical databases: a comparative study, ACM Comput. Surv., 21(4), 1989, 515-556, ISSN 0360-0300.
• [3] Aggarwal, C. C., Yu, P. S.: A Condensation Approach to Privacy Preserving Data Mining, Proc. 9th International Conference on Extending Database technology, Springer, 2004.
• [4] Aggarwal, G., Feder, T., Kenthapadi, K., Motwani, R., Panigrahy, R., Thomas, D., Zhu, A.: k-anonymity: Algorithms and Hardness, Under review, 2004.
• [5] Agrawal, D., Aggarwal, C.: On the design and quantification of privacy preserving data mining algorithms, Proc. 20th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, 2001, ISBN 1-58113-361-8.
• [6] Agrawal, R., Srikant, R.: Privacy-preserving data mining, Proc. ACM SIGMOD Conference on Management of Data, ACM Press, May 2000, ISBN 1-581-13218-2.
• [7] Beck, L. L.: A security mechanism for statistical databases, ACM TODS, 5(3), September 1980, 316-338.
• [8] Boneh, D., Boyen, X.: Secure identity based encryption without random oracles, Proceedings of the Advances in Cryptology (CRYPTO 04), 2004.
• [9] Boneh, D., Franklin,M. K.: Identity-based encryption from the weil pairing, Proceedings of the 21st Annual International Cryptology Conference on Advances in Cryptology, 2001.
• [10] Chin, F. Y., Ozsoyoglu, G.: Auditing and inference control in statistical databases, IEEE Trans. Sofw. Eng., SE-8(6), April 1982, 113-139.
• [11] Chor, B., Kushilevitz, E.: A zero-one law for Boolean privacy, SIAM J. Disc. Math., 4, 1991, 36-47.
• [12] Dalenius, T.: Finding a needle in a haystack C or identifying anonymous census record, Journal of Official Statistics, 2(3), 1986, 329-336.
• [13] Dinur, I., Nissim, K.: Revealing information while preserving privacy, Proc. 22nd ACM SIGMOD-SIGACTSIGART Symposium on Principles of Database Systems, ACM Press, 2003, ISBN 1-58113-670-6.
• [14] Evfimievski, A., Gehrke, J., Srikant, R.: Limiting privacy breaches in privacy preserving data mining, Proc. 22nd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, ACM Press, 2003, ISBN 1-58113-670-6.
• [15] Evfimievski, A., Srikant, R., Agrawal, R., Gehrke, J.: Privacy preserving mining of association rules, Proc. Eighth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, ACM Press, 2002, ISBN 1-58113-567-X.
• [16] Goldreich, O.: Foundations of Cryptography, vol. 2, Cambridge University Press, 2004.
• [17] Kantarcioglu, M., Clifton, C.: Privacy Preserving Distributed Mining of Association Rules on Horizontally Partitioned Data, ACM SIGMOD Workshop on Research Issues in Data Mining and Knowledge Discovery, ACM, 2002.
• [18] Kargupta, H., Datta, S., Wang, Q., Sivakumar, K.: On the Privacy Preserving Properties of Random Data Perturbation Techniques, Third IEEE International Conference on Data Mining, Florida, Nov 2003.
• [19] Kleinberg, J. M., Papadimitriou, C. H., Raghavan, P.: Auditing Boolean Attributes, Proc. of PODS, 2000.
• [20] Kushilevitz, E.: Privacy and Communication Complexity, IEEE Symposium on Foundations of Computer Science, 1989.
• [21] Lindell, Y., Pinkas, B.: Privacy Preserving Data Mining, Journal of Cryptology, 15(3), 2002, 177-206.
• [22] Machanavajjhala, A., Gehrke, J., Kifer, D., Venkitasubramaniam, M.: l-Diversity: Privacy Beyond k- Anonymity, Proceedings of ICDE 2006, 2006.
• [23] Meyerson, A., Williams, R.: On the Complexity of Optimal K-Anonymity, Proc. 22nd ACM SIGMODSIGACT-SIGART Symposium on Principles of Database Systems, Paris, France, June 2004.
• [24] Reiss, S.: Practical Data Swapping: The First Steps, ACM TODS, 9(1), 1984, 20-37.
• [25] Samarati, P., Sweeney, L.: Generalizing data to provide anonymity when disclosing information (abstract), Proc. of the 17th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, ACM Press, 1998, ISBN 0-89791-996-3.
• [26] Samarati, P., Sweeney, L.: Optimal anonymity using k-similar, a new clustering algorithm, Under review, 2003.
• [27] Shamir, A.: Identity-based cryptosystems and signature schemes, Proceedings of CRYPTO 84 on Advances in cryptology, 1985.
• [28] Shoshani, A.: Statistical databases: Characteristics, problems and some solutions, Proc. of the eighth International Conference on Very Large Data Bases, 1982.
• [29] Sweeney, L.: Guaranteeing anonymity when sharing medical data, the datafly system, Proc. of Journal of the American Medical Informatics Association, 1997.
• [30] Sweeney, L.: Achieving k-anonymity privacy protection using generalization and suppression, Int. J. Uncertain. Fuzziness Knowl.-Based Syst., 10(5), 2002, 571-588, ISSN 0218-4885.
• [31] Sweeney, L.: k-anonymity: a model for protecting privacy, Int. J. Uncertain. Fuzziness Knowl.-Based Syst., 10(5), 2002, 557-570, ISSN 0218-4885.
• [32] Traub, J., Yemini, Y.,Wozniakowksi, H.: The statistical Security of a Statistical Database, ACM TODS, 9(4), 1984, 672-679.
• [33] Vaidya, J., Clifton, C.: Privacy preserving association rule mining in vertically partitioned data, Proc. Eighth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2002, ISBN 1-58113-567-X.
• [34] Vaidya, J., Clifton, C.: Privacy-preserving k-means clustering over vertically partitioned data, Proc. Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, ACM Press, 2003, ISBN 1-58113-737-0.
• [35] Waters, B.: Efficient Identity-Based Encryption Without Random Oracles, Proceedings of Eurocrypt 2005, 2005.
• [36] Yang, Z., Zhong, S., Wright, R. N.: Privacy-Preserving Classification without Loss of Accuracy, SDM 2005, Proceedings of the Fifth SIAM International Conference on Data Mining, 2005.
• [37] Yao, A.: How to generate and exchange secrets, Proceedings of the 27th IEEE Symposium on Foundations of Computer Science, IEEE, 1986.
• [38] Zhong, S., Yang, Z., Wright, R. N.: Privacy Enhancing k-Anonymization of Customer Data, PODS 2005, Proceedings of the Twenty-Fourth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Databases, 2005.