🌐 Privacy-Preserving Multi-Party Computation Health Query

Shamir Secret Sharing — Splitting a Value So No Single Party Ever Sees It

Secure multi-party computation (SMPC) begins with a deceptively simple cryptographic primitive: splitting a secret value into multiple random-looking shares such that any share alone reveals nothing, but a sufficient quorum of shares can reconstruct the original. Adi Shamir's (t,n)-threshold scheme (1979) is the workhorse construction, letting a hospital distribute a patient-count or lab-value statistic across several computing parties so that no single party — not even a majority minus one — can recover the raw number.

• Shamir (t,n)-threshold: Scheme (1979, polynomial interpolation)
• Information-theoretic: Security (below threshold t, zero leakage)
• 𝔽_p (prime finite field): Field (arithmetic mod large prime)
• Lagrange interpolation: Reconstruction (any t of n shares suffice)

How Shamir secret sharing encodes a value as a polynomial

Construction: To share a secret value s (e.g., a hospital's local count of patients meeting a case definition), the dealer:

1. Chooses a prime p larger than any possible secret or share value, defining arithmetic over the finite field 𝔽_p. 2. Constructs a random polynomial of degree t−1: f(x) = s + a₁x + a₂x² + ... + a_{t−1}x^{t−1} (mod p), where a₁...a_{t−1} are freshly random coefficients and f(0) = s. 3. Distributes n shares, one per computing party: share_i = (i, f(i)) for i = 1...n.

Why fewer than t shares reveal nothing: Given any t−1 points (i, f(i)), infinitely many degree-(t−1) polynomials pass through them — one for every possible value of the secret s = f(0). This is not merely computationally hard to break, it is information-theoretically impossible: even an adversary with unlimited computing power gains zero information about s from t−1 or fewer shares. This is strictly stronger than the computational security guarantees offered by AES or RSA.

Reconstruction with t or more shares: Any t parties can pool their shares and use Lagrange interpolation to recover f(0) = s exactly: s = Σ_{i=1}^{t} f(i) · Π_{j≠i} [ (0−j) / (i−j) ] (mod p)

Additive homomorphism enabling computation ON shares: Critically for MPC, Shamir shares are additively homomorphic: if party i holds share f(i) of secret s1 and share g(i) of secret s2, then f(i)+g(i) is a valid share of s1+s2 — meaning parties can locally add their shares and, ONLY AT THE END, jointly reconstruct the sum, without any intermediate value ever being exposed. This is exactly the mechanism used to compute a cross-hospital SUM (e.g., total patients with a diagnosis) without any hospital's individual count ever leaving encrypted form. Multiplication requires an additional interactive round (Beaver triples) since the product of two degree-(t−1) polynomials has degree 2(t−1), requiring degree reduction — this is why secret-sharing-based MPC protocols like SPDZ and BGW treat multiplication as materially more expensive than addition.

Yao's Garbled Circuits — Evaluating Any Function Without Revealing Inputs

Andrew Yao's garbled circuit protocol (1986) solved the original two-party secure computation problem — the famous 'Millionaires' Problem': how can two people determine who is richer without revealing their actual wealth? The technique generalizes to any function expressible as a Boolean circuit, making it directly applicable to health queries like 'does this patient's genotype plus that hospital's cohort exceed a risk threshold' without either party learning the other's raw input.

• Yao 1986: Origin (Turing Award laureate, FOCS '86)
• Oblivious transfer (OT): Core primitive (1-out-of-2 OT per input wire)
• Boolean gates (AND/XOR): Circuit representation (any function → circuit)
• Garbler + Evaluator: Parties (classic 2PC; extends to N parties)

Garbling a circuit gate-by-gate and oblivious transfer for input delivery

Setup — expressing the query as a circuit: Any health-query function (e.g., "is the combined biomarker threshold exceeded") is first compiled into a Boolean circuit of AND and XOR gates operating on the parties' input bits. This is analogous to how a CPU executes any program as a sequence of logic gates — here, health-relevant comparisons and arithmetic are unrolled into a static gate list.

Garbling (Party 1, the 'garbler'): For every wire in the circuit, the garbler generates two random cryptographic labels — one representing bit 0, one representing bit 1 — that look like meaningless random strings to anyone without the mapping. For every gate, the garbler encrypts the gate's truth table: each of the 4 input-label combinations encrypts the output label corresponding to the correct gate result, then the four resulting ciphertexts are randomly shuffled (garbled) so their order leaks nothing about which corresponds to which input combination.

Oblivious transfer — delivering the evaluator's own input labels: The evaluator (Party 2) needs the labels corresponding to ITS OWN input bits, but the garbler must not learn which bits the evaluator holds, and the evaluator must not learn the label for the bit it does NOT have (which would leak the garbler's masking scheme). This exact requirement — 'transfer exactly one of two secrets, sender doesn't know which was picked, receiver learns nothing about the other' — is solved by 1-out-of-2 Oblivious Transfer (OT), typically instantiated efficiently via OT extension protocols (Ishai-Kilian-Nissim-Petrank) that amortize a small number of expensive public-key OTs into millions of cheap symmetric-key OTs.

Evaluation: With its own input labels (from OT) and the garbler's input labels (sent directly, since they're meaningless without the garbler's private mapping), the evaluator walks the garbled circuit gate by gate: at each gate, it tries decrypting each of the four garbled ciphertexts with its two known input labels — exactly one decrypts successfully, yielding the output wire label — and passes that forward as an input to the next gate layer, until the final output labels are reached and mapped back to a 0/1 result via a public output-label table.

Why neither party learns the other's input: At no point does either party ever see the OTHER party's raw input bit or intermediate wire value in the clear — only opaque labels flow through evaluation, and only the FINAL circuit output (the intended query answer) is ever decoded to a meaningful bit. This makes garbled circuits well suited to health-query use cases requiring exact Boolean/arithmetic logic (threshold comparisons, exact matching) rather than purely additive aggregation, where secret sharing (Stage 1) is typically more efficient.

Homomorphic Encryption — Arithmetic Directly on Ciphertexts

Homomorphic encryption (HE) takes a conceptually different approach from secret sharing and garbled circuits: rather than splitting a value across parties or garbling a circuit interactively, a single party encrypts its data once, and ANY party — even an untrusted compute provider — can perform arithmetic directly on the ciphertext, producing an encrypted result that, when decrypted by the data owner, equals the correct answer computed on the original plaintext. Microsoft SEAL, one of the most widely deployed open-source HE libraries, implements the leading schemes used in health-data pilots today.

• Paillier (1999): Partially HE (PHE) (addition only, efficient)
• Gentry 2009 breakthrough: Fully HE (FHE) (first working FHE construction)
• Microsoft SEAL: Production library (implements BFV and CKKS schemes)
• Approximate real-number arithmetic: CKKS use case (ideal for means, variances, ML inference)

From Paillier addition to Gentry's fully homomorphic breakthrough, and SEAL in practice

Partially homomorphic encryption — Paillier cryptosystem (1999): The Paillier scheme supports one operation homomorphically: given ciphertexts E(m1) and E(m2), anyone can compute E(m1+m2) without decrypting either — simply by multiplying the ciphertexts together under Paillier's modular arithmetic (the "addition under encryption via multiplication of ciphertexts" property). This alone is enough to let an untrusted aggregator sum encrypted per-hospital patient counts and hand the encrypted total back to a party holding the decryption key — a common building block in early privacy-preserving health-statistics pilots. Its limitation: no homomorphic multiplication, so only linear aggregate statistics (sums, means, weighted sums) are directly supported.

Fully homomorphic encryption — Gentry's 2009 breakthrough: Craig Gentry's 2009 dissertation (STOC 2009) constructed the first scheme supporting BOTH homomorphic addition AND multiplication, meaning any circuit (any computable function) can in principle be evaluated on ciphertexts. The key innovation was "bootstrapping": HE ciphertexts accumulate noise with every operation, and once noise exceeds a threshold the ciphertext becomes undecryptable; bootstrapping homomorphically evaluates the decryption circuit itself to refresh a noisy ciphertext into a fresh low-noise one, at significant computational cost, enabling arbitrarily deep computation.

Modern schemes and Microsoft SEAL: Microsoft SEAL (open-sourced 2018) implements two practically important post-Gentry schemes: • BFV (Brakerski/Fan-Vercauteren): exact integer arithmetic — ideal for counts, exact aggregate statistics where no approximation error is tolerable. • CKKS (Cheon-Kim-Kim-Song, 2017): approximate arithmetic over real/complex numbers with controlled precision loss — ideal for statistical computations like mean survival time, variance, or evaluating a linear/logistic regression model on encrypted patient features, since it natively supports the fixed-point-like real-number operations these require.

Computational cost: HE operations are dramatically more expensive than plaintext arithmetic — a single homomorphic multiplication can be 1,000–100,000× slower than its plaintext equivalent, and ciphertexts are far larger than plaintexts (expansion factors of 10–50×). This is why most production health-data HE pilots restrict themselves to shallow computations (a handful of additions/multiplications — e.g., a linear model or an aggregate statistic) rather than deep neural network inference, and why leveled/partially-homomorphic schemes (bounded multiplicative depth, no bootstrapping) are preferred over full bootstrapped FHE whenever the query is known in advance to be shallow.

Computing Mean Survival Time and Prevalence Across Hospitals Without Pooling Data

The practical payoff of these primitives is a concrete class of health queries: N hospitals, none willing or legally able to share patient-level records, jointly compute a pooled statistic — mean survival time in a rare cancer cohort, disease prevalence across combined catchment populations, or a pooled odds ratio — such that only the final aggregate is ever revealed, to all participants simultaneously, with mathematically provable guarantees that no intermediate patient-level value was exposed to any party at any point.

• Pooled mean survival time: Example query (across N independent cohorts)
• Secret sharing for sums: Protocol choice (HE for weighted/nonlinear stats)
• Aggregate only: Output exposure (no per-hospital value ever revealed)
• 3 – 12 hospitals: Typical N in pilots (consortium-scale, not internet-scale)

End-to-end protocol for a cross-hospital pooled statistic

Worked example — pooled mean survival time across hospitals:

Goal: compute mean(survival_time) across the UNION of patients at hospitals H1...HN, where each hospital only holds its own local cohort and none is willing to disclose individual patient survival times or even its own local mean (which itself could be disclosive for small cohorts).

Step 1 — local aggregation: each hospital Hi computes two LOCAL sums entirely on its own data: Si = Σ(survival_time) over its cohort, and Ci = its patient count. Neither of these local values leaves the hospital in the clear.

Step 2 — secret-share the local sums: each hospital splits Si and Ci into Shamir shares (Stage 1) and distributes one share of each to every party in the computation mesh (which may be the hospitals themselves acting as co-computing parties, or a separate small set of non-colluding compute nodes).

Step 3 — homomorphic summation across parties: because Shamir shares are additively homomorphic, each computing party locally sums the shares it received: it now holds one share of S_total = ΣSi and one share of C_total = ΣCi — again, no party has learned any individual hospital's S_i or C_i.

Step 4 — joint reconstruction of ONLY the final ratio: the parties combine their shares of S_total and C_total (Lagrange interpolation) to reveal S_total and C_total — and from these, and ONLY these, the mean = S_total / C_total. Division is typically handled by revealing the two sums and computing the ratio in the clear, since division is expensive to do homomorphically and revealing two aggregate sums (rather than any per-hospital value) is an intentional, pre-agreed disclosure boundary.

Prevalence queries follow an identical additive pattern: each hospital secret-shares its (case_count, population_count) pair; the mesh sums shares; only the pooled prevalence = Σcase_count / Σpopulation_count is reconstructed.

Why this differs from naive federated averaging: Simply asking each hospital to report its local mean and averaging those means is NOT equivalent (it weights hospitals equally regardless of cohort size, and it discloses each hospital's local mean — potentially disclosive for small or unusual cohorts). The MPC protocol above preserves the mathematically correct pooled statistic while disclosing strictly less information than even reporting local means would.

The Overhead Tax — What SMPC and FHE Actually Cost, and Where They Have Been Piloted

Secure multi-party computation and homomorphic encryption are not free lunches: every guarantee of "the raw data never left the building" is purchased with real computational and bandwidth overhead relative to plaintext computation — often one to three orders of magnitude. Understanding these costs is essential to deciding when MPC is the right tool versus when simpler federated aggregation or a Trusted Research Environment suffices, and several genomics and clinical-outcomes pilots have now demonstrated where the crossover point lies in practice.

• ~2–10×: Secret sharing overhead (for addition-heavy protocols)
• ~100–1000×: Garbled circuit overhead (for complex Boolean comparisons)
• ~1000–100,000×: FHE overhead (per homomorphic multiplication)
• Genomics MPC: Notable pilot domain (cross-biobank rare-variant association)

Quantifying overhead and surveying real deployments

Where the overhead comes from:

• Communication rounds: secret-sharing multiplication and garbled-circuit evaluation both require network round-trips between parties for every non-linear operation — latency-bound protocols suffer badly on high-latency (e.g., cross-institution, cross-country) networks, sometimes dominating total runtime more than raw computation does. • Ciphertext expansion: HE ciphertexts are typically 10–50× larger than the plaintexts they encrypt, and garbled circuit truth tables multiply data volume by roughly 4× per gate before compression — all of this must be transmitted between parties. • Cryptographic operation cost: modular exponentiation (Paillier), lattice-based ring arithmetic (BFV/CKKS), and symmetric encryption of every gate's truth table (garbled circuits) are all far more expensive per operation than native CPU arithmetic on plaintext integers/floats.

Practical benchmarks (illustrative, protocol- and hardware-dependent): • Simple additive aggregation (sums, counts, means) via secret sharing: often only 2–10× slower than plaintext — genuinely practical at the scale of a hospital consortium (single-digit to low-dozens of parties, thousands to low-millions of records). • Threshold/comparison logic via garbled circuits: 100–1000× overhead is common, since every comparison bit requires its own set of garbled AND/XOR gates plus OT rounds — feasible for one-off or infrequent queries, not real-time interactive use. • Deep or repeated FHE computation (e.g., evaluating a multi-layer model): can reach 1,000–100,000× overhead per multiplicative layer, especially once bootstrapping is required — this is why most production health-data HE pilots restrict themselves to shallow linear/logistic models rather than deep networks.

Real-world pilots: • Genomics MPC studies: multi-biobank rare-variant burden and GWAS-style association testing has been piloted using MPC (e.g., collaborations building on the Sharemind and MPC-based genomic frameworks explored in academic consortia) to test genotype-phenotype associations across institutions that cannot legally pool raw genotype data, particularly for rare diseases where any single biobank is underpowered alone. • Multi-hospital outcome studies: secure aggregation protocols have been piloted for pooling COVID-19 and other outbreak outcome statistics (case counts, mean time-to-event) across hospital networks during periods when data-sharing agreements could not be executed quickly enough for the clinical urgency involved. • Genome-wide association meta-analysis without raw genotype pooling has also been demonstrated using HE-based secure summary-statistic aggregation, avoiding the well-documented re-identification risks of even SHARING summary GWAS statistics naively (membership-inference attacks on GWAS summary stats are themselves a known vulnerability that motivated some of this work).

The practical rule of thumb used by most production teams: reach for Shamir secret sharing when the query reduces to sums/means/counts (cheap, ~single-digit-multiplier overhead); reach for garbled circuits when the query needs exact threshold/comparison logic on a bounded number of inputs; reserve full FHE (SEAL's CKKS/BFV) for cases where an untrusted third-party compute provider must do the work and cannot be trusted with interactive protocol participation at all — accepting substantially higher computational cost as the price of that stronger trust model.