Practical secure decision tree learning in a teletreatment application

S.J.A. Hoogh, de, B. Schoenmakers, Ping Chen, H. Op den Akker

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

9 Citations (Scopus)
14 Downloads (Pure)

Abstract

In this paper we develop a range of practical cryptographic protocols for secure decision tree learning, a primary problem in privacy preserving data mining. We focus on particular variants of the well-known ID3 algorithm allowing a high level of security and performance at the same time. Our approach is basically to design special-purpose secure multiparty computations, hence privacy will be guaranteed as long as the honest parties form a sufficiently large quorum. Our main ID3 protocol will ensure that the entire database of transactions remains secret except for the information leaked from the decision tree output by the protocol. We instantiate the underlying ID3 algorithm such that the performance of the protocol is enhanced considerably, while at the same time limiting the information leakage from the decision tree. Concretely, we apply a threshold for the number of transactions below which the decision tree will consist of a single leaf—limiting information leakage. We base the choice of the "best" predicting attribute for the root of a decision tree on the Gini index rather than the well-known information gain based on Shannon entropy, and we develop a particularly efficient protocol for securely finding the attribute of highest Gini index. Moreover, we present advanced secure ID3 protocols, which generate the decision tree as a secret output, and which allow secure lookup of predictions (even hiding the transaction for which the prediction is made). In all cases, the resulting decision trees are of the same quality as commonly obtained for the ID3 algorithm. We have implemented our protocols in Python using VIFF, where the underlying protocols are based on Shamir secret sharing. Due to a judicious use of secret indexing and masking techniques, we are able to code the protocols in a recursive manner without any loss of efficiency. To demonstrate practical feasibility we apply the secure ID3 protocols to an automated health care system of a real-life rehabilitation organization.
Original languageEnglish
Title of host publicationFinancial Cryptography and Data Security (18th International Conference, FC 2014, Christ Church, Barbados, March 3-7, 2014, Revised Selected Papers)
EditorsN. Christin, R. Safavi-Naini
Place of PublicationBerlin
PublisherSpringer
Pages179-194
ISBN (Print)978-3-662-45471-8
DOIs
Publication statusPublished - 2014
Event18th International Conference on Financial Cryptography and Data Security (FC 2014), March 3-7, 2014, Barbados - Accra Beach Hotel & Spa, Barbados
Duration: 3 Mar 20147 Mar 2014

Publication series

NameLecture Notes in Computer Science
Volume8437
ISSN (Print)0302-9743

Conference

Conference18th International Conference on Financial Cryptography and Data Security (FC 2014), March 3-7, 2014, Barbados
Abbreviated titleFC 2014
CountryBarbados
Period3/03/147/03/14

Fingerprint Dive into the research topics of 'Practical secure decision tree learning in a teletreatment application'. Together they form a unique fingerprint.

  • Cite this

    Hoogh, de, S. J. A., Schoenmakers, B., Chen, P., & Op den Akker, H. (2014). Practical secure decision tree learning in a teletreatment application. In N. Christin, & R. Safavi-Naini (Eds.), Financial Cryptography and Data Security (18th International Conference, FC 2014, Christ Church, Barbados, March 3-7, 2014, Revised Selected Papers) (pp. 179-194). (Lecture Notes in Computer Science; Vol. 8437). Springer. https://doi.org/10.1007/978-3-662-45472-5_12