Bootstrapping-Free Encrypted Long-Context Inference with Additive Fast Weights

When a server runs a language model on a user's encrypted text, the encryption is usually homomorphic: the server adds and multiplies ciphertexts without ever seeing the plaintext. Each multiplication adds noise to the ciphertext, and once the noise budget runs out the server must "bootstrap," meaning it refreshes the ciphertext by homomorphically decrypting it with an encryption of the secret key. Encrypting a key under itself is exactly the situation studied in key-dependent message (KDM) security, also called circular security. Standard security proofs do not cover it, and for lattice-based schemes it is adopted as an extra assumption. Bootstrapping is therefore expensive in two ways. It costs latency, and it moves the scheme's security from a standard assumption onto a circular one. This proposal asks which sequence architectures can process arbitrarily long encrypted inputs without ever bootstrapping. The answer, we argue, depends on the form of the attention recurrence.

The observation is simple. In linear attention, a variant of attention whose cost grows linearly with sequence length, the memory state is a sum $S_N=\sum_{i\le N}\phi(k_i)v_i^T$ of per-token outer products. Additions do not consume multiplicative depth, so the depth of the whole forward pass is fixed by the number of layers and the degree of the per-token polynomials. It does not grow with the context length $N$. The recurrences that the linear-attention literature adopted to fix its memory-capacity problem break this property. The delta rule multiplies the state by a data-dependent matrix at every step, so depth grows linearly in $N$. Top-$k$ routing and sliding-window softmax are not polynomials at all. We propose to build, and measure the recall limits of, linear-attention layers that are polynomial and have multiplicative depth independent of $N$. Such models can be evaluated under leveled homomorphic encryption with no circular-security assumption. The main new ingredient is a low-degree polynomial replacement for sparse state expansion that restores associative recall within this constraint.

Core Claim

A recurrence of the form

$$S^{(m)}_N=\sum_{i\le N}\gamma_m^{\,N-i}\,w_m(k_i)\,\phi(k_i)\,v_i^T,\qquad y_t=\sum_{m=1}^{M} w_m(q_t)\,\phi(q_t)\,S^{(m)}_t$$

is the target design. Here $\phi$ is a degree-2 feature map, $w_m$ is a degree-2 "routing weight" that softly assigns each token to one of $M$ memory slots, and $\gamma_m$ is a fixed plaintext decay constant per slot. Its multiplicative depth per layer is a small constant (about four) for every $N$. We claim it can recover most of the associative-recall gap that separates plain linear attention from the delta rule and from top-$k$ sparse state expansion. The prediction is falsifiable. Depth should be flat in $N$ by construction. Recall on synthetic key-value retrieval should rise with $M$ at fixed total state size, which unrouted polynomial attention cannot do. The circular-security payoff follows directly: the model runs to completion under a leveled scheme whose parameters are set once from the layer count and never refreshed with an encrypted secret key.

Where This Sits

The homomorphic side comes from ULD-Net, which trains fully polynomial networks of multiplicative depth at most 3. It replaces softmax in Vision Transformers with linear attention plus rotary embeddings and stabilizes training with a quadratic normalization (PolyNorm) and variance penalties. It reports 76.70% ImageNet top-1 for ViT-Small and a 2.76× homomorphic latency speedup on ResNet-18. We reuse its training recipe. ULD-Net does not address two things we do. It applies attention to fixed-length images, not long causal sequences. It also never asks how depth scales with context length or what security assumption long inputs force.

On the capacity side, three papers fix the memory interference of additive linear attention in ways this constraint rules out, and they serve as our upper bounds. DeltaNet parallelizes the error-correcting delta rule and reports near-perfect multi-query associative recall where Mamba fails, but its multiplicative state update makes depth grow with $N$. Sparse state expansion partitions the state and writes to it through top-$k$ selection, reaching nearly 100% on 32k-context RULER tasks. Top-$k$ is a comparison circuit, not a low-degree polynomial. BASED uses a second-order Taylor feature map, which is polynomial and which we adopt as $\phi$. BASED pairs it with a 64–128 token sliding softmax window that is not polynomial, and it attributes much of its recall to that window. Irie et al. constrain what we can hope for. Plain linear Transformers score near 0% on length generalization for parity and similar regular languages, and only recurrent delta or self-referential variants reach 100%. Our architecture belongs to the weaker class, and we expect it to fail those tasks. We report that failure rather than hide it.

The KDM literature frames what the design avoids. It does not supply a technique. Bounded KDM security, circular security beyond affine functions, subgroup-indistinguishability constructions and the generic homomorphism-plus-reproducibility construction show that circular security can be proven, but only through special structure, specific assumptions, or restricted function classes. For example, the generic construction covers only projection functions. None of these results covers the circular encryption of a lattice secret key that bootstrapping needs. Designing the computation so that no key cycle is ever created is therefore a meaningful goal. We do not build a new KDM-secure scheme. We remove the need for one in a concrete machine-learning workload.

Research Program

The first piece is an exact depth accounting for candidate attention layers under a CKKS-style leveled scheme. CKKS is an approximate-arithmetic homomorphic scheme. In it, a ciphertext-ciphertext product costs a level, and so does a plaintext rescale. The accounting covers softmax, plain linear attention, BASED's Taylor map with and without its window, retention-style fixed decay, the delta rule, and our routed variant. It records depth as a function of $N$ and layers. It also records how the magnitude of accumulated values grows, because additive sums of $N$ terms do not consume levels but do grow in scale, and the fixed-point precision must absorb that growth.

The second piece is the routed layer itself. We will train it in plaintext while simulating its polynomial-only operations. The routing weights $w_m(x)=(a_m^Tx)^2$ are left unnormalized, since division is unavailable, and are regularized with ULD-Net-style variance penalties. The decay constants $\gamma_m$ are applied per position as plaintext scalars, so they cost one level in total, not one per step. Total state size is held fixed while $M$ varies, so that routing is not credited with gains that come from a bigger memory.

The third piece is homomorphic execution of small trained models, around 10M–50M parameters, on encrypted prompts. The workload is prefill plus scoring: classification or next-token ranking over an encrypted context. Autoregressive generation feeds outputs back as inputs, so depth there does grow with generated tokens. For that case we treat per-token client re-encryption as the honest comparison and leave server-side generation out of the claim.

Baselines

The naive reference is unrouted polynomial linear attention of the ULD-Net type (ULD-Net), given the same parameter count, state size, data and tuning budget. It shares our depth property. Beating it means clearly higher recall on multi-query associative recall at matched state size, with no added dependence of depth on $N$.

The second baseline is BASED's degree-2 Taylor feature map without its sliding window, which is the strongest existing layer that is already fully polynomial (BASED). It is the most dangerous competitor, because it may already capture most of the achievable recall. We run it with identical training and hyperparameter sweeps, and we also report BASED with its window as a plaintext-only reference. The file gives no reported number for the windowless variant. It gives only the +10.36-point recall advantage of full BASED over Mamba at 1.3B scale.

The capacity upper bounds are DeltaNet (DeltaNet) and top-$k$ sparse state expansion (SSE). Both are trained in plaintext at matched size, and both break the constraint, one on depth and one on polynomiality. For SSE-H the reported figure is nearly 100% accuracy on 32k-context RULER tasks. For DeltaNet the file reports only "near-perfect" MQAR accuracy with no exact figure, and we will measure our own.

Two ablations isolate the key ingredient, polynomial routing. The first uses fixed random hash routing, which gives slot structure without learned assignment. The second uses our routed layer with the top-$k$ operation restored, in plaintext only. Together they separate how much of any gain comes from partitioning the state and how much the polynomial relaxation gives up relative to hard selection.

Why not just…?

Why not just bootstrap DeltaNet or a softmax model? This works in the sense that it computes the right answer. It costs latency proportional to how often the state must be refreshed, and its security rests on the circular-security assumption for encrypted evaluation keys, which the KDM literature cited above does not establish for lattice schemes. We will measure the latency gap directly. The difference in assumptions is categorical, so no experiment can close it. The real question is how much recall the bootstrapping-free design gives up, and the capacity baselines measure exactly that.

Why not just use BASED's Taylor attention without the window? This is the real threat. If windowless BASED matches the routed layer at equal state size, the routing contribution is void. The result would then shrink to the depth accounting plus the finding that polynomial Taylor attention is the right encrypted long-context layer. That is still worth reporting, but it is a smaller result. The matched-state MQAR sweep over $M$ is designed to settle this.

Why not just have the client refresh ciphertexts by decrypting and re-encrypting? Client refresh also avoids circular security, and it is the right answer for autoregressive generation. For long prefill, however, it needs a round trip every time the noise budget runs out. Our design needs zero round trips during prefill regardless of $N$. We will count communication rounds and bytes for both methods at matched depth budgets.

Why not just use ULD-Net as it stands? It is our naive baseline. Its attention was never tested on causal long-context recall, and it inherits the known interference problem of additive state. The first experiment tests whether that problem appears at the context lengths we care about.

Proposed Experiments

The decisive plaintext experiment is MQAR with the number of stored pairs swept past the state dimension. It compares the routed layer to the unrouted, windowless-BASED, hash-routed, top-$k$ and DeltaNet variants at matched total state. The routed layer should hold accuracy flat as $M$ grows where the unrouted polynomial layer degrades. Next come needle-retrieval tasks in the style of RULER, at lengths from 1k to 32k, and the SWDE and FDA extraction tasks used by BASED and DeltaNet. We also run small models on SlimPajama to check that perplexity does not collapse under polynomial-only training. Parity and Reset Dyck-1 from Irie et al. serve as a negative control. We expect failure there, and success would signal a bug in the depth accounting.

The decisive homomorphic experiment encrypts prompts of increasing length for a trained small model under a fixed leveled parameter set. It checks two things. First, the level consumption measured on real ciphertexts should be identical across lengths. Second, the decrypted outputs should match plaintext outputs within CKKS precision up to the largest $N$ the value-growth analysis allows. We report wall-clock time per token against a bootstrapped DeltaNet of equal size. No homomorphic latency for sequence models is reported on Lacuna; the only reported homomorphic numbers are ULD-Net's image results. The work fails if routing gives no recall over windowless Taylor attention, or if accumulated-value growth breaks CKKS precision at lengths far below those where recall matters.