Skip to content

The Power of Low Rank: Fast CKKS Functional Bootstrapping for High-Precision Lookup Tables

Year: 2026

type: technique collection: schemes status: auto

Links: ePrint 2026/1264

Summary

Auto-extracted summary (unreviewed)

Proposes LRMT-FBT, a CKKS functional bootstrapping method for high-precision lookup tables that exploits the low exact or numerical rank of LUT matrices: a spectral framework classifies functions by singular-value decay, and the LUT is evaluated through a rank-r truncated SVD instead of a dense matrix product, cutting homomorphic multiplications from O(P) to O(r sqrt(P)). Implemented in OpenFHE with lazy conjugation, lazy relinearization and rescale optimizations, at P = 2^20 it accelerates the LUT-evaluation step by 196.9x (Step) and 99.6x (ReLU) over Dumezy et al., for overall functional-bootstrapping speedups of 5.3x and 5.1x.

Abstract

The CKKS fully homomorphic encryption scheme has traditionally been viewed as suitable only for approximate arithmetic. However, recent work (Alexandru et al., Crypto 2025) has introduced functional bootstrapping techniques that enable accurate lookup tables (LUTs) evaluation in CKKS. Nevertheless, to deal with the high precision problem, the state-of-the-art scheme (Dumezy et al., TCHES 2026) requires reshaping the LUTs into a matrix, which incurs O(P) multiplications for a size-P table and dominates runtime. We first observe that LUT matrices for many practical functions are often highly structured, with exact or numerical rank much smaller than matrix dimension. We then develop a spectral framework for the LUT evaluation problem, which characterizes the relationship between function classes and the singular value decomposition. This framework yields exact rank bounds for structured function classes such as separable functions, and establishes exponential decay of singular values (implying low numerical rank) for smooth analytic functions. Building on this framework, we propose Low Rank Multiplexer Tree Functional Bootstrapping (LRMT-FBT), which evaluates the LUT via the singular values and singular vectors instead of direct matrix multiplication. This reduces the homomorphic multiplication cost from O(P) to O(r √ P), where r denotes the rank of matrix, while also supporting extensions to multi-value and multi-input settings. We implement LRMT-FBT in OpenFHE and evaluate it across different spectral classes. We also introduce implementation optimizations to improve the bootstrapping efficiency. At high precision, LRMT-FBT provides substantial performance improvements for common low rank functions compared with Dumezy et al. Typically, for P = 220, our method accelerates the LUT evaluation step by 196.9× for Step (r = 1) and 99.6× for ReLU (r = 3), yielding functional bootstrapping speedups of 5.3× and 5.1×, respectively.
Source: pdf

Extracted details

Field Value Source Confidence
contribution Spectral framework relating function classes to the SVD of LUT matrices, with exact rank bounds for separable functions and exponential singular-value decay for smooth analytic functions llm 0.85
contribution Low Rank Multiplexer Tree Functional Bootstrapping (LRMT-FBT) algorithm with noise analysis and correctness proof llm 0.85
contribution Extensions to multi-value and multi-input LUT settings llm 0.85
contribution OpenFHE implementation with lazy conjugation, lazy relinearization and rescale optimizations llm 0.85
contribution Evaluation across spectral classes at precisions up to 2^20, including multi-threaded and memory results llm 0.85
schemes CKKS llm 0.85
libraries OpenFHE llm 0.85
libraries lattice-estimator llm 0.85
tasks high-precision lookup table evaluation llm 0.85
tasks functional bootstrapping llm 0.85
tasks non-linear function evaluation (Step, ReLU) llm 0.85
security level 128-bit llm 0.85
interaction non-interactive FHE llm 0.85
code url https://github.com/malb/lattice-estimator (URL found in the full text) regex 0.50
limitations Class C functions admit no low-rank compression and gain nothing from the method llm 0.85
limitations Reported ReLU rank/speed-up figures differ slightly between abstract (r = 3, 99.6x, 5.1x) and conclusion (rank 2, 196.9x, 5.3x) llm 0.85
llm relevance low llm 0.85
key result LUT evaluation speed-up: 196.9x (Step function (rank 1), P = 2^20, vs Dumezy et al. (CMT-FBT)) llm 0.85
key result LUT evaluation speed-up: 99.6x (ReLU (rank 3), P = 2^20, vs Dumezy et al.) llm 0.85
key result functional bootstrapping speed-up: 5.3x (Step, P = 2^20) llm 0.85
key result functional bootstrapping speed-up: 5.1x (ReLU, P = 2^20) llm 0.85
key result multiplication cost: O(P) reduced to O(r sqrt(P)) (size-P LUT with rank r) llm 0.85

Keyword mentions

Counts of vocabulary terms in the full text (first page of occurrence in brackets).

  • scheme: CKKS 49 [p.1], TFHE 6 [p.2], FHEW 5 [p.2], BFV 4 [p.5], BGV 4 [p.5]
  • library: OpenFHE 4 [p.1], Zama 1 [p.28]
  • hardware: AMD EPYC 1 [p.22]
  • technique: Lookup table 140 [p.1], Bootstrapping 67 [p.1], Rescaling 17 [p.4], Functional bootstrapping 15 [p.1], ReLU 12 [p.1], Relinearization 8 [p.4], Paterson-Stockmeyer 7 [p.29], GELU 7 [p.3], Sigmoid 5 [p.3], SIMD packing 5 [p.2], Chebyshev 4 [p.8], RNS 4 [p.6], Polynomial approximation 2 [p.2], Rotations 2 [p.5], Quantization 2 [p.3]
  • assumption: RLWE 17 [p.6], Lattice-based 3 [p.22], 128-bit security 3 [p.22]
  • task: Language modeling / generation 2 [p.6]
  • topic: Homomorphic encryption 14 [p.1], Open source 2 [p.22]

Files

Path (under papers/) Collection Pages Size SHA-256 Note
references/schemes/s13-3_eprint-2026-1264.pdf schemes 35 919.0 KB 14307fe6b08d

Database key: the-power-of-low-rank-fast-ckks-functional-bootstrapping-for-high · created 2026-11-05 · updated 2026-11-05 · edit with python3 tools/paperdb.py set the-power-of-low-rank-fast-ckks-functional-bootstrapping-for-high COLUMN VALUE