When differential privacy meets NLP: The devil is in the detail

Ivan HabernalEMNLP 2021 · DOI

Introduction

As Natural Language Processing (NLP) systems increasingly handle sensitive user data—ranging from private messages to medical queries—the need for robust privacy protections has become paramount. Researchers have frequently turned to Differential Privacy (DP), and specifically Local Differential Privacy (LDP), to ensure that data is "privatized" on a user's device before reaching any central server.

In 2021, Amazon Alexa researchers introduced ADePT, an auto-encoder designed to rewrite text while providing formal LDP guarantees. The promise was significant: users could share "privatized" versions of their sentences that maintain utility for downstream NLP tasks while mathematically preventing an adversary from recovering the original text. However, a recent "fact-check" by Ivan Habernal reveals that ADePT’s privacy guarantees are fundamentally flawed due to a critical miscalculation of mathematical sensitivity, leaving user data potentially unprotected.

The Problem: Miscalculating Sensitivity

The core of the issue lies in how DP is applied to high-dimensional latent spaces—the internal vector representations used by AI models. In DP, the amount of noise added to a system is determined by its "sensitivity," which measures how much a single change in input can change the output. If sensitivity is underestimated, the noise added is insufficient, and the privacy guarantee evaporates.

Habernal identifies that applying DP to these high-dimensional spaces is notoriously tricky. If the mathematical bounds are not strictly adhered to, the "privacy-preserving" label becomes a false sense of security.

Methods

To dismantle the original claims, the paper employs two primary methods:

  1. Formal Mathematical Proof: Using the Lagrange multipliers method, Habernal solves an optimization problem to find the maximum possible distance between two points in ADePT’s latent space. This proof demonstrates that the sensitivity was calculated incorrectly in the original work.
  2. Simulation: To illustrate the real-world impact, the author simulated the latent space of an encoder. By sampling thousands of vectors across increasing dimensions, he measured the frequency with which pairs of data points violated the privacy bounds claimed by the original authors.

Key Insights: The $L_1$ vs. $L_2$ Trap

The failure of ADePT stems from a mismatch in mathematical norms. The original authors used $L_2$ (Euclidean) clipping to bound their vectors but applied the Laplace mechanism, which strictly requires an $L_1$ (Manhattan distance) sensitivity bound.

Furthermore, the paper highlights the Curse of Dimensionality. In DP, sensitivity often scales with the number of dimensions ($n$). While the original paper claimed sensitivity was a constant ($2C$), Habernal proves it is actually $2C\sqrt{n}$. Because modern NLP models use latent dimensions ranging from 32 to 1024, the actual sensitivity is 6 to 32 times higher than reported.

Results: 100% Exposure

The simulation results provide a stark visualization of this failure. As the dimensionality of the latent space increases, the percentage of data points that violate the claimed privacy bound rapidly approaches 100%.

Figure 1: Percentage of pairs violating the claimed sensitivity bound as a function of latent space dimensionality.

In a typical setup with 32 or more dimensions, virtually no data points are actually protected by the original mechanism. The paper provides a concrete counter-example in a simple 2-dimensional space where the ADePT mechanism clearly violates the fundamental inequality of Differential Privacy. The true sensitivity of the ADePT mechanism is formally derived as $\Delta f = 2C\sqrt{n}$.

Conclusion and Future Work

The findings suggest a dangerous trend where "privacy-preserving" labels are applied to models based on incomplete or incorrect proofs. If the math is wrong, the experimental results—which often show high utility—are unsubstantiated because the model wasn't actually adding enough noise to be private.

Habernal suggests two remedies for the NLP community:

  1. Switch to $L_1$ norm clipping for latent vectors.
  2. Use the correct sensitivity ($2C\sqrt{n}$) when adding noise.

However, he warns that both fixes will significantly increase the amount of noise required, which will likely degrade the performance (utility) of the NLP tasks. This reinforces a fundamental truth in privacy research: there is no such thing as a free lunch when balancing data utility and individual privacy.

Summary updated

BibTeX
@inproceedings{habernal2021when,
  author = {Ivan Habernal},
  title = {{When differential privacy meets NLP: The devil is in the detail}},
  booktitle = {Conference on Empirical Methods in Natural Language Processing},
  year = {2021},
  doi = {10.18653/v1/2021.emnlp-main.114},
}
Figure