Public-Context Packing for Federated Haplotype Association

Haplotype tests look at the combination of variants that sit together on one copy of a chromosome, rather than at each variant alone. They find disease signals that single-variant genome-wide scans miss. They are also the tests that hospitals can least safely share in the clear, because rare multi-variant haplotypes identify individuals far better than single variants do. The obvious way to run them across institutions is to encrypt each site's haplotype count tables, add them up under encryption, and release only test statistics. That approach runs into a problem network engineers know well as encapsulation overhead. Every encrypted value pays a fixed cost, because a ciphertext is hundreds of bytes regardless of whether it carries one count or a thousand. Meanwhile a window of $L$ variants has up to $2^L$ possible haplotypes, and almost all of them are absent in any given cohort. The result is that most of the transmitted bytes carry encrypted zeros.

This note proposes to borrow the fix that constrained IoT networks use for bloated headers, called static context compression. In that scheme both ends agree offline, from public traffic traces, on a shared "context" that says which fields to expect and how many bits each needs. Only the residue then travels over the link. Our analogue is a per-window haplotype dictionary and per-block bit-width schedule learned from a public reference panel (1000 Genomes). Each site maps its phased haplotypes onto this public dictionary and packs the counts densely into as few ciphertexts as possible. Because the layout is public and fixed before any private data is touched, the packing itself reveals nothing about which rare haplotypes a site holds. The claim to test is that this cuts communication by orders of magnitude for windows long enough to matter biologically, while keeping most of the association power of a pooled plaintext haplotype test.

Core Claim

Secure federated association work to date runs single-variant scans. SF-GWAS combines multiparty homomorphic encryption with secure multiparty computation for biobank-scale mixed models. sPLINK secret-shares regression gradients. SAFETY pairs Paillier encryption with SGX enclaves for linkage and Hardy–Weinberg statistics. The garbled-circuit GWAS of Constable et al. computes two-party allele frequencies and $\chi^2$. In all of these each locus contributes a scalar or a small vector, so the question of how to lay out a sparse, exponentially sized category table inside ciphertexts never arises.

Our claim is that for haplotype tests, communication is governed by a packing term. Suppose a ciphertext costs a fixed $c$ bytes and carries $P$ plaintext bits. Suppose window $w$ is encoded with $K_w$ categories at $b_w$ bits each, where $b_w$ must hold the pooled count across $S$ sites and so is about $\log_2(n_{\max}+1)+\log_2 S$. Then the cost of the window is

$$\text{bytes}_w = c \left\lceil \frac{2 K_w b_w}{P} \right\rceil ,$$

with the factor 2 for separate case and control counts. Naive dense encoding sets $K_w = 2^L$. A public-context encoding sets $K_w$ to the number of haplotypes actually seen in the reference panel plus one overflow category. It also lets $b_w$ vary by block rather than using a global worst case. That second choice is the direct analogue of the rule in Fed-CVLC, which varies code length across packets rather than per element and uses power-law update magnitudes to cut federated traffic. Haplotype frequencies are similarly long-tailed, but our constraint is different: the bit widths must be fixed from public data so that they leak nothing.

Research Program

The dictionary is built from a public reference panel. For each sliding window we take the distinct phased haplotypes in 1000 Genomes. Optionally, we merge near-identical haplotypes with the position-weighted clustering of F_HapMiner, which groups haplotypes with more weight on markers near the tested position. This parallels the offline k-means rule generation over packet traces in Automated Header Compression in Constrained Networks.

The central difficulty is private haplotypes that are missing from the public panel. These are the rare ones that haplotype analysis most wants to see. Throwing them into a single overflow bucket discards that signal. We instead map each unseen private haplotype to the dictionary entry with which it shares the longest match around the window centre, computed locally with a positional Burrows–Wheeler index (a data structure for fast longest-match queries across many haplotypes) as in SHAPEIT4 and HP-PBWT. The rationale is that a rare haplotype usually sits on an ancestral background it shares with others. This is the same intuition that lets FiMAP find associations through identity-by-descent sharing, meaning stretches of chromosome inherited from a common ancestor. The mapping happens inside each site on plaintext and depends only on public dictionary entries. It therefore changes what is counted, not what is revealed.

Each site phases locally with SHAPEIT4 and encodes its case and control counts under the public layout. Sites pack counts from many windows into shared ciphertexts, and the counts are summed under additive homomorphic encryption. The per-window test statistic is computed inside the secure protocol, following SF-GWAS's split of linear work under homomorphic encryption and nonlinear work under multiparty computation. The first statistic is a $\chi^2$ test on the haplotype-by-status table; the second is a covariate-adjusted score test. Only statistics are released. This matters because Tanaka et al. show that released haplotype frequency tables allow membership inference with power up to 13.82 times that of single-variant attacks. The design therefore never decrypts count tables.

We then choose the window length $L$ explicitly as a power-per-byte trade-off. Longer windows capture more cis-haplotype signal but grow $K_w$ and dilute counts. This mirrors the finding of Razi et al. and Skatchkovsky and Simeone that a fixed per-unit overhead pushes the best block size upward. We will measure the curve empirically rather than assume it is convex.

Baselines

The naive reference point encrypts each of the $2^L$ case and control counts in its own ciphertext. This is what a straightforward port of per-locus secure aggregation would do, and it bounds the problem from above. We run it at the same key sizes, the same number of sites and the same windows, and report bytes and wall-clock. It is expected to be infeasible beyond small $L$, which we will confirm rather than assert.

The strongest naive competitor is dense packing: the full $2^L$ table packed tightly into ciphertexts with a single global bit width. For short windows this is a real threat, since a 10-variant window has only 1,024 categories. We give it identical cryptographic parameters and the same per-site thread budget. Beating it means lower total bytes at equal statistical output, and we will report the $L$ at which the two cross.

The strongest existing federated method on this data is SF-GWAS's single-variant pipeline. Its paper reports agreement of $r^2 > 0.99$ with plaintext REGENIE across 409,547 UK Biobank individuals in about six days, 4.6 hours on the AMD cohort (14 times faster than S-GWAS), and a 3–4 times reduction in communication. We re-run its published pipeline on the same simulated site split and count its bytes. Beating it here does not mean using fewer bytes, because single-variant scans will be cheaper. It means detecting haplotype associations that SF-GWAS misses at a communication cost within a stated multiple of its cost. No reported result was found on Lacuna for any federated haplotype association method, so there is no direct prior number to beat.

The accuracy ceiling is a pooled plaintext haplotype test on the combined data using the same windows. Our target is statistic correlation of at least 0.99 with this ceiling on dictionary-covered haplotypes, and a stated fraction of its power on simulated rare-haplotype effects. Three ablations isolate the key ingredient. The first replaces longest-match mapping with a single overflow bucket. The second replaces per-block bit widths with a global worst case. The third replaces the public dictionary with an oracle dictionary built from the pooled private data. The gap between the public and oracle dictionaries measures exactly what the public-context restriction costs.

Why not just…?

Why not just run federated single-variant GWAS, which already works at biobank scale? This is the most serious objection, and the answer rests on evidence rather than argument. FiMAP reports 3,442 identity-by-descent associations across six UK Biobank anthropometric traits, 62% of which remain significant after conditioning on GWAS tag variants. F_HapMiner reports a 9% to 130% power gain over single-locus transmission tests under rare-haplotype models. These results suggest real haplotype signal exists, but neither was measured in a federated setting. We therefore report, on real UK Biobank traits, how many windows our method flags that remain significant after conditioning on SF-GWAS's hits. If that number is negligible, the proposal fails on its own terms.

Why not just have each site run its haplotype test locally and meta-analyse the p-values? sPLINK shows that meta-analysis misses associations under imbalanced case-control splits on COPDGene that a joint analysis recovers. Meta-analysis also handles rare haplotypes poorly, because they may appear at only one site. Local haplotype meta-analysis is still cheap enough to include as a baseline, and we will run it under the same imbalanced splits.

Why not just gzip or quantize the tables before sending? Compression cannot shrink ciphertexts after encryption. Data-dependent compression before encryption, such as sending only the haplotypes a site observes, reveals the site's haplotype set, which is exactly the leakage Tanaka et al. exploit. The only compression that leaks nothing is one whose layout is fixed from public information, which is what the public context provides.

Why not just compute the union of haplotypes across sites privately and use that as the dictionary? This is a legitimate alternative. It recovers rare haplotypes that the public panel lacks, but it costs an extra secure protocol round and reveals the union. The oracle-dictionary ablation bounds how much it could gain. If that gain is large, we would adopt private union for the rare tail only and report the extra cost.

Proposed Experiments

The primary testbed follows SF-GWAS in splitting UK Biobank array data into simulated institutional sites, including imbalanced case-control splits. It uses 1000 Genomes as the only source of dictionaries and SHAPEIT4 for local phasing. Phenotypes are simulated with three kinds of effect: cis-acting two- and three-variant haplotype effects, rare-haplotype effects on a common background, and purely single-variant effects as a negative control. We then run real anthropometric traits for discovery.

Metrics are total transmitted bytes and ciphertext count per window and genome-wide, wall-clock time, correlation of statistics with the pooled plaintext test, power at a genome-wide significance threshold, and type I error under the null. We also run a leakage audit. It confirms that the public-layout encoding makes transmitted ciphertext counts independent of the private data, and it applies the Tanaka reconstruction attack to everything released. The Cystic Fibrosis family dataset, where F_HapMiner reports its power gains, gives a small real check that longest-match mapping keeps known rare-haplotype signal.

The decisive checks are threefold. First, the public-context method must beat dense packing in bytes by a growing margin as $L$ increases past about 10, while matching the pooled test on covered haplotypes. Second, longest-match mapping must recover a clear majority of the rare-haplotype power that the overflow bucket loses, measured against the oracle dictionary. Third, on real traits, some windows must survive conditioning on single-variant hits. If the first two checks hold and the third does not, the result is still useful: an efficient secure haplotype protocol, together with an honest negative result about its marginal value at array density.