Secure Genotype Imputation

Genotype imputation relies on the Li-Stephens model, a Hidden Markov Model (HMM) that models chromosomes as mosaics of reference haplotypes. In the secure setting, the HMM's forward-backward algorithm is implemented using oblivious transitions where the state probabilities are computed via secure comparisons and arithmetic operations, hiding which reference haplotype is being copied at any locus.

A foundational cryptographic method where a sensitive value (e.g., a genetic variant) is split into random shares distributed among multiple computing parties. No single share reveals anything about the original data. Reconstruction requires a qualified subset of parties to combine their shares. In secure genotype imputation, secret sharing ensures that the study cohort's genotypes and the reference panel's haplotypes remain provably hidden during computation. Common schemes include Shamir's Secret Sharing (based on polynomial interpolation) and additive secret sharing (using modular arithmetic).

A two-party secure computation protocol introduced by Andrew Yao. A function is represented as a boolean circuit. The circuit 'garbler' encrypts the truth table of each gate, and the 'evaluator' computes the output using oblivious transfer to obtain the correct encrypted input keys. The evaluator learns the final result but sees no intermediate values. For genotype imputation, garbled circuits excel at evaluating non-linear operations like comparison and matching logic in hidden Markov models, often combined with secret sharing for arithmetic-heavy phases in a mixed-protocol approach.

A fundamental cryptographic primitive where a sender inputs two messages, and a receiver selects and learns exactly one, with the sender remaining oblivious to the choice. OT is the essential glue for garbled circuits, enabling the evaluator to securely receive the encrypted wire labels corresponding to its private input bits. OT Extension protocols dramatically improve efficiency by using a small number of expensive base OTs to bootstrap a large number of fast, symmetric-key OTs, making large-scale secure imputation computationally feasible.

A direct application of secure multi-party computation to perform genome-wide association studies across distributed, private datasets. Multiple institutions can collaboratively identify single nucleotide polymorphisms (SNPs) statistically associated with a disease or trait without ever pooling or exposing their raw patient genotype and phenotype data. Secure GWAS protocols typically compute allele frequencies, contingency tables, and logistic regression models under encryption, outputting only the final aggregated association statistics. This overcomes the data-sharing bottleneck that limits statistical power in traditional GWAS.

A privacy-preserving protocol for calculating an individual's genetic susceptibility to a complex disease. The computation securely combines a patient's private genomic data (held by a clinic) with a proprietary risk model (held by a research lab or company) consisting of weighted effect sizes for thousands of variants. Using secret sharing and secure linear combination, the protocol outputs only the final polygenic risk score to the authorized recipient. Neither party learns the other's input: the lab's valuable model IP and the patient's sensitive genome remain mutually protected.

Pre-computed, secret-shared multiplication triples of the form (a, b, c) where c = a * b. These are generated in a preprocessing phase independent of the actual inputs. During the online phase, Beaver triples enable efficient, non-interactive multiplication of secretly shared values at the cost of a few openings and local operations. For secure genotype imputation, which involves heavy matrix multiplication and statistical computations, a large supply of Beaver triples generated via oblivious transfer or homomorphic encryption is critical for achieving practical performance.