TL;DR
This paper introduces PPSDT, a novel privacy-preserving algorithm for building clinical decision-support systems (CDSS) using distributed patient data from multiple hospitals. By employing homomorphic encryption and a unique single decision tree approach, it enables accurate diagnoses without compromising patient privacy, outperforming existing methods in efficiency.
What Problem Does This Paper Address?
Clinical Decision-Support Systems (CDSSs) are invaluable tools for improving healthcare by assisting physicians in diagnosing diseases. These systems often rely on historical patient data to build predictive models. However, a significant challenge arises when this data is distributed across multiple institutions. Sharing such sensitive patient health records (PHRs) directly between hospitals raises serious privacy concerns, potentially violating patient confidentiality and exposing data to cyber threats. Existing approaches to address this often involve complex protocols or centralized data aggregation, which can still pose privacy risks or be computationally expensive. This paper tackles the problem of building an accurate and effective CDSS from distributed datasets while ensuring robust privacy protection for patient data.
Methods
The core of this work is the Privacy-Preserving Single Decision Tree (PPSDT) algorithm. It combines the well-established C4.5 decision tree algorithm with the Paillier homomorphic encryption scheme. Here's how it works:
- Distributed Data Handling: Instead of pooling raw patient data, each hospital prepares its local data to calculate attribute frequencies (f) required for decision tree construction.
- Homomorphic Encryption: These frequencies are then homomorphically encrypted using the Paillier cryptosystem. This allows computations to be performed on the encrypted data without decrypting it.
- Secure Aggregation: A central cloud server receives the encrypted frequencies from all participating hospitals. It then securely sums these encrypted values to obtain the aggregate frequencies for the entire distributed dataset. This aggregation is done without ever seeing the actual frequency values.
- Nonce for Enhanced Privacy: To prevent "semi-honest-but-curious" users (like other hospitals) from decrypting each other's data, a random nonce is generated by each hospital, added to the encrypted data, and then encrypted with the cloud's public key. The cloud decrypts the nonce and subtracts it from the aggregated data to restore the original values.
- Local Decision Tree Construction: After the cloud returns the aggregated, decrypted frequencies, each hospital can independently calculate the entropy and information gain for attributes. They then collaboratively select the best attribute to split the data, effectively building the same decision tree model locally.
- C4.5 Algorithm Integration: The PPSDT algorithm leverages the C4.5 algorithm's logic for selecting the optimal splitting attribute at each node of the decision tree, ensuring the standard decision tree construction process.
Datasets
The paper uses a dataset acquired from Ref. [37] for simulation and evaluation. For simplification, the "Temperature" attribute was removed, resulting in a dataset with five attributes: Nausea, Lumber pain, Urine pushing, Micturition pains, and Burning of urethra. The dataset was tested with two variations, DS1 and DS2, with DS2 having approximately 50% of its values changed compared to DS1. The dataset sizes varied from 10 to 120 tuples.
Key Insights and Ideas
- Decentralized Training, Centralized Aggregation (with Privacy): The approach cleverly distributes the initial data processing (frequency counting) to individual hospitals while using a cloud for secure aggregation, avoiding direct data sharing.
- Homomorphic Encryption as a Privacy Enabler: The use of Paillier homomorphic encryption is crucial, allowing computations on encrypted data, thus preserving the privacy of sensitive medical information throughout the model building process.
- Nonce for Preventing Collusion: The inclusion of a nonce mechanism is a smart addition to mitigate risks associated with semi-honest participants in a shared key environment.
- Local Model Ownership: Each hospital ends up with its own copy of the decision tree model, enabling offline diagnosis and further enhancing privacy by preventing patient symptoms from being transmitted over the network for classification.
Key Results
- Performance Improvement: The PPSDT algorithm outperformed the Naïve Bayes (NBC) algorithm from a previous study [9] by 46.67% in terms of run time.
- Dataset Size Independence: The average run time of the PPSDT model was found to be largely unaffected by the dataset size, remaining relatively stable between 14 and 16 seconds for dataset sizes ranging from 50 to 100 tuples.
- Homomorphic Encryption Overhead: Encryption and decryption times accounted for approximately 46% of the total run time, with average encryption taking around 10 seconds and decryption around 3 seconds.
- Key Size Impact: Increasing the homomorphic encryption key size (from 64 to 512 Bytes) did increase the run time, but the key value itself had no significant impact.
- Model Correctness: The generated decision trees were verified to be identical to those produced by the standard C4.5 algorithm on the combined dataset, confirming the correctness of the privacy-preserving approach.
Limitations and Future Work
- Scalability: The paper acknowledges that increasing the number of participating hospitals, features, or classes will increase the complexity and number of matrices to be summed at the cloud. The complexity is noted to grow with the number of attributes, classes, and attribute values.
- Future Work: The authors plan to incorporate additional security services like Message Authentication Code (MAC) and generalize the algorithm to handle more diverse dataset formats.
Summary updated