DP-SKETCH: Constant-Budget Differentially Private Text Sanitization via Sketch-and-Reconstruct

Differentially private (DP) text sanitizers either substitute tokens or rewrite the document with a language model; in both regimes a rigorous document-level guarantee grows with length, reported ε reaches the thousands, and releases stay highly re-identifiable. We introduce DP-SKETCH, a sanitizer whose budget is constant in document length. It reduces a document to a low-dimensional sketch, protects each component over a public output domain, and regenerates fluent text with one language-model call that never sees the raw document (hence DP post-processing). Evaluating at matched empirical privacy, since nominal budgets are not comparable across privacy models, DP-SKETCH reaches near-chance linkage across the evaluated English and Spanish corpora while baselines remain far above it at the same matched budget.