Article

Free access

Building decision tree classifier on private data

Authors:

Zhijun ZhanAuthors Info & Claims

CRPIT '14: Proceedings of the IEEE international conference on Privacy, security and data mining - Volume 14

Pages 1 - 8

Published: 01 December 2002 Publication History

Abstract

This paper studies how to build a decision tree classifier under the following scenario: a database is vertically partitioned into two pieces, with one piece owned by Alice and the other piece owned by Bob. Alice and Bob want to build a decision tree classifier based on such a database, but due to the privacy constraints, neither of them wants to disclose their private pieces to the other party or to any third party.We present a protocol that allows Alice and Bob to conduct such a classifier building without having to compromise their privacy. Our protocol uses an untrusted third-party server, and is built upon a useful building block, the scalar product protocol. Our solution to the scalar product protocol is more efficient than any existing solutions.

References

[1]

Agrawal, D. & Aggarwal, C. (2001), On the design and quantification of privacy preserving data mining algorithms, in 'Proccedings of the 20th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems', Santa Barbara, California, USA.]]

Digital Library

[2]

Agrawal, R. & Srikant, R. (2000), Privacy-preserving data mining, in 'Proceedings of the 2000 ACM SIGMOD on Management of Data', Dallas, TX USA, pp. 439-450.]]

Digital Library

[3]

Atallah, M. J. & Du, W. (2001), Secure multi-party computational geometry, in 'WADS2001: 7th International Workshop on Algorithms and Data Structures', Providence, Rhode Island, USA, pp. 165-179.]]

Digital Library

[4]

Beaver, D. (1997), Commodity-based cryptography (extended abstract), in 'Proceedings of the 29th Annual ACM Symposium on Theory of Computing', El Paso, TX USA.]]

Digital Library

[5]

Beaver, D. (1998), Server-assisted cryptography, in 'Proceedings of the 1998 New Security Paradigms Workshop', Charlottesville, VA USA.]]

Digital Library

[6]

Di-Crescenzo, G., Ishai, Y. & Ostrovsky, R. (1998), Universal service-providers for database private information retrieval, in 'Proceedings of the 17th Annual ACM Symposium on Principles of Distributed Computing'.]]

Digital Library

[7]

Du, W. (2001), A Study of Several Specific Secure Two-party Computation Problems, PhD thesis, Purdue University, West Lafayette, Indiana.]]

Digital Library

[8]

Du, W. & Zhan, Z. (2002), A practical approach to solve secure multi-party computation problems, in 'Proceedings of New Security Paradigms Workshop (to appear)', Virginia Beach, virginia, USA.]]

Digital Library

[9]

Franklin, M., Galil, Z. & Yung, M. (1992), An overview of secure distributed computing, Technical Report TR CUCS- 00892, Department of Computer Science, Columbia University.]]

[10]

Goldreich, O. (1998), 'Secure multi-party computation (working draft)', Available from http://www.wisdom.weizmann.ac.il/home/oded/pub- lic_html/foc.html.]]

[11]

Goldreich, O., Micali, S. & Wigderson, A. (1987), How to play any mental game, in 'Proceedings of the 19th Annual ACM Symposium on Theory of Computing', pp. 218-229.]]

Digital Library

[12]

Goldwasser, S. (1997), Multi-party computations: Past and present, in 'Proceedings of the 16th Annual ACM Symposium on Principles of Distributed Computing', Santa Barbara, CA USA.]]

Digital Library

[13]

Lindell, Y. & Pinkas, B. (2000), Privacy preserving data mining, in 'Advances in Cryptology - Crypto2000, Lecture Notes in Computer Science', Vol. 1880.]]

Digital Library

[14]

Rastogi, R. & Shim, K. (2000), '(public): A decision tree classifier that integrates building and pruning', Data Mining and Knowledge Discovery4(4), 315-344.]]

Digital Library

[15]

Vaidya, J. & Clifton, C. (2002), Privacy preserving association rule mining in vertically partitioned data, in 'Proceedings of the 8th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining'.]]

Digital Library

[16]

Yao, A. C. (1982), Protocols for secure computations, in 'Proceedings of the 23rd Annual IEEE Symposium on Foundations of Computer Science'.]]

Cited By

Xie XYuan MBai XGao WZhou ZOh ANaumann TGloberson ASaenko KHardt MLevine S(2023)On the gini-impurity preservation for privacy random forestsProceedings of the 37th International Conference on Neural Information Processing Systems10.5555/3666122.3668075(45055-45082)Online publication date: 10-Dec-2023
https://dl.acm.org/doi/10.5555/3666122.3668075
Akavia ALeibovich MResheff YRon RShahar MVald M(2022)Privacy-Preserving Decision Trees Training and PredictionACM Transactions on Privacy and Security10.1145/351719725:3(1-30)Online publication date: 19-May-2022
https://dl.acm.org/doi/10.1145/3517197
Hu SLi YLiu XLi QWu ZHe B(2022)The OARF Benchmark Suite: Characterization and Implications for Federated Learning SystemsACM Transactions on Intelligent Systems and Technology10.1145/351054013:4(1-32)Online publication date: 28-Jun-2022
https://dl.acm.org/doi/10.1145/3510540
Show More Cited By

Index Terms

Building decision tree classifier on private data

Recommendations

An approach of private classification on vertically partitioned data
ICWET '10: Proceedings of the International Conference and Workshop on Emerging Trends in Technology

Classification is one of the most ubiquitous data mining problems found in real life. Decision tree classification is one of the best-known solution approaches. This paper describes the construction of a decision tree classifier on vertically ...
Evaluating differentially private decision tree model over model inversion attack
Abstract
Machine learning techniques have been widely used and shown remarkable performance in various fields. Along with the widespread utilization of machine learning, concerns about privacy violations have been raised. Recently, as privacy invasion ...
A Practical Differentially Private Random Decision Tree Classifier

In this paper, we study the problem of constructing private classifiers using decision trees, within the framework of differential privacy. We first present experimental evidence that creating a differentially private ID3 tree using differentially ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image DL Hosted proceedings

CRPIT '14: Proceedings of the IEEE international conference on Privacy, security and data mining - Volume 14

December 2002

65 pages

ISBN:0909925925

Editors:
Chris Clifton
Purdue University
,
Vladimir Estivill-Castro
Griffiths University, Australia

Publisher

Australian Computer Society, Inc.

Australia

Publication History

Published: 01 December 2002

Author Tags

Qualifiers

Article

Conference

CRPIT '14

CRPIT '14: Privacy, security and data mining

01 12 2002

Maebashi City, Japan

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

76
Total Citations
View Citations
1,987
Total Downloads

Downloads (Last 12 months)54
Downloads (Last 6 weeks)8

Reflects downloads up to 26 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Xie XYuan MBai XGao WZhou ZOh ANaumann TGloberson ASaenko KHardt MLevine S(2023)On the gini-impurity preservation for privacy random forestsProceedings of the 37th International Conference on Neural Information Processing Systems10.5555/3666122.3668075(45055-45082)Online publication date: 10-Dec-2023
https://dl.acm.org/doi/10.5555/3666122.3668075
Akavia ALeibovich MResheff YRon RShahar MVald M(2022)Privacy-Preserving Decision Trees Training and PredictionACM Transactions on Privacy and Security10.1145/351719725:3(1-30)Online publication date: 19-May-2022
https://dl.acm.org/doi/10.1145/3517197
Hu SLi YLiu XLi QWu ZHe B(2022)The OARF Benchmark Suite: Characterization and Implications for Federated Learning SystemsACM Transactions on Intelligent Systems and Technology10.1145/351054013:4(1-32)Online publication date: 28-Jun-2022
https://dl.acm.org/doi/10.1145/3510540
Nanfack GTemple PFrénay B(2022)Constraint Enforcement on Decision Trees: A SurveyACM Computing Surveys10.1145/350673454:10s(1-36)Online publication date: 13-Sep-2022
https://dl.acm.org/doi/10.1145/3506734
Fang WZhao DTan JChen CYu CWang LWang LZhou JZhang BDemartini GZuccon GCulpepper JHuang ZTong H(2021)Large-scale Secure XGB for Vertical Federated LearningProceedings of the 30th ACM International Conference on Information & Knowledge Management10.1145/3459637.3482361(443-452)Online publication date: 26-Oct-2021
https://dl.acm.org/doi/10.1145/3459637.3482361
Lin XCrabbe MLi RDong RManta OComite U(2020)Sentiment Analysis of E-commerce Customer Reviews Based on Natural Language ProcessingProceedings of the 2020 2nd International Conference on Big Data and Artificial Intelligence10.1145/3436286.3436293(32-36)Online publication date: 28-Apr-2020
https://dl.acm.org/doi/10.1145/3436286.3436293
Yang QLiu YChen TTong Y(2019)Federated Machine LearningACM Transactions on Intelligent Systems and Technology10.1145/329898110:2(1-19)Online publication date: 28-Jan-2019
https://dl.acm.org/doi/10.1145/3298981
(2018)Heuristic-based hybrid privacy-preserving data stream mining approach using SD-perturbation and multi-iterative k-anonymisationInternational Journal of Knowledge Engineering and Data Mining10.5555/3292879.32928825:4(306-332)Online publication date: 1-Jan-2018
https://dl.acm.org/doi/10.5555/3292879.3292882
Shan ZRen KBlanton MWang C(2018)Practical Secure Computation OutsourcingACM Computing Surveys10.1145/315836351:2(1-40)Online publication date: 20-Feb-2018
https://dl.acm.org/doi/10.1145/3158363
Zhang JWang XYiu SJiang ZLi JWang CKantarcioglu M(2017)Secure Dot Product of Outsourced Encrypted Vectors and its Application to SVMProceedings of the Fifth ACM International Workshop on Security in Cloud Computing10.1145/3055259.3055270(75-82)Online publication date: 2-Apr-2017
https://dl.acm.org/doi/10.1145/3055259.3055270
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents