Moving Encrypted Inference Between Clouds at Its Cheapest Points

Fully homomorphic encryption (FHE) lets a server compute on data it cannot read. Each value travels as a large encrypted polynomial, and every multiplication adds noise that must eventually be "refreshed" by an expensive operation called bootstrapping. FHE has an unusual property for cloud deployment. Because the server never sees plaintext, the compute provider does not need to be trusted. In principle, any provider is as good as any other. That should make encrypted inference the easiest workload to keep free of vendor lock-in, the situation where an application becomes so tied to one provider's services and hardware that leaving is impractical. In practice the opposite happens. The fastest FHE implementations are hand-specialized to one vendor's accelerator, as in Adapting AlphaEvolve to Optimize Fully Homomorphic Encryption on TPUs. Moving encrypted state between providers is also feared to be ruinous: A Systematic Comparison of Encrypted Machine Learning Solutions for Image Classification measured about 56 GB of traffic for one HE-Transformer prediction.

This note proposes a compiler and placement layer that treats the size of an encrypted value as something the compiler controls. In the common CKKS scheme, a ciphertext is stored as a stack of residue polynomials, one per remaining multiplication "level". Each multiplication consumes a level and shrinks the ciphertext. A value just before bootstrapping can be several times smaller than the same value just after. We therefore claim the following. If the compiler that already decides where to bootstrap also decides where encrypted work may cross a provider boundary, it can place those crossings at low-level points and drop levels early on purpose. Cross-provider execution then becomes cheap enough to be a real option instead of a theoretical one. The paired claim is that, even where splitting a single request never pays, the same cost model gives an exact, measurable price for switching providers. That price is dominated by one-time upload of the evaluation keys (the public material the server needs to compute on a client's ciphertexts). It is far smaller than the "cloud gravity" intuition from Mapping Cross-Cloud Systems: Challenges and Opportunities suggests.

Core Claim

The quantity that decides whether encrypted work should move is the byte size of the ciphertext at the cut, and that size is a compiler decision, not a constant. For a CKKS ciphertext with ring degree $N$, $\ell$ remaining levels, and machine word size $w$ bytes per residue coefficient, the size is approximately

$$ S(\ell) = 2N(\ell+1)w . $$

This is the standard two-polynomial representation with one residue per remaining modulus. Moving a value from provider $a$ to provider $b$ at level $\ell$ then costs roughly $S(\ell)/B_{ab}$ seconds and $S(\ell)\,p_{a}$ dollars. Here $B_{ab}$ is the measured bandwidth between the two providers and $p_a$ is the source provider's per-byte egress price.

We fold this edge cost into the bootstrap-placement problem that Orion already solves. Orion splits the network's computation graph into regions that each have one entry and one exit, and finds the cheapest bootstrap placement as a shortest path. Its graph nodes carry per-level compute costs. We give each node a backend label, such as CPU on provider A, GPU on provider B, or TPU on Google Cloud. Edges get a transfer term $S(\ell)$ whenever the backend label changes, and the solver minimizes

$$ T + \lambda C , $$

where $T$ is end-to-end latency, $C$ is dollars per inference, and $\lambda$ is a user-chosen price of time. The ingredient no prior system has is coupling between the two decisions. A cut placed just before a bootstrap, preceded by the early modulus dropping that EVA introduced as Eager ModSwitch, ships the smallest possible ciphertext to the provider that bootstraps fastest.

Relation to Prior Work

Two FHE compilers supply the method we reuse. EVA compiles a vector-arithmetic graph and automates rescaling and modulus switching for CKKS on Microsoft SEAL. Orion compiles PyTorch models, packs convolutions, and places bootstraps via its region-wise shortest path. Both target a single CPU process. Neither has any notion of a backend, a provider, or a network. We keep their level-management machinery and add backend labels and transfer costs. Porcupine shows that synthesis can find better small kernels. That work operates below our level and is orthogonal.

Hardware specialization motivates the problem rather than solving it. AlphaEvolve's TPU work reports CKKS rotation falling from 4854 to 3714 µs and multiplication from 6340 to 5359 µs on the CROSS library. The SoK on FHE accelerators and cuHE document similar backend-specific gains on GPUs and other hardware. These gains are real, and each binds the user to one stack. This is the "least common denominator" dilemma Elkhatib describes: portable layers give up exactly these accelerators. Our answer is not a common denominator. We lower one shared graph to several native kernel libraries and let the cost model choose among them.

On the orchestration side, TORCH deploys containerized services across Kubernetes, Docker Swarm, and OpenStack from TOSCA models. SeBS-Flow transcribes one workflow description into three providers' serverless orchestrators. Both treat the workload as opaque. SeBS-Flow is also a constraint on our design. It found Azure Durable Functions spending 495.5 s orchestrating 13.5 s of ExCamera compute. Fine-grained serverless fan-out of FHE operations is therefore likely to lose, so we deploy long-lived containers through a TORCH-style descriptor and treat serverless only as a stress case. Finally, the image-classification comparison motivates the measurement gap: its evaluation was confined to one LAN and explicitly left wide-area and multi-cloud behaviour open.

Research Program

The work proceeds in three stages.

Build the portable layer. We extend Orion's intermediate graph with backend labels and write three lowerings from it: SEAL-style CPU, a GPU library in the cuHE family, and the CROSS TPU kernels. We keep each library's native fast paths instead of a shared slow path. The compiled artifact, the evaluation keys, and a TOSCA deployment descriptor together form the unit that moves between providers.

Calibrate the cost model. On each backend we profile per-level costs of addition, multiplication, rotation, and bootstrapping. Between each provider pair we measure bandwidth and current egress prices, and we check that $S(\ell)$ predicts the bytes actually sent.

Run the partitioner as a placement oracle. For each model and each value of $\lambda$, it returns either a single-backend plan or a cut plan. It also computes the switching cost of migrating the whole deployment, which is mostly key upload. From that it derives the break-even number of requests after which a cheaper provider pays for the move.

The analysis has two outcomes, and either is worth publishing. If cut plans beat the best single backend on some models and prices, we will characterize when: bootstrap-heavy, deep networks with large compute-to-ciphertext ratios are the likely winners. If they never do, the result is still a quantified rule, "place whole requests, and move only to switch providers", together with the measured switching cost that makes lock-in a number rather than a fear.

Baselines

The naive reference point is Orion-compiled inference on a single general-purpose CPU virtual machine on one provider. This is the setting in which Orion reports 8.98 hours for single-threaded ResNet-50 on ImageNet, and on ResNet-20 for CIFAR-10 it reports a 2.38× speedup over Fhelipe. We run it multithreaded on the same instance family used elsewhere, so the comparison isolates placement and not thread count.

The strongest competitor is whole-request execution on the single fastest backend: the same compiled graph, lowered entirely to the TPU kernels or entirely to the GPU library, whichever is faster for that model. This is the "accept lock-in" option the AlphaEvolve result argues for. Its kernel-level reference numbers are the reported CROSS figures of 3714 µs per CKKS rotation and 5359 µs per multiplication. We found no reported end-to-end encrypted ResNet result on TPU on Lacuna, so we will measure it ourselves. Both this baseline and our system use identical kernels, identical CKKS parameters, and the same tuning budget per backend. A cut plan beats it only if it lowers $T+\lambda C$ at a $\lambda$ a practitioner would plausibly choose, with the improvement exceeding run-to-run variance across repeated trials on different days.

The third baseline is the plain container answer. Each FHE library runs whole requests inside Docker on several providers, as TORCH deploys microservices, and requests go to whichever provider is cheapest. It has portability but no visibility into ciphertext levels.

The ablation that isolates our key ingredient runs the same partitioner with the transfer cost fixed at the fresh-ciphertext size $S(L)$ and with early modulus dropping disabled before cuts. If the level-aware version does not find cheaper plans than this level-oblivious version, the central idea fails.

Why not just…?

Why not just run inside a hardware enclave? The LAN comparison found TF-Trusted on Intel SGX at 0.14 s per Model Z image versus 549 s for HE-Transformer. For workloads where trusting a chipmaker is acceptable, enclaves win and we do not dispute it. Two points from the same source limit them. Enclave memory limits complicate large networks, and enclaves tie the deployment to specific chips and instance types, which is hardware lock-in by another route. Our proposal targets the case where the provider must not be trusted at all. We will report the enclave numbers alongside ours so readers can see the price of that requirement.

Why not just secret-share across two non-colluding clouds? CrypTen evaluated Model Z in 0.25 s on a LAN, so secret-sharing protocols are a serious threat. Their weakness is many rounds of interaction per nonlinearity, and PySyft already exceeded 8 s per image on that LAN. On a wide-area link between providers, round-trip time multiplies with depth. We will run CrypTen across the same provider pairs we use for FHE cuts. If it stays faster than our cut plans over the wide-area link, we will say so plainly. FHE then keeps only its non-interactive, single-provider-trust advantage.

Why not just containerize the FHE library and route whole requests? This could plausibly match us, and the third baseline exists to test it. Containers give portability, but they force each request onto one backend. They also cannot exploit the fact that a pre-bootstrap ciphertext is cheap to ship. If whole-request routing matches cut plans everywhere, our contribution shrinks to the calibrated switching-cost model and the portable lowering, and we will present it that way.

Why not just accept lock-in to the fastest accelerator? Speed is not the only cost. A provider price change or regional unavailability forces a migration, and the user then needs to know what it costs. Our switching-cost measurement answers that directly. If key upload and redeployment take minutes and the break-even point is a few thousand requests, lock-in to an FHE accelerator is cheap to escape and the warning matters less. If it takes hours, the warning stands.

Proposed Experiments

Workloads follow the compilers' own benchmarks: LeNet-5 on MNIST as in EVA, ResNet-20 on CIFAR-10 as in Orion, SqueezeNet on CIFAR-10 (EVA reports 72.7 s), and ResNet-50 on ImageNet as the deep, bootstrap-heavy case. Backends are CPU instances on two providers, one GPU instance, and TPUv5e. We record end-to-end latency, dollars per inference at list prices, bytes crossing provider boundaries, accuracy relative to the plaintext model (which should be unchanged, since placement does not alter arithmetic), and deployment switching time and cost.

Three checks decide the outcome. First, measured transfer sizes and times must match the $S(\ell)$ model within measurement noise on every provider pair; otherwise the cost model is wrong and later results are uninterpretable. Second, across a sweep of $\lambda$, we ask whether any cut plan beats the best single-backend whole request, and whether level-aware cuts beat level-oblivious ones. We predict a win only for ResNet-50-scale networks, where bootstraps dominate and pre-bootstrap ciphertexts are small relative to the compute they unlock. Third, we measure the portability tax, meaning whether lowering from the shared graph costs any speed against each library run natively, and the switching cost, from which we report the break-even request count. No reported result exists on Lacuna for cross-provider FHE ciphertext transfer or multi-cloud encrypted inference cost, so these measurements are themselves the first data points for that question.