Ultra-Fast Homomorphic Encryption Models enable Secure Outsourcing of Genotype Imputation

Miran Kim, Arif Harmanci, Jean-Philippe Bossuat, Sergiu Carpov, Jung Hee Cheon, Ilaria Chillotti, Wonhee Cho, David Froelicher, Nicolas Gama, Mariya Georgieva, Seungwan Hong, Jean‐Pierre Hubaux, Duhyeong Kim, Kristin Lauter, Yiping Ma, Lucila Ohno‐Machado, Heidi J. Sofia, Yongha Son, Yongsoo Song, Juan Ramón Troncoso-Pastoriza, Xiaoqian JiangbioRxiv 2020 · DOI

TL;DR

This paper introduces the first fully secure genotype imputation method using ultra-fast homomorphic encryption (HE). It allows researchers to outsource computationally intensive genotype imputation without compromising data privacy, achieving comparable accuracy and competitive performance to existing non-secure methods.

What Problem Does This Paper Address?

Genotype imputation is a crucial step in genomic analysis, like Genome-Wide Association Studies (GWAS), for filling in missing genetic data. While outsourcing this task can save costs and leverage powerful computing resources, it raises significant privacy concerns. Sharing raw genotype data with untrusted third-party imputation services risks exposing sensitive personal information, potentially leading to discrimination or stigmatization. Existing secure methods often fall short in practicality or computational efficiency, leaving a gap for a truly secure and performant solution.

Methods

The core innovation is the application of ultra-fast homomorphic encryption (HE) techniques to enable secure genotype imputation. HE allows computations to be performed directly on encrypted data, meaning the genotype data remains encrypted throughout the entire imputation process – in transit, at rest, and crucially, during analysis. The researchers implemented five different imputation pipelines utilizing three leading HE schemes: BFV, CKKS, and TFHE. These pipelines involve two main steps: (1) building plaintext imputation models using publicly available population panels, and (2) securely evaluating these models on encrypted genotype data. The encrypted results are then sent back to the data owner for decryption.

Datasets

The study utilized publicly available datasets:

  • Illumina Duo 1M version 3 variant loci: Used to identify tag variants.
  • 1000 Genomes Project phased genotypes: Used for both training imputation models and as a population panel for evaluation. Specifically, chromosome 22 was used for detailed benchmarking.

No new benchmarks were introduced, but the study provides a comprehensive comparison against existing state-of-the-art non-secure imputation methods like IMPUTE2, Minimac3, and Beagle.

Key Insights and Ideas

  • Privacy-Preserving Outsourcing is Achievable: The paper demonstrates that computationally intensive tasks like genotype imputation can be securely outsourced using HE, offering a practical solution for privacy-sensitive genomic data.
  • HE is No Longer Just Theoretical: Contrary to the common perception of HE being impractical, this work shows its viability for real-world, resource-intensive applications.
  • Comparable Performance: Secure HE-based imputation achieves accuracy levels very close to, and sometimes even slightly better than, non-secure methods, with competitive or even superior time and memory requirements.
  • Modular Design: The separation of plaintext model building and secure evaluation allows for flexibility and independent work between model builders and data owners.

Key Results

  • Accuracy: HE-based methods provided full genetic data security with comparable or only slightly lower accuracy (e.g., a 2-3% decrease in some cases) compared to non-secure methods.
  • Performance:
    • Time: Secure imputation evaluation took less than 25 seconds for 80,000 target variants, scaling linearly with the number of variants. This is comparable to or even faster than some non-secure methods in certain aspects.
  • Memory: All secure methods required less than 15 GB of main memory, with most using less than 5 GB, making them feasible on commodity hardware.
  • Scalability: The methods demonstrated linear scaling with the number of target variants, suggesting suitability for genome-wide and population-wide computations.
  • Practicality: The study provides five different implementations and workflows, making the developed methods accessible for the computational genomics community.

Limitations and Future Work

  • Model Retraining: The current approach requires retraining imputation models when tag variants are updated, unlike HMM-based methods that can adapt more seamlessly. The authors suggest that a-priori training for new array platforms can mitigate this.
  • Accuracy Trade-off: While accuracy is comparable, there is a slight decrease in some scenarios, which the authors deem acceptable given the significant privacy benefits.
  • Future Work: The authors foresee further optimizations for linear models and suggest exploring deep neural networks for imputation within HE frameworks. They also propose adapting these secure evaluation techniques for other privacy-sensitive genomic analyses, such as rare variant association tests. The publicly available codebases are intended to serve as a reference for future secure genomic data analysis developments.

Summary updated

Abstract

ABSTRACT Genotype imputation is a fundamental step in genomic data analysis such as GWAS, where missing variant genotypes are predicted using the existing genotypes of nearby ‘tag’ variants. Imputation greatly decreases the genotyping cost and provides high-quality estimates of common variant genotypes. As population panels increase, e.g., the TOPMED Project, genotype imputation is becoming more accurate, but it requires high computational power. Although researchers can outsource genotype imputation, privacy concerns may prohibit genetic data sharing with an untrusted imputation service. To address this problem, we developed the first fully secure genotype imputation by utilizing ultra-fast homomorphic encryption (HE) techniques that can evaluate millions of imputation models in seconds. In HE-based methods, the genotype data is end-to-end encrypted, i.e., encrypted in transit, at rest, and, most importantly, in analysis, and can be decrypted only by the data owner. We compared secure imputation with three other state-of-the-art non-secure methods under different settings. We found that HE-based methods provide full genetic data security with comparable or slightly lower accuracy. In addition, HE-based methods have time and memory requirements that are comparable and even lower than the non-secure methods. We provide five different implementations and workflows that make use of three cutting-edge HE schemes (BFV, CKKS, TFHE) developed by the top contestants of the iDASH19 Genome Privacy Challenge. Our results provide strong evidence that HE-based methods can practically perform resource-intensive computations for high throughput genetic data analysis. In addition, the publicly available codebases provide a reference for the development of secure genomic data analysis methods.
BibTeX
@misc{kim2020ultra,
  author = {Miran Kim and Arif Harmanci and Jean-Philippe Bossuat and Sergiu Carpov and Jung Hee Cheon and Ilaria Chillotti and Wonhee Cho and David Froelicher and Nicolas Gama and Mariya Georgieva and Seungwan Hong and Jean‐Pierre Hubaux and Duhyeong Kim and Kristin Lauter and Yiping Ma and Lucila Ohno‐Machado and Heidi J. Sofia and Yongha Son and Yongsoo Song and Juan Ramón Troncoso-Pastoriza and Xiaoqian Jiang},
  title = {{Ultra-Fast Homomorphic Encryption Models enable Secure Outsourcing of Genotype Imputation}},
  year = {2020},
  doi = {10.1101/2020.07.02.183459},
  howpublished = {bioRxiv},
}
Figure