A Differentially Private (Random) Decision Tree without Noise from k-Anonymity
Source abstract
Abstract
This paper focuses on the relationship between decision trees, a typical machine learning method, and data anonymization. It is known that information leaked from trained decision trees can be evaluated using well-studied data anonymization techniques and that decision trees can be strengthened using k-anonymity and ℓ-diversity; unfortunately, however, this does not seem sufficient for differential privacy. In this paper, we show how one might apply k-anonymity to a (random) decision tree, which is a variant of the decision tree. Surprisingly, this results in differential privacy, which means that security is amplified from k-anonymity to differential privacy without the addition of noise.
Source: crossref · Quality: baseline
Research context
OpenAlex topics: Privacy-Preserving Technologies in Data · Cryptography and Data Security · Internet Traffic Analysis and Secure E-voting
SciVX discovery tags are terminology-based. OpenAlex topics are source-provided classifications.
Affiliations
Department of Informatics, Faculty of Informatics, Tokyo University of Information Sciences, 4-1 Onaridai, Wakaba-ku, Chiba 265-8501, Japan
College of Information Science and Engineering, Ritsumeikan University, 2-150 Iwakura-cho, Ibaraki 567-8570, Japan
Cybersecurity Research Institute, National Institute of Information and Communications Technology (NICT), 4-2-1 Nukui-Kitamachi, Koganei 184-8795, Japan
Funding
JST CREST
References (22)
Show source-provided references
1. k-Anonymity: A Model for Protecting Privacy10.1142/S0218488502001648 ↗
2. Machanavajjhala, A., Gehrke, J., Kifer, D., and Venkitasubramaniam, M. (2006, January 3–8). ℓ-Diversity: Privacy Beyond k-Anonymity. Proceedings of the 22nd International Conference on Data Engineering, ICDE 2006, Atlanta, GA, USA.10.1109/ICDE.2006.1 ↗
3. Li, N., Li, T., and Venkatasubramanian, S. (2007, January 15–20). t-Closeness: Privacy Beyond k-Anonymity and ℓ-Diversity. Proceedings of the 23rd International Conference on Data Engineering, ICDE 2007, The Marmara Hotel, Istanbul, Turkey.10.1109/ICDE.2007.367856 ↗
4. Yao, A.C. (1986, January 27–29). How to Generate and Exchange Secrets (Extended Abstract). Proceedings of the 27th Annual Symposium on Foundations of Computer Science, Toronto, ON, Canada.10.1109/SFCS.1986.25 ↗
5. Subramanian, S., Nadarajan, R., Rao, S., and Sheen, S. (2016). Enhanced ℓ– Diversity Algorithm for Privacy Preserving Data Mining. Digital Connectivity—Social Impact, Proceedings of the 51st Annual Convention of the Computer Society of India, CSI 2016, Coimbatore, India, 8–9 December 2016, Proceedings, Springer.10.1007/978-981-10-3274-5 ↗
6. Stadler, T., Oprisanu, B., and Troncoso, C. (2022, January 10–12). Synthetic Data - Anonymisation Groundhog Day. Proceedings of the 31st USENIX Security Symposium, USENIX Security 2022, Boston, MA, USA.
7. Providing k-anonymity in data mining10.1007/s00778-006-0039-5 ↗
8. k -Anonymous Data Mining: A Survey10.1007/978-0-387-70992-5_5 ↗
9. Fan, W., Wang, H., Yu, P.S., and Ma, S. (2003, January 19–22). Is random model better? On its accuracy and efficiency. Proceedings of the 3rd IEEE International Conference on Data Mining (ICDM 2003), Melbourne, FL, USA.
10. A Practical Differentially Private Random Decision Tree Classifier
11. A Differentially Private Random Decision Forest Using Reliable Signal-to-Noise Ratios
12. Decision Tree Classification with Differential Privacy: A Survey
13. Li, N., Qardaji, W.H., and Su, D. (2012, January 2–4). On sampling, anonymization, and differential privacy or, k-anonymization meets differential privacy. Proceedings of the 7th ACM Symposium on Information, Compuer and Communications Security, ASIACCS ’12, Seoul, Republic of Korea.10.1145/2414456.2414474 ↗
14. Li, C. (2005). Practical privacy: The SuLQ framework. PODS, Proceedings of the Twenty-Fourth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, Baltimore, Maryland, 13–15 June 2005, ACM.
15. Rao, B., Krishnapuram, B., Tomkins, A., and Yang, Q. (2010). Data mining with differential privacy. KDD ’10, Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Washington, DC, USA, 25–28 July 2010, ACM.
16. L-diversity: Privacy beyond k-anonymity10.1145/1217299.1217302 ↗
17. The Algorithmic Foundations of Differential Privacy10.1561/0400000042 ↗
18. Rajkovic, V. (2024, August 24). Nursery. UCI Machine Learning Repository. Available online: https://archive.ics.uci.edu/dataset/76/nursery.
19. Becker, B., and Kohavi, R. (2024, August 24). Adult. UCI Machine Learning Repository. Available online: https://archive.ics.uci.edu/dataset/2/adult.
20. Mushroom (2024, August 24). UCI Machine Learning Repository. Available online: https://archive.ics.uci.edu/dataset/73/mushroom.
21. Mahdi, N. (2024, August 24). Bank_Personal_Loan_Modelling. Available online: https://www.kaggle.com/datasets/ngnnguynthkim/bank-personal-loan-modellingcsv.
22. (2024, August 24). Mobile Kukan Toukei (Guidelines). Available online: https://www.intage.co.jp/english/service/platform/mobile-kukan-toukei/.