Pixel Lookup Tables as Bootstrapping Programs for Encrypted Super-Resolution

Image super-resolution with lookup tables replaces a neural network with a few small precomputed tables. The client reads a handful of neighboring pixel values, uses them as an index, and fetches the predicted high-resolution pixels. The catch is exponential memory. A table indexed by $k$ pixels at $q$ bits each has $2^{kq}$ entries, so this line of work has spent years finding ways to keep each table's index short.

A separate line of work runs neural networks on encrypted data. One encryption scheme there, TFHE (Torus Fully Homomorphic Encryption), has a basic operation called programmable bootstrapping. It applies any one-input function, written as a table, to an encrypted value and cleans away accumulated cryptographic noise at the same time. Its cost rises steeply with the bit-width of that encrypted value. This proposal starts from one observation: these are the same constraint. A lookup-table super-resolution network is already close to a TFHE program. Each table becomes one bootstrapping. Its index is a cheap encrypted weighted sum of a few pixels. The quantity plaintext methods minimize, index bits per table, is exactly what drives encrypted cost.

Core Claim

We claim that a lookup-table super-resolution network can be trained under an explicit encrypted-cost budget and then run end to end under TFHE without polynomial activation approximations. The server holds its tables in plaintext as private bootstrapping functions and never sees the image. We further claim that the right designs differ from the plaintext optimum, and the differences are concrete.

Memory, which the plaintext literature fights hardest, becomes almost free on a server. Two other costs replace it: the number of bootstraps and the bit-width each one handles.

Cascade depth also stops being dangerous. In noise-accumulating encryption schemes such as CKKS, extra depth requires larger parameters, which is the "depth trap" documented by HEMET. In our setting every table lookup refreshes the noise, so depth adds cost only linearly.

Interpolation between table vertices, which plaintext methods rely on, has to go. The tetrahedral interpolation of SR-LUT multiplies encrypted weights by encrypted vertex values and branches on sorted coordinates. Both are expensive under encryption.

The new element is the cost-aware search over table shapes and bit allocations, together with a working encrypted pipeline that agrees bit-for-bit with its quantized plaintext twin.

Concretely, for table $i$ with $k_i$ input pixels each quantized to $q_i$ bits, the encrypted index is $w_i = \sum_{j} 2^{q_i j} x_j$. This is a weighted sum of encrypted pixels, which TFHE computes cheaply. Its width is $B_i = k_i q_i$ bits. We train with

$$\min_\theta \; \mathcal{L}_{\text{rec}}(\theta) + \lambda \sum_i c(B_i), \qquad B_i \le B_{\max},$$

Here $\theta$ are the table entries and quantizer parameters, $\mathcal{L}_{\text{rec}}$ is the reconstruction loss, and $c(B)$ is the measured latency of one bootstrapping at $B$ bits. $B_{\max}$ is the largest width the chosen TFHE parameters support, and $\lambda$ trades fidelity against encrypted time. The form $kq \le B_{\max}$ is the plaintext $2^{kq}$ memory curse restated as an encrypted precision limit. It forces a choice among tables that see four pixels at two bits, two pixels at four bits, or one pixel at eight bits.

Relation to Prior Work

The plaintext lookup-table literature supplies the building blocks.

  • Decoupled single-pixel tables. RCLUT approximates an $n\times n$ convolution with $n^2$ one-dimensional tables combined by averaging. This is the $k=1$ end of our trade-off.
  • Splitting pixel bits. SPLUT splits each pixel into high-order and low-order bit branches and avoids interpolation. This shows interpolation-free tables can work, and gives a way to spend bits unevenly.
  • Cooperating small tables. MuLUT combines small tables in width and cascades them in depth to widen the view. It also provides the training trick we reuse: a straight-through quantizer that rounds in the forward pass and passes full-precision gradients backward.
  • Bounded residuals. AutoLUT replaces additive residuals with convex combinations so intermediate values stay in $[0,255]$. In plaintext this keeps tables small. Under TFHE it matters more: an out-of-range value wraps around the plaintext modulus and decodes to garbage, so a guaranteed range is a correctness requirement.

None of these papers models encrypted cost, and all of them use memory as their budget. We change the budget and retrain.

On the encryption side, three papers touch lookup tables but none covers dense spatial image grids.

  • CodedHELUT evaluates one-dimensional embedding lookups under CKKS. It uses polynomial indicator functions and base-$p$ index codes, reaching 79.56% IMDB accuracy against 79.64% unencrypted. It handles isolated tokens rather than overlapping pixel neighborhoods, and it does not interpolate.
  • Narisada et al. trade memory for bootstrap count when evaluating arbitrary Boolean tables in TFHE. They report a 17.9x speedup on 8-bit functions, but their tables are random logic, not trained on any task loss. Their decompositions are a candidate tool when $B_i$ exceeds $B_{\max}$.
  • Glyph uses TFHE bootstrapping only for scalar activations, at 0.1 s per ReLU versus 307.9 s for a BGV table. Convolutions stay in BGV.

Our proposal moves the convolutions themselves into tables. These papers motivate the design and supply primitives. The documented cost of deep encrypted networks constrains it, including 56 GB of traffic and 549 s for one HE-Transformer prediction in the systematic comparison.

Research Program

Step 1: measure the cost curve. We first measure $c(B)$ for TFHE bootstrapping at widths from 2 to the largest practical width, on a fixed CPU. We also measure the cost of the weighted-sum index computation and of summing table outputs. Every later comparison rests on this measured curve, not on an assumed one.

Step 2: define the search space. The design space combines three ingredients. The first is table shapes with $k \in \{1,2,4\}$ pixels drawn from standard, dilated and offset patterns, following MuLUT's complementary indexing. The second is per-table bit allocations $q_i$, including uneven splits into high-order and low-order bits as in SPLUT. The third is cascades of two to four stages, whose outputs pass through a learned quantizer and an AutoLUT-style convex residual.

Step 3: train under the cost budget. We train on DIV2K with the cost-penalized objective. Discrete shape and bit choices are relaxed with a softmax during search and fixed afterwards, in the spirit of AutoLUT's learned sampling.

Step 4: compile and verify. Each trained network is compiled into a TFHE program. The client encrypts low-resolution pixels at their quantized width. The server forms indices, bootstraps through its private tables, and sums the outputs with plaintext weights. Each stage boundary re-quantizes through one more bootstrap. We verify that decrypted outputs match the quantized plaintext model and report any mismatch rate. A nonzero rate would point to range violations or decryption failures.

Baselines

Naive reference points. The do-nothing reference is bicubic upsampling evaluated under encryption. It is linear, so it needs no bootstrapping and is nearly free in either scheme. SR-LUT reports 28.42 dB Set5 PSNR at ×4 for bicubic, which is the fidelity floor any encrypted method must clear to justify its cost. A second naive point is the plaintext Set5 numbers of the original table models: SR-LUT-S at 29.82 dB, MuLUT at 30.60 dB and RCLUT at 30.72 dB, the latter two as reported in the RCLUT paper. These are ceilings showing what quantization to encryptable widths costs.

Direct port. We take RCLUT and an interpolation-free MuLUT variant as published and compile them to TFHE with 8-bit indices, rounding any table with more bits down to the budget, with no cost-aware retraining. This isolates whether the cost-aware design matters or whether simply porting existing tables suffices. Beating it means a better point on the PSNR-versus-encrypted-latency curve, which we call the Pareto front.

Strongest competitor: packed CKKS CNN. This is a small super-resolution CNN with low-degree polynomial activations, in the spirit of polynomial backbones like PolyNeXt. It is evaluated in CKKS with SIMD slot packing, which processes many pixels per operation. Super-resolution is mostly local and nearly linear, so packing may give it much better amortized cost than per-pixel bootstraps. No reported result was found on Lacuna for encrypted super-resolution with such a model, so we will train and run it ourselves. It gets the same DIV2K data, the same hyperparameter-search budget in GPU hours and the same server CPU, with CKKS parameters tuned to its depth. Beating it means either higher PSNR at equal per-image latency or equal PSNR at lower single-image latency, with amortized throughput reported separately so neither regime is hidden.

CKKS lookups. We evaluate our trained tables through CodedHELUT-style indicator polynomials in CKKS rather than TFHE bootstraps. This separates the value of the table architecture from the value of the TFHE primitive.

Ablations. Three ablations remove one ingredient each. The first fixes uniform bit allocation instead of learning it. The second uses plain additive residuals instead of convex ones, and we measure the resulting wraparound errors. The third collapses everything to $k=1$ (pure RCLUT shapes) to test whether multi-pixel tables earn their bits.

Why not just…?

Why not just run a small polynomial CNN in CKKS? This is the real threat. SIMD packing amortizes cost across thousands of pixels, and HEMET shows careful merging of coefficients can cut CKKS latency substantially. Our counter-argument has three parts. Shallow polynomial networks are known to lag on sharp textures. Depth in CKKS consumes noise budget. Each of our table lookups refreshes noise, so a cascade costs only linearly in its length. Whether these advantages outweigh packing is exactly what the Pareto comparison settles. If the CKKS network dominates at every budget, we will report that lookup tables are the wrong primitive for encrypted restoration and retain only the cost-measurement study.

Why not just upsample bicubically under encryption, or let the client run the table model locally? Bicubic is nearly free, so the table network must gain clearly over 28.42 dB on Set5 to be worth hundreds of bootstraps. SR-LUT's plaintext gap of about 1.4 dB is the maximum the cheapest model can hope for. Local execution is cheap too: SR-LUT reports 15 ms on a phone for its smallest variant. The encrypted setting matters only when the provider will not ship its learned tables, or when restoration feeds a further encrypted pipeline such as clinical classification. We state this scope plainly. Here the server's tables never leave the server, which a local deployment cannot offer.

Why not just use a hardware enclave or interactive multi-party computation? The systematic comparison reports 0.14 s with an Intel SGX enclave and 0.25 s with CrypTen. Neither of our methods will approach these numbers. Enclaves rest on trust in the hardware vendor, and multi-party computation needs the client online across many rounds. We target the non-interactive, hardware-agnostic setting and do not claim to compete on speed with those threat models.

Proposed Experiments

Training and test data. All models train on DIV2K at ×4. We evaluate PSNR on Set5 and Manga109 and test demosaicing transfer on Kodak, where MuLUT reports a 6.0 dB gain over SR-LUT in plaintext.

Encrypted metrics. Encrypted runs report three quantities. The first is single-image latency on fixed-size low-resolution crops. The second is client upload size, which matters because TFHE encrypts each pixel separately at its quantized width. The third is server evaluation-key size.

Decisive check one: does the cost model hold? Measured end-to-end latency should be predicted, within a small error, by the sum of $c(B_i)$ plus linear overhead. If not, the training objective is aimed at the wrong target.

Decisive check two: does cost-aware design matter? The cost-aware networks must strictly dominate the direct port of RCLUT and MuLUT on the Pareto front. If they do not, existing plaintext designs already suffice.

Decisive check three: does the approach beat its two closest rivals? At least one operating point must exceed encrypted bicubic by a clear margin, and match or beat the packed CKKS CNN in single-image latency at equal PSNR. Passing the first two checks but failing the third would show that lookup tables transfer correctly to encryption but are not competitive, and we would report it that way.

Correctness. Bit-exact agreement between encrypted and quantized plaintext outputs is required for any result to count.