💻 computer science

Hardware-Friendly Randomization: Enabling Random-Access and Minimal Wiring in FHE Accelerators with Low Total Cost

This paper proposes a hardware-friendly randomization scheme for FHE accelerators that generates RLWE polynomials on-the-fly from small seeds, significantly reducing communication overhead and wiring complexity while enabling parallel access and substantial power savings without compromising client-side efficiency.

Original authors: Ilan Rosenfeld, Noam Kleinburd, Hillel Chapman, Dror Reuven

Published 2026-02-24

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Ilan Rosenfeld, Noam Kleinburd, Hillel Chapman, Dror Reuven

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Picture: The "Secret Recipe" Problem

Imagine you are a famous chef (the Client) who wants to send a secret, encrypted recipe to a massive, high-speed factory (the Server) to cook a meal. The factory has thousands of chefs working in parallel to cook this meal as fast as possible.

In the world of Fully Homomorphic Encryption (FHE), the "recipe" is a mathematical polynomial. To keep the food secure, part of this recipe is a giant list of random numbers (let's call it the "Random Spice Mix").

The Problem:

The Size: This "Random Spice Mix" is huge. Sending it over the internet takes forever and clogs up the pipes.
The Factory Floor: Inside the factory, there are thousands of cooking stations (processors). If the factory tries to generate this spice mix in one central kitchen and pipe it out to every single station, the pipes get clogged, the wiring gets messy, and the factory uses a massive amount of electricity just to move the spices around.
The Bottleneck: The current way of making these spices is like a single assembly line. You have to make spice #1, then #2, then #3, all in order. If the factory needs spice #500 right now, it has to wait for #1 through #499 to be made first, or it has to store all of them in a giant warehouse (memory) to grab the right one later. This slows everything down.

The Solution: "Distributed Spice Stations"

The authors propose a clever new way to handle this. Instead of one central kitchen, they suggest giving every single cooking station its own tiny, self-contained spice shaker.

Here is how their system works, broken down into simple concepts:

1. The "Seed" (The Master Key)

Instead of sending the giant list of random numbers, the client sends a tiny seed (a short password or code).

Analogy: Imagine sending a single key to a locked box instead of sending the whole box of gold. The factory uses this key to unlock the ability to generate the gold (random numbers) instantly.

2. Distributed Generation (Local Shakers)

In the old way, one big machine made all the numbers and sent them out. In this new way, every little processor in the factory has its own mini-generator.

Analogy: Instead of one water tower pumping water through miles of pipes to every house, every house has its own rain barrel.
The Benefit: This eliminates the need for massive, thick, expensive wires inside the chip. It saves a huge amount of electricity (power) and space.

3. Random Access (Jumping to the Page)

The old method was like reading a book from page 1 to page 1000 to get to page 500. The new method lets you jump straight to page 500.

Analogy: Imagine a library where you used to have to walk down every aisle to find a specific book. Now, every book has a GPS coordinate. If the factory needs the "Spice for Modulus #5," it just asks its local shaker to generate only that specific spice, ignoring the rest.
The Benefit: No waiting in line. No need to store thousands of unused numbers in memory. The factory can work on whatever task it wants, whenever it wants.

4. The "Rejection Sampling" Safety Net

Generating perfect random numbers from a seed is tricky. Sometimes the machine generates a number that is slightly "off" (too big or too small).

Analogy: Imagine a machine that tries to pour exactly 1 cup of flour. Sometimes it pours 1.1 cups. The system checks the cup; if it's too much, it dumps it and tries again.
The Innovation: The authors figured out how to set the rules so that the machine almost never has to dump the flour. They tweaked the math so the "waste" is less than 3%. This means the client (the chef) doesn't have to do much extra work, and the factory never gets stuck waiting for a "retry."

Why Does This Matter?

Saves Money and Energy: By getting rid of the massive wiring and central generators, the factory chips use significantly less power (potentially saving tens of watts per chip). In a data center with thousands of chips, that's a massive energy bill saved.
Faster Cooking: Because the factory doesn't have to wait for data to travel across the chip or wait for a serial line to finish, the encryption/decryption happens much faster.
Scalability: As we try to encrypt bigger and more complex data, the old wiring methods would break under the weight. This new "distributed" method scales up easily without breaking the bank or the power grid.

Summary in a Nutshell

The paper solves a traffic jam in the world of encrypted computing. Instead of forcing a massive amount of random data to travel through a crowded, expensive highway (wiring) from a central hub, they give every worker a local generator. This allows workers to grab exactly what they need, instantly, without waiting in line, saving massive amounts of energy and making the whole system much faster and cheaper to build.

1. Problem Statement

Fully Homomorphic Encryption (FHE) schemes, particularly those based on Ring-Learning With Errors (RLWE), rely heavily on uniformly random polynomials ( $\mathbf{a}$ ) within ciphertexts and Key-Switching Keys (KSK).

Communication Overhead: Transmitting these large polynomials (often reaching gigabytes for KSKs) from client to server creates a massive bandwidth bottleneck.
Hardware Implementation Challenges: While a known optimization involves transmitting only a seed and generating $\mathbf{a}$ $a$ on-the-fly using a Pseudo-Random Number Generator (PRNG) on the server, implementing this in high-throughput ASIC accelerators faces three critical engineering hurdles:
1. Wiring Density & Power: A centralized PRNG feeding thousands of parallel computation units requires long, high-bandwidth global wires. This consumes excessive power (tens of Watts) and requires thick metal layers, which are scarce in modern chip designs.
2. Serial Dependency: Standard hash-based PRNGs (XOFs like SHAKE128 or BLAKE2) are serial. To generate the $k$ -th output, all preceding $0$ to $k-1$ outputs must be computed. This prevents random access to specific parts of the polynomial (e.g., specific Residue Number System (RNS) limbs), forcing either strict scheduling or large memory buffers.
3. Non-Deterministic Latency: Rejection sampling (used to ensure uniform distribution) introduces probabilistic latency. If a sample is rejected, the process repeats. This complicates hardware scheduling, which prefers deterministic execution profiles.

2. Methodology

The authors propose a Distributed, Domain-Separated PRNG Architecture that shifts the complexity of randomness generation to the client side while optimizing the server-side hardware.

A. Distributed Generation Architecture

Instead of a single central PRNG, the design distributes PRNG engines across the accelerator chip.

Segmentation: A polynomial limb (of size $N$ ) is divided into $n_{seg}$ segments.
Local Engines: Each segment is generated by a local PRNG engine placed adjacent to a specific group of computation units (multipliers/adders).
Wiring Reduction: This eliminates long global wires. Data travels only short distances via local wiring, significantly reducing power consumption and metal layer usage.

B. Domain Separation for Random Access

To overcome the serial nature of hash functions and enable random access to specific RNS limbs:

Input Construction: The input to the hash function is constructed as: seed || q || idseg.
- seed: Common seed for the key.
- q: The specific modulus (RNS base) being targeted.
- idseg: The segment index.
Mechanism: By varying q and idseg, the system can generate any specific segment of any specific RNS limb independently. This allows the hardware to jump directly to the required data without generating intermediate values.

C. Deterministic Scheduling via Client-Side Validation

To eliminate non-deterministic latency caused by rejection sampling:

Client-Side Guarantee: The client generates the polynomial using the proposed algorithms (Algorithm 1 & 2). If the rejection sampling fails to produce enough valid samples within a fixed hash output, the client retries with a different seed.
Server-Side Certainty: The server accelerator receives a seed guaranteed to produce a successful generation. The hardware does not need to handle "failures" or back-pressure, ensuring a deterministic execution profile with no stalls.

D. Rejection Sampling Optimization

The paper utilizes a specific rejection sampling technique where $w$ -bit samples are accepted if they fall within a specific range $[0, \lfloor 2^w/q \rfloor \cdot q)$ .

Trade-off: The system limits the supported set of prime moduli ( $S(q)$ ) to those with low Hamming Weight in their Non-Adjacent Form (NAF). This allows for efficient modular reduction hardware while ensuring the rejection probability ( $p_r$ ) remains low enough to keep the client-side retry rate negligible (<3%).

3. Key Contributions

Hardware-Friendly Randomization Scheme: A concrete method to generate uniformly distributed polynomials that supports random access to RNS limbs, breaking the serial dependency of standard XOFs.
Distributed PRNG Topology: A shift from centralized to distributed PRNG generation, which drastically reduces wiring density, eliminates the need for thick metal layers for randomness distribution, and lowers power consumption.
Deterministic Execution: By offloading the probabilistic nature of rejection sampling to the client (via seed validation), the accelerator achieves a deterministic latency profile, simplifying hardware scheduling.
Client-Side Efficiency: The proposed scheme adds less than 3% overhead to the client-side key generation process, a negligible cost compared to the massive savings in server-side power and communication.

4. Results and Performance Analysis

The authors provide a case study based on a 15mm square ASIC with 16,384 parallel 32-bit multipliers running at 1GHz.

Power Savings:
- Centralized Approach: Requires transmitting data across an average Manhattan distance of 7.5mm. Estimated power consumption for wiring alone is ~19.7 Watts.
- Distributed Approach: Eliminates long-reach wiring. The power consumption associated with data travel is effectively eliminated, saving tens of Watts per chip in high-throughput configurations.
Throughput: The system supports a theoretical throughput of 65.5 Tbps for uniform polynomial generation.
Parameter Trade-offs:
- Using a 288-bit seed and SHAKE128/KangarooTwelve.
- By limiting the modulus set to primes with specific characteristics (HWNAF $\le$ 5), the system maintains a rejection probability bound where the client-side failure rate is $\le$ 3%.
- This allows for a wide variety of NTT-friendly primes to be supported without compromising the deterministic nature of the server.

5. Significance

This work addresses the transition of FHE from a theoretical concept to a practical engineering reality.

Scalability: As FHE accelerators scale to higher parallelism, wiring and power become the primary bottlenecks. This scheme removes the "wiring wall" that limits the scaling of centralized PRNG architectures.
Ecosystem Impact: By enabling random access and deterministic scheduling, this scheme allows FHE compilers and libraries to optimize program execution more effectively, reducing memory footprints and latency.
Energy Efficiency: The reduction of tens of Watts per chip is critical for data center deployment, making large-scale encrypted computation more energy-efficient and economically viable.

In summary, the paper proposes a holistic architectural change that moves the burden of randomness generation complexity to the client to unlock massive efficiency gains in server-side hardware, specifically targeting wiring density, power consumption, and scheduling flexibility.