Maverick: Rethinking TFHE Bootstrapping on GPUs via Algorithm-Hardware Co-Design

TFHE lets you compute on encrypted data and even apply any function while refreshing the noise, but its core "bootstrapping" step is a long chain of operations that each depend on the last, so it is inherently serial and painfully slow — and just adding more GPU compute does not help; this paper (Institute of Information Engineering, Chinese Academy of Sciences — Zhiwei Wang, Rui Hou, and colleagues) presents Maverick, which algebraically restructures that one long chain into many independent shorter chains that run in parallel, and rebalances the polynomial-math work across the GPU, for large speedups.

The argument in one glance

Problem

TFHE can compute on encrypted data, but its core refresh step is brutally slow

Fully homomorphic encryption (FHE) lets a computer perform arbitrary computation on encrypted data without ever decrypting it, so a cloud could run your program on your data while learning nothing about it. Within the FHE family, TFHE is especially attractive because of its versatile bootstrapping: not only does bootstrapping refresh a ciphertext (every homomorphic operation adds noise, and once the noise budget runs out the ciphertext is unusable, so it must periodically be refreshed), but TFHE's programmable bootstrapping can also apply an arbitrary function to the data at the same time, encoded as a lookup table. That combination makes TFHE powerful for security-critical applications. The catch is cost: bootstrapping is prohibitively expensive, dominating the runtime and severely limiting practical deployment. The natural response is hardware acceleration — run it on a GPU with its thousands of parallel cores. But simply throwing more compute at it does not work. The core of TFHE bootstrapping, an operation called blind rotation, is built as a long chain of operations in which each step depends on the result of the step before it. A dependency chain like that is inherently sequential: no matter how many cores a GPU has, they cannot all work at once on a computation that must proceed one step at a time. So the GPU sits mostly idle, and the real barrier is not a lack of compute but a lack of parallelism in the algorithm itself.
What people did

Accelerate bootstrapping by scaling up the hardware

The standard path to making an expensive kernel faster is to run it on more powerful hardware: move TFHE bootstrapping from the CPU to the GPU, and use the GPU's massive parallelism and high-throughput arithmetic units to churn through the polynomial multiplications that bootstrapping requires. Prior GPU implementations do exactly this, mapping the bootstrapping computation onto the GPU and optimizing the low-level math.
Why it fell short

More compute cannot fill a GPU that the algorithm keeps serial

Merely scaling compute runs into two inherent barriers. The first is limited algorithmic parallelism. Blind rotation is a single chain of length n (n is a security parameter) of external products, and each external product consumes the accumulator produced by the one before it, so the whole chain must run in order. Its parallelism is effectively one: at any instant only a single external product can proceed, which leaves a GPU's thousands of cores with almost nothing to do in parallel. A faster GPU makes each step of the chain a little faster but cannot make the steps run at the same time, so the speedup saturates far below the hardware's potential. The second barrier is an inadequate understanding of how the hardware actually behaves: the polynomial-transform work inside each external product — done with a number-theoretic transform (the modular-arithmetic cousin of the fast Fourier transform) — is not evenly distributed across the GPU's operators, so even the work that could run in parallel is unbalanced, wasting capacity. Together these mean a large gap between the GPU's available performance and what TFHE bootstrapping actually achieves. What was missing was a rethinking of the algorithm to create parallelism, matched to how the hardware really runs.
This paper's idea

Turn one long serial chain into many parallel short chains, and rebalance the math

Maverick is a GPU solution that rethinks TFHE bootstrapping through joint algorithm-hardware co-design, attacking both barriers at once. At the algorithmic level, it reconstructs blind rotation by changing when the lookup table (the "test vector") is applied: instead of pre-loading it into the accumulator at the start of the chain, Maverick injects it later (post-injection). This reformulation breaks the original single chain of length n into a multi-chain structure — roughly the square root of n independent sub-chains, each of depth the square root of n. Because the sub-chains no longer depend on one another, they can run at the same time, so the parallelism of the external products jumps from one all the way up to the square root of n, which is the theoretical maximum for this structure. Now the GPU has many independent chains to work on instead of one. At the hardware level, Maverick introduces a partial-domain transformation strategy: it terminates the number-theoretic transform early, in a stage-aware way, and selectively shifts the remaining computation into downstream operators, redefining the boundaries between operators so the workload is balanced evenly across the external-product operators. This makes the parallel work the reformulation exposed actually run efficiently on the GPU rather than piling up unevenly. Together, the paper reports, Maverick delivers state-of-the-art GPU acceleration: it outperforms the best existing CPU and GPU baselines by 331.2 times and 3.4 times, respectively, on programmable bootstrapping, with up to a 108.5 times speedup reported.

Why this problem is worth solving

FHE is one of the strongest privacy technologies known, and TFHE’s bootstrapping is the bottleneck standing between it and real use.

Fully homomorphic encryption offers something remarkable: a server can compute on data it cannot read, so sensitive information — medical, financial, personal — could be processed in the cloud without ever being exposed. TFHE is a particularly appealing member of the family because its programmable bootstrapping can refresh a ciphertext and apply an arbitrary function in one step, which makes it flexible enough for a wide range of security-critical computations. But every homomorphic computation of any length depends on bootstrapping to keep the noise in check, and in TFHE that operation is so expensive that it dominates runtime and keeps the whole approach impractical. So the gap between FHE’s promise and its use is, to a large degree, the cost of bootstrapping. Driving that cost down is therefore not an incremental tuning problem but the thing that decides whether privacy-preserving computation is a laboratory curiosity or a deployable capability. Because bootstrapping is invoked constantly, even a multiplicative speedup translates directly into more practical encrypted computation, which is why so much effort targets exactly this operation.

The essential insight is that the barrier is a lack of parallelism in the algorithm, not a lack of compute in the hardware.

It is tempting to treat a slow kernel as a hardware problem and reach for a bigger GPU, but that only helps if the work can actually occupy the hardware. Blind rotation, the heart of TFHE bootstrapping, is structured as a chain where each external product needs the output of the previous one, so it is intrinsically sequential — its parallelism is one, regardless of how many cores are available. On a GPU, whose entire advantage is doing thousands of things at once, a computation with parallelism of one is nearly the worst case: the cores stand idle waiting for a single chain to advance. No amount of faster arithmetic changes the fundamental shape of the dependency. This is why Maverick’s decisive move is algorithmic: by reformulating blind rotation so the one long chain becomes many independent shorter chains, it creates the parallelism the GPU needs to be filled in the first place. The square-root decomposition is the sweet spot — it trades a single chain of depth n for the square root of n chains each of depth the square root of n, maximizing how many can run at once. Only after the parallelism exists does the hardware-level rebalancing matter, ensuring that the newly-parallel work is spread evenly rather than bottlenecking on an uneven transform. The order of reasoning — first make the algorithm parallel, then make the hardware run it evenly — is why co-design, rather than either half alone, is what unlocks the performance.

What people did before, and where it broke

Run TFHE bootstrapping on the CPU. Execute the polynomial arithmetic on a general-purpose processor. Where it broke. It is prohibitively slow, so bootstrapping dominates runtime and limits practical deployment.
Move bootstrapping to the GPU and optimize the math. Map the computation onto a GPU’s parallel cores and tune the low-level arithmetic. Where it broke. Blind rotation is a single serial chain of external products, so its parallelism is one and the GPU’s cores sit mostly idle.
Keep pre-loading the test vector at the start of the chain. Apply the lookup table before the long external-product chain runs, as standard blind rotation does. Where it broke. It forces the entire computation into one length-n dependency chain, foreclosing parallelism.
Use a full number-theoretic transform per external product. Compute the polynomial transforms in the usual way. Where it broke. The transform work is unevenly distributed across the GPU’s operators, so even the parallelizable work is unbalanced and wastes capacity.
The gap. No approach restructured the algorithm to create parallelism, and matched that restructuring to the hardware so the parallel work ran evenly.

How Maverick works

Creating parallelism in blind rotation, then balancing it on the GPU

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

The idea

Restructure an inherently serial computation to expose parallelism. Maverick’s core algorithmic move is to reformulate blind rotation so a single long dependency chain becomes many independent shorter ones, creating parallelism where there was none. Recovering latent parallelism by reorganizing a computation whose naive form is serial, so that independent work can run at once, is the same undertaking the work on accelerating task-parallel workloads by recovering program parallelism (TaskStream) covered elsewhere on this site pursues, finding the concurrency hidden in a seemingly sequential structure. Maverick does this algebraically for blind rotation, turning one chain of depth n into the square root of n chains, which is what lets a GPU finally be filled.

Co-design the algorithm and the hardware for FHE bootstrapping. Maverick treats the algorithm reformulation and the hardware execution strategy as one joint problem, because exposing parallelism only helps if the hardware runs it evenly. Attacking the cost of homomorphic-encryption bootstrapping by co-designing the algorithm and the hardware together, rather than optimizing one in isolation, is the same approach the work on algorithm-hardware co-design for efficient fully homomorphic encryption (Falcon) covered elsewhere on this site takes, matching the mathematics to the machine. Maverick applies this specifically to TFHE on GPUs, pairing its multi-chain blind rotation with a partial-domain transform strategy.

Redraw the boundaries of the pipeline to balance the work. Maverick’s hardware contribution stops the number-theoretic transform partway and pushes the leftover computation into downstream operators, redefining where one operator ends and the next begins so no operator is overloaded. Rebalancing a hardware dataflow by rethinking how work is partitioned across its stages, so a bottleneck stage no longer dominates, is the same principle the work on an optimized dataflow for mitigating attention bottlenecks (FLAT) covered elsewhere on this site is built on, reshaping the operator pipeline to spread the load. Maverick redraws the transform-and-external-product boundaries so the GPU’s operators are evenly loaded.

Following a bootstrapping through Maverick

Refreshing a ciphertext with parallel blind rotation

An illustrative walkthrough, based on the paper's abstract (this explainer is written without the full paper text; exact details are in the paper).

Step 1 of 5

A ciphertext needs bootstrapping

A homomorphic computation has run long enough that its ciphertext's noise budget is nearly exhausted, so it must be bootstrapped — and, with programmable bootstrapping, a chosen function applied at the same time via a lookup table.

In standard TFHE this triggers a long serial blind-rotation chain.

Why it works

Independent sub-chains let the GPU do many things at once. A single length-n chain has parallelism of one and idles the GPU → but breaking it into the square root of n independent sub-chains → so many external products run simultaneously and the cores are filled.
Late injection is what makes the split legal. Pre-loading the test vector forces one dependency chain → but injecting it after, as post-injection → so the computation can be reorganized into independent chains without changing the result.
The square-root split maximizes the available parallelism. A different decomposition would trade depth and width unfavorably → but the square root of n chains each of depth the square root of n → so the parallelism reaches the theoretical bound for this structure.
Partial transforms balance the operator workload. A full number-theoretic transform per external product loads operators unevenly → but terminating it early and pushing leftover work downstream → so the workload is spread evenly across the external-product operators.
Co-design beats either half alone. Exposing parallelism without balancing it, or balancing without exposing it, leaves performance on the table → but doing both together → so the GPU’s headroom is actually exploited, yielding state-of-the-art speedups.

What it costs (trade-offs and scope)

The reformulation is specific to blind rotation’s structure. Maverick’s multi-chain decomposition and post-injection are tailored to TFHE blind rotation; the technique is not a generic parallelization method, so its benefit is tied to this particular algorithm and its dependency structure.
Restructuring adds combination work. Turning one chain into many independent sub-chains means their results must later be combined, and the partial-domain transform shifts computation between operators; these introduce coordination the single serial chain did not have, a cost the design bets is far outweighed by the parallelism gained.
The balance depends on understanding the hardware. The partial-domain strategy relies on a careful, stage-aware account of how the number-theoretic transform maps onto the GPU’s operators; the gains hinge on that hardware-behavior modeling being accurate for the target GPU.
It targets programmable bootstrapping on GPUs. The reported results are for TFHE programmable bootstrapping accelerated on GPUs; other FHE schemes, other operations, or other accelerators would need their own analysis and would not automatically inherit these speedups.
Reported numbers are baseline- and setup-specific. The 331.2-times, 3.4-times, and up-to-108.5-times figures are measured against particular CPU and GPU baselines on specific workloads; the exact speedup depends on the parameters, the baselines, and the hardware.

The evaluation

Accelerating TFHE programmable bootstrapping

Property	CPU implementation	Prior GPU (compute scaling)	Maverick
Blind-rotation structure
External-product parallelism
Transform workload balance
GPU utilization
Reported speedup

A comparison of ways to accelerate TFHE programmable bootstrapping. By reconstructing blind rotation (shifting the test vector from pre-loading to post-injection) into about the square root of n independent sub-chains — raising external-product parallelism from one to the square root of n — and balancing the transform workload with a partial-domain strategy, Maverick reports state-of-the-art GPU acceleration: 331.2 times over the best CPU baseline and 3.4 times over the best GPU baseline on programmable bootstrapping, with up to a 108.5 times speedup. This explainer is written from the paper's abstract; exact figures and mechanisms should be read from the paper.Underlined values explain themselves when clicked.

Where this stops working

What to keep in mind

This explainer is written from the paper’s abstract (the full text was not accessible at the time of writing — the ASPLOS 2026 paper is open access under CC BY, but the copy was reachable only through a publisher page that could not be retrieved, and no author-hosted copy or preprint was found). The described system is the paper’s: Maverick is a GPU-based solution that rethinks TFHE bootstrapping acceleration through joint algorithm-hardware co-design. At the algorithmic level, it reconstructs blind rotation by shifting the test vector from pre-loading to post-injection, turning the original length-n single chain into a multi-chain structure with (per the abstract) the square root of n sub-chains of depth the square root of n, raising external-product parallelism from one to the theoretical bound of the square root of n. At the hardware level, it introduces a partial-domain transformation strategy that terminates the number-theoretic transform early in a stage-aware manner and selectively shifts computation to downstream operators, redefining operator boundaries to balance the workload across external-product operators. The paper reports that Maverick delivers state-of-the-art GPU acceleration, outperforming the best existing CPU and GPU baselines by 331.2 times and 3.4 times, respectively, on programmable bootstrapping, and achieving up to a 108.5 times speedup. The background above on FHE, TFHE, bootstrapping, blind rotation, external products, and the number-theoretic transform is standard homomorphic-encryption context provided to make the approach intuitive; the paper’s own account of the reformulation and the partial-domain strategy is the authority. The step-by-step walkthrough is illustrative, not a claim about the paper’s exact implementation, and the exact meaning of the reported 108.5-times figure (and the full evaluation) should be read from the paper.

Background

Why accelerating encrypted computation keeps coming down to its structure, not just its hardware

It helps to see Maverick within a broad pattern: fully homomorphic encryption is astonishingly powerful but astonishingly slow, and the slowness is concentrated in a few core operations — above all bootstrapping — so nearly all progress toward practicality is an assault on those operations. What is instructive is how often the winning move is not simply faster hardware but a rethinking of the computation’s structure so that hardware can help at all. Encrypted computation is full of operations that look, in their textbook form, inherently serial or awkwardly shaped for parallel machines, and the recurring lesson is that reformulating the mathematics — changing when a value is applied, how a transform is staged, where one operator ends and the next begins — can expose parallelism and balance that a straightforward implementation leaves buried. Maverick is a clean instance: it recognizes that TFHE’s blind rotation is serial by construction, and instead of asking for a bigger GPU it re-derives the algorithm so the serial chain becomes parallel chains, then tunes the transform to the hardware. This effort to make homomorphic encryption practical by attacking the cost and structure of its bootstrapping is the same terrain the work on affinity-based optimizations for TFHE on processing-in-DRAM covered elsewhere on this site occupies, reshaping how TFHE’s heavy operations map onto the hardware. Maverick’s contribution is to show that, for TFHE bootstrapping on GPUs, co-designing a parallelism-creating algorithm with a workload-balancing transform strategy turns a computation that could not fill a GPU into one that achieves state-of-the-art speed.

If you remember only three things

1. TFHE is a fully homomorphic encryption scheme whose programmable bootstrapping can refresh a ciphertext's noise and apply an arbitrary function at once, making it attractive for security-critical computation on encrypted data — but bootstrapping is prohibitively slow and dominates runtime. Hardware acceleration alone does not fix it, because the core operation, blind rotation, is a single chain of length n of external products where each step consumes the previous step's result. That makes it inherently serial: its parallelism is essentially one, so a GPU's thousands of cores sit idle, and on top of that the polynomial-transform work inside each external product is unevenly balanced across the GPU's operators. The barrier is a lack of algorithmic parallelism, not a lack of compute.
2. Maverick rethinks TFHE bootstrapping through algorithm-hardware co-design. Algorithmically, it reconstructs blind rotation by shifting the lookup table (test vector) from pre-loading at the chain's start to post-injection later, which breaks the single length-n chain into about the square root of n independent sub-chains, each of depth the square root of n. Because the sub-chains no longer depend on one another, they run in parallel, raising external-product parallelism from one to the square root of n, the theoretical maximum for this structure — finally giving the GPU many independent chains to fill its cores. At the hardware level, a partial-domain transformation strategy terminates the number-theoretic transform early (stage-aware) and selectively shifts leftover computation to downstream operators, redefining operator boundaries so the workload is balanced across the external-product operators.
3. The paper reports Maverick delivers state-of-the-art GPU acceleration for TFHE programmable bootstrapping, outperforming the best CPU and GPU baselines by 331.2 times and 3.4 times respectively, with up to a 108.5 times speedup. The trade-offs: the reformulation is specific to blind rotation's structure, splitting one chain into many adds combination and operator-shifting coordination, the balancing depends on an accurate stage-aware model of the GPU's behavior, and the results target programmable bootstrapping on GPUs rather than other schemes or accelerators. This explainer is written from the abstract, so the exact mechanisms and the precise meaning of the reported figures should be confirmed in the paper.

Check yourself

Check your understanding

1. Why does simply running TFHE bootstrapping on a more powerful GPU fail to make it fast?
2. What is Maverick's core algorithmic idea for creating parallelism in blind rotation?
3. What is Maverick's hardware-level contribution, and why is it needed alongside the algorithmic one?
4. What does Maverick achieve, and what are the limits of the approach?

Sources

The paper is “Maverick: Rethinking TFHE Bootstrapping on GPUs via Algorithm-Hardware Co-Design” by Zhiwei Wang, Haoqi He, Lutan Zhao, Qingyun Niu, Dan Meng, and Rui Hou (State Key Laboratory of Cyberspace Security Defense, Institute of Information Engineering, Chinese Academy of Sciences), published at ASPLOS 2026, DOI 10.1145/3779212.3790186. The paper is open access under CC BY.

This explainer is written from the paper’s abstract; the full text was not accessible at the time of writing (the open-access copy was reachable only through a publisher page that could not be retrieved, and no author-hosted copy or preprint was found). Maverick is a GPU-based solution that rethinks TFHE bootstrapping through joint algorithm-hardware co-design. Algorithmically, it reconstructs blind rotation by shifting the test vector from pre-loading to post-injection, turning the original length-n single chain into a multi-chain structure with the square root of n sub-chains of depth the square root of n, raising external-product parallelism from one to the theoretical bound of the square root of n. At the hardware level, it introduces a partial-domain transformation strategy that terminates the number-theoretic transform early in a stage-aware manner and selectively shifts computation to downstream operators, redefining operator boundaries to balance the workload across external-product operators. The paper reports state-of-the-art GPU acceleration, outperforming the best CPU and GPU baselines by 331.2 times and 3.4 times respectively on programmable bootstrapping, with up to a 108.5 times speedup. The background on FHE, TFHE, bootstrapping, blind rotation, and the number-theoretic transform is standard homomorphic-encryption context; exact mechanisms and full results should be confirmed in the paper.