An Inversion Attack Against Obfuscated Embedding Matrix in Language Model Inference

Yu Lin, Qizhi Zhang, Quanwei Cai, Jue Hong, Wu Ye, Huiqi Liu, Bing DuanEMNLP 2024 · OpenReview

Abstract

With the rapidly-growing deployment of large language model (LLM) inference services, privacy concerns have arisen regarding to the user input data. Recent studies are exploring transforming user inputs to obfuscated embedded vectors, so that the data will not be eavesdropped by service provides. However, in this paper we show that again, without a solid and deliberate security design and analysis, such embedded vector obfuscation failed to protect users’ privacy. We demonstrate the conclusion via conducting a novel inversion attack called Element-wise Differential Nearest Neighbor (EDNN) on the glide-reflection proposed in (CITATION), and the result showed that the original user input text can be 100% recovered from the obfuscated embedded vectors. We further analyze security requirements on embedding obfuscation and present several remedies to our proposed attack.

Introduction

As Large Language Models (LLMs) become central to cloud-based services, a massive privacy bottleneck has emerged: how can users send private data to a server for processing without the server being able to read it?

Traditional cryptographic solutions like Multi-Party Computation (MPC) or Homomorphic Encryption (HE) are mathematically secure but computationally expensive, often making real-time inference sluggish. To solve this, recent research proposed embedding obfuscation. Instead of sending raw text, the user sends "obfuscated" mathematical vectors (embeddings). Specifically, a geometric transformation called glide-reflection was proposed to scramble the data, aiming for a balance between security and inference speed. This paper investigates whether this approach truly protects user privacy.

Methodology: The EDNN Attack

We introduce the Element-wise Differential Nearest Neighbor (EDNN) attack, which exploits a mathematical oversight in the glide-reflection schema. The original obfuscation method applies a transformation where the random vectors used for scrambling ($l_i$ and $t_i$) have identical values across all their elements.

Because these "scrambling" values are constant across the vector, the difference between any two elements within a single obfuscated vector remains identical to the difference between those same elements in the original, non-obfuscated vector.

The EDNN Algorithm follows three steps:

  1. Shift and Subtract: For every obfuscated vector, the attacker cyclically shifts the elements and subtracts them from the original (e.g., $element_1 - element_2$).
  2. Distance Matching: The attacker performs the same operation on the publicly available pretrained embedding matrix.
  3. Nearest Neighbor Search: By comparing these "differential signatures," the attacker can find the exact match in the original vocabulary. Even if the model was fine-tuned, the relative distances between elements remain stable enough to allow for perfect reconstruction.

Key Insights and Robustness

The vulnerability stems from the fact that "naive" linear transformations like glide-reflection preserve the internal structure of the data. If the transformation doesn't change the relative relationship between vector elements, an attacker can simply analyze those relationships.

Distribution of distances between obfuscated tokens and original vocabulary showing a clear separation between correct and incorrect matches.

As shown in the figure above, the distance between an obfuscated token and its correct original counterpart is approximately three orders of magnitude smaller than the distance to any other token. This makes the attack incredibly robust against noise or minor model changes.

Experimental Evaluation

We evaluated the EDNN attack across several standard NLP benchmarks and models:

  • Models: BERT, RoBERTa, and mBERT (multilingual BERT).
  • Benchmarks: GLUE (general language understanding), CoNLL2003 (Named Entity Recognition), and XNLI (cross-lingual inference).

The results were definitive: the EDNN attack achieved a 100% token recovery rate across all tested models and datasets.

Recovery accuracy of the EDNN attack across various models and NLP tasks.

Notably, fine-tuning the models on specific tasks—which slightly alters the embeddings—did not degrade the attack's effectiveness. Furthermore, the attack is computationally efficient, requiring only basic matrix operations and nearest-neighbor lookups, meaning a malicious server could perform this reconstruction in real-time.

Discussion and Security Requirements

Based on these findings, we propose two formal requirements for future embedding obfuscation schemes:

  1. Fixed-point nonexistence: An adversary should not be able to find any mathematical "invariant" (like the element-wise difference) that survives the transformation.
  2. $(k, \epsilon)$-anonymity: Obfuscated embeddings should be indistinguishable from at least $k-1$ other embeddings to prevent precise matching.

While EDNN successfully breaks glide-reflection, its effectiveness against more complex obfuscation schemes remains to be tested. Future work should focus on more sophisticated defenses, such as integrating Differential Privacy (DP) noise into embeddings or optimizing Homomorphic Encryption by applying it selectively to the initial layers of a model.

Summary updated

Abstract

With the rapidly-growing deployment of large language model (LLM) inference services, privacy concerns have arisen regarding to the user input data. Recent studies are exploring transforming user inputs to obfuscated embedded vectors, so that the data will not be eavesdropped by service provides. However, in this paper we show that again, without a solid and deliberate security design and analysis, such embedded vector obfuscation failed to protect users’ privacy. We demonstrate the conclusion via conducting a novel inversion attack called Element-wise Differential Nearest Neighbor (EDNN) on the glide-reflection proposed in (CITATION), and the result showed that the original user input text can be 100% recovered from the obfuscated embedded vectors. We further analyze security requirements on embedding obfuscation and present several remedies to our proposed attack.
BibTeX
@inproceedings{lin2024inversion,
  author = {Yu Lin and Qizhi Zhang and Quanwei Cai and Jue Hong and Wu Ye and Huiqi Liu and Bing Duan},
  title = {{An Inversion Attack Against Obfuscated Embedding Matrix in Language Model Inference}},
  booktitle = {Conference on Empirical Methods in Natural Language Processing},
  year = {2024},
  url = {https://openreview.net/forum?id=Cgq3ZckAVL},
}
Figure