BitPacker: Enabling High Arithmetic Efficiency in Fully Homomorphic Encryption Accelerators

Fully homomorphic encryption (FHE) lets a cloud compute directly on your ENCRYPTED data without ever decrypting it — perfect privacy, but about 10,000x slower than normal, which is why people build custom accelerator chips for it; the trouble is those chips run an encryption scheme (CKKS) designed for CPUs, and CKKS stores each huge encrypted number as a bundle of smaller "residues" whose sizes (30 to 60 bits) are tied to a precision knob and rarely fill the chip's fixed-width (say 64-bit) lanes — leaving roughly 60% of the very expensive multiplier hardware empty; this paper (MIT) presents BitPacker, a redesign of CKKS that DECOUPLES residue size from precision so almost every residue fills a full word (one small leftover "terminal" residue mops up the rest), cutting the waste from 60% to about 7% — the same data, precision, and security in far fewer, fuller words — which, because multiplier cost grows quadratically with width, makes a state-of-the-art accelerator gmean 59% faster and 59% lower-energy with no hardware changes and no loss of accuracy.

The argument in one glance

Problem

Computing on encrypted data is a privacy dream — but painfully slow

Fully homomorphic encryption (FHE) is one of the most remarkable ideas in cryptography: it lets a server run a computation directly on ENCRYPTED data and produce an encrypted result, without ever decrypting anything. A cloud can run your neural network on your data and never see the data or the answer — only you, holding the key, can decrypt it. This enables private machine-learning inference, private genome analysis, and more. The catch is speed: FHE is roughly 10,000x slower than the same computation on plaintext, because it turns simple arithmetic into operations on enormous encrypted numbers. That slowdown is what has kept FHE out of practical use.
What people did

Build accelerators, and use the Residue Number System to fit the huge numbers in hardware

The response has been custom accelerator chips — F1, CraterLake, ARK, SHARP, BTS — that recover well over 1000x of the gap and bring FHE within reach of real-time use. They target CKKS, the leading FHE scheme, which does approximate arithmetic on encrypted vectors of numbers and suits machine learning well. CKKS represents each encrypted value as a gigantic integer, over 1000 bits wide. To handle such integers on hardware, every fast implementation uses the RESIDUE NUMBER SYSTEM (RNS): split each wide integer into several narrow "residues," each small enough to fit in one hardware word, and compute on the residues in parallel. Accelerator designers then pick a good fixed word width — 64 bits in BTS and ARK, about 28 bits in F1 and CraterLake, 36 bits in SHARP.
Why it fell short

Residue sizes are tied to precision, so they never fill the datapath

Here is the inefficiency. In standard RNS-CKKS, each residue's SIZE is linked to the "scale" — a per-level precision parameter that programs deliberately vary from 30 to 60 bits to trade precision against cost. So the residues come in odd sizes that rarely match the accelerator's fixed word width: a 30-bit residue placed in a 64-bit lane leaves 34 bits unused, and across a program's whole range of scales, NO single fixed width fits well. The result is that around 60% of the datapath sits empty. On a CPU this barely matters, but accelerators are dominated by MULTIPLIERS whose area and energy grow QUADRATICALLY with word width — multipliers are about 70% of functional-unit area in CraterLake — so a 60% space overhead becomes roughly a 2.6x energy overhead in the multipliers. And the reason RNS-CKKS tied residues to scales in the first place — it made the frequent "rescale" operation cheap (just drop a residue) — is exactly what wastes the hardware.
This paper's idea

Redesign the scheme for the hardware: decouple residue size from precision

This paper (MIT — Samardzic and Sanchez) makes the case that fully using an FHE accelerator requires redesigning the FHE ALGORITHM for it, not just accelerating the CPU version — and it delivers the first such redesign. BitPacker is a new RNS implementation of CKKS that DECOUPLES residue size from the scale. It packs most of the data into full word-sized "non-terminal" residues and puts the leftover bits into one small "terminal" residue — encoding the SAME information in far fewer, fuller words, cutting datapath waste from about 60% to about 6.6%, with no loss of precision, no extra bootstrapping, and the same security. The hard part is that decoupling breaks RNS-CKKS's cheap rescale (which just dropped a residue), so BitPacker introduces new implementations of rescale and adjust: it temporarily scales the ciphertext UP to a larger modulus with more residues, then scales DOWN to shed the ones it does not need — and it maps that work onto the change-RNS-base functional unit accelerators already have, so level management stays cheap. Because a homomorphic multiply costs O(R^2) in the number of residues R, using fewer residues pays off superlinearly: gmean 59% faster, 59% less energy, and 19% smaller area on a state-of-the-art accelerator, with no hardware changes.

Why this problem is worth solving

FHE is the closest thing cryptography has to magic — the ability to outsource computation on private data with a mathematical guarantee that the data stays secret — and the only thing standing between it and wide use is efficiency. Understanding what makes it slow, and how it is made fast, starts with the scheme everyone accelerates. A

FULLY HOMOMORPHIC ENCRYPTION (FHE) is encryption under which you can compute: given encryptions of numbers, anyone can produce the encryption of their sum or product without the key, so a server computes on ciphertexts and learns nothing. CKKS is the state-of-the-art FHE scheme for numerical work — it encrypts a whole vector of approximate (fixed-point) numbers in one ciphertext and supports element-wise addition, element-wise multiplication, and rotations, which makes it a natural fit for machine learning. Its cost comes from three facts: each ciphertext is a pair of polynomials with tens of thousands of coefficients, each coefficient is a huge integer over 1000 bits wide, and every multiplication adds noise that must be periodically cleaned up by a very expensive procedure called BOOTSTRAPPING. Those enormous integers and the noise management are why FHE is thousands of times slower than plaintext, and why it is worth building special hardware for

makes clear why raw arithmetic throughput is the whole game. Accelerators exist precisely because CKKS turns a small computation into a mountain of big-integer arithmetic.

The specific place efficiency leaks is in how those big integers are laid out on the hardware. A

the RESIDUE NUMBER SYSTEM (RNS) is the trick that makes big-integer FHE fast: instead of working with a 1000-bit integer directly, you pick several smaller coprime moduli and represent the integer by its remainder (“residue”) modulo each one, so a wide number becomes a bundle of narrow residues that each fit in a hardware word and can be processed independently and in parallel. The number of residues, R, sets how much work a homomorphic operation takes. The mismatch is this: in standard RNS-CKKS, each residue’s bit-width is pinned to the SCALE at its level — the precision parameter the program chose, anywhere from 30 to 60 bits — so residues are sized by a precision knob, not by the hardware. When a 30-bit residue lands in a 64-bit multiplier lane, more than half the lane is idle, and because a program uses many different scales, no fixed lane width can fit them all. Roughly 60% of the datapath goes unused

is the crux. It matters because the wasted width is not free: the multipliers that fill most of an FHE accelerator scale quadratically with their width, so half-empty lanes translate directly into a large, avoidable energy and area cost. Fixing the layout, without touching the math or the security, is what BitPacker is about.

What people did before, and where it broke

Run CKKS on CPUs. Flexible, but about 10,000x slower than plaintext — impractical for real workloads. The datapath waste is invisible here because CPUs have general datapaths, so the CPU-era design of CKKS never had to care about it.
Accelerate CKKS with a fixed 64-bit datapath (BTS, ARK). Fast, but a 64-bit lane holding a 30-bit residue wastes most of its width, and the multipliers that dominate the chip pay quadratically for that width.
Use narrow datapaths and split each scale (F1, CraterLake, ~28-bit). Represent a large scale with two smaller residues (double-prime rescaling). More efficient at some scales, but adds residues (more R, more work) and is still tuned to particular scales.
Carefully choose the word size (SHARP, 36-bit). Pick one width and force programs to use scales that fit it. Better on average, but it caps precision at about 20 bits — far less than the range 16-bit floating point gives — and still cannot be efficient across the full range of scales a program uses.
The gap. As long as residue size is tied to scale, NO fixed datapath can be efficient across a program’s 30-to-60-bit scales — the utilization is bad at some scale no matter what width you pick. Nobody had broken that link. That is the gap BitPacker fills.

How BitPacker fills the datapath

Decouple residue size from precision, then keep the level operations cheap on existing hardware

Compute on encrypted data, on an algorithm built for CPUs

FHE accelerators recover over 1000x of FHE's slowdown, but they run CKKS as designed for CPUs, where residue size is tied to the precision scale and datapath waste is invisible. On an accelerator dominated by wide multipliers, that inherited design leaves most of the datapath idle.
↓ →
Decouple residue size from the scale new

BitPacker breaks the RNS-CKKS rule that a residue must be sized to its level's scale. Instead it sizes residues to the HARDWARE word, so the precision a program wants and the width the hardware offers are no longer forced to match — the same encrypted value, laid out to fit the lanes.
↓ →
Split into non-terminal and terminal residues new

Most of the ciphertext is stored in full word-sized "non-terminal" residues that pack the lanes completely; the leftover bits go into one (occasionally two) smaller "terminal" residue. The same amount of information now lives in fewer, fuller words — datapath waste drops from about 60% to about 6.6% — with the same number of levels and no precision loss.
↓ →
Re-implement rescale and adjust new

Decoupling breaks RNS-CKKS's cheap rescale, which simply dropped the last residue. BitPacker instead scales the ciphertext UP to a larger modulus with extra residues, then scales DOWN to shed the residues it no longer needs — accurately moving between levels while keeping every remaining residue fully packed, sometimes introducing new moduli rather than only dropping them.
↓ →
Map the level work onto hardware that already exists new

Scaling up is a cheap multiply-by-a-constant; scaling down sheds several residues at once, which the accelerator's existing change-RNS-base functional unit (bConv in ARK and SHARP) performs almost as fast as shedding one. So level management stays as cheap as RNS-CKKS's, and BitPacker needs NO hardware changes.
↓ →
Choose NTT-friendly moduli per level new

A greedy algorithm picks non-terminal moduli as NTT-friendly primes just under the word width, and terminal moduli to match each level's target scale within 0.5 bits. It preserves the same security (every modulus stays under the same bound) and the same accuracy as RNS-CKKS.

A software/algorithm redesign of CKKS's RNS layer, evaluated on the CraterLake accelerator (28-bit words, 2048 lanes, 256MB register file, 1 TB/s HBM) and swept to ARK-like (64-bit) and SHARP-like (36-bit) designs, on five FHE benchmarks. Requires no hardware changes and applies to all three accelerators.

The idea

To use an accelerator fully, redesign the algorithm for it — do not just port the CPU version. The framing insight is that FHE accelerators inherited an algorithm shaped by CPU assumptions, and CPUs never paid for half-empty datapaths, so the inefficiency was baked into the scheme before any chip was built. BitPacker is the first redesign of an FHE scheme aimed at accelerators, and its whole value is in changing the algorithm so the hardware is used well. This co-design-the-algorithm-for- the-hardware discipline is one the site keeps rewarding from both directions: the quantized-transformer and autotuning pages reshape the computation to fit what the hardware does cheaply, and the non-GEMM- accelerator page does the mirror image — reshape the hardware to fit the workload. The lesson is that the biggest wins often live not in the hardware or the algorithm alone but in the seam between them, which a port across that seam leaves untouched.

A mismatched representation wastes the resource — change the encoding to fit. The concrete problem is representational: CKKS encoded its numbers so that a precision knob (the scale) also decided the storage unit (the residue width), and that coupling left the multiplier lanes half-empty. BitPacker fixes it by choosing a representation whose unit is the hardware word, so the lanes fill. This change-the-encoding-to-remove- waste move is exactly the one the site’s kernel-re-randomization page makes when it shows a painful limit was merely an artifact of 32-bit instruction encodings and dissolves it by switching code models, and the one the orientation-learning page makes when a bad coordinate choice is swapped for one that fits. The recurring pattern: when a resource sits idle, suspect the representation, because a limit that looks fundamental is often just an accident of how the data was encoded.

Untie two things that were conflated, then pay a small price to restore what the coupling bought. The scale and the residue width were tied together for a reason — the tie made rescaling trivial (drop a residue). BitPacker’s real work is to separate the two concerns and then re-implement rescale and adjust so they stay cheap without the tie, scaling up and shedding residues and mapping that onto an existing functional unit. Rejecting a convenient-but-costly coupling and then engineering back the convenience it provided is the same move the site’s scheduling and allocation pages make when they refuse a false either/or and hybridize — and the mapping of the new rescale onto the accelerator’s change-RNS-base unit is the same map-onto-a-primitive-the-hardware- already-has trick the site’s pages use when they cast a new problem onto a solved one. The payoff is disproportionate because the cost that was freed — the O(R^2) multiplier work — grows superlinearly, so shrinking R buys far more than the modest extra bookkeeping costs.

Why packing tighter makes FHE far faster

From wasted lanes to a 59% speedup

Reworking CKKS's RNS layout for accelerators. Numbers from the paper's evaluation on CraterLake-class designs.

Step 1 of 5

Where the waste comes from

In RNS-CKKS each residue is sized to its level's scale, which programs vary from 30 to 60 bits. A 30-bit residue in a 64-bit lane wastes 34 bits, and since one program uses many scales, no fixed lane width fits them all. Roughly 60% of the datapath sits unused.

a 6-scale ciphertext (30+40+40+50+50+60 bits) needs six 64-bit words = 384 bits to hold 240 bits of information
that is 144 wasted bits, a 60% space overhead, on every such ciphertext

Why it works

RNS-CKKS ties each residue’s size to its level’s scale (30 to 60 bits) → residues rarely fill a fixed hardware word, and no single width fits a program’s many scales → about 60% of the datapath sits idle.
Multiplier area and energy grow quadratically with word width, and a homomorphic multiply costs O(R^2) in residues → the idle width and the extra residues cost far more than linearly → the waste becomes about a 2.6x multiplier-energy overhead.
BitPacker sizes residues to the hardware word (full non-terminal residues plus one small terminal residue) → the same information packs into fewer, fuller words → datapath waste drops to about 6.6% and R falls, cutting the O(R^2) work superlinearly.
Decoupling would normally make rescale expensive, but scaling up then shedding residues maps onto the existing change-RNS-base unit → level management stays as cheap as RNS-CKKS’s → the packing win comes with no new hardware and no offsetting slowdown.
Moduli are chosen as NTT-friendly primes matching each level’s scale within 0.5 bits, all under the same bound → the same information, levels, and modulus limits are preserved → security and accuracy are unchanged.

What it costs (trade-offs and scope)

Level management does more arithmetic. BitPacker’s rescale and adjust introduce moduli and scale up and down rather than dropping a single residue, costing 4-7% more work; this is only cheap because the accelerator’s change-RNS-base unit sheds many residues at once — on a CPU, which lacks that unit, the level cost is higher, so BitPacker’s CPU speedup is 24% versus 59% on accelerators.
Terminal moduli are constrained. Moduli must be NTT-friendly primes no wider than the word, and few exist, so some scales need two terminal residues; the greedy matcher lands within 0.5 bits of the target and is occasionally 1 bit worse on a numerically sensitive workload — though end-to-end accuracy is unchanged.
The win scales with how bad the waste was. Gains are largest on small-scale workloads and on wide (64-bit) datapaths, where RNS-CKKS is up to 2.18x slower; a program whose scales happen to align with the word width benefits less.
It does not reduce levels or bootstrapping. BitPacker shrinks the residues-PER-level, not the number of levels or how often the expensive bootstrapping runs; it is a datapath-utilization win, not a change to FHE’s fundamental depth cost.
It targets CKKS on accelerators with the right functional unit. The specific gains rely on approximate fixed-point vector FHE (CKKS) and on an accelerator that already has a change-RNS-base-style unit (CraterLake, ARK, SHARP do); other FHE schemes are out of scope, though the pack-to-the-datapath idea is broader.

The evaluation

CraterLake as the baseline (28-bit words, 2048 lanes, 256MB register file, 1 TB/s HBM, RTL synthesized in 12/14nm), swept to ARK-like (64-bit) and SHARP-like (36-bit) word sizes, on five FHE programs (ResNet-20, ResNet-20+AESPA, RNN, SqueezeNet, LogReg) with two bootstrapping algorithms, N = 64K, and 128-bit security.

Filling the accelerator's datapath

Property	RNS-CKKS (fixed datapath)	Tuned word size (SHARP, 36-bit)	BitPacker (this work)
Residue size
Datapath waste
Precision
Multiplier cost (quadratic in width)
Versus baseline

As long as residue size is tied to scale, no fixed datapath is efficient across a program's 30-to-60-bit scales, and forcing a single scale (SHARP) sacrifices precision. BitPacker sizes residues to the word, cutting waste from about 60% to 6.6% with full precision — gmean 59% faster and 19% smaller than RNS-CKKS, and 43% faster than a 36-bit design, all with no hardware changes and no accuracy loss.Underlined values explain themselves when clicked.

Where this stops working

What to keep in mind

Read the scope precisely. BitPacker is a redesign of CKKS’s RNS layer, so it targets approximate fixed-point vector FHE (CKKS) and relies on the accelerator already having a change-RNS-base-style functional unit — which CraterLake, ARK, and SHARP have — to make its heavier rescale and adjust cheap. On a CPU, which lacks that unit, the level-management cost is higher and the speedup drops to 24% versus 59% on accelerators. The gains scale with how badly RNS-CKKS wasted the datapath: largest on small-scale workloads and wide (64-bit) datapaths (where RNS-CKKS is up to 2.18x slower), smaller when a program’s scales happen to match the word width. BitPacker shrinks the residues-per-level, not the number of levels or how often the expensive bootstrapping runs, so it is a utilization win, not a change to FHE’s depth cost; and its greedy moduli choice can be about 1 bit less precise on a numerically sensitive workload, though end-to-end accuracy and 128-bit security are unchanged. Within that scope the message is clean and general: a representation that ties a precision knob to a storage unit will waste whatever hardware it runs on, and untying them — sizing the data to the datapath and paying a small, hardware-mapped cost to keep the level operations cheap — recovers a large, superlinear win for free, with no hardware changes and no loss of accuracy.

Background

Co-design for the hardware, unwaste the representation, and shrink the superlinear cost

This paper sits in the site’s cryptography-and-accelerators cluster and rhymes with several ideas covered elsewhere on this site. Its framing is co-design: an accelerator inherits inefficiency when it runs an algorithm built for a different machine, so the win is to redesign the algorithm for the hardware — the same reshape-the-computation-to-fit-the-hardware discipline the quantized-transformer and autotuning pages use, and the mirror image of the non-GEMM-accelerator page, which reshapes the hardware to fit the workload; the biggest gains live in the seam a naive port leaves untouched. Its core technique is to recognize that a mismatched representation wastes a resource and to change the encoding so it fits — the same move the kernel-re-randomization page makes when it shows a 2GB limit is merely an artifact of 32-bit instruction encodings and dissolves it by switching code models, and the orientation-learning page makes when it swaps a bad coordinate choice for one without the defect. It works by untying two conflated concerns — precision scale and residue width — the same refuse-a-convenient-but-costly-coupling move the scheduling and allocation pages make when they hybridize instead of accepting a false either/or, and it restores the cheapness the coupling bought by mapping its new rescale onto the change-RNS-base unit the chip already has, the same cast-the-new-problem-onto-a-primitive-you-already- have trick behind the graph and search pages that reduce a fresh problem to a solved one. And the reason the payoff is so large is that the freed cost — the O(R^2) multiplier work, quadratic in datapath width — grows superlinearly, the same attack-the-superlinear-term logic the non-GEMM- accelerator page uses when it notes multipliers dominate and scale with width. Together they make BitPacker a case study in finding a free, superlinear win by fixing the representation at the hardware-algorithm seam.

If you remember only three things

1. Fully homomorphic encryption (FHE) lets a server compute on ENCRYPTED data without decrypting it — a privacy breakthrough that is about 10,000x slower than plaintext, so custom accelerators recover over 1000x of the gap. But those accelerators run CKKS, the leading FHE scheme, as designed for CPUs: CKKS splits each huge (over-1000-bit) encrypted number into narrow "residues" via the Residue Number System, and RNS-CKKS ties each residue's size to the "scale" (a precision knob programs vary from 30 to 60 bits), so residues rarely fill the chip's fixed-width lanes and about 60% of the datapath sits idle — costly because multipliers dominate these chips and scale QUADRATICALLY with width.
2. BitPacker (the first redesign of an FHE scheme for accelerators) DECOUPLES residue size from the scale: it packs most data into full word-sized "non-terminal" residues and mops up the leftover in one small "terminal" residue, encoding the same information in fewer, fuller words and cutting datapath waste from about 60% to 6.6% — with the same levels, precision, and 128-bit security. The catch is that decoupling breaks RNS-CKKS's cheap rescale (drop a residue), so BitPacker re-implements rescale and adjust by scaling the ciphertext UP to more residues and then shedding the unneeded ones, mapping that work onto the change-RNS-base functional unit accelerators already have — so level management stays cheap and no hardware changes are needed.
3. Because a homomorphic multiply costs O(R^2) in the number of residues R, reducing R pays off superlinearly: gmean 59% faster (up to 3x), 59% less energy, 37% less data movement, and a 19% smaller chip on a state-of-the-art accelerator, plus 43% faster than a 36-bit SHARP-like design, all with no accuracy loss. The transferable lessons: to use an accelerator fully, redesign the algorithm for it rather than porting the CPU version; when a resource sits idle, suspect the representation and change the encoding to fit; untie a precision knob from a storage unit and pay a small, hardware-mapped cost to keep the freed operations cheap; and attack the cost that grows superlinearly.

Check yourself

Check your understanding

1. RNS-CKKS wastes about 60% of an FHE accelerator's datapath, yet the paper stresses this waste is far more costly than "60% more area" suggests. Predict why the penalty is disproportionate.
2. BitPacker's central move is to stop sizing residues by the precision scale and size them by the hardware word instead. Predict what general principle this illustrates.
3. RNS-CKKS tied residue size to scale specifically because it made rescaling cheap — just drop a residue. Predict how BitPacker can decouple them without making rescale expensive.
4. The paper argues that fully using an FHE accelerator requires redesigning the FHE algorithm, not just accelerating the existing one. Predict why porting the CPU algorithm leaves so much on the table.

Sources

BitPacker: Enabling High Arithmetic Efficiency in Fully Homomorphic Encryption Accelerators (MIT DSpace PDF) — ASPLOS 2024 (full text read).
ACM DL: BitPacker (DOI 10.1145/3620665.3640397) — published version.
DBLP record — bibliographic entry.