Hiding Which Pages You Read: Steganographic Access Patterns for Offloaded Encrypted LLM Inference

Encrypted language-model inference has become fast enough to measure in seconds. The best system in the file is Sylph. It runs Llama-3-8B under CKKS, a homomorphic encryption scheme that lets a server compute on encrypted numbers without decrypting them. Sylph gains speed by splitting the context into a public part, such as a shared document, and a short private part, such as the user's question, which stays encrypted. Even so, cost grows with the public context: summarization takes 20 s with 128 encrypted tokens and 64 s with 4096 total tokens. Encryption also inflates weight memory about fourfold, so a long public context cannot all sit in GPU memory. In plaintext serving, the standard fix is to keep the context's attention cache in host RAM. The attention cache, or KV cache, holds the stored keys and values of past tokens. The system then fetches across the PCIe bus only the blocks the current query will attend to, as SpeCache does. In private inference, that fix creates a leak. Which public blocks get fetched depends on the private question, so the server learns something about the question just by watching what is read from memory.

This proposal treats that leak as a steganography problem, meaning a problem of hiding a signal inside innocent-looking traffic. The set of blocks a request fetches should look, to the server, like a draw from a fixed distribution that does not depend on the question. The genuinely needed blocks hide among decoys. This brings in the steganographic trilemma: one cannot have high capacity, high fidelity and strong undetectability all at once. Here capacity is how many of a fixed fetch budget's slots carry useful blocks. Fidelity is task accuracy relative to full attention. Undetectability is how poorly an adversary can infer the question from the fetch pattern. The aim is to measure this trade-off curve honestly and to find a design that sits well on it. The design must beat both "fetch everything", which is private but slow, and "fetch a query-independent subset", which is private but may lose accuracy.

Core Claim

The claim is that, in public/private encrypted inference, a client-chosen block-fetch set with randomized decoys gives a strictly better latency-accuracy frontier than query-independent static selection, at a quantified and small access-pattern leakage. Selection happens once per request, so leakage does not accumulate over generated tokens.

The client already holds the private question in the clear. It can run a cheap scorer locally: a 1–2 bit "scout" copy of the public keys in the style of SpeCache, or a small draft model in the spirit of the asymmetric large/small split of Think Big, Generate Quick. The scorer ranks public blocks for relevance. The client then sends a fetch set of fixed size $B$. Each block $j$ enters the set with probability $p_{hi}$ if the scorer marks it relevant and $p_{lo}$ otherwise, with the remaining slots filled from a query-independent prior. The server streams those blocks from host RAM and encodes them as plaintext operands for Sylph-style plaintext-ciphertext attention. It computes encrypted attention only over them.

The randomized inclusion gives a concrete guarantee. For any two questions $q, q'$ and any fetch set $S$:

$$\frac{\Pr[S \mid q]}{\Pr[S \mid q']} \le \left(\frac{p_{hi}(1-p_{lo})}{p_{lo}(1-p_{hi})}\right)^{k},$$

Here $k$ is the maximum number of blocks whose relevance label can differ between the two questions, which is the same as the number of relevant blocks per request. This bounds how much better than chance any server-side detector can do. The ratio $p_{hi}/p_{lo}$ is the single knob that trades fidelity and capacity against undetectability. Setting $p_{hi} = p_{lo}$ recovers static selection. Setting $p_{lo} = 0$ recovers leaky plaintext-style sparsification.

What is new is not sparse attention or decoy traffic in isolation. It is the joint treatment of three things in the FHE public/private regime. The first is the PCIe offloading that encryption's memory blow-up forces. The second is the compression needed to make a client-side scout small enough to ship. The third is a steganographic security measure, built from both a likelihood-ratio bound and learned detectors, for the access pattern itself.

Research Program

The work has three parts.

Leakage measurement. The first part establishes that the leak is real and large. A server-side "access-pattern steganalyzer" is trained to predict properties of the private question from fetch sets alone, using the plaintext-oracle selection SpeCache-style top-$k$ would make. The steganalyzer predicts which of $N$ candidate questions was asked, and for Needle-in-a-Haystack, the needle's depth. The evaluation borrows from steganography, which judges hiding by detector accuracy against chance. INRSteg reports its hidden payloads driving the SiaStegNet and XuNet detectors to about 50% on binary detection. The same standard is applied here: the steganalyzer's accuracy against $1/N$, or 50% for paired tests.

The decoy-sampling pipeline. The second part builds the pipeline. This includes the client-side scout and its compression level. 1-bit scouts are cheap to ship but miss relevant blocks; SpeCache's modified KIVI quantization is reused for the scout. It also includes the choice of the prior that fills the remaining slots. The prior options are uniform, a position prior learned from many questions, or a prior matched to the marginal of real selections, analogous to how generative steganography in StyleGAN2 buys undetectability by matching the cover distribution at the cost of density. Finally, it includes the server pipeline. The server double-buffers block transfers behind encrypted compute, following FPDT's overlap strategy. It also lays out fetched blocks so that unused slots align with whole ciphertext tiles. SpENCNN and HE-PEx both show that sparsity saves no encrypted compute unless it removes entire rotation sub-blocks or tiles.

Mapping the trilemma. The third part maps the trilemma surface: accuracy versus budget $B$ versus detector advantage, across $p_{hi}/p_{lo}$.

Feasibility. Accuracy and leakage can be studied in plaintext, because attention over a fixed block subset is a deterministic function of that subset. Latency is measured in an encrypted CKKS implementation of PC-attention on a smaller model, then extrapolated with a cost model calibrated against Sylph's reported per-layer and end-to-end timings. Full Llama-3-8B encrypted runs are reserved for the final operating points if hardware permits.

Baselines

Naive reference. The do-nothing reference is Sylph-style full PC-attention over the entire public context, with the public KV kept resident or streamed in full. It leaks nothing, so it is the correct privacy reference. The file reports 20 s summarization and 18 s per output token for 128 encrypted tokens, and 64 s summarization and 22 s per token for 4096 tokens with the last 128 encrypted, on 8 RTX PRO 6000 GPUs (Sylph). It is run on the same hardware and model as our system. Beating it means matching its LongBench and Needle-in-a-Haystack accuracy within a preregistered tolerance at lower end-to-end latency.

Strongest privacy-preserving competitor. This is query-independent static eviction: MPCache's look-once removal of tokens unimportant to all queries, applied at prefill using only public information (MPCache). Our decoy scheme degenerates to it when $p_{hi}=p_{lo}$. MPCache reports 1.8–2.01× latency reduction and 3.39–8.37× communication reduction in three-party computation at 5–10% cache retention. It also notes drops on recall-heavy tasks. I found no reported result on Lacuna for static eviction under FHE, so we run it ourselves at identical fetch budgets $B$. Beating it means higher accuracy at equal $B$, especially on recall-heavy tasks, at a measured detector advantage below a preset threshold.

Non-private upper bound. SpeCache's plaintext scout-and-prefetch defines the best accuracy achievable at a given budget when leakage is allowed. The file reports a 4.6× throughput gain at 32k context on an A6000. On LongBench accuracy the file says only "near-parity" with full 16-bit caching; I found no reported scalar on Lacuna for SpeCache's LongBench accuracy. This baseline is a ceiling, not a target.

Ablations. Two ablations isolate the key ingredient. The first is uniform-random decoys, the same budget with an uninformed prior. It tests whether prior matching matters. The second is client selection with no decoys, $p_{lo}=0$. It shows how much leakage the decoys actually remove. All arms share the same scout, budget grid, model and tuning budget for $p_{hi}$, $p_{lo}$ and the prior.

Why not just…?

Why not just fetch the whole public context? The cost grows with context length, and Sylph's own numbers show summarization latency roughly tripling from 128 to 4096 tokens. Encryption's fourfold weight expansion also leaves little GPU memory for long public KV caches, so full streaming makes PCIe transfer the limit. The naive baseline above measures exactly how much this costs at 16k–32k public tokens.

Why not let the server choose blocks with an encrypted scorer? Choosing top-$k$ blocks under encryption needs encrypted comparisons. MPCache found that the analogous sorting and argmax in secure computation can be slower than keeping the full cache. Under CKKS, comparisons need high-degree polynomial approximations, which drive the extra bootstrapping cost that PowerSoftmax and Sylph work hard to avoid. The client already holds the question in the clear, so selecting there costs nothing cryptographically.

Why not just use static, query-independent selection? This is the real threat. It leaks nothing, and if relevance in long-document tasks is mostly position-driven or query-agnostic, it may match our accuracy. The proposal is falsified if the decoy scheme's accuracy at equal $B$ is within noise of static eviction. That outcome would still be informative, because it would mean Sylph-style systems can sparsify freely. The experiments test this on retrieval tasks such as Needle-in-a-Haystack and NarrativeQA, where MPCache already reports static eviction struggling.

Why not use lightweight obfuscation like OSNIP instead of FHE? OSNIP protects input embeddings by mapping them into a region of the model's latent space that leaves the output unchanged, at 0.96 ms overhead. It relies on a trusted setup and on geometric heuristics rather than lattice hardness. It also says nothing about access patterns, because a server running an obfuscated query against an offloaded cache still sees which blocks it reads. Our leakage measurement applies unchanged to OSNIP-style pipelines, and we report it for them as a side result.

Decisive Experiments

Evaluation uses LongBench and Needle-in-a-Haystack, the benchmarks used by SpeCache and MPCache. Public contexts are 8k–32k tokens and private questions are up to 128 tokens, matching Sylph's split. The model is Llama-3-8B, with polynomial-attention variants in the PowerSoftmax style for the encrypted runs.

The first check is that the leak exists. With no decoys, the access-pattern steganalyzer should identify the needle's depth and the question's identity far above chance. If it cannot, the problem is moot.

The second check is the frontier. At budgets of 5–20% of blocks, the decoy scheme should trace an accuracy-versus-detector-advantage curve that dominates static eviction at small but nonzero advantage. It should also stay close to SpeCache's plaintext ceiling.

The third check is whether the likelihood-ratio bound is honest. Empirical detector advantage should never exceed what the bound permits, and the gap between the two tells us whether prior matching buys real slack beyond the bound.

The fourth check is end-to-end latency in the encrypted runs. Tile-aligned block layout should turn the budget reduction into an actual drop in ciphertext rotations, with PCIe transfers hidden behind compute. Success means beating Sylph's full-context latency at equal accuracy. A secondary analysis maps how scout bit-width trades the client's download cost against recall of relevant blocks.