Keyed Distance Sketches: Removing the Coordinate Frame to Defeat Offline Dictionary Attacks on Embeddings

When a database of text embeddings leaks, attackers do not break encryption — they exploit the fact that embeddings are not one-way functions. Universal Zero-shot Embedding Inversion (ZSinvert) shows that an adversary with a small open model can decode arbitrary leaked embeddings in about 90 seconds on a single GPU, recovering sensitive content with a leakage rate of over 80% on the Enron corpus, and that light Gaussian noise ($\sigma = 0.01$) does not stop it. Structurally, this is the classic offline dictionary attack from password security: the leaked material hands the attacker a local verification oracle — no server interaction, guesses tested at machine speed against millions of candidates. The cryptographic literature has long understood that once such an oracle exists, per-guess obfuscation loses; only removing the oracle (as designated-tester constructions attempt in Security models for delegated keyword searching within encrypted contents) or forcing the attacker online (as decoy systems do in Kamouflage: Loss-Resistant Password Management) changes the game. Every current machine-learning defense against embedding inversion — isotropic noise, and even the strongest concept-aware mechanism of Concept-Aware Privacy Mechanisms for Defending Embedding Inversion Attacks (SPARSE) — keeps the oracle intact and merely makes each individual guess noisier.

This proposal removes the oracle instead, by removing the coordinate frame. The core observation is that an attacker's dictionary test needs the leaked representation to live in the same absolute coordinates the attacker's decoder was trained on. We propose to store and release embeddings only through their distances to a set of secret anchors held by the data owner — a keyed, mean-invariant, pairwise-only representation. Retrieval utility survives because similarities can be computed from the anchor distances (anchor graphs even give linear-time scaling, as Centerless Multi-View K-means Based on the Adjacency Matrix demonstrates), but an offline guesser must now recover two unknowns at once: the text and the anchors. Placing the anchors in hyperbolic space and quantizing the stored distances adds a second, independent ingredient: verification becomes hierarchical, so an attacker can at best confirm that a guess lies in a coarse region of the taxonomy (a hypernym), never an exact leaf token — a geometric counterpart of the designated-tester restriction, applied to the keyword-guessing problem that Public Key Encryption with keyword Search identified as inherent to public searchability.

Core Claim

The released form of each embedding $x_i$ is a sketch $$s_i = \big(q(d(x_i, a_1)), \dots, q(d(x_i, a_m))\big),$$ where $a_1, \dots, a_m$ are secret anchors, $d$ is a distance (Euclidean or hyperbolic), and $q$ is a coarsening quantizer. No absolute coordinates of $x_i$ are ever computed or stored. The claim is twofold: first, that this keyed, mean-invariant representation breaks the offline verification oracle that makes embedding inversion a dictionary attack — an attacker's decoder no longer applies, because the frame it was trained on does not exist in the leak; and second, that training the underlying encoder with pairwise, centerless objectives (the intrinsic-variance idea of HoroPCA: Hyperbolic Dimensionality Reduction via Horospherical Projections, the robust pairwise PCA of Avoiding Optimal Mean Robust PCA/2DPCA with Non-greedy, and the centerless clustering of Enhanced Unsupervised Discriminant Dimensionality Reduction for Nonlinear Data) is what prevents residual frame information — such as a recoverable empirical mean — from leaking through the sketch. Crucially, hyperbolic anchors with $L$ quantization levels control verification granularity: with few levels, only hypernym regions are checkable, which is exactly the trade cryptographic models want — searchable at a chosen coarseness, not exactly guessable offline. This is the hierarchical-embedding-distortion direction (the volume mismatch that makes hyperbolic space fit trees, per Hyperbolic Neural Networks) repurposed as a security dial rather than a fidelity claim.

The proposal differs from the closest existing work in a specific way. Hyperbolic Embeddings for Preserving Privacy and Utility in Text is the nearest neighbor on privacy-plus-hyperbolic: it perturbs word embeddings with a hyperbolic Laplace mechanism so that privatized words drift toward hypernyms, and reports authorship attribution falling from 12% to 5% at $\epsilon = 0.5$ and MR utility of 74.52 versus 81.10 unperturbed. But its perturbed vectors remain in absolute coordinates of a fixed embedding space, and it never evaluated against inversion decoders — its own open problem. SPARSE is the strongest defense against ZSinvert-style attacks, but it works by adding anisotropic noise around an explicit Euclidean mean (a Mahalanobis mechanism over identified "privacy neurons"), so the absolute frame — and the attacker's decoder — survive. Neither removes the oracle; both soften individual tests. HoroPCA supplies our training objective but was built for distortion reduction and classification whitening, never for leakage or adversarial settings — its own stated open problem. No paper in the file studies inversion attacks against distance-only or keyed representations; no reported result found on Lacuna for that setting.

Research Program

The program has four parts. First, formalize the leakage game: the adversary receives the full sketch database $\{s_i\}$, knows the scheme and the encoder, has the ZSinvert decoder and unlimited offline compute, but not the anchors; utility is measured by whether a retrieval system built only on sketch-similarity still ranks correctly. Second, build the mean-invariant training pipeline: an encoder regularized so that its pairwise-distance structure is preserved while any function of absolute coordinates (means, canonical origins) carries minimal information, using pairwise-robust objectives from the centerless literature. Third, place anchors on a hyperbolic manifold (via the machinery of Hyperbolic Neural Networks and Hyperbolic Neural Networks++) and sweep the quantization level $L$, mapping each level to the taxonomy depth an attacker can confirm. Fourth, analyze the attack economically: since both passwords and tokens follow Zipf's law (the empirical foundation of On the Economics of Offline Password Cracking), we compute whether anchor ambiguity multiplies the per-guess cost or shrinks the verifiable fraction enough to push a rational attacker below the threshold $T$ at which cracking stops paying.

Baselines

The "do nothing" reference point is the raw leaked embedding, for which the file gives hard numbers: ZSinvert reports over 80% sensitive-information leakage on the Enron corpus across all tested encoders, inversion in roughly 90 seconds on a single GPU, and robustness to Gaussian noise up to $\sigma = 0.01$. Any proposal must first show its mechanism degrades this attack meaningfully below that operating point.

The strongest existing competitor is SPARSE (Concept-Aware Privacy Mechanisms for Defending Embedding Inversion Attacks): concept-aware elliptical noise applied to detected privacy neurons. It is the strongest because it is the only defense in the file evaluated directly against modern inversion attacks with concrete numbers: on STS12 at $\epsilon = 10$ it reduced privacy leakage from 60% to 19% while keeping 65% downstream utility (its own spherical-noise baseline achieved 22% leakage at 60% utility), and on MIMIC-III it reduced patient sex attribute leakage from 88% to 28% where a standard DP baseline achieved only 43%. We will reimplement SPARSE, tune it on the same training data, and attack it with the identical attack pipeline and compute budget used against our sketch, so the comparison isolates the representation rather than the adversary's effort. Beating SPARSE means: at matched utility (within about two points on STS12-style similarity tasks and FIQA-style retrieval), the exact-token recovery rate of the strongest adaptive attack on our sketch is at least halved relative to SPARSE's 19% leakage figure, and attribute leakage on MIMIC-III falls below its 28%.

Two further references complete the picture. The hyperbolic Laplace mechanism of Hyperbolic Embeddings for Preserving Privacy and Utility in Text is the strongest prior geometry-aware defense, and we run it under the same inversion attack — its authors explicitly did not evaluate against decoders like ZSinvert, so this is both a baseline and a reproduction of an open question. Finally, the key ablation that isolates our central ingredient is a keyed sketch with standard mean-centered Euclidean training (anchors kept, mean-invariance dropped) alongside an absolute-coordinate release protected only by a secret random rotation (frame secrecy kept, distance-only structure dropped). If the full mean-invariant distance sketch does not beat both, the claim that the oracle removal comes from pairwise geometry rather than mere key secrecy is wrong, and we would report that.

Why not just…?

Why not just add heavier or smarter noise? Because the evidence says noise trades utility for at most incremental leakage reduction, while leaving the oracle standing. ZSinvert is robust to Gaussian noise at $\sigma = 0.01$ and stronger noise destroys utility; SPARSE's careful elliptical noise buys only a few points of leakage over spherical noise (19% versus 22% on STS12) at one point more utility. The honest caveat is that SPARSE is a real threat to our framing: one could bolt a keyed component onto SPARSE and get "noise plus a key." Our experiments settle this directly — we run SPARSE on top of our sketch and SPARSE alone under the same attack, and we also run the mean-invariant sketch with no noise at all. If the noiseless sketch alone already undercuts SPARSE's leakage figure, the coordinate-frame mechanism, not noise, is doing the work; if SPARSE-on-sketch adds substantial protection, we will say so and the combined design becomes the deliverable.

Why not just use high-dimensional Euclidean embeddings and skip hyperbolic machinery? Comparing Euclidean and Hyperbolic Embeddings on the WordNet Nouns Hypernymy Graph found that once the Euclidean baseline was properly tuned and unconstrained, it reached 92.2% MAP at $d = 200$ on WordNet, and the hyperbolic advantage vanishes at $d \geq 50$. We take this seriously as a constraint on the design, not a footnote: every hyperbolic-anchor experiment is run against Euclidean anchors at exactly matched dimension and matched tuning budget, across $d \in \{5, 20, 50, 100\}$. The one place curvature plausibly matters for us is not fidelity but granularity — quantized distances on a negatively curved manifold separate taxonomy depth from sibling direction, which is what makes hypernym-level verification meaningful. If Euclidean quantized anchors match hyperbolic ones at $d \geq 50$, we report that the geometry claim fails and keep the mean-invariant keyed sketch, which does not depend on curvature.

Why not just fix this cryptographically — key stretching or a designated-tester scheme? The economics literature already rules out stretching for hashes: On the Economics of Offline Password Cracking shows PBKDF2 with $10^5$ iterations (LastPass's setting, ten times NIST guidance) fails against a rational attacker, and matching a memory-hard function's protection would demand login delays above 400 seconds. But the deeper reason is that embeddings are not password hashes: the whole point of releasing them is fuzzy, similarity-based search, and an exact keyed hash destroys that utility. The designated-tester dPEKS of Security models for delegated keyword searching within encrypted contents achieves the same oracle-removal goal, but requires interactive registration and per-keyword salted hashes — incompatible with dense continuous search. Our sketch is honestly a keyed scheme, and a cryptographic reviewer may call it "a keyed metric with extra steps." The extra steps are precisely the research: unlike a keyed hash, it must preserve graded, hierarchical similarity, and it is an empirical question — which our utility and granularity experiments answer — whether a geometric key can deliver oracle removal and usable search at once.

Proposed Experiments and Decisive Checks

Utility is measured on MS-Marco v2.1 retrieval (the corpus ZSinvert used, where its correction model raised GTR reconstruction F1 from 31.81 to 54.39 — we reuse the corpus for both utility and attack), on STS12 and FIQA similarity tasks (SPARSE's benchmarks, enabling direct comparison with its 19%-leakage / 65%-utility operating point), and on taxonomy granularity checks over the WordNet noun hierarchy. Leakage is measured on Enron (where the raw-leak baseline exceeds 80%) and MIMIC-III for attribute leakage (where the unprotected baseline is 88% and SPARSE achieves 28%).

The attack suite has three escalating adversaries. The first transplants ZSinvert directly: beam-search decoding against the sketch, which now must jointly infer anchor positions. The second is the decisive check for the whole proposal: an anchor-recovery attack, in which the attacker inverts their own large corpus with the decoder to obtain estimated coordinates for items they possess, then solves the resulting nonlinear system for the anchors using their sketches. If this succeeds at modest compute, the keyed claim collapses, and we report it as such. The third is a frequency-weighted dictionary attack ordering guesses by Zipf frequency, feeding measured guesses-per-success into the threshold-$T$ economic model to determine whether the sketch moves the attacker below the rational-cracking threshold. Alongside these, we sweep anchor count $m$, quantization levels $L$ (reporting, for each $L$, the deepest taxonomy level an attacker can confirm — the granularity-versus-utility frontier), and the mean-invariant versus standard-training ablation. If the anchor-recovery attack stands but quantization still confines verification to hypernym regions at acceptable utility, the fallback contribution is a precise characterization of hierarchical verification granularity — the first quantitative bridge between the PEKS guessing problem and embedding geometry. Either outcome is a result; the field currently has neither.