💻 computer science

Protecting User Prompts Via Character-Level Differential Privacy

This paper proposes a character-level differential privacy method that sanitizes user prompts by randomly perturbing characters before sending them to a remote LLM, which then reconstructs common non-sensitive words while effectively obscuring rare sensitive information, thereby achieving a strong privacy-utility tradeoff without requiring explicit PII identification.

Original authors: Shashie Dilhara Batan Arachchige, Hassan Jameel Asghar, Benjamin Zi Hao Zhao, Dinusha Vatsalan, Dali Kaafar

Published 2026-03-30

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Shashie Dilhara Batan Arachchige, Hassan Jameel Asghar, Benjamin Zi Hao Zhao, Dinusha Vatsalan, Dali Kaafar

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you have a very smart, but slightly nosy, assistant (a Large Language Model or LLM) who lives in a different country. You want to ask this assistant to summarize a medical report or an email for you. The problem? Your report contains your home address, your phone number, and your doctor's name. If you send the raw text, the assistant might memorize it, leak it, or accidentally show it to someone else.

This paper proposes a clever way to send your message that protects your secrets but still lets the assistant do its job. Here is the simple breakdown:

The Problem: The "Glass House"

Currently, when you talk to an AI, you are essentially shouting your secrets into a glass house. The AI sees everything. If you type "My name is John Doe and I live at 123 Maple Street," the AI sees "John Doe" and "123 Maple Street" clearly.

The Solution: The "Scrambler" and the "Fixer"

The authors suggest a two-step process that happens before your message even leaves your computer.

Step 1: The Scrambler (Character-Level Noise)

Instead of trying to find and hide specific secrets (which is hard because you might miss something), they propose scrambling every single letter in your message randomly.

The Analogy: Imagine you are sending a letter, but before you put it in the envelope, you take a pair of scissors and randomly snip out a few letters from every word, replacing them with random gibberish.
- Original: "John Doe"
- Scrambled: "Joh3 D0e" or "Jxhn D#e"
- Original: "Call me at 555-0199"
- Scrambled: "C@ll m3 555-0!99"

This is done using a mathematical rule called Differential Privacy. It guarantees that the scrambled version looks almost like a random mess to anyone who intercepts it.

Step 2: The Fixer (The AI's Superpower)

Now, you send this scrambled, messy text to the AI and say: "Please fix the typos, make it readable, and then summarize it."

Here is where the magic happens. The AI is like a super-smart editor who has read millions of books.

Common Words: If the scrambled word was "Call," and it looks like "C@ll," the AI knows immediately, "Oh, that's 'Call'!" because "Call" is a common word, and the context (like "me at") makes it obvious. The AI fixes it easily.
Rare/Secret Words: If the scrambled word was a specific name like "Harlan," and it looks like "H_rlan" or "H@rld," the AI is stuck. It doesn't know if the name is "Harlan," "Herman," or "Harold." Because these names are rare and unique, the AI cannot guess them correctly. It might guess "Harold," but it's just a guess, not the real secret.

The Result: A "Magic Filter"

The paper tested this on real medical records and emails. The results were impressive:

The Good Stuff (Utility): The AI successfully fixed the common words (like "patient," "doctor," "hospital"). The final summary made perfect sense and was very useful.
The Secret Stuff (Privacy): The AI failed to guess the specific names, phone numbers, and addresses. It reconstructed them at a rate no better than just guessing randomly.

Why is this better than other methods?

Old Way (Redaction): Imagine trying to hide secrets by crossing them out with a black marker. If you miss one spot, the secret is out. Also, if you cross out too much, the sentence makes no sense.
This Paper's Way: You don't need to know what is a secret. You just scramble everything. The AI naturally fixes the boring stuff but leaves the secrets as a mystery. It's like sending a puzzle where the easy pieces snap together, but the unique, secret pieces remain a blur.

The Bottom Line

This method is like sending a letter through a foggy window.

If you look at a common object (like a chair) through the fog, you can still tell it's a chair.
If you look at a specific, unique object (like your house key) through the fog, you can't tell what it is.

The authors found that by adjusting how "foggy" the window is (a setting called epsilon), you can get the perfect balance: the AI gets enough clarity to do its job, but your secrets remain safely hidden in the fog.

1. Problem Statement

Large Language Models (LLMs) are increasingly used for personal and professional tasks, often requiring users to submit prompts containing sensitive Personally Identifiable Information (PII) such as names, medical record numbers, and addresses. Since these models are typically hosted by third parties, there is a significant risk of data leakage, where sensitive information could be memorized by the model or exposed to untrusted entities.

Existing mitigation strategies have notable limitations:

NER/Rule-based Filtering: Relies on detecting specific entities, leading to false negatives (missed PII) and false positives (over-redaction).
Homomorphic Encryption/SMC: Computationally expensive and requires changes to the remote LLM infrastructure, which is often impractical.
Word-level Differential Privacy (DP): Perturbs entire words, which often destroys semantic coherence and utility, even for non-sensitive words.
Obfuscation: Lacks formal privacy guarantees.

The core challenge is to sanitize user prompts automatically without explicitly identifying sensitive terms, while maintaining the utility (readability and task performance) of the prompt for the downstream LLM task.

2. Methodology

The authors propose a Character-Level Local Differential Privacy (LDP) mechanism combined with LLM-based prompt restoration. The process involves two main stages:

A. Noise Injection (Client-Side)

Before sending a prompt to a remote, untrusted LLM, the user applies a $k$ -ary Randomized Response ( $k$ -RR) mechanism to every character in the prompt.

Mechanism: For each character in a word, the algorithm decides whether to keep the original character or replace it with a random printable ASCII character (excluding spaces).
Privacy Parameter ( $\epsilon$ ): Controls the probability of perturbation. A lower $\epsilon$ increases privacy (more noise) but reduces utility.
Independence: Each character is perturbed independently. Crucially, the length of the word is preserved, providing a structural cue for the LLM.

B. Prompt Restoration and Task Execution (Server-Side)

The perturbed text ( $T^*$ ) is sent to the remote LLM. The LLM is instructed to:

Restore: Correct the typos and noise introduced by the $k$ -RR mechanism to reconstruct the original text as much as possible.
Execute: Perform the intended downstream task (e.g., summarization).

The Core Intuition:

Common Words (Non-Sensitive): These words have low entropy and strong contextual correlations. Even with character-level noise, LLMs can easily reconstruct them using context, word length, and common spelling patterns (e.g., reconstructing "correspondence" from "cbrr/MpondenXe").
Rare Words (Sensitive/PII): Sensitive terms (e.g., specific patient names, unique IDs) are high-entropy and rare in training data. They lack strong contextual constraints. When perturbed, the LLM cannot reliably distinguish the original word from other plausible rare words, effectively making reconstruction close to random guessing.

3. Key Contributions

Character-Level LDP Mechanism: A novel approach applying $k$ -RR at the character level rather than the word level. This avoids the semantic destruction of word-level DP and the detection failures of NER-based methods.
Automated Privacy without Detection: The method does not require identifying sensitive entities beforehand. It applies uniform protection, relying on the statistical rarity of sensitive words to ensure they remain unrecoverable.
Theoretical Baseline: The authors establish a theoretical baseline for the reconstruction probability of completely random words under $k$ -RR. They demonstrate that sensitive PII reconstruction rates in their experiments closely match this theoretical "random guessing" baseline.
Unified Evaluation Framework: A comprehensive comparison against Word-level DP and Rule-based PII redaction (Presidio) using a unified Privacy-Utility trade-off metric.

4. Experimental Results

The method was evaluated on two datasets: i2b2/UTHealth (medical records) and Enron (emails), using GPT-4o mini and Llama-3.1 8B as the remote LLMs.

Privacy Performance:
- Sensitive words were reconstructed at rates close to the theoretical baseline for random words (i.e., near random guessing).
- For example, at $\epsilon = 5.5$ (GPT-4o mini), sensitive term reconstruction was $\approx 20\%$ , while non-sensitive reconstruction was $\approx 70\%$ .
- Iterative restoration (asking the LLM to restore a second time) did not significantly increase the reconstruction of sensitive terms, confirming the robustness of the method.
Utility Performance:
- Despite significant noise, the semantic similarity between the summary of the original prompt and the restored prompt remained high (often $>80\%$ ).
- The LLM successfully recovered the context and meaning of the prompt even when specific PII was unrecoverable.
Comparison with Baselines:
- vs. Word-level DP: Character-level DP achieved higher utility (semantic similarity) for the same level of privacy protection. Word-level DP caused larger semantic shifts that were harder to repair.
- vs. Presidio (Rule-based): Presidio offered high utility at a fixed setting but lacked tunability. More importantly, Presidio failed to protect non-standard or misspelled PII, whereas the character-level method protected all text uniformly.

5. Significance and Implications

Balanced Trade-off: The method successfully navigates the privacy-utility trade-off, offering strong protection for high-entropy sensitive data while preserving the readability and context of common language.
Deployment Feasibility: It requires no changes to the remote LLM infrastructure and no complex cryptographic overhead, making it suitable for client-side browser plugins or local agents.
Robustness against Detection: By not relying on entity detection, the method is immune to "false negatives" where NER models miss novel or obfuscated PII formats.
Future Calibration: The authors suggest that the optimal $\epsilon$ should be calibrated based on the specific restoration model used, as stronger models might reconstruct slightly more, but the character-level noise ensures that even state-of-the-art models struggle with rare, sensitive strings.

In conclusion, this paper presents a practical, mathematically rigorous, and effective solution for protecting user prompts in LLM interactions, leveraging the inherent statistical properties of language to differentiate between recoverable context and unrecoverable sensitive data.