Veil-Then-Reveal: Protecting PII Privacy via Reversible Pseudo-Anonymization in Zero-Trust User--LLM Interaction

1 Introduction

• VTR keeps raw PII outside the remote LLM while preserving useful prompt context through reversible, user-side pseudo-anonymization.Detected values are replaced locally with realistic, same-type surrogates, and originals are restored after inference.Source: §1 · pp. 1–2
• Rank-class FPE preserves date format and ambiguity while reducing encryption overhead by 410–730×.It improves valid-date generation from 0.3% to 88.4%.Source: §1 · pp. 1–2
• Its hybrid design uses format-preserving encryption for structured identifiers and keyed semantic substitution with user-only mappings and session-specific surrogates.The mappings support cross-session unlinkability.Source: §1 · pp. 1–2
• Across three datasets, VTR achieves 97.9% detection recall, 95.2% protection of detected values, and 99.9% exact round-trip restoration.The evaluation covers 11,322 annotated PII instances.Source: §1 · p. 2

PII Detection and Text Anonymization

• Generic NER models can miss PII-specific contexts, while masking or removal can disrupt linguistic structure and prevent exact recovery.RECAP combines regex and LLM-based detection to improve recall (Rajgarhia et al., 2025).Source: §2 · p. 2

Cryptographic Sanitization

• FPE preserves structured values’ format and length, but prior approaches do not unify protection for context-dependent entities with exact end-to-end restoration.PRϵϵMPT combines FPE with metric-DP transformations for semantic attributes (Chowdhury et al., 2025).Source: §2 · p. 2

User-Side and Zero-Trust Protection

• User-side protection keeps sensitive data from untrusted cloud services, but described approaches may add computational overhead or depend on learned models.The paper contrasts these approaches with deterministic keyed mappings and FPE for user-side restoration.Source: §2 · p. 2

3 Threat Model

• VTR replaces detected PII with surrogates before transmission, so the remote LLM does not receive original values.The user runs VTR locally while interacting with a remote cloud LLM.Source: §3 · p. 2
• The provider may inspect, log, retain, analyze, and correlate inputs and outputs across sessions, but cannot access user-side keys, mappings, or the restoration vault.The model assumes correct inference and no compromise of the user or modification of inference.Source: §3 · p. 2
• Protection guarantees apply only to detected PII and assume an uncompromised user device with inaccessible keys, mappings, and restoration state.VTR does not prevent contextual or semantic inference.Source: §3 · pp. 2–3

4 Methodology

• VTR locally detects PII and replaces it with realistic surrogates before transmission, then restores the response on-device to complete a reversible round trip.Only the pseudonymized prompt is sent to the untrusted cloud LLM.Source: §4 · p. 3

4.1 PII Detection and Protection

• A local detector identifies PII spans and assigns each a type; session-specific key material is derived from a device-held master key to prevent straightforward cross-session linkability.Distinct labels derive separate syntactic and semantic keys.Source: §4.1 · p. 3

4.2 PII-Aware Surrogate Pseudonymization

• Detected entities are assigned to syntactic protection for structured formats or semantic protection for entities requiring type and linguistic plausibility.Examples include SSNs, phones, cards, and dates for syntactic handling, and people, locations, organizations, and email for semantic handling.Source: §4.2 · p. 3

4.2.1 Syntactic PII protection Method

• For structured PII, FPE encrypts digits while retaining the original non-digit layout; date translation instead applies a common document-level offset to preserve relative order and duration unless a date crosses the supported-range boundary.Independent date encipherment can break temporal relations, so translation is used when those relations matter.Source: §4.2.1 · pp. 3–5
• For dates, rank-then-encipher maps values into valid representations, preserving supported ambiguity and original layout; incomplete dates are declined.Timestamps retain separators, fractional precision, and time zone; valid dates are drawn from the supported range.Source: §4.2.1 · pp. 3–4

4.2.2 Semantic PII Protection Mechanism

• For semantic PII, VTR selects plausible same-type surrogates from curated pools using a session key, with a session-local vault supporting restoration and collision handling.Session-specific keys produce different surrogates across sessions while preserving consistency within a session.Source: §4.2.2 · p. 5

4.3 On-Device PII Restoration

• VTR restores the returned response locally, reversing syntactic transformations and using the session-local vault for semantic surrogates; keys and vault never reach the remote model.Restoration state is discarded at session termination.Source: §4.3 · p. 6

5.1 Experimental Setup

• The setup evaluates four corpora, three untrusted models, and eleven protection baselines, with metrics spanning detection, transformation, trust-boundary privacy, and restoration.The corpora are ai4privacy, PUPA, WildChat, and ShareGPT; the models are Llama-3.2-3B, Gemma-2-2B, and Phi-3.5-mini.Source: §5.1 · p. 6

5.2 Main Results: VTR vs. Baselines

• On all 664 PUPA rows, VTR reduces Leaked from 95.1% to 27.0% (3.5×) while retaining 95% of the request without local generation.HaS lowers leakage to 19.8% but retains 86% and requires about two Local generations per request.Source: §5.2 · p. 6, Table 1 · p. 7
• On 1,000 ai4privacy documents, VTR leaks 2.9% of values with 99.1% retention; Rescriber has 2.8% leakage and 98.0% retention.The per-type comparison covers VTR and every baseline on the same documents using Llama-3.2-3B.Source: §5.2 · p. 6, Table 3 · p. 8
• VTR round-trips 99.9% of protected entities without collisions, and valid surrogates reach 77.3%, versus 75.5% without FPE.DATE validity is 88.4% with FPE, versus 65.9% without FPE and 0.3% for Prεεmpt; DATE FALLBACK protection is 67.2%.Source: §5.2 · p. 7, Table 2 · p. 7
• All echoed surrogates restore correctly (100.0%); VTR recovers 42.2%, 48.7%, and 79.7% on Llama, Gemma, and Phi, respectively.Recovery varies with the models’ Echoed rates.Source: §5.2 · pp. 7–8, Table 4 · p. 8

5.3 Ablation Study

• Rank-class preserves 100.0% of date ambiguity across corpora, versus 37.8–96.9% for walk and 54.8–95.5% for rank.It requires 1.4–2.6 cipher calls per date, 410–730× fewer than walk.Source: §5.3 · p. 8, Table 5 · p. 8
• On 97 ShareGPT files, SHIFT restores Order and Computed date (100.0%, 97.9%) but reduces Tense to 5.2%; SHIFT-CAPPED raises Tense to 75.3%.Encipherment alone shifts dates by 11,242 days, yielding 53.6% Order, 24.7% Tense, and 0.0% Computed date.Source: §5.3 · p. 8, Table 6 · p. 8

6 Conclusion

• Across 11,322 PII instances, VTR achieves 97.9% detection recall, 95.2% protection, and 100% restoration of echoed surrogates.The framework combines FPE for structured identifiers and keyed semantic surrogates with local restoration.Source: §6 · p. 8

Limitations

• VTR’s protection depends on detection recall, and omitted, modified, or paraphrased surrogates cannot be restored exactly.Implicit, ambiguous, and domain-specific PII may need additional detection; semantic surrogates may also miss fine-grained contextual relationships.Source: Limitations · p. 9
• The evaluation covers text-based LLM interaction, not multimodal inputs, tool calls, or long-term conversational state.Those settings may raise additional privacy and restoration considerations.Source: Limitations · p. 9

A.1 Value recovery: VTR vs. baselines.

• On values returned to users, VTR recovers 38.2%, matching the unprotected prompt’s 38.4%, while leaking no values; it combines near-unprotected value recovery with less than 3% leakage.Source: §A.1 · p. 10

A.2 Time per Request: VTR vs. baselines

• VTR spends 0.057 s per request on the device, with encryption and restoration each under a millisecond and no local generation.Its CPU-based detector and cipher need no device GPU; local-model baselines take about 60 to 1,300 times as long.Source: §A.2 · pp. 10–11

A.3 Local regeneration: VTR vs. baselines

• VTR restores echoed values exactly from local state without querying a local model, while keeping the remote model unaware of original PII.Local regeneration can recover additional values by querying a model with access to the original prompt, but incurs local inference cost.Source: §A.3 · pp. 11–12

B.1 End-to-End Round-Trip Examples

• With the system prompt, sanitized-prompt refusals fall from 22/40 to 16/40 and repeated surrogates rise from 31/137 to 52/137.The prompt is applied identically to each method and the unprotected control; the authors state it removes a penalty sanitization would otherwise impose rather than giving sanitized prompts an advantage.Source: §B.1 · p. 12

B.2 Detector Choice

• The VTR detector configuration reaches 97.9% Recall, missing 240 of 11,322 entities, versus 1,941 for Rescriber and 2,677 for HaS.Detector choice changes Missed by 7.8× and largely determines how much PII remains exposed.Source: §B.2 · p. 12

C.1 Failure of Independent Date Encipherment

• Independent date encipherment can reverse chronology and distort an 878-day interval to 26,599 days; a common document-level offset preserves relative temporal structure.The example makes an article appear updated seventy-two years before it was written.Source: §C.1 · pp. 12–13

C.2 Parameters

• The translation uses S = 4000 days to bound displacement and g = 15 days to exclude offsets near whole-year shifts.The stated range yields 8,001 candidate offsets.Source: §C.2 · p. 13

C.3 Admissible Offsets

• The admissible-offset filter excludes weekday-preserving and near-whole-year shifts; exhaustive enumeration accepts 6,322 of 8,001 offsets, an empirical rate of 0.790.The constraints remove calendar structure that could reveal systematic date shifts.Source: §C.3 · pp. 13–14

C.4 Offsets of the Worked Example

• In the worked example, SHIFT and SHIFT-TODAY use a 3,328-day displacement, while SHIFT-CAPPED uses 27 days.The smallest displacement any date receives is 3,328 days for SHIFT and SHIFT-TODAY, versus 27 days for SHIFT-CAPPED.Source: §C.4 · p. 15

• Dates shifted beyond the supported range wrap to its far end, losing their order and distance relative to other document dates while remaining exactly restorable.Source: §C.5 · p. 15
• No date wraps when every date lies at least S days inside the range, from 1910-12-15 to 2089-01-17.The condition is 0 ≤ ai + ∆d < N for all dates.Source: §C.5 · pp. 15–16
• Two of fourteen dates in synthetic ai4privacy multi-date documents fall outside that interval; offsets can wrap 1902 and 1907 dates into the 2090s.The wrapped dates restore exactly but lose their relationships to other dates in the document.Source: §C.5 · p. 16
• When the result does not wrap, inverse translation restores a model-computed date c days after its surrogate as c days after the real date.In the example, 2017-07-19 inverts to 2026-08-29, thirty days after the real visit; the inverse of Eq. (5) instead maps it to 1973-09-30.Source: §C.5 · pp. 16–17

D Privacy Guarantee

• The ideal game reveals only the leakage function: surrounding text, surrogate format, repeated-value patterns, and, under date translation, within-document date differences.The detector is treated as a black box, so the guarantee covers the PII entities it returns.Source: D Privacy Guarantee · pp. 17–18
• Theorem 1 bounds an adversary’s distinguishing advantage by twice the total cost of replacing VTR’s cryptographic primitives with ideal versions.The proof compares real and ideal games; in the ideal game, equal-leakage candidates produce sanitized prompts with the same distribution.Source: D Privacy Guarantee · p. 18
• Per-session keys support unlinkability: replacing a value with a same-type, same-format value unused in that session leaves leakage unchanged.A long-lived key would instead assign the same surrogate across sessions.Source: D Privacy Guarantee · p. 18
• Date translation preserves within-document gaps but reveals them, and SHIFT-TODAY can reveal the offset to a provider that knows the real present.Encipherment is the default; translation is used only when intervals between dates matter.Source: D Privacy Guarantee · p. 18

E Examples of the Syntactic Mechanism

• Direct identifiers retain their layout while their digits are enciphered; a phone’s leading country code is copied unchanged.The worked examples also show that rank-based date encipherment preserves the original representation and ambiguity class.Source: E Examples of the Syntactic Mechanism · pp. 18–19
• Dates without a full calendar form to rank are handed to the semantic mechanism; digit-bearing fragments use vault surrogates, while digit-free text is unchanged.A transformed time-like string such as 18:13 may not remain a valid time.Source: E Examples of the Syntactic Mechanism · p. 19

• Semantic pools use locale data for names and cities, generated company names, and common e-mail providers.The city pool contains 21,396 entries, the company pool 5,392 names, and the e-mail domain pool 15 providers.Source: F Examples of the Semantic Mechanism · p. 19
• Name lists are maintained per locale and merged globally for e-mail addresses; city lists are merged across locales into one pool.The US name lists derive from Social Security Administration given-name tables and Census surname counts.Source: F Examples of the Semantic Mechanism · p. 19, Table 17 · p. 20

G.1 Datasets

• ai4privacy is template-generated text with gold PII annotations, used to assess detection recall and per-entity protection.WildChat and ShareGPT test transfer to naturally occurring conversations; PUPA provides 664 annotated WildChat turns for privacy–utility comparisons.Source: §G.1 · p. 20

G.2 Detector Configuration

• The detector combines a transformer sequence model with validating recognizers and two groups of surface-form shape recognizers.The shape patterns use a 0.4 threshold, admitting all eight patterns, and lower-scoring duplicates are discarded.Source: §G.2 · pp. 20–21, Table 19 · p. 21

G.3 Baselines

• Baselines span entity substitution, local rewriting, and differential-privacy methods, with entity-level methods applied to the same detected entities.The reported operating points use method-specific ε values; ε is not directly comparable between DP-MLM and DP-Prompt.Source: §G.3 · pp. 21–22

G.4 Evaluation Metrics

• Evaluation metrics cover detection, transformation, trust-boundary leakage and retention, date handling, and end-to-end restoration.Leakage and retained content are considered together because discarding more content can reduce leakage at a utility cost.Source: §G.4 · pp. 22–23

G.5 Environment and Cryptographic Parameters

• Experiments use a 256-bit master key, HKDF-SHA256-derived 256-bit session keys, AES-256 FF1, and HMAC-SHA256 for semantic hashing.The evaluation ran on a single workstation with an RTX PRO 6000 Blackwell GPU.Source: §G.5 · p. 23