Letting the Ciphertext Choose the Tokens: Bit-Cost-Guided Attention for Encrypted JPEG Retrieval

Some privacy-preserving image search systems let an untrusted cloud server search a user's photos without ever decrypting them. The user encrypts each JPEG so that its content is hidden but certain statistics survive. The best recent system feeds these surviving statistics into a Vision Transformer, a network that splits an image into patches ("tokens") and compares every token with every other one. That all-pairs comparison makes cost grow with the square of the token count. The cloud can therefore only afford small images, while real photo collections are high resolution. Our proposal rests on a simple observation. In these encrypted JPEGs, the server can already see how many bits each 8×8 pixel block costs to encode. That number is a free, content-free map of where the image has detail and where it is flat. We propose to use this bit-cost map to decide, before the network runs, which regions get many fine tokens and which are merged into a few coarse ones. Encrypted retrieval at native resolution then fits under a fixed compute budget.

Plaintext token-pruning methods must run several attention layers before they know which tokens matter, and they fail when they prune too early. The ciphertext supplies its importance signal at layer zero. Because the allocation is computed only from data the server already observes, it can be shown to reveal nothing beyond what the existing encryption scheme already leaks. If the idea holds, encrypted retrieval stops being stuck at thumbnail resolution, and the privacy cost of doing so can be bounded rather than argued.

Core Claim

EViT: Privacy-Preserving Image Retrieval via Encrypted Vision Transformer in Cloud Computing encrypts JPEGs with a stream cipher applied to the variable-length integer codes of the DCT coefficients (the frequency coefficients JPEG stores per block). This leaves each code's length unchanged regardless of the key. The cloud builds local length-sequence features per 8×8 block and global Huffman-code frequency features, and trains a standard full-attention ViT on them, first with contrastive self-supervision and then with ArcFace fine-tuning. We call this paper "encrypted EViT." Its attention cost grows quadratically in the number of blocks, and the paper does nothing to reduce it.

We claim that the per-block bit cost $c_i$ is an effective importance score for allocating tokens. Here $c_i$ is the sum of code lengths in block $i$, which the cloud can already read. Under a fixed compute budget, a quadtree that keeps high-cost regions fine and merges low-cost regions should beat three alternatives on high-resolution encrypted retrieval. The first is uniform coarsening. The second is learned attention-based pruning. The third is linear attention.

We also claim that the allocation adds no leakage. Every allocation decision is a deterministic function of the server's existing view, so any attack possible on the pruned representation is already possible on the unpruned one.

This gives a direct answer to a tension the research file raises. In plaintext, SG-Former: Self-guided Transformer with Evolving Token Reallocation allocates fine tokens to salient regions using a significance map derived from attention over plaintext content. Done naively in the encrypted domain, such a map could expose saliency the encryption was meant to hide. Our map is built from information the cloud already has, so it cannot expose more.

Research Program

We build the cloud-side model in three stages.

The first stage is allocation. Starting from regions of 16×16 blocks, we recursively split any region whose share of total bit cost exceeds a threshold, down to single 8×8 blocks. The threshold can be set to meet a fixed token budget $B$. Alternatively, it can be set adaptively, so that the kept fine tokens cover a fraction $\rho$ of the image's bits:

$$S^\ast = \arg\min_{S} |S| \quad \text{s.t.} \quad \sum_{i \in S} c_i \ge \rho \sum_{i} c_i,$$

where $S$ is the set of blocks kept at fine resolution. The adaptive rule directly targets the fixed keep-rate weakness that the research file notes for EViT: Expediting Vision Transformers via Token Reorganizations, which keeps the same fraction of tokens for every image. Busy images get more tokens, and flat images get fewer.

The second stage is embedding. A merged region is embedded by pooling its blocks' length sequences, with a learned scale embedding and a positional encoding at the region's block coordinates. Block coordinates are visible in a format-compliant JPEG, so using them reveals nothing new.

The third stage is training. Training follows encrypted EViT's recipe so that only the token layer changes: contrastive pretraining with its random-swap and random-splice augmentations, then ArcFace fine-tuning.

Alongside the model we write a short leakage argument. We do not claim the existing bit-cost map is harmless; the research file records that this scheme already leaks code lengths and has weaker visual security. Our claim is only that the allocation adds zero leakage on top of what the scheme already exposes. We check this empirically, as described in the experiments.

Baselines

The do-nothing reference has two versions. The first is encrypted EViT exactly as published, run at its native working resolution. We take its reported numbers as anchors. On Corel10K-a (open-set retrieval, where test classes are unseen in training) it reports 0.554 mAP@100 supervised and 0.466 unsupervised. On Corel10K-b (closed-set) it reports 0.759 supervised and 0.295 unsupervised. These figures come from EViT (encrypted). The second version is the same model applied to high-resolution images. Here it is either forced to downsample before encryption or run with full attention until memory runs out. This shows what resolution costs and buys when no allocation is used.

On high-resolution retrieval, the strongest existing encrypted method in the file is OPPR. OPPR builds bag-of-words histograms over permutation-invariant DCT group indices and reports a peak mAP of 0.56517 on Inria Holidays. In the same paper, the Markov-based retrieval of Markov process-based retrieval for encrypted JPEG images scores 0.54187. We found no reported result on Lacuna for encrypted EViT on Inria Holidays, so we will run it ourselves.

Beating the field requires two things. The method must exceed OPPR's 0.565 on Holidays at native resolution. It must also match or exceed encrypted EViT's published Corel10K numbers while using fewer attention operations.

The strongest plaintext-style competitor is EViT: Expediting Vision Transformers via Token Reorganizations, which we call token-reorganization EViT. It ranks tokens by how much attention the class token pays them, keeps the top-K, and fuses the rest into one token. In plaintext it raises DeiT-S throughput from 2923 to 4385 images/s at a cost of 0.3% top-1 accuracy. We transplant it onto the encrypted length-sequence tokens, pruning at the layers that paper recommends rather than before layer 3, and match its FLOPs to ours. A further learned-allocation baseline transfers SG-Former's attention-derived significance map to encrypted tokens.

The decisive ablation compares against two controls at an identical token budget. One is random allocation. The other is a quadtree driven by a bit-cost map shuffled across blocks within the same image. This shuffled map preserves the distribution of token sizes but destroys spatial correspondence. If our method does not clearly beat both controls, the bit-cost signal itself is not doing the work.

All models share the same backbone width and depth, augmentation, training schedule, and hyperparameter search budget. Each is compared at three matched FLOP levels, and we also report peak memory and measured wall-clock throughput, since theoretical FLOPs savings from variable-length tokens do not always appear on GPUs.

Why not just…?

Why not just coarsen uniformly, grouping every 2×2 or 4×4 block region into one token? This is the real threat. If detail in natural photos is spread roughly evenly, uniform coarsening at the same budget will match our method. SG-Former's plaintext result argues against this. Its saliency-guided allocation beats uniformly downsampled and windowed designs, reaching 84.7% vs. 83.4% ImageNet top-1 and 51.2 vs. 48.5 COCO box AP against Swin-B. That evidence comes from plaintext, though. Our matched-budget comparison on Holidays settles the question directly. If uniform coarsening comes within noise of our method, we will report that the allocation idea fails, and that the gain comes from resolution alone.

Why not just use linear attention over every block? QT-ViT approximates softmax attention with a second-order Taylor expansion in linear time and reports 84.7% ImageNet top-1 at 5.26G FLOPs. Applied to encrypted length sequences, it would avoid the quadratic cost without dropping any token. Why Softmax Attention Outperforms Linear Attention argues that linear attention loses the sharp concentration softmax provides. Sharp concentration may matter when tokens are abstract code-length statistics rather than pixels, but nobody has tested this. We run QT-ViT-style attention at full block resolution at matched FLOPs, and also combine it with our allocation, since the two are compatible.

Why not just use the class-token attention scores the network already produces? Learned importance needs several layers of context. Token-reorganization EViT itself reports that pruning before layer 3 degrades accuracy badly. The early full-attention layers stay quadratic, and at high resolution those layers are where memory blows up. Bit cost is available before the first layer. The transplanted baseline described above measures whether learned scores are more accurate enough to justify that early cost.

Why not just extract features on the client before encryption? OPPR notes that this places a heavy compute load on user devices. The outsourcing setting assumes the client only encrypts; OPPR's encryption of all 1,491 Holidays images takes 5.19 seconds in total. We treat client-side extraction as a different threat-model point rather than a competitor, and leave it out of the experiments.

Proposed Experiments

The main experiment runs on Inria Holidays, which consists of high-definition images, at native resolution, compared against OPPR's 0.565 mAP. The second runs on Corel10K-a and Corel10K-b with encrypted EViT's protocol, compared against its published mAP@100.

A resolution sweep then encrypts the same images at increasing resolutions. For each method we plot mAP against FLOPs and against peak memory. The prediction, by analogy with token-reorganization EViT's plaintext result, is that bit-cost allocation turns extra resolution into accuracy at constant compute. That paper gained 1% top-1 accuracy by moving from 224 to 304 pixels at unchanged multiply-accumulate count.

We also compare the adaptive coverage rule against fixed budgets, reporting how token count varies with per-image bit cost.

For leakage, we train a reconstruction attacker and a scene-attribute classifier on two inputs. One is the raw cloud view (lengths, Huffman statistics, coordinates). The other is the cloud view plus our allocation. Both attackers should perform identically within noise, which empirically confirms that the allocation adds nothing. Separately, and without claiming it as a contribution, we report how much the bit-cost map alone already reveals.

The project rests on two checks. The first is that the bit-cost quadtree clearly beats uniform coarsening, random allocation, and the shuffled-cost control at matched FLOPs on Holidays. The second is that it exceeds 0.565 mAP there. If the first fails, the allocation idea is wrong regardless of other results.