Abstract
Fully Homomorphic Encryption (FHE) traditionally treats Look-Up-Tables (LUTs) as static tools for function evaluation during bootstrapping. RevoLUT introduces a paradigm shift by treating LUTs as dynamic, "first-class" data structures. By implementing a suite of blind primitives for reading, writing, and sorting, RevoLUT enables efficient oblivious algorithms. Benchmarks show that RevoLUT’s Blind Radix Sort outperforms traditional bitonic sorting by nearly 5x, while maintaining low latency for multi-dimensional tensor access.
Introduction
In the world of Fully Homomorphic Encryption (FHE), performing even simple operations like sorting an array or looking up a value in a table can be agonizingly slow. Traditionally, researchers have treated Look-Up-Tables (LUTs) as static tools used during "bootstrapping" to evaluate non-linear functions. RevoLUT reimagines LUTs as dynamic, "first-class" data structures that can be manipulated obliviously.
Fully Homomorphic Encryption allows a server to compute on data without ever seeing it. However, FHE is computationally expensive. For years, it was mostly limited to "vanilla" arithmetic (addition and multiplication). Complex operations like sorting or accessing an array at an encrypted index required building massive, inefficient circuits of "comparators."
A breakthrough called Programmable Bootstrapping (PBS) allowed any function to be evaluated "for free" during the noise-clearing process by using a Look-Up-Table. But in standard TFHE, these LUTs are ephemeral; they are used to compute a result and then discarded. RevoLUT identifies a gap: if we treat the LUT itself as the encrypted data (an array or matrix), we can perform complex data manipulations much more efficiently than by using standard logic gates.
Methods
RevoLUT leverages the mathematical structure of TFHE to implement several "blind" operations—meaning the server performs the operation without knowing the indices or the values involved.
First-Class LUTs and Blind Access
Instead of using a LUT to calculate $f(x)$, RevoLUT stores actual data (like an array of records) inside the LUT. The library implements Blind Array Access (BAA), Blind Matrix Access (BMA), and Blind Tensor Access (BTA). These allow a user to fetch an element from an encrypted multi-dimensional structure using an encrypted index.
Blind Writing and Sorting
The library introduces Blind Array Add (BAAdd), which allows adding a value to a specific, encrypted position in an array without revealing which position was modified. This is achieved by adding a shifted unit vector to the target LUT.
Perhaps the most novel contribution is the Blind Counting Sort (BCS). Unlike traditional sorting (like Bitonic Sort) which relies on $O(n \log n)$ expensive comparisons, BCS leverages the "indexing" nature of LUTs to sort data in linear time relative to the array size.
Noise Management
Because repeated operations in FHE introduce noise that can misalign the "boxes" of data in a LUT, the authors implement a "repacking" mechanism (using Sample Extraction and Public Functional Key Switching) to refresh the LUT and prevent errors.
Key Results
The performance gains are substantial when compared to traditional FHE sorting methods:
- Sorting Speedup: Sorting 256 values using RevoLUT’s Blind Radix Sort takes approximately 209 seconds. In contrast, a state-of-the-art bitonic sort using standard TFHE comparators takes roughly 1000 seconds on the same hardware—a nearly 5x improvement.
- Microbenchmarks: For a LUT with 64 elements ($p=64$), a Blind Array Access (reading) takes only 128ms, while a Blind Array Add (writing) takes 162ms.
- Scalability: The library handles multi-dimensional tensors (up to $M=4$) with reasonable execution times (e.g., 4D tensor access in ~16s for $p=8$), making it viable for complex database-like queries on encrypted data.
Discussion and Future Work
RevoLUT demonstrates that indexing is often more efficient than comparison in the TFHE paradigm. By building a sorting algorithm around indexing, they bypass the most expensive part of FHE computation.
However, limitations remain. The "repacking" process required to fix noise-induced misalignment is expensive, utilizing Public Functional Key Switching (PFKS). Additionally, current implementation is bound by the parameter $p$ (the number of elements in a LUT), typically limited to 256. Future work will focus on "chaining" LUTs for larger datasets and leveraging parallelization on multi-core systems or GPUs to further reduce execution times.
Summary updated