PrivRewrite: Differentially Private Text Rewriting Under Black-Box Access with Refined Sensitivity Guarantees

Text data is indispensable for modern machine learning and natural language processing but often contains sensitive information that must be protected before sharing or release. Differential privacy (DP) provides rigorous guarantees for privacy preservation, yet applying DP to text rewriting poses unique challenges. Existing approaches frequently assume white-box access to large language models (LLMs), relying on internal signals such as logits or gradients. These assumptions limit practicality, since real-world users typically interact with LLMs only through black-box APIs. We introduce PrivRewrite, a framework for differentially private text rewriting that operates entirely under black-box access. PrivRewrite constructs a diverse pool of candidate rewrites through randomized prompting and pruning and then employs the exponential mechanism to select a single release with end-to-end ϵ-DP. A key contribution is our refined sensitivity analysis of the utility function, which yields tighter bounds than naive estimates and thereby strengthens the accuracy guarantees of the exponential mechanism. The framework requires no fine-tuning, internal model access, or local inference, making it lightweight and deployable in practical API-based settings. Experimental results on benchmark datasets demonstrate that PrivRewrite achieves strong privacy–utility trade-offs, producing fluent and semantically faithful outputs while upholding formal privacy guarantees. These results highlight the feasibility of black-box DP text rewriting and show how refined sensitivity analysis can further improve utility under strict privacy constraints.