Tiny devices offload heavy computation like AI inference to powerful servers, but that hands over your private data — homomorphic encryption (HE) fixes the privacy by letting the server compute on ENCRYPTED data, and a practical "client-aided" variant runs the linear parts encrypted on the server and bounces the intermediate results back to the client to decrypt, do the non-linear parts in plaintext, and re-encrypt; the catch is that every prior system tuned the SERVER and ignored the little client, where encrypting and decrypting again and again is actually the bottleneck (over 99% of the client's work) plus gigabytes of ciphertext to ship; this paper (CMU) builds CHOCO, which optimizes for the CLIENT with three moves — pick the smallest possible ciphertexts, a new "rotational redundancy" trick that packs a little extra data so encrypted values can be rearranged with one cheap rotation instead of noise-hungry operations (halving ciphertext size), and CHOCO-TACO, a chip that accelerates the WHOLE of client encryption and decryption rather than just one kernel — cutting communication by up to 2948x and encryption by up to 1094x, making private offload 2.2x faster than just computing on the device.
The argument in one glance
-
Problem
Offloading computation to a server means handing over your data
Client devices — phones, IoT sensors — keep shrinking in compute and energy even as the computations they want to run (machine-learning inference) keep growing. The natural answer is to OFFLOAD the heavy work to a powerful server ("inference as a service"). But offloading exposes the client's sensitive data to a server it may not trust. Homomorphic encryption (HE) offers the strongest possible fix: the server computes DIRECTLY on encrypted data and never sees the plaintext, with a provable privacy guarantee. The trouble is that running an entire program under full HE is impractically slow and limited in the operations it can perform, so pure encrypted offload has not been feasible for real applications.
-
What people did
Use client-aided HE and make the server fast
A practical middle ground has emerged: CLIENT-AIDED HE. Instead of running everything encrypted, only the LINEAR operations of a network (convolutions, matrix multiplies) run as HE on the server; the encrypted intermediate results are sent back to the client, which decrypts them, performs the NON-LINEAR operations (activation functions) in plaintext, re-encrypts, and sends them back for the next layer. This sidesteps full HE's depth limits and expensive bootstrapping and supports arbitrary networks. Prior systems (Gazelle and others) then optimize this model hard — minimizing the SERVER's computation and communication so the offload service scales.
-
Why it fell short
Optimizing the server ignores where the real cost is — the client
Prior work tuned the wrong side. Client-aided HE moves the burden ONTO the client: it must decrypt and re-encrypt intermediate results at EVERY layer, and it must send and receive large ciphertexts — gigabytes for a single DNN inference. On a resource-constrained device, this is crushing. Measurements show over 99% of the client's compute time is spent in HE encryption and decryption, not in the application itself, and the ciphertext communication saturates low-power links. Crucially, in server-only HE, encryption and decryption happen ONCE, so their cost is a minor setup step nobody optimizes; in client-aided HE they happen REPEATEDLY and define the client's critical path. The one prior hardware effort accelerates only the polynomial multiplication (about 60% of encryption time), which is not enough. So client-aided HE remains infeasible on exactly the small devices that most need to offload.
-
This paper's idea
Optimize for the client: smaller ciphertexts, a cheaper permutation, and full acceleration
This paper (Carnegie Mellon — van der Hagen and Lucia) builds CHOCO, which flips the priority to the CLIENT, minimizing its time, energy, and communication. Three moves. First, CLIENT-FOCUSED PARAMETER SELECTION: for a given security level, choose the SMALLEST ciphertexts (via aggressive 4-bit quantization and careful operation scheduling), which shrinks everything the client must encrypt, decrypt, and send. Second, ROTATIONAL REDUNDANCY, a new encrypted-permutation algorithm: aligning packed values for a convolution normally needs noise-expensive masking multiplications plus full rotations, which force LARGER ciphertexts to hold enough noise budget; instead, CHOCO packs a little REDUNDANCY around each window so a single cheap rotation does the job, and the client (which unpacks anyway) simply discards the overflow — halving ciphertext size. Third, CHOCO-TACO, a hardware accelerator for the WHOLE of client encryption and decryption (not just the polynomial multiply), virtually eliminating their time cost. Together, CHOCO cuts client communication by up to 2948x and encryption/decryption by up to 1094x (648x less energy), making encrypted offload 2.2x faster than computing locally — the first time client-aided HE is competitive with local compute.
Why this problem is worth solving
Private computation on personal data is one of the defining problems of
edge computing, and homomorphic encryption is the tool with the strongest
guarantee — but only if it can run on the devices that hold the data.
Understanding the practical form of HE comes first. A
HOMOMORPHIC
ENCRYPTION (HE) lets you compute on ciphertexts: given encryptions of two
numbers, anyone can produce the encryption of their sum or product without
the key, so a server operates on encrypted data and learns nothing.
Modern HE schemes (BFV, CKKS) encrypt a whole VECTOR of values into one
ciphertext and support encrypted addition, multiplication, and rotation.
The catch is that FULL HE — running an entire program encrypted — is
crippled by depth limits and an expensive noise-cleanup operation called
bootstrapping, so it is impractical for real workloads. CLIENT-AIDED HE is
the pragmatic alternative: run only the LINEAR parts of a computation (the
convolutions and matrix multiplies of a neural network) as HE on the
server, then send the encrypted intermediate results to the client, which
decrypts, applies the NON-LINEAR parts (activations) in plaintext,
re-encrypts, and returns them. This avoids depth limits and supports any
network, at the price of repeated client decryption, re-encryption, and
communication at every layer
The reason prior work’s answer is wrong, and where CHOCO’s cleverest idea
lives, is the noise budget. A
every HE ciphertext
carries a NOISE BUDGET: encryption injects random noise for security, and
each operation adds more — a little for additions, a lot for
multiplications — until the budget is exhausted and the ciphertext becomes
undecryptable garbage. Bigger HE parameters (larger ciphertexts) give a
larger budget but cost more to compute and communicate, so you want the
smallest parameters that still leave enough budget. Here is the squeeze:
to compute a convolution, the values packed into a ciphertext vector must
be REARRANGED so the right ones line up, and arbitrary encrypted
PERMUTATIONS require a series of rotations plus MASKING MULTIPLICATIONS —
and each masking multiply consumes a chunk of the precious noise budget.
So aligning data forces you to reserve budget for masking, which forces
larger ciphertexts, which inflates exactly the client costs client-aided
HE is drowning in. Conserving noise budget by avoiding those masking
multiplies is therefore the key to smaller ciphertexts
What people did before, and where it broke
- Full (server-only) homomorphic encryption. Run the whole program encrypted on the server. Strongest privacy and no client work per layer, but depth limits and bootstrapping make it impractically slow, and the ciphertexts are enormous.
- Server-optimized client-aided HE (Gazelle, LoLa). Split linear operations (server, encrypted) from non-linear (client, plaintext), and minimize the SERVER’s compute and communication. Makes the service scale, but ignores the client, which now does repeated decryption and re-encryption and ships gigabytes of ciphertext.
- Multi-party computation (MPC). Hide both the client’s data and the server’s model. Strong mutual privacy, but very high compute and communication cost, and it manipulates single values rather than packed vectors, so it is heavy for resource-constrained clients.
- Prior HE hardware. Accelerate the polynomial multiply and NTT, which are about 60% of encryption. A help, but leaving the other 40% un-accelerated means encryption still dominates the client, and prior hardware targeted large server GPUs and FPGAs, not tiny devices.
- The gap. No approach made client-aided HE feasible on a resource-constrained client — with small ciphertexts, cheap encrypted permutation, and full acceleration of the client’s crypto. That is the gap CHOCO closes.
How CHOCO makes encrypted offload feasible on tiny clients
Optimize for the client: shrink ciphertexts, rearrange cheaply, and accelerate all of encryption
-
The client-aided model and its hidden bottleneck
Linear operations run encrypted on the server; the client decrypts each layer's result, does the non-linear operation in plaintext, and re-encrypts. Encryption and decryption thus happen on the client's critical path EVERY layer and dominate — over 99% of client compute — while huge ciphertexts saturate the link. Prior work optimized only the server.
-
Optimize for the client, not the server new
CHOCO minimizes client time, energy, and communication rather than server cost. For a target security level it selects the SMALLEST ciphertexts — aggressive 4-bit input quantization, careful operation scheduling, and ciphertexts of 8192 or fewer elements with only 2 prime residues — so everything the client encrypts, decrypts, and sends shrinks.
-
Rearrange encrypted data with rotational redundancy new
Aligning packed values for a convolution normally needs masking multiplications plus full rotations, which drain the noise budget. Instead CHOCO packs REDUNDANT copies of values around each window before encryption, so a single cheap rotation performs the windowed rearrangement; the values that wrap out of the window are simply discarded by the client and fresh ones repacked.
-
Conserve the noise budget to shrink ciphertexts new
By avoiding masking multiplications, rotational redundancy leaves far more noise budget intact, which permits smaller HE parameters. This yields a 50% reduction in ciphertext size (half of it from rotational redundancy alone) and achieves convolution with optimal multiplication efficiency — a single multiply of weights with inputs.
-
Accelerate the WHOLE of encryption and decryption new
Because prior hardware accelerated only the polynomial multiply (about 60% of encryption), CHOCO-TACO accelerates ALL sub-operations — random-number generation, NTT and inverse NTT, polynomial addition, modulus switching, and message encoding — in a parallel, pipelined RNS datapath, virtually eliminating the client's crypto time for both BFV and CKKS.
-
Split the work client-first new
CHOCO partitions linear operations (server, encrypted) from non-linear (client, plaintext), and chooses the data-packing that minimizes the CLIENT's ciphertext count even when it burdens the server — for example a "collapsed" packing for distance algorithms that produces and consumes the fewest client ciphertexts.
The idea
Optimize the side everyone ignored — the client is where the cost is. The reframing move is to notice that client-aided HE quietly relocated the dominant cost onto the weakest device. In server-only HE, encryption and decryption are one-time setup, so nobody optimizes them; in client-aided HE they run every layer on the client and become over 99% of its compute. Prior work kept optimizing the server anyway. CHOCO measures where the time actually goes and attacks THAT — the client’s repeated encryption, decryption, and communication. This chase-the-real-bottleneck, measure-where-the-cost-actually-is discipline is one the site keeps rewarding: the non-GEMM-accelerator page finds the neglected 15% of operators dominating runtime once the obvious part is fast, the heterogeneity-aware scheduler measures true per-hardware cost rather than assuming uniformity, and the GPU value-profiler measures the values the counters ignore. The obvious thing to optimize (the server) was not the thing that mattered.
Trade a cheap resource to save the scarce one — space for noise budget. Rotational redundancy is a small algorithmic gem with an outsized payoff. The scarce resource in HE is the noise budget, and arbitrary encrypted permutations spend it lavishly on masking multiplications. CHOCO spends a cheap resource instead — a little extra SPACE, packing redundant copies of values around each window — so the rearrangement needs only one rotation and no masking, conserving the budget and letting the ciphertexts be half the size. Spending an abundant resource to save a scarce one is the same move the site’s FHE-accelerator page makes when it packs residues tightly to save the expensive multiplier, and it is the client-side twin of that work: both redesign the HE data layout to relieve the resource that actually limits performance. The enabling trick is client-aided-specific — the client unpacks and repacks anyway, so it can discard the redundant overflow for free.
Accelerate the whole operation, because the un-accelerated part becomes the bottleneck. Prior HE hardware sped up the NTT and polynomial multiply, about 60% of encryption, and stopped — but by Amdahl’s law the remaining 40% then dominates, so encryption still crushed the client. CHOCO-TACO accelerates EVERY sub-operation of encryption and decryption, driving their cost toward zero. Accelerating the entire pipeline rather than the one obvious kernel is the same lesson the non-GEMM-accelerator page teaches from the other direction — optimize the matmul hard enough and the leftover operators become the ceiling — and it reflects the co-design discipline of building hardware for the true critical path, not the textbook hotspot. Only with the whole of encryption accelerated does the client stop being the bottleneck.
Turning the client from bottleneck into contender
From infeasible to faster-than-local
Making client-aided HE practical on a resource-constrained device. Numbers from the paper's evaluation.
Step 1 of 5
The hidden cost
Client-aided HE decrypts and re-encrypts the intermediate result at every layer, on the client's critical path, and ships large ciphertexts. On a small device, over 99% of the client's compute is HE encryption and decryption, not the application — yet prior systems optimized only the server, leaving the client infeasible.
in server-only HE, encryption and decryption are one-time; client-aided HE makes them a repeated critical-path cost a single DNN inference can require gigabytes of ciphertext communication
Why it works
- Client-aided HE runs encryption and decryption on the client every layer, not once → they become over 99% of client compute and define its critical path → optimizing the client (not the server) is what actually helps the weak device.
- Arbitrary encrypted permutations spend the noise budget on masking multiplications, forcing larger ciphertexts → rotational redundancy packs redundancy so one rotation suffices, and the client discards the overflow → the noise budget is conserved and ciphertexts shrink 50%.
- Smaller ciphertexts mean less to encrypt, decrypt, and send → CHOCO’s client-focused parameter selection plus rotational redundancy minimize ciphertext size → client communication drops by up to 2948x over prior work.
- Prior hardware accelerated only ~60% of encryption, so the rest dominated (Amdahl) → CHOCO-TACO accelerates the whole encryption and decryption pipeline → their cost falls up to 1094x, making client compute 2.2x faster than local inference.
- Linear operations suit HE and non-linear ones do not → running linear on the server encrypted and non-linear on the client in plaintext, with client-first packing → the approach avoids full HE’s depth limits while minimizing what the client must process.
What it costs (trade-offs and scope)
- Communication is still the bottleneck on slow links. Over a 10 mW Bluetooth link, communication adds about a 24x average TIME overhead versus computing locally — CHOCO wins on energy (up to 37% savings) and privacy for battery devices, but not on latency over low-bandwidth channels.
- The benefit is workload-dependent. Only workloads with many multiply-accumulates per megabyte of communication (like VGG) come out ahead; workloads with little compute per byte (like SqueezeNet) break even or lose, because communication dominates.
- The hardware is essential and is modeled, not fabricated. CHOCO in software alone is 14.5x SLOWER than local compute; the 2.2x-faster result requires the 19.3-square-millimeter CHOCO-TACO accelerator, evaluated in RTL and simulation — it is a hardware proposal, not a drop-in library.
- Rotational redundancy trades space for budget. It conserves noise by spending extra vector space on redundant values, which reduces the density of useful inputs in a ciphertext; the amount of redundancy needed depends on the rotation, though it is typically a small fraction.
- The threat model is client-first and semi-honest. The server is assumed curious but faithful, and CHOCO protects the CLIENT’s data but does NOT hide the server’s model or data from the client (unlike full MPC) — a deliberate trade that makes it the wrong tool when the server’s model must also stay private.
The evaluation
A software client on an NXP IMX6 (ARM Cortex-A7 at 528 MHz) and a server on an Intel Xeon at 2.5 GHz, with CHOCO-TACO modeled from RTL (Cadence Genus, 45 nm; SRAM via Destiny), on four BFV DNNs (LeNet variants, SqueezeNet, VGG16), and CKKS K-Nearest-Neighbors, K-Means, and PageRank, compared against seven prior HE and MPC systems and against local TensorFlow-Lite inference.
Making encrypted offload work on a weak client
| Property | Full HE (server-only) | Server-optimized client-aided | CHOCO (this work) |
|---|---|---|---|
| What is optimized | |||
| Client encryption cost | |||
| Ciphertext size | |||
| Encrypted permutation | |||
| Client vs local compute |
Check yourself
Check your understanding
1. Prior client-aided HE systems worked hard to optimize the server, yet CHOCO argues this misses the point. Predict where the real cost is and why.
2. Rotational redundancy packs EXTRA redundant data into a ciphertext, which seems wasteful, yet it makes ciphertexts SMALLER overall. Predict how.
3. Prior HE hardware accelerated the polynomial multiply (about 60% of encryption), but CHOCO-TACO accelerates all of encryption and decryption. Predict why the partial approach was insufficient.
4. CHOCO makes encrypted offload 2.2x faster than local compute, yet over a Bluetooth link it adds a 24x time overhead. Predict how both can be true and what it means for when to use CHOCO.
Sources
- Client-Optimized Algorithms and Acceleration for Encrypted Compute Offloading (author PDF, CMU) — ASPLOS 2022 (full text read).
- ACM DL: Client-Optimized Algorithms and Acceleration for Encrypted Compute Offloading (DOI 10.1145/3503222.3507737) — published version.
- Presentation slides (CMU ABSTRACT group) — talk overview of CHOCO and CHOCO-TACO.