SHARD: cell-keyed residual splitting for alignment-resistant private dense retrieval
Sergey M. Kurilenko · 2026
Read SHARD: cell-keyed residual splitting for alignment-resistant private dense retrieval by Sergey M. Kurilenko (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2606-27976.txt.
Introduction
Dense embeddings power semantic search and retrieval-augmented generation. A leaked vector store can hand the underlying text back to an attacker, though. Sergey Kurilenko shows in 2026 that modern inversion attacks share one weakness to exploit. They all rely on the store being a single global geometry. Any single geometry can be aligned with a known geometry. Even a secret global rotation falls once enough known pairs are gathered.
His transform, SHARD, removes that weak axis. The embedding is split into a short public prefix and a private residual. The residual is sharded into cells, each rotated under its own secret key. Reranking runs under encryption, where the keys cancel and inner products stay exact. Retrieval quality matches raw-space scores, unlike truncation methods. Attack cost scales with the number of cells. At 256 cells, the median anchors needed rise from 200 to over one hundred thousand.
Catalog record
| CREATOR | Sergey M. Kurilenko |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 104 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2606.27976
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
SHARD: cell-keyed residual splitting for alignment-resistant private dense retrieval Sergey M. Kurilenko Abstract Dense embeddings underpin semantic search and Retrieval-Augmented Generation, yet a leaked vector store hands much of the underlying text back to whoever holds it. The modern attacks that make this possible—few-shot alignment, zero-shot inversion, unsupervised cross-space translation—all turn on the same weakness: the protected store is a single global geometry , and any single geometry can be aligned to a known one. A secret global rotation, the usual lightweight defence, is no exception, since orthogonal Procrustes recovers it once the attacker has assembled on the order of the subspace dimension in known plaintext pairs. We introduce Shard , a retrieval-preserving embedding transform built to remove that weak axis rather than to mask a distortion surrogate. The centred embedding is rotated and split into a short public prefix, which drives coarse stage-1 retrieval, and a private residual, which is sharded into C C cells and rotated cell by cell under separate secret keys; the residual is reranked under CKKS, where those keys cancel and leave the inner product exact. A single parameter C C carries the design from the global-linear baseline it replaces ( C = 1 C{=}1 ) to per-document micro-keys ( C = N C{=}N ). Measured on cached embeddings from five encoders, the transform earns its keep on three fronts. Because the rerank is full-dimensional it returns the raw-space nDCG@10 that half-SVD truncation gives up; because the residual is keyed cell-locally, recovering it into a common frame under a diffuse known-plaintext leak costs roughly C C times more anchors (the median rises from 200 200 to 102,400 102{,}400 at C = 256 C{=}256 ) for only a handful of encrypted residual queries per search; and because the public channel is a short prefix rather than half the space, it exposes far less neighbour structure, with a micro-key limit that drives the residual graph to zero and leaves an unlinkable, renewable template. The barrier holds against the stronger aligners we tried—learned-linear, non-linear, and unsupervised—and where a distortion-aware noise defence at matched utility still de-anonymises almost every probe, Shard de-anonymises none. We are equally plain about what it does not do: within a cell the keys cancel and similarities survive, a targeted attacker who concentrates on one victim’s cell needs only about d priv d_{\mathrm{priv}} anchors, and an overlapping reference corpus still leaks through the public prefix. Shard is an attack-aware geometric defence, not a cryptographic guarantee. Keywords: dense retrieval, embedding privacy, protective transforms, alignment attacks, embedding inversion, cell-keyed splitting, cancellable templates, homomorphic encryption, CKKS, retrieval-augmented generation. 1 Introduction The privacy of vector representations of text—“embeddings”—has become a first-class concern in production retrieval systems. Dense retrievers (DPR [ 5 ] , ColBERT [ 6 ] ) and state-of-the-art encoders (Sentence-BERT [ 1 ] , multilingual-E5 [ 2 ] , GTR [ 3 ] , BGE-M3 [ 4 ] ) push the per-document representation through a \sim 10^{2} -dimensional bottleneck that nevertheless preserves enough information to reconstruct the original text with high BLEU. Vec2Text [ 7 ] reports \mathrm{BLEU}\approx 97.3\% on 32 -token inputs when the attacker has query access to the encoder; GEIA [ 8 ] and TEIA [ 9 ] show that even snapshot attacks (an adversary with read access to the vector database) recover personally identifiable information at high rates. For Retrieval-Augmented Generation pipelines whose vector stores typically contain customer support tickets, internal corporate documents and personal data, this rule of thumb—“a leak of the embedding is a leak of the text”—is now well documented [ 48 , 18 ] . The defensive landscape is bracketed by two extremes that, individually, do not satisfy industrial requirements. Differential privacy [ 22 , 23 ] adds calibrated noise per-record but, in the naive coordinate-Gaussian formulation on retrieval-quality embeddings, it faces a difficult operating-point choice: mild noise preserves much of the nearest-neighbour geometry, while stronger noise destroys ranking quality long before the privacy budget reaches a level considered useful. Fully homomorphic encryption [ 27 , 33 ] allows arbitrary computation on ciphertexts, but the ciphertext-ciphertext (ct-ct) regime is too expensive for top- k search across 10^{6} documents. The weak axis of global-linear defences. Between the two extremes sits a popular lightweight middle ground: compress the collection onto a data-dependent SVD subspace, apply a single secret orthogonal rotation, publish an approximate-nearest-neighbour (ANN) index, and rerank the encrypted query under CKKS. We first measure this global-linear stack and confirm that its protection lives on one weak axis —the protected store is a single globally-aligned geometry. Concretely (Section 7 ): a known-plaintext orthogonal Procrustes attack recovers the secret rotation with about k=d/2 anchors, after which an overlapping reference corpus yields near-exact paragraph recovery ( 99.8\% top-1); the public product-quantisation index preserves a mean cosine of 0.95 and 67\% of exact top-10 neighbours; and because the rerank happens in the truncated half, the stack loses retrieval quality on real IR, dropping nDCG@10 by 2 – 8 points on BEIR. These are exactly the weaknesses that modern few-shot alignment [ 10 ] , zero-shot inversion [ 11 ] and unsupervised cross-space translation [ 17 ] attacks exploit: a single global map is, in the end, alignable. Shard : an attack-aware geometric transform. We introduce Shard , a family of retrieval-preserving protective transforms designed against the alignment and index-leakage attack surface rather than against a distortion surrogate such as \sigma_{rec} (which, as we and others show, is not a privacy metric). The construction (Section 6 ) keeps the CKKS/ct-pt machinery of the baseline but replaces its single global geometry. The construction itself is quick to state. We rotate the centred embedding and split it into a short public prefix u —the top- d_{\mathrm{pub}} PCA directions, which carry coarse stage-1 retrieval—and a private residual r . The residual is sharded into C coarse cells defined by u , and each cell is turned by its own secret orthogonal key H_{c} , a product of Householder reflections, so that the server ever only stores z_{i}=H_{c(i)}r_{i} . Reranking then happens under CKKS in the residual space, where the per-cell keys cancel, \langle H_{c}r_{q},z_{i}\rangle=\langle r_{q},r_{i}\rangle , and the inner product comes back exact . The single knob C interpolates between the global-linear baseline it replaces ( C{=}1 ) and per-document micro-keys ( C{=}N ), and along the way buys revocability at cell granularity. What this construction buys—measured rather than assumed—comes to four findings. The first is utility (Section 7.4 ): because the rerank is full-dimensional, Shard recovers the raw ranking that the truncating baseline sacrifices, so that on the BEIR tasks where half-SVD truncation significantly drops nDCG@10 it matches raw (e5-base/SciFact 0.638 against raw 0.637 and baseline 0.585 ) while exposing a public channel only a quarter to a half as wide. The second, and the headline, is that alignment resistance scales with C (Sections 7.4 – 7.5 ): under a diffuse known-plaintext leak the anchors needed to map the private residual back into its native frame grow roughly C -fold—a median of 200 for the global key, 25{,}600 at C{=}64 and 102{,}400 at C{=}256 , and the same on a second encoder—at a cost of some 7 – 30 encrypted residual queries per search. We are careful