Source-linked AI summary
Countering Gattaca: Efficient and Secure Testing of Fully-Sequenced Human Genomes (Full Version)
Pierre Baldi, Roberta Baronio, Emiliano De Cristofaro, Paolo Gasti, Gene Tsudik
TL;DR
The paper addresses privacy and computational challenges arising as fully sequenced genomes enable digital genomic applications. It analyzes paternity testing, personalized medicine, and genetic compatibility testing, then develops private-set-operation protocols that securely reproduce relevant in-vitro procedures and are practical today.
Problem
As genomic data becomes increasingly available and queried computationally, it remains unclear how to protect personal genomic information and conduct privacy-sensitive applications over fully sequenced genomes.
Method
The paper analyzes the privacy requirements of three genomic applications and constructs specialized protocols using PSI, PSI-CA, and APSI to replicate corresponding in-vitro operations securely.
Results
The protocols have sufficiently low online overhead to be practical today, and the privacy-preserving paternity protocol is less expensive in computation and communication than prior work.
Takeaways & Limitations
Secure in-silico versions of paternity, personalized medicine, and genetic compatibility tests can be designed to mimic state-of-the-art biological tests performed in hospitals and laboratories.
Takeaways & Limitations
A naive PSI-CA implementation over the full human genome is impractical on commodity hardware, with a single test estimated to require approximately 10 days.
Abstract
from arXiv · showhide
Recent advances in DNA sequencing technologies have put ubiquitous availability of fully sequenced human genomes within reach. It is no longer hard to imagine the day when everyone will have the means to obtain and store one's own DNA sequence. Widespread and affordable availability of fully sequenced genomes immediately opens up important opportunities in a number of health-related fields. In particular, common genomic applications and tests performed in vitro today will soon be conducted computationally, using digitized genomes. New applications will be developed as genome-enabled medicine becomes increasingly preventive and personalized. However, this progress also prompts significant privacy challenges associated with potential loss, theft, or misuse of genomic data. In this paper, we begin to address genomic privacy by focusing on three important applications: Paternity Tests, Personalized Medicine, and Genetic Compatibility Tests. After carefully analyzing these applications and their privacy requirements, we propose a set of efficient techniques based on private set operations. This allows us to implement in in silico some operations that are currently performed via in vitro methods, in a secure fashion. Experimental results demonstrate that proposed techniques are both feasible and practical today.
1. INTRODUCTION
Affordable full-genome sequencing could move genomic tests into computational settings, creating opportunities for personalized medicine alongside substantial privacy and security challenges. The paper analyzes three applications and develops specialized privacy-preserving protocols evaluated on commodity hardware.
- Motivation: Full-genome sequencing is becoming broadly available, enabling genome-based predictive, preventive, participatory, and personalized medicine.The paper links this trend to the prospect of genomes becoming part of every individual’s electronic medical record.
- Motivation: Genomic data creates unusual privacy risks because a genome uniquely identifies an individual and reveals ancestry, disease predispositions, and other traits.De-identification and aggregation are described as ineffective because the genome itself is an ultimate identifier.
- System setting: The paper frames genomic querying as an interaction between data centers storing genomes and agents or agencies seeking access to selected genomic information.Possible data-center granularities range from individuals to national or international repositories, with differing query permissions and privacy requirements.
- Research challenge: The main technical challenge is supporting genomic queries with low storage costs and short query times while satisfying transaction-specific security and privacy requirements.The paper notes that existing privacy-preserving querying methods do not scale to fully sequenced genomes.
- Applications: The paper studies paternity tests, personalized medicine, and genetic compatibility tests as privacy-sensitive applications of computational genomic testing.Its protocol designs are based on analyzing current in vitro procedures and their digital privacy requirements.
- Evaluation: Experiments on commodity hardware show that the proposed protocols are viable and practical today, with publicly available implementations.The authors emphasize that lower overhead alone is insufficient evidence of practicality, motivating direct experimental evaluation.
2. RELATED WORK
Prior work provides privacy-preserving computation for DNA searching, matching, sequence similarity, genomic queries, and selected tests, but generally does not address efficient fully sequenced-genome applications. The paper identifies scalability, error-resilience, and paternity-testing gaps motivating its protocols.
- Scope of prior work: Existing cryptographic work supports private searching, matching, similarity computation, and selected operations on genomic data, but its limitations remain relevant for full genomes.The related-work survey distinguishes general DNA protocols from application-specific genomic operations.
- Searching and matching DNA: Error-resilient string-searching protocols privately test whether a short template occurs within a DNA snippet using oblivious finite-state-machine execution.Communication complexity is O(n · (|Σ| + |Q|)).
- Searching and matching DNA: Secure pattern-matching protocols reveal pattern locations while protecting the underlying text, with one semi-honest homomorphic-encryption construction using O(m + n) communication and computation.The protocols operate on binary strings and patterns and disclose only specified outputs.
- Searching and matching DNA: Secure text-processing work combines garbled circuits, private keyword search, and OPRFs to compute functions such as CODIS, but assumes a threshold on pattern occurrences.Its keyword-search component is linear in |T|, while circuit count depends on the number of occurrences.
- Similarity of DNA sequences: Secure edit-distance and sequence-alignment techniques face substantial scalability limits, including 2GB circuits for 200-character strings and quadratic oblivious transfers.The cited approaches exploit dynamic-programming structure but remain constrained for longer strings.
- Open problems: The paper identifies three open problems: scaling from snippets to three-billion-nucleotide genomes, achieving error resilience without excessive overhead, and preventing input manipulation in privacy-preserving paternity tests.It targets fully sequenced genomes owned by individuals and focuses on paternity, personalized medicine, and genetic compatibility testing.
3. PRELIMINARIES
The preliminaries introduce biological representations and variation markers, cryptographic set-operation building blocks, homomorphic encryption, and adversarial-security models used by the proposed protocols.
- Biology background: Human genomes are encoded as double-stranded DNA composed of complementary chains built from nucleotides A, C, G, and T.The genome includes both genes and non-coding DNA sequences.
- Biology background: RFLP analysis compares restriction-fragment lengths produced by enzyme digestion, providing length information without revealing subsequence composition.RFLP is described as an early widely applicable DNA-profiling technique used in mapping, genotyping, forensics, paternity tests, and diagnostics.
- Biology background: SNPs are single-nucleotide differences, occurring approximately once per 1,000 human nucleotide pairs on average, and are associated with disease and treatment responses.They are presented as important genetic-variation markers for genomic medicine.
- Biology background: STRs are adjacent repeats of nucleotide patterns whose differing repeat counts can distinguish unrelated individuals.STR loci are targeted with sequence-specific primers and analyzed through resulting DNA fragments.
- Cryptographic building blocks: PSI, PSI-CA, and APSI provide privacy-preserving set intersection, intersection cardinality, and authorized intersection functionality for genomic protocols.PSI reveals the intersection to the Client, PSI-CA reveals its size, and APSI incorporates client-side authorizations.
- Cryptographic building blocks: Additively homomorphic encryption permits ciphertext multiplication to encode plaintext addition and ciphertext exponentiation to encode scalar multiplication.These properties allow encrypted sums to be computed without decrypting individual inputs.
- Security model: The paper’s security arguments use the semi-honest adversary model, while malicious-participant extensions for PSI, PSI-CA, and APSI are outside its scope.The adversarial model concerns protocol insiders; outside adversaries are excluded because standard network security techniques are assumed to mitigate them.
4. GENOME TESTING
The paper develops efficient privacy-preserving tests for fully sequenced genomes by tailoring private-set techniques to paternity, personalized medicine, and genetic compatibility applications. The approaches use domain-specific reductions and report practical accuracy, error resilience, and computational feasibility.
- Scope: Fully sequenced genomes motivate application-specific privacy-preserving tests rather than generic genomic computation.The paper focuses on paternity testing, personalized medicine, and genetic compatibility testing.
- Strawman approach: About 3 · 10^9 nucleotide positions make naïve PSI-CA impractical, with a single test estimated to require approximately 10 days.The naïve approach performs online computation over the entire genome, including modular exponentiations linear in input size.
- Strawman approach: Comparing a properly chosen 1% of the genome is reported to achieve accuracy comparable to analyzing the entire genome.The paper notes that available statistical knowledge does not identify exactly where the variable 0.5% occurs.
- Efficient RFLP-based PPGPT with PSI-CA: The proposed RFLP-based PPGPT builds a secure protocol from in vitro paternity-testing procedures and can also be adapted to SNP-based testing.The technique uses domain knowledge and avoids generic computation over the full genome.
- Efficient RFLP-based PPGPT with PSI-CA: RFLP-based testing provides about 99.999% accuracy, while its digital genome emulation cost is not significantly affected by the number of selected markers.The technique closely mimics the regulated in vitro procedure and supports increasing the number of markers to improve accuracy.
- Personalized Medicine: P3MT uses authorized private set intersection to let a pharmaceutical test a patient genome against an approved fingerprint without revealing unrelated genomic information.The pharmaceutical inputs a fingerprint and authorization, while the patient inputs her genome; the pharmaceutical learns whether the match is authorized.
- Personalized Medicine: P3MT and PPGCT are resilient to uniformly distributed sequencing errors because the client inputs are small and corresponding genome positions have extremely low error probability.PPGCT additionally prevents disclosure of other genomic information and which disease is being tested or carried.
5. SECURITY DISCUSSION
The protocols’ security is grounded in secure underlying PSI-family functionalities, with specific instantiations selected primarily for efficiency. Figure 4 specifies the common cryptographic inputs for the PSI construction used in the protocols.
- PSI construction: Figure 4’s PSI protocol uses common primes p and q with q | p − 1, a subgroup generator g, and hash functions H and H′ modeled as random oracles.All computation in the depicted construction is performed modulo p.
- PSI construction: The PSI protocol is presented in a simplified form for semi-honest security and serves as the building block selected for favorable communication and computation complexity.The construction can also be instantiated in the malicious model with a small constant additional overhead.
- Security reductions: The cryptographic building blocks can be treated as black boxes, while particular instantiations are chosen to maximize protocol efficiency.Security is preserved when the selected PSI, APSI, or PSI-CA construction provides the corresponding secure functionality.
- Security reductions: Security of PPGPT, P3MT, and PPGCT reduces to the security of their underlying PSI-CA, APSI, and PSI functionalities, respectively.The reductions are stated for semi-honest adversaries; PPGPT additionally uses a PSI-CA construction secure under the One-More-DH assumption in the Random Oracle Model.
6. CONCLUSIONS AND FUTURE WORK
The paper develops privacy-preserving protocols for three fully sequenced-genome applications and reports practical experimental overhead. It also identifies extensions including additional paternity markers, ancestry testing, probabilistic methods, and broader participant outputs.
- Conclusions: The paper proposes efficient constructions for paternity testing, personalized medicine, and genetic compatibility testing using PSI, PSI-CA, and APSI.The constructions target fully sequenced genomes and address the applications’ privacy and computational challenges.
- Results: Privacy-preserving paternity testing is significantly less expensive than prior work in both computation and communication.The comparison is stated at the protocol level rather than for a single reported benchmark value.
- Future work: Future work includes STR or SNP-based paternity testing, genetic ancestry testing, MinHash-based probabilistic testing, and extending paternity testing to both participants.These directions are listed as prospective extensions rather than completed contributions.