Cheddar: A Swift Fully Homomorphic Encryption Library Designed for GPU Architectures

Fully homomorphic encryption lets a cloud server compute on your data while it stays encrypted the whole time — a huge privacy win, but so slow it can be thousands of times costlier than ordinary computing; this work from Seoul National University builds Cheddar, a GPU library that speeds it up by matching the math to what a graphics chip does natively (32-bit integer arithmetic instead of emulated 64-bit) and by fusing operations to avoid needless trips to memory, running an encrypted image-classification network in under a second and beating the best prior GPU and even custom-chip implementations.

The argument in one glance

Problem

Computing on encrypted data is private but crushingly slow

Fully homomorphic encryption lets a cloud server compute directly on encrypted data, a strong privacy guarantee, but it runs several orders of magnitude slower than plain computation. GPUs can accelerate its highly parallel operations, yet a mismatch limits them: FHE math uses 64-bit primes, while GPUs do integer arithmetic on a 32-bit datapath.
What people did

Run the standard 64-bit FHE math on the GPU

Accelerate FHE by porting the popular libraries, which represent the huge modulus with 64-bit primes, onto the GPU and running the polynomial arithmetic in parallel.
Why it fell short

64-bit math wastes the GPU, and 32-bit fixes broke parallelism

Because a GPU emulates each 64-bit integer operation with several 32-bit ones, 64-bit FHE incurs quadratically higher cost on the hardware. Switching to 32-bit primes would fit the datapath, but prior 32-bit constructions either demanded excessive memory for extra keys or caused control divergence that destroys GPU parallelism. And memory bandwidth remains a bottleneck.
This paper's idea

A GPU-friendly 32-bit number system, plus heavy kernel fusion (Cheddar)

Cheddar is a fast GPU library for CKKS FHE. It introduces a compact 32-bit number system (the 25-to-30-prime system) that uses a single compatible public key with no thread divergence, matching the GPU's native datapath. It hand-optimizes the low-level kernels per GPU architecture, and it extensively fuses kernels — reordering and splitting operations so intermediate data stays in fast memory. It runs 2.18 to 4.45 times faster than the best prior GPU library, finishing an encrypted ResNet-20 inference in 0.72 seconds on a single GPU.

Why this problem is worth solving

Homomorphic encryption promises something almost magical — useful computation on data that is never decrypted — but the price has been prohibitive.

Homomorphic encryption lets a server compute on ciphertexts, encrypted data, and produce an encrypted result that, when the client decrypts it, is exactly what the computation would have produced on the plain data — all without the server ever seeing the underlying information. That is a powerful privacy guarantee for cloud computing. Fully homomorphic encryption, or FHE, goes further by supporting bootstrapping: a mechanism that refreshes a ciphertext, because each operation adds a little noise and, without refreshing, only a fixed number of operations can be done before the result becomes undecryptable. Bootstrapping resets that budget, enabling practically unlimited computation. The obstacle to real-world use is performance: processing encrypted data with FHE is several orders of magnitude slower than the same computation on plain data. Fortunately, FHE operations are highly parallel, so hardware acceleration — on GPUs, FPGAs, or custom chips — helps a great deal. This work targets GPUs and the CKKS scheme, the FHE variant with the highest throughput and the ability to handle real numbers with good precision, which makes it well suited to machine learning. Prior GPU work already cut an encrypted ResNet-20 image classification from 2271 seconds on a CPU to under 6 seconds on a GPU — impressive, but still far from the speed of ordinary inference.

The reason GPUs cannot go faster still is a mismatch between how FHE does its arithmetic and how a GPU is built.

FHE works over polynomials with an astronomically large modulus — on the order of two raised to roughly the twelve-hundredth power. Doing arithmetic with numbers that large directly would be hopeless, so FHE uses the residue number system: it breaks the huge modulus into a product of many small primes, each small enough to fit in a machine word, and represents each polynomial as many separate pieces, one for each prime. All the polynomial arithmetic is then done piece-by-piece, in parallel, with ordinary machine-word integers — a perfect fit for parallel hardware. The catch is the word size. Popular FHE libraries use 64-bit primes, so every arithmetic operation is a 64-bit integer operation. But a GPU performs integer math on a 32-bit datapath, meaning it does not have native 64-bit integer operations — it emulates each one with several 32-bit operations, and the cost grows quadratically. So a GPU running 64-bit FHE spends most of its effort emulating arithmetic its hardware was never built to do. Using 32-bit primes instead would match the GPU exactly, and recent cryptographic techniques make equivalent security possible with only 32-bit primes. But earlier 32-bit constructions were poorly suited to GPUs: they either required excessive extra memory for additional keys, or caused control divergence — threads taking different branches — which is precisely what destroys a GPU’s parallelism.

What people did before, and where it broke

Accelerate 64-bit FHE libraries on the GPU. Port the standard libraries, which use 64-bit primes, and run their parallel polynomial arithmetic on the GPU. Where it broke. The GPU has no native 64-bit integer operations, so it emulates each with several 32-bit ones at quadratically higher cost, wasting most of the hardware.
Adopt existing 32-bit number systems. Use recent constructions that achieve equivalent security with only 32-bit primes. Where it broke. Prior 32-bit constructions demanded excessive memory for additional public keys, or caused control divergence among GPU threads, which collapses parallelism.
Optimize compute kernels but keep the operation sequence. Speed up the arithmetic-heavy kernels while leaving the sequence of FHE operations as-is. Where it broke. Memory-bound operations like rotations and element-wise steps remain bottlenecked on memory bandwidth, so compute optimizations alone leave large gains on the table.
The gap. No GPU FHE library combined a 32-bit number system that keeps the GPU fully parallel with aggressive reduction of memory traffic. Providing both is what Cheddar does.

How Cheddar works

From emulated 64-bit FHE to a GPU-native 32-bit library

↓ →
new
↓ →
new
↓ →
new
↓ →
new
↓ →
new

The idea

Match the number system to the GPU’s native datapath. Cheddar’s foundational move is to stop asking the GPU to emulate 64-bit arithmetic and instead do FHE’s residue-number-system math with 32-bit primes, exactly the width the GPU’s integer datapath handles natively, eliminating the quadratic emulation overhead. Choosing a numeric representation that fits what the hardware executes most efficiently, rather than forcing the hardware to fake a wider one, is the same bet the edge-training work covered elsewhere on this site makes, running its computation in the reduced numeric form the processors handle best so the hardware’s real capability is spent on useful work rather than on emulation.

Reorder and fuse operations so data stays in fast memory. Once the arithmetic is cheap, the bottleneck becomes memory bandwidth — rotations and element-wise operations spend their time moving data — so Cheddar extensively fuses kernels, reordering and splitting the sequence of FHE operations to maximize how much intermediate data can be produced and consumed without ever writing it out to slow memory. Arranging a heavy computation so that intermediate results flow directly between operations kept close to the compute, instead of round-tripping through distant memory, is the same locality-driven scheduling the tensor-dataflow compiler work covered elsewhere on this site performs, restructuring the computation to keep data local so the memory system is not the limit.

Tune the low-level primitives to the specific hardware. Because FHE’s core polynomial operations run an enormous number of times, Cheddar hand-optimizes them — using a cheaper form of modular reduction that needs fewer integer operations, and transform algorithms that can be selectively applied according to a given GPU’s compute and memory characteristics — so per-operation savings compound. Crafting the low-level building blocks around the exact characteristics of the target hardware, rather than using generic implementations, is the same architecture-aware optimization the tinyML design-exploration work covered elsewhere on this site is built on, tailoring the primitive operations to what the specific device does well to extract efficiency a one-size-fits-all design would miss.

Following an encrypted inference through Cheddar

Running a neural network on an encrypted image

A trace of encrypted CKKS inference on Cheddar, following the paper's design.

Step 1 of 5

The client encrypts and sends its data

A client wants a cloud server to classify its private image without revealing it, so it encrypts the image with CKKS and sends only the ciphertext.

The server will never see the plaintext image.

Why it works

FHE is valuable but punishingly slow. Because computing on encrypted data protects privacy in the cloud, yet FHE is orders of magnitude slower than plain computation → the technology stays impractical until it is fast → so accelerating it well is what makes privacy-preserving computation usable.
The number system should match the hardware datapath. Because GPUs execute integer math on a 32-bit datapath and emulate 64-bit operations at quadratic cost → using 64-bit primes wastes most of the GPU → so a 32-bit prime system does far less work for the same result.
A compact prime set avoids the GPU’s worst enemies. Because prior 32-bit schemes needed excess memory or caused thread divergence → minimizing the number of unique primes yields a single compatible key and uniform thread execution → so the GPU stays fully parallel without extra memory.
Memory bandwidth, not compute, is the remaining wall. Because rotations and element-wise operations are limited by memory bandwidth rather than arithmetic → fusing kernels keeps intermediate results in fast memory → so the slow trips to main memory that dominated those steps are removed.
Hardware-specific tuning compounds the gains. Because the core polynomial operations run an enormous number of times → optimizing their modular arithmetic and transforms and tailoring them to each GPU → so small per-operation savings multiply into a several-times overall speedup.

What it costs (trade-offs and scope)

The 32-bit number system is intricate to get right. Achieving equivalent security with only 32-bit primes, while minimizing the number of unique primes and avoiding thread divergence, requires a carefully engineered construction (the 25-to-30-prime system with a specific data layout). The benefit is real, but it rests on non-trivial cryptographic and systems design.
It is specialized to GPUs and to CKKS. Cheddar’s wins come from matching the GPU’s 32-bit datapath and memory system; the design choices are specific to GPUs and to the CKKS scheme, and would not transfer unchanged to other hardware or other FHE schemes.
Optimizations are device-tuned. Some kernel optimizations are selectively applied according to a specific GPU’s compute and memory characteristics, so peak performance depends on tuning to the device rather than being automatic across all GPUs.
FHE remains slower than plaintext computation. Even at 0.72 seconds for an encrypted ResNet-20 inference, FHE is still far slower than the same inference on unencrypted data; Cheddar narrows the gap and makes more applications practical, but does not erase the fundamental overhead of computing on ciphertexts.
The headline numbers are workload- and hardware-specific. The 2.18 to 4.45 times speedups and the sub-second inference are measured on particular FHE workloads and GPUs (including a recent RTX 5090); other workloads, parameters, and hardware would shift the figures.
Complexity of a full library. Delivering a full-fledged library that compiles high-level code to optimized GPU programs, with bootstrapping and state-of-the-art algorithms, is a substantial engineering artifact whose behavior depends on correct use of many FHE mechanisms.

The evaluation

Three ways to run FHE, by hardware and number system

Property	CPU FHE	Prior GPU (64-bit primes)
Uses the GPU's native integer datapath	Not applicable
Reduces memory-bandwidth traffic	Not applicable	Some fusion
Encrypted ResNet-20 inference latency
Speedup over prior GPU library	Much slower	Baseline
Faster than custom FPGA designs	No	No

Three ways to run fully homomorphic encryption, contrasted by the paper. On a single-core CPU, an encrypted ResNet-20 inference took 2271 seconds. Prior GPU libraries cut this to a few seconds, but they represent FHE's huge modulus with 64-bit primes, which the GPU must emulate on its 32-bit integer datapath at quadratically higher cost. Cheddar redesigns the residue number system to use only 32-bit primes (its compact 25-to-30-prime system, with a single compatible public key and no thread divergence), matching the GPU natively, then hand-optimizes the low-level kernels per architecture and extensively fuses kernels to cut memory-bandwidth traffic. The result is 2.18 to 4.45 times faster than a state-of-the-art GPU library across representative FHE workloads, faster even than some custom FPGA designs, and it brings encrypted ResNet-20 inference down to 0.72 seconds on a single recent GPU. FHE still remains slower than unencrypted computation; Cheddar narrows the gap toward practicality.Underlined values explain themselves when clicked.

Where this stops working

What to keep in mind

Cheddar is a strong systems-and-cryptography engineering result aimed at one of the most consequential barriers in privacy technology: fully homomorphic encryption is a genuine way to compute on data without ever decrypting it, but it has been orders of magnitude too slow to use widely. The paper’s central insight is elegant and hardware-grounded: FHE breaks its enormous modulus into small primes and does arithmetic in parallel pieces, and the pieces should be sized to what the GPU executes natively — 32 bits — rather than the 64 bits standard libraries use, which the GPU can only emulate at quadratic cost. Making 32-bit work well on a GPU is the hard part, and Cheddar’s compact prime system delivers a single compatible key with no thread divergence, avoiding the memory blow-up and lost parallelism of earlier 32-bit attempts. On top of that it does the unglamorous but decisive work: hand-tuned low-level kernels with cheaper modular arithmetic, and extensive kernel fusion that reorders and splits the operation sequence to keep memory-bound steps from thrashing main memory. The payoff is concrete — 2.18 to 4.45 times faster than the state-of-the-art GPU library, faster than some custom FPGAs, and an encrypted ResNet-20 inference in 0.72 seconds on a single GPU. Read the scope precisely. The gains are specific to GPUs and to the CKKS scheme; some optimizations are tuned per device; the numbers depend on the workloads and hardware measured; and, crucially, FHE is still much slower than plaintext computation — Cheddar narrows the gap, it does not close it. The durable idea is that when a workload must run on an accelerator, the biggest wins come from respecting the accelerator’s real shape — its datapath width, its memory bandwidth, its need for uniform threads — and reshaping even the mathematics to fit it.

Background

Why respecting the accelerator's real constraints is where the speed hides

It helps to see Cheddar within a recurring lesson in high-performance computing: once an algorithm is on an accelerator, the dominant performance factor is rarely raw arithmetic and almost always how well the work fits the hardware’s real constraints — the width of its datapath, the bandwidth of its memory, the uniformity its threads demand. Cheddar’s largest single win comes from a change to the mathematics itself, choosing 32-bit primes so the GPU stops emulating operations it was never built for; its second comes from restructuring the operation sequence so data stays close to the compute. The warehouse-scale memory-traffic work covered elsewhere on this site distills the underlying principle: data movement, not computation, is usually the true bottleneck, and the transfers a system manages to avoid are where the efficiency is found. The common thread is that peak performance is a negotiation with the hardware’s shape rather than a matter of doing arithmetic faster — the same kilobytes of intermediate data, kept in fast memory instead of spilled to slow memory, or the same result computed in the native word size instead of an emulated one, can be several times cheaper. As specialized accelerators proliferate and workloads as demanding as FHE become important, the ability to co-design an algorithm down to its number system around a specific accelerator is likely to separate the implementations that are merely correct from the ones that are actually usable.

If you remember only three things

1. Fully homomorphic encryption (FHE) lets a cloud server compute directly on encrypted data and return an encrypted result, giving strong privacy, and its bootstrapping mechanism refreshes ciphertexts so unlimited operations are possible. But FHE is several orders of magnitude slower than plaintext computation. Its operations are highly parallel, so GPUs help, and the CKKS scheme (best for real numbers and machine learning) has been pushed from thousands of seconds to a few seconds for an encrypted neural-network inference. A key inefficiency remains: FHE breaks its astronomically large modulus into small primes and computes in parallel pieces, and popular libraries use 64-bit primes — but GPUs do integer math on a 32-bit datapath, so they emulate each 64-bit operation with several 32-bit ones at quadratically higher cost.
2. Cheddar is a fast GPU library for CKKS FHE built around matching the hardware. Its core contribution is a compact 32-bit number system (the 25-to-30-prime system with an inverted-terminal data layout) that achieves equivalent security using only 32-bit primes, needs a single compatible public key, and avoids the control divergence that ruined prior 32-bit constructions on GPUs — so the GPU runs the arithmetic it was actually built for, fully in parallel. On top of that it hand-optimizes the low-level polynomial kernels (using a cheaper signed Montgomery reduction and transform algorithms selectively tuned per GPU) and applies extensive kernel fusion, reordering and splitting the FHE operation sequence so memory-bound rotations and element-wise steps keep intermediate data in fast memory instead of spilling to slow memory.
3. Cheddar runs 2.18 to 4.45 times faster than a state-of-the-art GPU library across representative FHE workloads, is faster than some custom FPGA designs, and brings encrypted ResNet-20 inference down to 0.72 seconds on a single recent GPU. Scope: the wins are specific to GPUs and the CKKS scheme, some kernels are tuned per device, the numbers depend on the measured workloads and hardware, and FHE still remains slower than unencrypted computation — Cheddar narrows the gap toward practicality rather than closing it. The durable lesson is that on an accelerator the biggest speedups come from respecting the hardware's real shape — its datapath width, memory bandwidth, and need for uniform threads — and reshaping even the algorithm's mathematics to fit it.

Check yourself

Check your understanding

1. What does fully homomorphic encryption make possible, and what is its practical obstacle?
2. Why do standard 64-bit FHE libraries run inefficiently on GPUs?
3. What are Cheddar's two main techniques for speeding up FHE on GPUs?
4. What does the 0.72-second encrypted ResNet-20 inference demonstrate, and what remains true?

Sources

The paper is “Cheddar: A Swift Fully Homomorphic Encryption Library Designed for GPU Architectures” by Wonseok Choi, Jongmin Kim, and Jung Ho Ahn, published at ASPLOS 2026, DOI 10.1145/3760250.3762223. The authors are at Seoul National University.

This explainer is based on the full text of the paper, obtained from the authors’ open-access arXiv version (arXiv:2407.13055), which corresponds to the CC-BY version of record. The problem framing (homomorphic encryption and computing on ciphertexts, fully homomorphic encryption and bootstrapping, the orders-of-magnitude slowdown, the parallelism that enables GPU acceleration, the CKKS scheme and its suitability for machine learning, and the reported reduction of encrypted ResNet-20 inference from 2271 seconds on a CPU to a few seconds on a GPU), the central technical insight (the residue number system decomposing a large modulus into small primes, the quadratic overhead of emulating 64-bit operations on a GPU’s 32-bit datapath, and the drawbacks of prior 32-bit constructions — excessive memory for additional keys, or control divergence), Cheddar’s contributions (the 25-to-30-prime 32-bit number system with the inverted-terminal data layout and a single compatible public key; the hand-optimized low-level kernels using signed Montgomery reduction and selectively applied number-theoretic-transform and basis-conversion optimizations; and the extensive sequential and parallel kernel fusion that reorders and splits operation sequences to reduce memory-bandwidth pressure), and the evaluation results (the 2.18 to 4.45 times speedup over a state-of-the-art GPU library, the comparison favorable to custom FPGA designs, and the 0.72-second encrypted ResNet-20 inference on a single RTX 5090 GPU) are all drawn directly from the paper. Background explanations of homomorphic encryption, the residue number system, GPU datapaths and thread divergence, kernel fusion, and memory bandwidth are standard and provided to make the paper’s contribution understandable.