TL;DR
This paper presents a novel approach to patient risk stratification in healthcare using secure multi-party computation (MPC). By combining Yao's garbled circuits with Cuckoo hashing, they achieve highly efficient and provably secure cross-institution data analysis, enabling accurate identification of high-utilizing patients and calculation of comorbidity scores without compromising patient privacy.
What Problem Does This Paper Address?
Healthcare systems increasingly recognize the importance of patient risk stratification to optimize resource allocation and improve care quality. However, a significant challenge arises from data fragmentation: patient information is often siloed across multiple healthcare institutions. This makes it difficult to accurately identify high-risk patients based on metrics like comorbidity and past healthcare utilization, as a complete picture requires data from all providers. Traditional methods for linking this data often rely on a trusted third-party "honest broker," which introduces security risks, time delays, and complex policy arrangements. This paper aims to overcome these limitations by developing secure and efficient MPC protocols for cross-institution risk stratification.
Methods
The core of this work lies in developing two MPC protocols: PSI-CI (for Charlson Comorbidity Index calculation) and PSI-HU (for High Utilizer identification). These protocols are built upon Yao's garbled circuits, a well-established cryptographic technique for secure computation. To enhance performance, they integrate Cuckoo hashing, a fast and efficient hash-based data structure, into the Private Set Intersection (PSI) phase. PSI is used to securely identify common patients across institutions.
The process involves:
- Secure Patient Matching (PSI): Institutions A and B use Cuckoo hashing (Institution A) and bin-and-ball hashing (Institution B) with agreed-upon hash functions to create data tables. A PSI protocol then securely identifies patients present in both datasets without revealing non-matching information.
- Use-Case Specific Computation: Once common patients are identified, the protocols securely compute the desired metrics. For PSI-CI, this involves combining disease data to calculate the Charlson comorbidity index. For PSI-HU, it involves aggregating ED visit data to identify high utilizers.
- Optimization: To further improve efficiency, the authors employ an optimization where the use-case function is computed only once for matched patients, or if no match is found, it's computed using the first patient's payload from each bin. This significantly reduces comparisons.
Datasets
The authors utilize a synthetically generated Chicago city-wide dataset created using the Synthea platform. This dataset comprises approximately 2.7 million patients and 141 million encounters. For evaluation, they specifically use data from two institutions with 120,666 and 109,072 patients, respectively, simulating a real-world cross-institution scenario. The synthetic data is designed to mimic realistic patient demographics and health records, with no inherent privacy restrictions.
Key Insights and Ideas
- MPC is Practical for Healthcare: The paper demonstrates that MPC, once considered theoretical, is now a viable and performant technology for complex clinical use cases like risk stratification.
- Cuckoo Hashing is a Game-Changer for PSI: Integrating Cuckoo hashing dramatically speeds up the PSI process, reducing patient comparison complexity from O(N²) to O(1.56N), leading to significant time savings.
- Eliminating the "Honest Broker": The MPC approach removes the need for a trusted third party, enhancing security and streamlining data exchange.
- Balancing Generality and Performance: The proposed two-component building blocks (PSI and analytics) allow for both generalizability to various clinical tasks and optimized performance for specific use cases.
- Security Guarantees: The protocols are provably secure against computationally bounded adversaries in the semi-honest setting, which is the standard assumption for cross-institution data analytics.
Key Results
The developed protocols achieve impressive performance:
- Running Time: PSI-CI completes in approximately 3 minutes, and PSI-HU in about 7 minutes, on large datasets. This is a significant improvement over previous MPC applications in healthcare.
- Memory Usage: The protocols are memory-efficient, with PSI-CI using 2.9 GB and PSI-HU using 3.5 GB, making them suitable for standard computing resources.
- Network Traffic: Network communication is primarily dependent on circuit size, with PSI-HU requiring more resources due to its more complex circuit.
- Comparison to Prior Work: The paper shows an order-of-magnitude improvement in performance compared to earlier circuit-based MPC applications for simpler tasks, despite handling significantly larger datasets and more complex analytics.
Limitations and Future Work
- Limitations:
- The Cuckoo hashing scheme has a small failure rate (approx. 1/240) where a patient might not fit into the hash table. The authors suggest re-generating the table in such rare cases.
- The current approach relies on the availability of unique identifiers for patient linkage, which are not always present in real-world scenarios. However, they note that deterministic linkage methods can be optimized with Cuckoo hashing.
- Future Work:
- Develop protocols for heterogeneous data domains (genomics, mobile health, social determinants of health).
- Expand payload sizes to represent more complex clinical data elements.
- Explore MPC for multi-party scenarios.
- Investigate memory-friendly payload designs for more sophisticated clinical data models.
- Conduct direct comparisons with existing trusted third-party approaches for PPRL.
Summary updated