Collaborative Private Decision-Tree Evaluation using (Multi-Key) Fully Homomorphic Encryption

Abstract

Decision-tree evaluation is a widely-used classification approach known for its simplicity and effectiveness. Decision-tree models are shown to be helpful in classifying instances of fraud, malware, or diseases and can be used to make dynamic, flexible access decisions within an access-control system. These applications often require sensitive data of more than one party, like financial or health-related records. It is important to keep this data private, especially when the decision-tree evaluation is done in a collaborative manner where more than one party provides sensitive input data. Current privacy-preserving solutions only consider scenarios in which input data originates from a single source. However, collaboration for decision-tree evaluation tasks is needed more and more since these collaborations often bear fruit. Therefore, in this work we address Private Decision-Tree Evaluation in a collaborative setting. We assume one entity, called the server, that holds the decision tree and multiple users that provide private data on which the decision tree is evaluated. The focus of our research lies on solutions that make use of homomorphic encryption. We give ten different protocols that each take place in a different setting; either the holder of the decision tree receives the evaluation result or the users that provide the input. The protocols use Multi-Key Fully Homomorphic Encryption (FHE) or normal FHE with a Semi-Trusted Third Party (STTP). Additionally, we introduce a novel key-switching method within two of the STTP protocols such that the dependency on the STTP is greatly reduced. All protocols are proven to be secure in the semi-honest model and compared in terms of run-time complexity and communication costs. Due to the high computational overhead for the Multi-Key FHE schemes, the protocols that make use of these schemes are not yet feasible. Therefore, the protocols that use an STTP are the most promising. All protocols take no more than 4 communication rounds. Assuming that the implementation can be parallelized and given an input bit length of 4, the decision-tree evaluation in our protocols takes in the worst case between 60 and 160 hours, executed on an Intel Core Processor at 2.4 GHz with 16 GB memory.