dX-Privacy for Text and the Curse of Dimensionality

Hassan Asghar (Paper author · Macquarie University), Robin Carpentier (Paper author · Macquarie University), Benjamin Zi Hao Zhao (Paper author · Macquarie University), Dali Kaafar (Paper author · Macquarie University)

Privacy Enhancing Technologies Symposium (PETS) 2026 · Day 3 · Beaver

Overview

In an era increasingly dominated by AI, particularly large language models (LLMs), the privacy of user-submitted text has become a paramount concern. The talk "dX-Privacy for Text and the Curse of Dimensionality," presented by Hassan Asghar from Macquarie University, along with colleagues Robin Carpentier, Benjamin Zi Hao Zhao, and Dali Kaafar, delves into a critical challenge encountered when applying differential privacy mechanisms to textual data. Specifically, the research uncovers an inherent issue with the application of dX-Privacy to word embeddings – high-dimensional vector representations of words – which leads to a severe degradation in the privacy-utility trade-off.

Watch on YouTube · Slides

Visual summary for dX-Privacy for Text and the Curse of Dimensionality by Hassan Asghar, Robin Carpentier, Benjamin Zi Hao Zhao, Dali Kaafar
Visual summary for dX-Privacy for Text and the Curse of Dimensionality by Hassan Asghar, Robin Carpentier, Benjamin Zi Hao Zhao, Dali Kaafar

Key moments

  1. 0:00 Introduction to text privacy via noisy word embeddings
  2. 2:00 Unusual privacy-utility trade-off behavior in text embeddings
  3. 4:00 Explaining the multi-dimensional Laplace mechanism for privacy
  4. 5:50 Discovery: High-dimensional word isolation causes issue
  5. 7:00 Proposed post-processing fix to recover smooth transitions
  6. 8:00 Conclusion and future work on privacy-preserving embeddings

dX-Privacy for Text and the Curse of Dimensionality

Speakers: Hassan Asghar (Paper author, Macquarie University); Robin Carpentier (Paper author, Macquarie University); Benjamin Zi Hao Zhao (Paper author, Macquarie University); Dali Kaafar (Paper author, Macquarie University)

Conference: PETS

YouTube: https://www.youtube.com/watch?v=mnSlKx--WII

Overview

In an era increasingly dominated by AI, particularly large language models (LLMs), the privacy of user-submitted text has become a paramount concern. The talk "dX-Privacy for Text and the Curse of Dimensionality," presented by Hassan Asghar from Macquarie University, along with colleagues Robin Carpentier, Benjamin Zi Hao Zhao, and Dali Kaafar, delves into a critical challenge encountered when applying differential privacy mechanisms to textual data. Specifically, the research uncovers an inherent issue with the application of dX-Privacy to word embeddings – high-dimensional vector representations of words – which leads to a severe degradation in the privacy-utility trade-off.

The core of the problem lies in the "curse of dimensionality" as it manifests in the embedding space, causing a breakdown in the expected behavior of privacy mechanisms. While dX-Privacy is designed to offer a more nuanced privacy guarantee than traditional differential privacy, particularly for "nearby" data points, its direct application to text embeddings results in an undesirable binary outcome: either perfect utility with no privacy, or complete privacy with zero utility. This talk meticulously dissects the root cause of this phenomenon and proposes an elegant post-processing solution to restore the desired smooth privacy-utility gradient.

This research is highly significant for anyone working with privacy-preserving AI, especially in natural language processing (NLP). As AI systems become more ubiquitous, ensuring that user inputs are handled with robust privacy guarantees is crucial. The findings highlight that simply porting privacy mechanisms designed for low-dimensional or generic data to complex, high-dimensional textual representations is insufficient and can lead to unintended security and utility failures, urging a re-evaluation of how privacy is conceptualized and implemented in advanced NLP applications.

Background

▶ Watch: Introduction to text privacy via noisy word embeddings (0:00)

The journey into text privacy often begins with word embeddings, a fundamental technique in modern NLP. Word embeddings transform individual words into high-dimensional numerical vectors, typically ranging from hundreds to thousands of dimensions. A key characteristic of these embedding spaces is their ability to capture semantic relationships: words with similar meanings or contexts are mapped to vectors that are geometrically "close" to each other. This property makes them invaluable for a wide array of NLP tasks, from machine translation to sentiment analysis.

The initial approach explored by the researchers to provide privacy for user-submitted text involved a straightforward process:

  1. Take each word in a user prompt.
  2. Convert it into its corresponding high-dimensional word embedding vector.
  3. Add noise to this vector using a privacy mechanism.
  4. Find the nearest word in the entire vocabulary to the noisy vector.
  5. Output this new word.

The intuition behind this method was twofold: from a privacy perspective, the original word is replaced, making it harder to identify. From a utility perspective, if the noise is small enough, the replacement word should ideally be a synonym or a semantically similar term, preserving the overall meaning of the prompt. An illustrative example provided in the talk demonstrated a sensitive user prompt being perturbed into "gibberish" by this mechanism, which an LLM could then "restore" into a coherent prompt, notably without reconstructing the original sensitive terms.

However, when this mechanism was applied to text, an "unusual behavior" emerged, contrasting sharply with the expected smooth privacy-utility trade-off typically associated with differential privacy. The canonical Laplace mechanism in one dimension, for instance, exhibits a predictable pattern: small epsilon (higher privacy) yields distant values, while increasing epsilon (lower privacy) gradually brings the output closer to the original value, eventually converging to it. This smooth transition allows for fine-grained control over the privacy-utility balance.

In stark contrast, the dX-Privacy mechanism for text showed a discontinuous behavior. As epsilon was varied, the output was either the original word (no privacy) or a very dissimilar, distant word (no utility), with very few or no intermediate "nearby" words being output. This effectively created a binary privacy-utility choice, undermining the very purpose of a tunable privacy mechanism. The researchers embarked on this study to understand why this was happening – was it an issue with the definition of dX-Privacy itself, the specific mechanism chosen, or an inherent property of high-dimensional spaces?

Key Findings

▶ Watch: Explaining the multi-dimensional Laplace mechanism for privacy (4:00)

The core discovery of this research is that the multi-dimensional Laplace mechanism, when applied within a dX-Privacy framework to high-dimensional word embeddings, is fundamentally working as mathematically intended. The "unusual behavior" observed is not due to a flaw in the mechanism's implementation or the dX-Privacy definition itself, but rather a profound consequence of the curse of dimensionality inherent to the word embedding space.

Specifically, the researchers found that in high-dimensional spaces like those used for word embeddings, the geometric arrangement of words is peculiar. While embeddings are designed to place semantically similar words "nearby," the absolute distance between a word and its nearest neighbor is often disproportionately large compared to the relative differences in distances between any two of its neighbors. This leads to a scenario where "every word is isolated."

This isolation has a critical impact on the privacy mechanism's output:

  • When epsilon is large (meaning less noise is added, aiming for lower privacy/higher utility), the added noise is often insufficient to push the perturbed vector beyond the "basin of attraction" of the original word. Consequently, the original word itself is identified as the nearest neighbor to the noisy vector, resulting in no privacy.
  • Conversely, when epsilon is small (meaning more significant noise is added, aiming for higher privacy/lower utility), the noise is so substantial that it almost always pushes the perturbed vector far away from the original word's immediate vicinity. Due to the "isolated" nature of words in high dimensions, this noisy vector lands in a region where any word, even a semantically distant one, could be its nearest neighbor. This results in no utility, as the output is effectively random and unrelated to the original word.

The crucial implication is that there is no "middle ground" where the mechanism outputs a semantically similar but distinct word. The smooth transition from original to nearby to distant words, which is characteristic of effective privacy mechanisms, is entirely absent. This finding clarifies that the problem is not with the privacy mechanism's logic, but with the geometric properties of the data space it operates within, and how these properties interact with the nearest neighbor search used to map noisy vectors back to words.

Technical Deep Dive

▶ Watch: Discovery: High-dimensional word isolation causes issue (5:50)

To understand the observed behavior, it's essential to first establish the foundational concepts. Word embeddings are dense vector representations of words, where each word is mapped to a point in a high-dimensional continuous vector space. These vectors are typically learned through neural networks trained on vast text corpora, such that the spatial relationships between vectors reflect semantic and syntactic relationships between words. For instance, the vector for "king" might be close to "queen" and "ruler," and the vector arithmetic "king - man + woman" might yield a vector close to "queen."

The privacy mechanism under investigation is based on dX-Privacy, a generalization of differential privacy. Unlike standard differential privacy, which typically aims for indistinguishability across all possible inputs, dX-Privacy introduces a distance metric d(x, y) between inputs. It ensures that the output probabilities for two inputs x and y are close, with the degree of closeness depending not just on the privacy budget epsilon (ε), but also on the distance d(x, y) between x and y. Formally, for any two inputs x, y and any output o, a mechanism M is (ε, d)-dX-private if Pr[M(x) = o] ≤ exp(ε d(x, y)) Pr[M(y) = o]. This design aims to provide a better privacy-utility trade-off, as it allows for stronger privacy guarantees for inputs that are "far apart" while still offering privacy for "nearby" inputs, which is particularly useful in contexts like location privacy where indistinguishability across the entire map is less important than indistinguishability for nearby locations.

The specific mechanism employed in this work is the multi-dimensional Laplace mechanism. In one dimension, the Laplace mechanism adds noise drawn from a Laplace distribution, whose scale is inversely proportional to epsilon. For high dimensions, the multi-dimensional Laplace distribution is constructed from two components:

  1. An angular component: This is obtained by drawing a random point uniformly on the surface of a hypersphere in the high-dimensional space. This dictates the direction of the noise.
  2. A length component: This is drawn from a distribution proportional to the negative exponential, which dictates the magnitude of the noise.

These two components are multiplied to generate a multi-dimensional noise vector. When applied to a word embedding vector w, the mechanism adds this noise n to w, resulting in w' = w + n. Since w' is almost certainly not an exact word embedding from the vocabulary, a post-processing step finds the word v in the vocabulary whose embedding is closest to w' in Euclidean distance. This word v is then output.

The researchers conducted a deep analysis of how this mechanism selects between the original word W and its nearest neighbor X. They derived an equation that governs this selection. Given an original word W, its nearest neighbor X, and the midpoint between their embeddings (let's call it M), the mechanism outputs W if the projection of the added noise Z onto the vector (X - W) is less than the distance from W to M. Conversely, if the projection is greater than this distance, X (or another neighbor) is output. This relationship can be expressed by Pr[output = W] = Pr[Z_projection < ||X - W|| / 2]. Similar equations can be derived for any two neighbors X and Y of W, dictating which one is more likely to be selected.

Their analysis revealed that, on average, the mechanism does tend to output the original word W most often, followed by its nearest neighbor X, then the second nearest neighbor, and so on. This confirms that the mechanism itself is functioning according to its design principles. However, the critical insight is that in high-dimensional word embedding spaces, the Euclidean distance between a word and its nearest neighbor is often substantial. More importantly, the relative differences in distances between any two neighbors of a word are typically very small. This means that while X is the "nearest" neighbor, it's still quite far, and other neighbors Y, Z are only marginally further away.

This geometric property of high-dimensional spaces leads to the "isolation" phenomenon. When epsilon is large (small noise), the noise vector Z is usually too short to push w' beyond the "decision boundary" where W is the closest. Hence, W is always selected. When epsilon is small (large noise), Z is so long that w' is propelled into a region where the original W is no longer the closest. Because all other words are relatively "far" and their relative distances are small, the noisy vector w' can land closer to any word in the vocabulary, not necessarily a semantically similar one. This absence of a smooth gradient of "nearby" words for intermediate epsilon values explains the observed lack of a smooth privacy-utility trade-off.

Demo / Proof of Concept

▶ Watch: Proposed post-processing fix to recover smooth transitions (7:00)

While the talk did not feature a live coding demonstration, it effectively "demonstrated" the problem and its solution through conceptual examples and graphical representations.

The initial demonstration of the problem involved a two-stage process:

  1. Illustrating the "gibberish" output: The speaker presented an example user prompt containing sensitive terms (highlighted in red). Applying the dX-Privacy mechanism word-by-word resulted in a highly perturbed, "gibberish" sentence. This visually underscored the immediate utility loss when strong privacy (large noise) is applied.
  2. LLM restoration and privacy verification: The "gibberish" output was then fed into a large language model. The LLM successfully restored the prompt into a coherent, grammatically correct sentence. Crucially, the sensitive terms from the original prompt were not reconstructed, showcasing that the privacy mechanism had successfully obfuscated the sensitive information, albeit at the cost of direct human readability. This conceptual demonstration highlighted the potential of a privacy-preserving front-end combined with an LLM for utility restoration, but also subtly hinted at the underlying issue if the privacy mechanism itself isn't well-behaved.

The core of the problem's demonstration was through comparative graphs. A graph of the canonical Laplace mechanism in one dimension was shown, clearly depicting the smooth transition: as epsilon increases, the probability of outputting the original value increases, with intermediate epsilons showing a high probability of outputting nearby values. In stark contrast, a second graph illustrated the observed behavior of dX-Privacy for text. This graph visually confirmed the "unusual behavior": for small epsilons, only distant words were output; for large epsilons, only the original word was output. The critical "middle ground" where nearby words should be frequently output was conspicuously absent, appearing as a flat line near zero probability. This graphical representation was a powerful proof of concept for the problem's existence and severity.

Following the explanation of the "isolation" issue, the talk then conceptually demonstrated the proposed fix. The researchers suggested a post-processing step: instead of directly outputting the nearest neighbor to the noisy vector, the mechanism should first arrange candidate words according to their nearest neighbor distance from the original word and then sample proportionally to that distance. While this isn't a true distance metric for dX-Privacy, it acts as a filter. A third graph was presented, showing that this post-processing step successfully recovered the desired smooth transition. The green line in this graph clearly indicated that at intermediate epsilon values, the nearest neighbors were indeed being output by the mechanism, bridging the gap between no privacy and no utility. This served as a compelling demonstration that the "fix" could restore the expected behavior, although it required a constant C to be fixed once for each vocabulary.

Defensive Implications

▶ Watch: Conclusion and future work on privacy-preserving embeddings (8:00)

The findings presented in "dX-Privacy for Text and the Curse of Dimensionality" carry significant implications for security practitioners and developers working on privacy-preserving NLP systems. The primary defensive takeaway is a critical caution: simply applying existing differential privacy mechanisms, even advanced ones like dX-Privacy, to high-dimensional text embeddings without accounting for the inherent geometric properties of these spaces can lead to broken privacy guarantees or severe utility loss.

Defenders should be aware of the following:

  1. Beware the Curse of Dimensionality: The "isolation" of words in high-dimensional embedding spaces is not merely an academic curiosity; it's a practical impediment to effective privacy. When designing systems that use word embeddings and aim for dX-Privacy, or any mechanism reliant on nearest neighbor search, one must explicitly consider how high dimensionality distorts distances and impacts the sensitivity of the mechanism.
  2. Validate Privacy-Utility Trade-off: Do not assume a smooth privacy-utility trade-off when applying noise to text embeddings. Rigorously test the mechanism's behavior across the full range of epsilon values. If the output exhibits a binary pattern (original word or random word), the mechanism is likely suffering from the curse of dimensionality, and the desired privacy guarantees for "nearby" data points are not being met.
  3. Implement the Proposed Post-Processing Fix: The talk offers a concrete solution: a post-processing step that arranges candidate words by their nearest neighbor distance and samples proportionally. This step can effectively "flatten" the distance landscape and restore the smooth privacy-utility curve. While it requires a one-time pre-processing step to determine a constant C for each vocabulary, this is a manageable overhead for achieving functional privacy.
  4. Consider Alternative Embedding Strategies: The research also highlights that other mechanisms, like the exponential mechanism, suffer from the same issue if they rely on Euclidean distance in high dimensions. This suggests a broader problem. A forward-looking defensive strategy could involve exploring or developing word embedding models that are intrinsically designed to work with noise-generating mechanisms. This might involve training embeddings in a way that makes their geometry more amenable to privacy mechanisms, perhaps by explicitly minimizing the "isolation" effect or by embedding words into spaces with different distance metrics.
  5. Contextualize Privacy Guarantees: Understand that dX-Privacy, while powerful, makes specific assumptions about the "closeness" of inputs. In text, semantic closeness is paramount. If the underlying embedding space fails to adequately represent this closeness in a way that aligns with the geometric assumptions of the privacy mechanism, the privacy guarantees might be misleading. Defenders should ensure that the chosen distance metric for dX-Privacy genuinely reflects the desired notion of "closeness" for text.

In essence, defenders must move beyond a superficial application of privacy mechanisms and engage with the deep technical nuances of the data structures they are protecting. For text privacy, this means grappling with the unique challenges posed by high-dimensional word embeddings to build truly robust and effective systems.

Key Takeaways

  • dX-Privacy for Text is Challenged by High Dimensions: Applying dX-Privacy mechanisms (specifically the multi-dimensional Laplace mechanism) directly to high-dimensional word embeddings results in an undesirable, discontinuous privacy-utility trade-off.
  • The "Curse of Dimensionality" Isolates Words: The root cause is that in high-dimensional embedding spaces, words are effectively "isolated." The distance to the nearest neighbor is large, and relative distances between neighbors are too small, preventing a smooth transition between privacy levels.
  • Mechanism Works, But Data Space is Problematic: The multi-dimensional Laplace mechanism functions as intended mathematically, but the geometric properties of word embeddings in high dimensions break its practical utility for text privacy.
  • A Post-Processing Fix Restores Smoothness: A proposed post-processing step, which samples candidate words proportional to their nearest neighbor distance from the original, successfully recovers the desired smooth privacy-utility curve.
  • Problem Extends Beyond Laplace: The issue is not unique to the Laplace mechanism; other dX-Privacy mechanisms like the exponential mechanism, if reliant on Euclidean distance in high dimensions, suffer from the same problem.
  • Future Direction: Noise-Aware Embeddings: A promising avenue for future research involves developing or training word embedding models that are intrinsically designed to be compatible with noise-generating privacy mechanisms.

About the Speaker(s)

The research presented in this talk is a collaborative effort from Macquarie University, Australia. Hassan Asghar, who delivered the presentation, is credited as a paper author from Macquarie University. He is joined in this work by his colleagues and co-authors Robin Carpentier, Benjamin Zi Hao Zhao, and Dali Kaafar, all affiliated with Macquarie University. Their collective expertise in privacy and machine learning contributed to identifying and addressing the complex interaction between differential privacy techniques and high-dimensional textual data.

Reviews

Dr. Zero (Offensive Security Researcher) — MUST SEE

Finally, someone brings actual math to the AI privacy circus to explain why sprinkling Laplace noise on word embeddings is a fool's errand. The Macquarie team proves that the curse of dimensionality fundamentally breaks dX-Privacy in LLMs, turning the privacy-utility gradient into a binary switch. This is the exact kind of rigorous, assumption-breaking research we need before vendors blindly ship broken crypto.

Heather Calloway (CISO) — MUST SEE

This research exposes a fundamental mathematical flaw in how differential privacy is applied to enterprise text and LLMs. Vendors selling "privacy-preserving AI" often rely on mechanisms that this paper proves either fail to protect the data or destroy its utility entirely. For any leadership team evaluating enterprise GenAI solutions handling sensitive data, this dictates a mandatory change in how we validate vendor privacy claims.

→ Top-rated talks at Privacy Enhancing Technologies Symposium (PETS) 2026

All talks from Privacy Enhancing Technologies Symposium (PETS) 2026