Falcon: Algorithm-Hardware Co-Design for Efficient Fully Homomorphic Encryption Accelerator

Liang Kong, Xianglong Deng, Guang Fan, Shengyu Fan, Lei Chen, Yilan Zhu and 4 others

Fully homomorphic encryption lets a server compute on data it can never see, which is ideal for private cloud computing, but it is so slow that people build dedicated accelerator chips for it — and a recurring frustration is that a clever cryptographic optimization that looks great on paper often fails to speed up the real hardware, because constraints like limited on-chip memory get in the way; this paper (Chinese Academy of Sciences and Ant Group — Liang Kong, Mingzhe Zhang, and colleagues) presents Falcon, which co-designs the algorithm and the hardware together so that the algorithmic gains actually translate into hardware efficiency.

The argument in one glance

Problem

A clever FHE optimization on paper often does not speed up the real accelerator

Fully homomorphic encryption (FHE) is a remarkable idea: it lets a server compute directly on encrypted data, producing an encrypted result, without ever decrypting anything or learning what the data is. This makes it a natural fit for secure cloud computing, where you want to hand a cloud your sensitive data and get a useful answer back without trusting the cloud with the plaintext. The obstacle is speed. FHE turns even simple operations into enormous computations over big encrypted objects (ciphertexts are large polynomials, and the operations that combine them are heavy), so running a real workload under FHE can be orders of magnitude slower than on plaintext. That overhead is why people build dedicated hardware accelerators for FHE, custom chips that do the specific heavy operations fast. But there is a persistent, frustrating gap. Cryptographers keep inventing algorithmic optimizations that reduce the amount of work FHE needs in theory, and those optimizations look like clear wins on paper. When you actually deploy them on an FHE accelerator, however, the hardware's constraints get in the way — most notably its limited on-chip memory. An optimization that reduces arithmetic but increases how much data must be shuffled, or that assumes more fast memory than the chip has, can end up no faster, or even slower, on the real hardware. So the theoretical algorithmic advantage does not translate into hardware efficiency, and the promise of a faster FHE gets stuck between the algorithm and the machine.
What people did

Optimize the algorithm and the hardware separately

The usual division of labor treats the two as separate problems. Cryptography researchers design algorithmic optimizations that reduce the theoretical cost of FHE operations, and hardware architects build accelerators that execute FHE's primitives quickly, each side working within its own discipline and then handing off to the other.
Why it fell short

Separate optimization lets hardware constraints erase the algorithmic gains

Optimizing the two sides in isolation is exactly what produces the gap. An algorithmic optimization is usually evaluated by an abstract cost measure — how many of some expensive operation it removes — that assumes the data it needs is readily available. But an FHE accelerator does not have unlimited fast memory: ciphertexts and the auxiliary keys FHE uses are large, and only a small amount can sit in on-chip memory at once, so a great deal of the real cost is moving data between the chip and slower memory. An optimization that shaves arithmetic while changing the data-access pattern can increase that data movement, and under the chip's limited memory capacity the extra movement can cost more than the arithmetic it saved. Conversely, hardware designed without knowledge of which algorithmic optimizations it will run may not provide the on-chip structure those optimizations need to pay off. Because neither side sees the other's constraints, the theoretical advantage measured on the algorithm side and the efficiency achieved on the hardware side diverge. What was missing was a way to design the algorithm and the hardware together, so that the algorithmic choices respect the hardware's memory limits and the hardware is built to make those choices efficient.
This paper's idea

Co-design the algorithm and the hardware so the gains survive

Falcon is an FHE accelerator built through algorithm-hardware co-design, whose premise is that the gap between an FHE optimization's theoretical advantage and its real hardware efficiency should be closed by designing both sides together rather than in isolation. Instead of taking an algorithmic optimization as fixed and then trying to run it on a fixed accelerator, co-design lets each side inform the other: the algorithmic choices are shaped so they remain efficient under the hardware's constraints — above all its limited on-chip memory capacity — and the hardware is shaped to make those algorithmic choices pay off. The goal is that an optimization's theoretical reduction in work actually shows up as a speedup on the chip, because the design has accounted for how much data has to move and what fits in on-chip memory, rather than assuming those away. By aligning the algorithm and the architecture, Falcon aims to deliver the efficiency that separately-optimized designs leave on the table, making FHE acceleration more practical for the secure-cloud use cases FHE is meant to enable. (The paper's specific co-design techniques and quantitative results are in its full text, which was not available for this write-up; see the note below.)

Why this problem is worth solving

FHE could remove one of the deepest obstacles to using the cloud with sensitive data, but only if it can be made fast enough, and accelerators are the main path there.

The value proposition of fully homomorphic encryption is unusual and powerful: it lets you outsource computation on your most sensitive data — medical records, financial information, private queries — to a server you do not fully trust, because the server computes on ciphertexts and never sees the plaintext or the result. If this were practical, it would resolve a fundamental tension in cloud computing between wanting the cloud’s scale and not wanting to expose your data to it. The reason FHE is not yet ubiquitous is purely performance: the encrypted computations are so much heavier than their plaintext equivalents that many real workloads would be unacceptably slow. Dedicated accelerators are the leading response, because the heavy FHE primitives are regular and specializable, so custom hardware can run them far faster than a general CPU. But an accelerator only helps if the algorithmic progress the cryptography community makes can be realized on it. When a promising optimization stalls on the hardware, the field loses the compounding benefit of algorithm and hardware improving together. So making sure algorithmic gains actually translate into accelerator speedups is central to whether FHE becomes practical at all.

The core difficulty is that the algorithm’s cost model and the hardware’s real costs are not the same, and on-chip memory is where they diverge most.

FHE’s data is big. Ciphertexts are large polynomials, and the auxiliary evaluation keys used by operations like key-switching and bootstrapping are larger still, so the working set of an FHE computation vastly exceeds what fits in an accelerator’s on-chip memory. That makes many FHE operations bound not by arithmetic but by data movement: the time is dominated by shuttling ciphertexts and keys between fast on-chip memory and slower off-chip memory. An algorithmic optimization is typically judged by a clean abstract metric — how many expensive operations it eliminates — which implicitly assumes the operands are on hand. But if the optimization reorganizes the computation in a way that touches more distinct data, or that needs more of it resident at once than the chip’s limited memory holds, then the real bottleneck, data movement under a memory cap, can grow even as the arithmetic shrinks. The clean theoretical win and the messy hardware reality part ways precisely because the abstract metric ignores the memory constraint the hardware cannot escape. Bridging that requires reasoning about the algorithm and the memory-limited hardware jointly, so the design chooses optimizations whose reduced work survives contact with the chip’s memory limits — which is the hard, worthwhile problem.

What people did before, and where it broke

Design algorithmic optimizations against an abstract cost metric. Reduce the theoretical count of expensive FHE operations. Where it broke. The metric assumes operands are available; on real hardware, an optimization can increase data movement and, under limited on-chip memory, run no faster or slower.
Build accelerators for FHE primitives in isolation. Make custom hardware that executes FHE operations quickly. Where it broke. Hardware built without knowledge of which algorithmic optimizations it will run may lack the on-chip support those optimizations need to pay off.
Take an optimization as fixed and port it to a fixed accelerator. Combine the best algorithm with the best chip after the fact. Where it broke. Neither side accounted for the other’s constraints, so the algorithm’s theoretical advantage and the hardware’s achievable efficiency diverge.
Add more on-chip memory to fit the working set. Enlarge the accelerator’s fast memory. Where it broke. On-chip memory is expensive and limited, and FHE’s working set is huge, so this cannot be scaled indefinitely and does not target the algorithm-hardware mismatch itself.
The gap. No design chose the algorithmic optimizations and the accelerator together so that the theoretical gains held up under the hardware’s real memory limits.

How Falcon approaches it

Closing the gap between algorithmic advantage and hardware efficiency

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

The idea

Co-design the algorithm and the hardware, especially around memory capacity. Falcon’s central stance is that FHE’s algorithmic optimizations and its accelerator must be designed jointly, with the hardware’s limited on-chip memory as a first-class concern, so the two fit rather than fight. Exploring the algorithmic and hardware choices together, with memory capacity as the binding constraint that shapes both, is the same undertaking the work on hardware mapping co-exploration toward memory capacity (Cocco) covered elsewhere on this site pursues, refusing to optimize the mapping and the memory in isolation. Falcon applies this co-exploration to FHE, aligning the cryptographic optimizations with what the accelerator’s memory can actually sustain.

Tame the huge, memory-hungry state that FHE operations create. The reason the gap exists is that FHE’s ciphertexts and keys are enormous relative to on-chip memory, so a central part of making FHE fast is managing that large state so it does not overwhelm the memory system. Carefully managing the large intermediate state of FHE so the memory system is not swamped is the same principle the work on region-based bootstrapping management for FHE (ResBM) covered elsewhere on this site is built on, keeping FHE’s memory demands in bounds so computation can proceed. Falcon’s co-design is aimed squarely at this pressure point, choosing algorithmic organizations whose data movement stays within the accelerator’s memory limits.

Build a dedicated accelerator because general hardware cannot keep up. Falcon is, at bottom, a custom chip for FHE, taking the position that FHE’s overhead is large enough to justify specialized hardware rather than relying on a general processor. Designing purpose-built hardware to make fully homomorphic encryption practical, because commodity processors are far too slow, is the same idea the work on resilient design for fully homomorphic encryption accelerators (ReliaFHE) covered elsewhere on this site develops, committing to an FHE-specific accelerator as the path to practicality. Falcon adds the co-design discipline, so its accelerator and the algorithms it runs are matched to each other.

Following an FHE computation on such an accelerator

Where the algorithm-hardware gap appears, and where co-design helps

An illustrative sketch, based on the paper's abstract and standard FHE-accelerator concepts, of where the gap arises. It is not a specific mechanism from the paper, whose full text was not available; details should be read there.

Step 1 of 5

A workload is expressed as FHE operations

A computation to run on encrypted data is compiled into FHE operations over large ciphertexts, including heavy primitives like the ones behind multiplication, key-switching, and bootstrapping that dominate the cost.

Ciphertexts and their auxiliary keys are large relative to on-chip memory.

Why it works

Joint design lets the algorithm respect the memory limit. An optimization judged only by abstract cost ignores the memory cap → but co-designing it with the hardware keeps its data movement within on-chip memory → so its reduced arithmetic is not swamped by extra transfers.
Joint design lets the hardware support the algorithm. An accelerator built blind to its optimizations may lack the right on-chip structure → but shaping the hardware around the algorithmic choices → provides what those choices need to pay off.
Aligning the two closes the theory-hardware gap. The abstract metric and the real hardware cost diverge when designed apart → but choosing algorithm and architecture together aligns them → so a theoretical reduction shows up as actual speedup.
Controlling data movement targets the real bottleneck. FHE’s working set exceeds on-chip memory, so movement dominates → but co-design that keeps the working set within limits attacks that bottleneck directly → rather than optimizing arithmetic the hardware was not bound by.
A dedicated, matched accelerator beats general hardware plus a mismatched chip. General processors are far too slow for FHE and a mismatched accelerator wastes its algorithm → but a purpose-built chip matched to its algorithms → delivers the efficiency FHE needs to be practical.

What it costs (trade-offs and scope)

Co-design ties the algorithm and hardware together. Designing the two jointly means they are matched to each other, which can make the accelerator less general — hardware specialized around a set of algorithmic choices may serve other FHE optimizations or schemes less well than a more generic design.
It targets FHE’s memory-bound regime. The benefit comes from resolving the mismatch that limited on-chip memory creates; the approach is aimed at the memory-capacity constraint specifically, and workloads or operations that are not memory-bound would gain less from it.
Building a dedicated accelerator is a large commitment. A custom FHE chip is costly to design and fabricate, and its advantages depend on the FHE schemes and operations remaining stable enough to justify the specialization.
The gains depend on the specific co-design. Whether an algorithmic optimization’s theoretical advantage is fully recovered depends on how well the particular algorithm and hardware are matched, which the paper details for its design; other combinations may recover more or less.
This explainer is drawn from limited source material. The full paper text was not accessible for this write-up; the description here is based on the paper’s abstract and standard FHE-accelerator background, so Falcon’s specific co-design techniques, its architecture, and its quantitative results should be confirmed in the paper.

How it compares

Realizing FHE algorithmic optimizations on hardware

Property	Algorithm optimized alone	Accelerator built alone	Falcon (co-design)
Accounts for on-chip memory limits
Data movement considered
Algorithm and hardware matched
Theoretical gain realized on hardware
Generality

A qualitative comparison, based on the paper's abstract and standard FHE-accelerator background, of ways to realize FHE algorithmic optimizations. Falcon co-designs the algorithm and the hardware, with limited on-chip memory as a first-class concern, so an optimization's theoretical advantage translates into real hardware efficiency instead of being erased by data movement. The paper's specific techniques and quantitative results should be read from its full text.Underlined values explain themselves when clicked.

Where this stops working

What to keep in mind

This explainer is based on the paper’s abstract and standard background on FHE and FHE accelerators, not its full text, which was not accessible for this write-up (the ACM version was not retrievable and no author preprint or open copy was found). The problem is stated by the authors: fully homomorphic encryption enables computation on encrypted data without compromising privacy, positioning it for secure cloud computing, but its substantial computational overhead impedes practical deployment and motivates dedicated hardware accelerators; and when deploying cryptographic algorithm optimizations on FHE accelerators, hardware constraints — typically limited memory capacity — often lead to a disparity between the theoretical algorithmic advantage and the achievable hardware efficiency. The response, as reflected in the title and abstract, is Falcon, an FHE accelerator built through algorithm-hardware co-design intended to close that disparity by designing the algorithm and the hardware together rather than in isolation. The specific co-design techniques Falcon introduces, its microarchitecture, the FHE scheme and operations it targets, and all quantitative results were not available for this write-up and are not asserted here; the account of the mechanism describes the general co-design approach and standard FHE-accelerator context, not the paper’s detailed contributions. Those should be read from the paper. This page is marked as a draft for that reason.

Background

Why the gap between algorithms and hardware keeps reopening

It helps to see Falcon within a recurring theme in computer systems: an algorithmic improvement and a hardware platform are often designed by different communities against different assumptions, and the improvement’s promised benefit only materializes when someone reconciles the two. Algorithm designers reason with clean abstract cost models — count the expensive operations, ignore where the data lives — because that abstraction is what makes analysis tractable and portable. Hardware, though, imposes stubborn physical realities, above all a memory hierarchy in which fast memory is small and moving data is expensive, so a computation’s real cost is often dominated by data movement the abstract model never saw. Whenever the working set is large relative to fast memory, this mismatch bites, and the fix is co-design: choosing the algorithm with the memory system in mind, and building the memory system with the algorithm in mind. Fully homomorphic encryption is an extreme case, because its ciphertexts and keys are so large that essentially every operation strains the memory hierarchy, so algorithmic cleverness that ignores memory is especially likely to disappoint on real hardware. The broader push to make privacy-preserving computation on encrypted data efficient enough to deploy is the same terrain the work on client-optimized algorithms and acceleration for encrypted compute offload covered elsewhere on this site occupies, driving encrypted computation toward practicality by matching algorithms to what the hardware can do. Falcon contributes the co-design stance for FHE accelerators, arguing that only by designing the cryptographic optimizations and the chip together can the field keep the algorithmic gains it works so hard to produce.

If you remember only three things

1. Fully homomorphic encryption (FHE) lets a server compute on encrypted data without ever seeing it, which is ideal for secure cloud computing, but it is orders of magnitude slower than plaintext computation, so dedicated hardware accelerators are built to make it practical. A recurring frustration is that cryptographic algorithm optimizations which reduce work in theory often fail to speed up the real accelerator, because hardware constraints — especially limited on-chip memory — leave a disparity between the optimization's theoretical advantage and its achievable hardware efficiency.
2. The root cause is that an algorithmic optimization is judged by an abstract cost metric that assumes its operands are on hand, but on an FHE accelerator the ciphertexts and keys are huge relative to on-chip memory, so much of the real cost is moving data. An optimization that shaves arithmetic while increasing data movement can be no faster, or slower, under the memory cap. Falcon's response is algorithm-hardware co-design: choosing the algorithmic organization and building the accelerator together, with limited on-chip memory as a first-class concern, so an optimization's theoretical reduction actually shows up as hardware efficiency rather than being erased by data movement.
3. The trade-offs and caveats: co-design matches the algorithm and hardware, which can make the accelerator less general; the benefit targets the memory-bound regime specifically; a custom FHE chip is a large commitment; and how fully a theoretical gain is recovered depends on the particular co-design. This explainer is a draft based on the abstract and standard FHE-accelerator background — Falcon's specific techniques, architecture, and quantitative results should be confirmed in the paper.

Check yourself

Check your understanding

1. Why does fully homomorphic encryption motivate dedicated hardware accelerators?
2. What causes the "disparity between theoretical algorithmic advantage and achievable hardware efficiency" that the paper targets?
3. What is Falcon's core approach to closing this gap?
4. Predict: a new FHE optimization halves the number of expensive operations but doubles the amount of ciphertext data that must be streamed through the accelerator. On a memory-bound FHE accelerator, what is likely, and why does co-design help?

Sources

The paper is “Falcon: Algorithm-Hardware Co-Design for Efficient Fully Homomorphic Encryption Accelerator” by Liang Kong, Xianglong Deng, Guang Fan, Shengyu Fan, Lei Chen, Yilan Zhu, Geng Yang, Yisong Chang, Shoumeng Yan, and Mingzhe Zhang, published at ASPLOS 2026, DOI 10.1145/3779212.3790160.

This explainer is written from the paper’s abstract and standard background on fully homomorphic encryption and FHE accelerators, because the full paper text was not accessible for this write-up (the ACM version was not retrievable and no author preprint or open copy was found). The problem, as the authors state it, is that fully homomorphic encryption enables computation on encrypted data without compromising privacy, positioning it as a promising solution for secure cloud computing, but its substantial computational overhead impedes practical deployment and prompts dedicated hardware accelerators; and when deploying cryptographic algorithm optimizations on FHE accelerators, hardware constraints (typically limited memory capacity) often lead to a disparity between the theoretical algorithmic advantage and the achievable hardware efficiency. The paper’s response, reflected in its title and abstract, is Falcon, an FHE accelerator built through algorithm-hardware co-design intended to close that disparity by designing the algorithm and hardware together. Falcon’s specific co-design techniques, its microarchitecture, the FHE scheme and operations it targets, and its quantitative results were not available for this write-up and are not asserted here; they should be confirmed in the paper. This page is marked draft because the full text was unavailable.