Private Genome Analysis through Homomorphic Encryption

Miran Kim, Kristin E. LauterBMC Medical Informatics Decis. Mak 2015 · DOI

TL;DR

This paper presents a practical approach to performing genomic analyses on encrypted data using homomorphic encryption (HE). It introduces efficient HE-based algorithms for Genome-Wide Association Studies (GWAS) and DNA sequence comparison, demonstrating their feasibility and comparing the performance of two prominent HE schemes: BGV and YASHE.

What Problem Does This Paper Address?

The increasing availability of large-scale genomic datasets, while promising for medical research, raises significant privacy concerns. Sharing or processing this sensitive data, even in anonymized forms, risks genetic disease disclosure or discrimination. This paper addresses the challenge of enabling secure genomic analysis in untrusted environments, like cloud platforms, without compromising individual privacy. The core problem is to perform complex computations on encrypted genomic data without ever decrypting it, ensuring that the data owner's secret key is never exposed.

Methods

The paper proposes novel evaluation algorithms for two key genomic tasks:

  • Genome-Wide Association Studies (GWAS): They focus on privately computing minor allele frequencies (MAFs) and the $\chi^2$ test statistic. Their approach leverages homomorphic encryption to perform additions and multiplications on encrypted genotype data, allowing for the aggregation of allele counts and subsequent statistical calculations.
  • DNA Sequence Comparison: This involves privately computing the Hamming distance and an approximate Edit distance between encrypted DNA sequences. They adapt existing algorithms to work with homomorphically encrypted data, utilizing bit-wise operations and specialized circuits for efficiency.

A significant contribution is the adaptation and comparison of these algorithms with two practical HE schemes: the BGV scheme (Gentry, Halevi, and Smart) and the YASHE scheme (Bos, Lauter, Loftus, and Naehrig). They also utilize batching techniques to parallelize computations across multiple data points within a single ciphertext, significantly improving efficiency.

Datasets

The paper uses datasets for evaluation that are relevant to the iDASH Privacy & Security challenge:

  • Task 1 (GWAS): A dataset consisting of 200 case group individuals (from the Personal Genome Project - PGP) and 200 simulated control group individuals (based on haplotypes from the CEU population of the HapMap Project).
  • Task 2 (DNA Sequence Comparison): Two individual genomes randomly selected from the PGP.

The paper does not introduce new benchmark datasets but rather uses existing data to evaluate their proposed methods.

Key Insights and Ideas

  • Practical HE for Genomics: The paper demonstrates that homomorphic encryption, previously considered computationally prohibitive for complex tasks, can be practically applied to real-world genomic analyses.
  • Batching is Crucial: The use of batching techniques is highlighted as a key enabler for achieving efficient computations, allowing for parallel processing of multiple data points within a single ciphertext.
  • Trade-off Between Schemes: A clear trade-off emerges between BGV and YASHE. BGV generally offers better performance for deep circuits (like Edit distance), while YASHE might be more efficient for shallower computations (like MAFs and $\chi^2$ tests).
  • Encoding Matters: The choice of encoding for genomic data (e.g., integer representation for genotypes) significantly impacts the efficiency of homomorphic operations.

Key Results

The paper presents quantitative results comparing the performance of BGV and YASHE for both tasks.

  • Task 1 (GWAS):
    • For MAF computation, YASHE showed faster evaluation times (e.g., 1.63s for BGV vs. 0.01s for YASHE with specific parameters).
  • For $\chi^2$ test computation, BGV was slightly faster in evaluation (e.g., 11.61s vs. 1.61s).
  • Overall, YASHE generally had faster key generation and encryption times.
  • Task 2 (DNA Sequence Comparison):
    • BGV significantly outperformed YASHE in evaluation times for both Hamming distance and Edit distance computations, especially for larger sequence sizes (e.g., 5K and 10K). For 10K sequences, BGV's evaluation was around 29.39s for Hamming and 40.86s for Edit distance, while YASHE took 68.31s and 134.87s respectively.
  • BGV also had considerably faster key generation times.

Limitations and Future Work

  • Noise Management: While HE schemes handle noise growth, it remains a critical factor. The paper mentions that larger parameters are needed to ensure correctness, which can impact performance.
  • Computational Cost: Despite improvements, HE operations are still computationally intensive compared to plaintext computations. The paper notes that YASHE's performance can be limited by costly key switching operations.
  • Future Work: The authors suggest exploring further optimizations and potentially hybrid approaches to balance security and performance. They also hint at the possibility of using YASHE for low-degree computations where its advantages might be more pronounced. The paper also implicitly points to the need for more efficient HE schemes or hardware acceleration for widespread adoption in genomics.

Summary updated

BibTeX
@inproceedings{kim2015private,
  author = {Miran Kim and Kristin E. Lauter},
  title = {{Private Genome Analysis through Homomorphic Encryption}},
  booktitle = {BMC Medical Informatics Decis. Mak},
  year = {2015},
  doi = {10.1186/1472-6947-15-s5-s3},
}
Figure