Fully homomorphic encryption lets you compute directly on encrypted data but is thousands of times slower than plaintext, and the usual speedup — packing many values into one ciphertext and doing SIMD-style vector math — has a nasty catch, because the only way to move a value from one vector slot to another is to rotate the whole ciphertext, and rotations are as costly as multiplies, so tools that aggressively vectorize can actually run SLOWER than scalar; Coyote (Purdue) is a compiler that treats rotations as the real cost, co-optimizing where each value sits in the vector AND how the operations are scheduled, deliberately keeping small subcircuits in a single lane (rotation-free) and vectorizing only across them, and grouping data so one rotation serves many operations — cutting rotation counts to single digits and running arbitrary encrypted circuits up to 3.5x faster than scalar FHE.
The argument in one glance
-
Problem
Computing on encrypted data works, but it is agonizingly slow
Fully Homomorphic Encryption (FHE) is a near-magical capability: you can run a computation directly on ENCRYPTED data and get an encrypted result that, when decrypted, equals what you would have gotten on the plaintext — so a cloud can compute on your data without ever seeing it. The catch is speed. Homomorphic operations on ciphertexts are orders of magnitude slower than the same operations on plaintext, which is what keeps FHE from being used everywhere it would be valuable. Anything that recovers some of that lost performance directly widens where privacy-preserving computation is practical.
-
What people did
Use FHE's built-in SIMD: pack many values into one ciphertext and vectorize
FHE schemes have a saving grace: a single ciphertext can PACK thousands of plaintext values into separate vector "slots" (8192 in the scheme Coyote targets), and one homomorphic operation applies to all slots at once — SIMD-style batching. So the natural way to speed up an FHE program is to VECTORIZE it: find operations that do the same thing to different data and pack them into a single vectorized operation. Prior FHE compilers (CHET, Porcupine, SLP-based vectorizers) do exactly this, aggressively grouping isomorphic instructions into vectors.
-
Why it fell short
Moving data between slots needs a rotation, and rotations can cost more than they save
Vectorizing hits a wall unique to FHE: the only way to move a value from one vector slot to another is to ROTATE the entire ciphertext (a cyclic shift of all slots), and a rotation is roughly as expensive as a homomorphic MULTIPLY — about ten times an addition. In ordinary SIMD hardware, shuffling lanes is nearly free; in FHE it is one of the most expensive operations there is. So when you vectorize aggressively, you pay for all the rotations needed to line operands up in matching slots — and those rotations can cost more than the SIMD saves. The paper's example is damning: naively vectorizing ((a+b)*(c+d))+((e+f)*(g+h)) costs 3.2, while plain scalar execution costs only 2.5. Aggressive vectorization made the program SLOWER.
-
This paper's idea
Treat rotations as the real cost, and co-optimize layout with scheduling
Coyote (Purdue — Malik, Sheth, Kulkarni) is a compiler that vectorizes ARBITRARY FHE circuits while minimizing the thing that actually costs: rotations. Its core realization is that two decisions — where each value sits in the vector (data layout) and when each operation runs (scheduling) — jointly determine how many rotations you need, so they must be solved TOGETHER. It splits the circuit into SUBCIRCUITS, locking each into a single lane so no rotations happen inside it, and vectorizes only ACROSS subcircuits — deliberately NOT over-vectorizing. It chooses input layouts so that one rotation of the packed vector serves many operations at once. On the running example this yields cost 2.3, beating both scalar and naive vectorization. Across benchmarks it cuts rotations to single digits and runs up to 3.5x faster than scalar FHE.
Why this problem is worth solving
FHE could transform privacy — computation on data you never
decrypt — and the only thing standing in the way is performance,
which is why squeezing speed out of it matters so much. The most
promising lever is the scheme’s built-in parallelism, its
the ability of a modern
FHE ciphertext to hold not one encrypted number but a whole VECTOR
of them, in thousands of independent “slots” (8192 in Coyote’s
target scheme). A single homomorphic operation — one add, one
multiply — applies to all slots simultaneously, exactly like a
SIMD vector instruction on a CPU. This is FHE’s answer to its own
slowness: if you can arrange your computation so that many
independent operations become one vectorized operation across the
slots, you amortize the enormous per-operation cost over thousands
of data elements at once
But FHE’s vectors are not like a CPU’s, and the difference is the
whole problem. On a CPU, rearranging data within a vector — picking
out lane three, shuffling lanes around — is cheap. In FHE, the only
primitive for moving data between slots is a
a homomorphic operation that
cyclically shifts EVERY slot of a ciphertext by the same amount — so
to bring a value from slot 5 into slot 2, you rotate the whole
vector by 3, and everything else moves with it. There is no way to
touch a single slot in isolation. Crucially, a rotation is one of
the most expensive FHE operations, roughly the cost of a
homomorphic multiply and about ten times the cost of an addition.
So whenever a vectorized computation needs two values that live in
different slots to interact, it must pay for a rotation to align
them — and the number of rotations, not the number of arithmetic
operations, becomes the dominant cost of vectorized FHE code
What people did before, and where it broke
- Scalar FHE (no vectorization). Run the circuit one ciphertext per value. Simple and rotation-free, but it throws away all of FHE’s SIMD parallelism, leaving the huge per-operation cost un-amortized — the baseline everyone is trying to beat.
- Aggressive vectorizers (CHET, Porcupine, SLP-based). Pack every isomorphic instruction into a vector to maximize SIMD width. For arbitrary circuits this generates a flood of rotations to align operands, and because rotations are as costly as multiplies, the vectorized code can be slower than scalar — 3.2 versus 2.5 on the paper’s example.
- Hand-optimized FHE kernels. An expert lays out data and schedules operations to minimize rotations by hand. Fast, but labor-intensive, error-prone, and per-kernel — it does not scale to arbitrary programs, which is exactly the automation gap a compiler should fill.
- Layout-only or schedule-only optimization. Optimize data placement, or instruction scheduling, but treat them as separate passes. This misses that the two are coupled — a layout is only good relative to a schedule and vice versa — so optimizing one in isolation leaves rotations on the table.
- The gap. No compiler vectorized arbitrary FHE circuits while making rotations the first-class cost AND co-optimizing layout and scheduling together, applying vectorization selectively rather than maximally. Coyote does all of this, and even correctly declines to vectorize when it would not pay.
How Coyote works
Make rotations the cost, keep subcircuits scalar, and co-optimize layout with schedule
-
Cost the circuit by rotations, not arithmetic new
Coyote's objective is a cost model where a rotation and a multiply weigh 1 while an addition or subtraction weighs 0.1, reflecting real FHE latencies. Crucially, rotations are counted by DISTINCT amount per epoch: many cross-lane moves that need the same shift amount cost only one rotation, because the whole vector rotates once. Minimizing this is the whole game.
-
Split into subcircuits and lock each to one lane (quotient) new
Rather than vectorize globally, Coyote contracts circuit edges to carve the program into SUBCIRCUITS, and locks all the operations within a subcircuit into a single vector lane so no rotation ever happens inside it. This "quotient" collapses each subcircuit to one vertex, preventing the over-vectorization that would demand alignment rotations — vectorization happens only ACROSS subcircuits, in parallel lanes.
-
Co-optimize layout and schedule together new
Because where a value sits (layout) and when an operation runs (schedule) each determine the other's rotation needs, Coyote solves them jointly, not as separate passes. It automatically packs the circuit's inputs into vectors — honoring any packing constraints — and chooses the in-vector layout to make subsequent rotations line up and share.
-
Search: annealing inside, best-first outside new
A two-layer search navigates the coupled space. The inner loop uses simulated annealing (tens of thousands of rounds) to place subcircuit vertices into vector slots for a given quotient. The outer loop runs a best-first search over possible quotient graphs, contracting on the order of 150-200 edges, guided by the rotation cost model to decide how to carve subcircuits.
-
Align isomorphic operations with an ILP new
Within the chosen structure, an integer linear program schedules the scalar instructions — a variable per instruction for the time slot it runs — so that isomorphic operations at the same circuit depth line up into shared vector operations. It iteratively tightens a schedule-height constraint until a timeout, trading a little optimality for tractability.
-
Generate vector code, and know when not to vectorize new
Finally Coyote topologically schedules the vector instructions, inserting only the rotations and blends actually required, and emits FHE vector IR. Because its objective is honest about cost, it correctly leaves circuits scalar when vectorization would not pay — on non-profitable cases it lands near 1.0x rather than making things worse.
The idea
Optimize the cost that actually dominates, even when it means distrusting a universally-good optimization. Vectorization is one of the most reliable speedups in all of computing, so the instinct to pack every isomorphic instruction is deeply ingrained — and in FHE it is a trap, because the cost that dominates is not arithmetic but ROTATIONS, and aggressive packing buys SIMD width by spending rotations it never counts. Coyote’s foundational move is to make rotations the objective and treat arithmetic as nearly free, which flips the whole optimization: sometimes the right answer is to vectorize LESS. This is the measure-the-true-cost discipline the site returns to constantly — counting tile intersections instead of points, whole-accelerator area instead of one MAC, throughput instead of FLOPs — but with an unusually sharp edge: it shows that a transformation which is nearly always beneficial can be actively harmful when the cost structure changes, so the real skill is knowing which cost your target actually charges you for.
Co-optimize the decisions that are coupled, and apply the optimization selectively. Two ideas do the heavy lifting. First, data layout and instruction scheduling are entangled — a layout is only good relative to a schedule and vice versa — so Coyote refuses to optimize them in separate passes and searches them jointly, the same co-optimize-coupled-decisions logic the heterogeneous-serving page uses when it folds placement and routing into one program. Second, Coyote deliberately keeps subcircuits scalar and vectorizes only across them, applying vectorization selectively rather than maximally — the same restraint the optimal-inlining page discovers when it finds production compilers are systematically too eager and the optimum inlines LESS. In both cases the lesson is that a good transformation over-applied becomes a cost, and the win comes from a principled sense of where to stop.
Share the expensive operation across many uses. The subtle lever in Coyote’s cost model is that rotations are counted by distinct AMOUNT, not by arc — many cross-lane moves that need the same shift cost a single rotation, because one rotation of the whole vector serves all of them. So Coyote lays data out to make rotations SHARED: group related values (both matrices into one packed vector) so that rotating once yields useful alignments for several operations at once, where scattering the same values would force separate rotations. This is the amortize-one-operation-across- many-consumers move the site just met in the task-parallel page’s multicast — one memory fetch serving many tasks — applied here to one rotation serving many alignments, and it is why grouping beats scattering by more than a factor of two in rotation count.
The example that makes vectorization backfire
((a+b)*(c+d))+((e+f)*(g+h)), three ways
The paper's running example. Costs weight rotations and multiplies at 1, additions at 0.1.
Step 1 of 5
The tempting SIMD move
The expression has four isomorphic additions — (a+b), (c+d), (e+f), (g+h) — that all do the same thing to different data. Every prior FHE vectorizer sees this and packs them into one vector addition, then packs the two multiplies, chasing maximal SIMD width. It looks like a textbook vectorization win.
the four adds are isomorphic; so are the two multiplies — irresistible to an aggressive packer SIMD width is the metric these tools maximize, ignoring what it costs to line the operands up
Why it works
- Rotations, not arithmetic, dominate FHE cost, and each is about ten times an addition → Coyote makes rotation count the optimization objective → it optimizes the quantity that actually governs performance instead of chasing SIMD width.
- Aggressive packing needs rotations to align operands, which can cost more than the SIMD saves → Coyote keeps each subcircuit locked to one lane and vectorizes only across subcircuits → it avoids the alignment rotations that make naive vectorization backfire.
- Data layout and instruction schedule each determine the other’s rotation needs → Coyote searches them jointly rather than in separate passes → it finds low-rotation solutions that independent optimization would miss.
- Many cross-lane moves can share one rotation amount, costing a single rotation → Coyote lays out data so related values rotate together → grouping cuts rotation counts by more than half versus scattering.
- The objective is honest about when vectorization does not pay → Coyote declines to vectorize non-profitable circuits → it stays near 1.0x on those instead of the slowdowns aggressive tools produce.
What it costs
- The search is expensive and not always optimal. The outer best-first search runs only 150-200 iterations because each lane-placement call is costly, and the inner annealing and the ILP both sacrifice optimality (the ILP tightens a constraint only until a timeout), so large circuits need decomposition into blocks and the search does not always reach the global optimum.
- Experts still beat it on large circuits. On bigger benchmarks, hand-optimized code can be 50-66% faster by finding schedules with one or two fewer rotations (a 5-point distance kernel: Coyote 15.3s versus an expert’s 5.5s) — the compiler closes most but not all of the gap.
- Arithmetic circuits only, fully unrolled. Coyote requires straight-line arithmetic circuits with no control flow that depends on encrypted data; conditionals and loops must be fully evaluated and unrolled, so only statically-known execution paths are supported.
- Compiled kernels may not compose. Coyote chooses non-canonical input layouts to minimize rotations, so two kernels it compiles separately may not chain together without manual layout specification — composing circuits is not automatic.
- The cost model is scheme-specific. The roughly 10-to-1 multiply-to-add weighting is tuned empirically for the target BFV parameters; a different FHE scheme or parameter set (for example CKKS) would need recalibration, and its trade-offs could differ.
The evaluation
FHE circuits on the BFV scheme (8192 slots) — matrix multiply, convolution, point-cloud distance, dot product, and random polynomial trees — compiled by Coyote and compared against scalar FHE and against hand-optimized expert schedules, measuring speedup, rotation count, and compile time.
Vectorizing an FHE circuit
| Property | Scalar FHE (no vectorization) | Aggressive vectorizers (CHET, Porcupine) | Coyote |
|---|---|---|---|
| What it optimizes | |||
| Rotations generated | |||
| Vectorization strategy | None | ||
| Can it make things worse? | |||
| Speedup over scalar | Reference |
Check yourself
Check your understanding
1. Prior FHE compilers aggressively vectorize by packing every isomorphic instruction, yet the paper shows this can make a program slower than scalar (3.2 vs 2.5). Predict why a normally-reliable optimization backfires here.
2. Coyote insists on solving data layout and instruction scheduling TOGETHER rather than as separate compiler passes. Predict why treating them independently would leave performance on the table.
3. Coyote deliberately keeps each subcircuit locked into a single lane (rotation-free) and vectorizes only ACROSS subcircuits, rather than packing as much as possible. Predict the general principle this restraint illustrates.
4. Coyote's cost model counts one rotation per distinct shift AMOUNT, and it lays out data so related values (e.g., both matrices of a product) share a vector. Predict why this sharing matters so much.
Sources
- ACM DL: Coyote: A Compiler for Vectorizing Encrypted Arithmetic Circuits — ASPLOS 2023 (full text read via the ACM PDF; no arXiv preprint).
- Galois: Coyote overview — accessible summary from a collaborating lab.