Secure multi-party computation (MPC) lets several hospitals compute jointly over genomes that none of them is willing to reveal. To do this it compiles a program into a fixed circuit in which every branch is evaluated and the results are combined with selectors, so the execution path leaks nothing. Compilers that do this automatically from ordinary C, such as Smaug, assume that every loop in the program has a single entry point. They break on irreducible loops, meaning loops that can be entered at more than one place. Such loops are common in hand-tuned C that uses goto and early exits, and in code after optimizers such as gcc -O2 thread jumps. Genomic kernels written for speed have exactly this shape: seed-and-extend alignment with early termination, k-mer scanners that break on ambiguous bases, and VCF parsers written as jump-table state machines.
We propose a targeted compiler pass with two parts. First, it finds the irreducible regions in a single linear-time traversal. Second, it lowers only those regions to a "dispatch loop": a public-bounded loop that carries a secret one-hot record of which block is active and evaluates the region's blocks under selectors. Everything else stays on the existing structured path. The same straight-line output also serves a second purpose. Rotational cryptanalysis asks whether rotating a cipher's input bits by $\gamma$ positions predictably rotates its output. It has no tool for code that branches. Once branches become selectors driven by all-zero or all-one masks, rotation commutes with them exactly, and the open question shrinks to a probability calculation. We use this to audit the lightweight hash functions built from additions, rotations and XORs (ARX) that private genomic matching uses to turn DNA strings into fixed-length tokens.
Core Claim
Irreducible control flow can be compiled to oblivious circuits at a cost that grows linearly in the number of loop entry points, avoiding the exponential code duplication of node splitting. The pass is a small extension of a dominance-based compiler, not a rewrite. The flattened form also gives a sound way to compute how rotational symmetry survives data-dependent branches, provided the analysis respects the finding that chained additions are not independent events.
The pass is meant to be a secondary win. If ordinary node splitting followed by Smaug matches it on real genomic code, we will say so. In that case the contribution becomes the benchmark, the measurement of how unstructured genomic code actually is, and the rotational audit.
Where the pieces come from
The gap is documented by the compiler work. Smaug compiles LLVM intermediate code with mixed public and secret branch conditions into Yao and GMW circuits. It reports 570× lower circuit depth than COMBINE on a histogram benchmark. Its flattening, however, rests on dominance relations that irreducible loops violate. Differential assertion checking hits the same wall from the verification side: its loop-to-tail-recursion conversion is only efficient for reducible graphs. Compiling business processes untangles multi-entry workflow loops by duplicating nodes or state, which is the classical fix we compare against.
The detection step comes from A New Algorithm for Identifying Loops in Decompilation. It finds loop headers and re-entry points in one depth-first traversal in $O(N + kE)$ time, where $N$ is the number of nodes, $E$ the number of edges, and $k$ an "unstructuredness coefficient". Across 11,526 real control-flow graphs it measured average $k<1.5$. That statistic cuts both ways. It means our pass is rarely triggered, and it also means node splitting may be cheap, which is the main threat we must test.
The genomic workloads come from iDASH with ObliVM, which handled allele frequency, χ² tests and set-union cardinality. It sidestepped alignment and hashed variable-length strings into fixed bitstrings, and it wrote programs in a structured domain-specific language rather than C.
The rotational analysis supplies both a method and a constraint:
- Rotational Cryptanalysis of ARX shows that XOR and rotation preserve rotational pairs exactly and that addition preserves them with a probability fixed by $\gamma$ and the word size.
- Rotational Cryptanalysis of ARX Revisited shows that chained additions violate the independence assumption. For 25 chained additions at $\gamma=1$ the true probability is $2^{-109.6}$, against a naive $2^{-35.4}$. The BLAKE2 distinguisher falls from 12 rounds to 7 as a result.
- Analysis of BLAKE2, Practical Cryptanalysis of PAES and the Midori64 invariant subspace attack show that symmetry survives many rounds when round constants are dropped or weak. Dropping or weakening constants is exactly the temptation when trimming a primitive for circuit cost.
Any audit we build must reproduce the revised numbers rather than the older ones. Otherwise it is wrong.
Research Program
The dispatch lowering. The single-pass loop finder marks each irreducible region $R$, with blocks $B_1,\dots,B_m$ and entry headers $h_1,\dots,h_k$. Outside $R$, Smaug's passes run unchanged. Inside $R$, we emit a loop with a public step bound $T$. The bound counts block visits, and the programmer or a profile supplies it, as MPC already requires for any loop. Each step evaluates every block under a selector taken from a secret one-hot vector $a\in\{0,1\}^m$. It then computes the next $a$ from the successor edges, using the block's own branch conditions.
The gate cost per step is the sum of the block sizes plus $O(m)$ selectors. Node splitting produces a reducible graph whose size can grow exponentially in $k$ when entries overlap. The price of dispatch is that $T$ counts block visits rather than loop trips, so circuit depth can increase. Measuring this depth-versus-size trade-off is a primary result, not a footnote.
Program-counter-style oblivious execution is a known general idea. What is new is confining it to the regions the linear-time finder identifies, and leaving the reducible bulk to the dominance-based compiler. The pass is implemented as an LLVM pass in front of Smaug's pipeline. Correctness is checked differentially against the plaintext program on 1000 Genomes inputs.
The rotational audit on flattened circuits. After flattening, a branch on a one-bit condition $c$ becomes
$$\mathrm{sel}(c,a,b) = (C \wedge a) \vee (\neg C \wedge b),$$
where $C$ is $c$ copied to every bit position. An all-zero or all-one word is unchanged by rotation, so
$$\mathrm{sel}(c,a,b)\lll\gamma = \mathrm{sel}(c,\,a\lll\gamma,\,b\lll\gamma).$$
This holds exactly whenever the two runs of a rotational pair compute the same condition bit. The probability that a rotational pair crosses a flattened branch therefore reduces to the probability that the conditions agree. Conditions in genomic code are mostly comparisons, and a comparison is a subtraction whose borrow chain is correlated with neighbouring additions. We therefore group each comparison with its adjacent addition chain and evaluate the group jointly in the spirit of Lemma 2, never as a product of independent factors.
The audit propagates rotational pairs through the gate-level output and reports a probability bound per path segment. On reduced word sizes (8 and 16 bits) it is checked by exhaustive enumeration and by sampling.
The genomic twist that makes the audit matter. DNA packed two bits per base turns repeats into rotational pairs. Take a short tandem repeat whose period divides the word length. Sliding its k-mer window by one base produces the previous word rotated by two bits, and a homopolymer is unchanged by rotation. Rotational attacks normally require the attacker to construct such input pairs. Repeat-rich DNA supplies them for free. Short tandem repeats are also forensic identifiers.
We will measure whether constant-reduced ARX token hashes leak repeat structure through relations among their outputs. This matters only in settings where tokens are revealed, as in Bloom-filter or token-matching designs, and only for primitives without strong constants or under related keys. We state that scope plainly. Standard primitives with their full constants are expected to pass, and the audit should confirm it.
Baselines
The naive reference point is full unrolling with every branch evaluated. We run it, with a generous budget, on the irreducible regions after converting them by hand into equivalent nested if chains. It is the simplest correct strategy and sets the gate-count and depth ceiling.
The strongest existing compiler is Smaug itself. On reducible workloads we run it unchanged, and its published 570× depth advantage over COMBINE on the histogram benchmark is the number we must not degrade. Our pass must leave reducible code byte-identical. On irreducible code we report Smaug's behaviour as is, whether failure or fallback.
The most dangerous competitor is classical node splitting followed by Smaug. It is fair because it is what a practitioner would try first, and because real code has low $k$. Both pipelines get the same LLVM front end, the same Smaug back end, the same MPC protocol (Yao and GMW) and the same hardware.
For hand-structured code we compare against ObliVM-style rewrites of the same algorithms. That paper reports compiler output only 1–2% larger than hand-optimized circuits, and uses 40 AND gates for allele frequency and 7,763–14,443 gates for χ². These are the reference figures for the iDASH tasks. No reported result was found on Lacuna for MPC compilation of irreducible control-flow graphs or for oblivious genomic alignment, so those comparisons are new measurements.
An ablation applies dispatch lowering to the whole program rather than only to the regions the finder identifies. This isolates whether targeting matters.
Beating the baselines means the following. On irreducible regions, our pipeline must use fewer AND gates than node splitting plus Smaug, at no more than a stated depth penalty. It must match Smaug exactly elsewhere. It must come within a small margin of the hand-structured ObliVM versions.
For the audit, the baseline is the independence-assumption calculation used before the revision. The audit beats it if it reproduces $2^{-109.6}$ for 25 chained additions and the 7-round BLAKE2 bound from the revisited paper. On toy-size branching programs, its bounds must agree with exhaustive enumeration where the independence estimate does not.
Why not just…?
Why not just split nodes and hand the result to Smaug? This is the real threat. Average $k<1.5$ suggests that duplication is usually mild, and node splitting is the standard untangling method in the business-process work. Its worst case is exponential, but whether genomic kernels reach that worst case is an empirical question. We will plot gate count against $k$ and against the size of overlapping entry regions across the whole benchmark. If node splitting matches dispatch on every real workload, we will recommend it and report the measured unstructuredness of genomic code as the finding.
Why not just rewrite the genomic kernels by hand in a structured language like ObliVM? The iDASH results show that hand-structured code compiles almost optimally. Restructuring is, however, expert labour, and it is exactly what kept that competition away from alignment. Our comparison against hand-structured versions measures what automation costs. A gap above a few percent would weaken the case for automation.
Why not just use AES or full-strength ARX hashes and skip the rotational audit? For unmodified primitives with their constants intact, that is the right answer, and the audit should simply confirm it. The audit earns its place only for constant-reduced or round-reduced variants adopted to save gates. PAES and Midori64 show those reductions can be fatal. AES S-boxes, meanwhile, cost far more AND gates in Boolean circuits than additions do. We will report AND-gate cost and audit results side by side, so a designer can see what each saved gate costs in security.
Why not just share summary statistics instead? Summary-statistic imputation is powerful for association work. It cannot perform alignment, repeat genotyping or exact cross-cohort linkage computations, which SAFETY and SVAT require raw-level computation for. Our workloads are chosen from that class.
Proposed Experiments
Workloads. The benchmark combines three sources:
- the Smaug suite, including string matching, histogram and private set intersection;
- the iDASH tasks: allele frequency, χ² and sequence distance;
- new C kernels with naturally unstructured control: banded Smith-Waterman with early termination, seed-and-extend with
gotoexits, canonical k-mer and minimizer selection, and a jump-table VCF record parser.
Each kernel is compiled at -O0 and at -O2, so we capture both irreducibility written by hand and irreducibility introduced by the optimizer. Inputs are drawn from the 1000 Genomes populations used by SAFETY and SVAT.
Metrics. We record AND-gate count, circuit depth, compile time, peak memory, MPC wall-clock time, and output equality with plaintext.
Decisive check for the compiler. The thesis fails if, on the irreducible kernels, node splitting plus Smaug comes within 10% of dispatch in AND gates without worse depth. In that case we drop the compiler claim.
Decisive checks for the audit. We run three in order:
- Reproduce the revised chained-addition probability and the 7-round BLAKE2 bound.
- Match exhaustive enumeration on 8- and 16-bit toy ARX programs containing comparison branches. The independence-assumption estimate is expected to fail here.
- On repeat-rich 1000 Genomes regions, measure output rotational correlation of constant-free versus constant-bearing toy ARX token hashes. Leakage should appear only in the constant-free variant, and only at offsets matching the repeat period.
References
- Smaug: Modular Augmentation of LLVM for MPC
- Differential assertion checking
- Compiling business processes: untangling unstructured loops in irreducible flow graphs
- A New Algorithm for Identifying Loops in Decompilation
- iDASH Secure Genome Analysis Competition Using ObliVM
- Rotational Cryptanalysis of ARX
- Rotational Cryptanalysis of ARX Revisited
- Analysis of BLAKE2
- Practical Cryptanalysis of PAES
- Invariant Subspace Attack Against Midori64 and The Resistance Criteria for S-box Designs
- SAFETY: Secure gwAs in Federated Environment through a hYbrid Solution
- SVAT: Secure outsourcing of variant annotation and genotype aggregation