PrivCert: Certifying Statement Support under Differential Privacy

Tsubasa Takahashi; Takumi Hiraoka

cs.CRSep 30, 2026

PrivCert: Certifying Statement Support under Differential Privacy

Authors: Tsubasa Takahashi, Takumi Hiraoka

Organizations: Acompany Co., Ltd.

Abstract

Differentially private (DP) text generation can protect individual records, but privacy alone does not specify what evidence a released statement carries about the underlying data. We identify this as an evidence gap: a private report may contain plausible claims without indicating whether they are strongly supported by the private dataset. We introduce PrivCert, a framework for privacy-preserving reporting that makes statement support explicit through privacy-preserving certificates and emit-or-abstain decisions. As a canonical instantiation, PrivCert-PF (Proposal-and-Filter) separates data-independent candidate discovery from private support certification, emitting only statements whose support passes a private evidence test. We provide theoretical grounding for this framework by characterizing the limits of implicit evidence under DP, deriving a sharp privacy--honesty frontier for single-statement certification, and establishing a worst-case cost for fine-grained multi-statement certification. Experiments on synthetic tasks and TAB, WildChat, and Yelp show that explicit certification maintains low unsupported emission, while free-text DP baselines frequently produce low-support claims under the same declared support semantics. We further show that the PrivCert contract can be realized with histogram, sparse-vector, and Gaussian mechanisms, and use DP synthetic data to illustrate an important boundary: support in a private proxy does not automatically certify support in the original data. Together, these results position privacy-preserving reporting as an evidence-design problem: not only how to generate private text, but what a private report can substantiate about its underlying data.

Figures & tables

Figure 1: From private text to private reporting with explicit support evidence. DP free-text generation can produce fluent private text without exposing the evidential basis of its claims. PrivCert -PF (Proposal-and-Filter), one instantiation of PrivCert , separates candidate discovery from DP support verification and emits only statements that pass a privacy-preserving evidence test.

Dataset	Unfiltered	Doc-DP	InvisibleInk (TinyLlama)	InvisibleInk (Qwen)	PrivCert -PF
TAB	1.000	0.894	0.958	0.994	0.010
WildChat	0.947	0.729	0.647	0.619	0.014
Yelp	0.943	0.803	0.877	0.856	0.000

Table 1: FalseEmission on realistic datasets under the declared support semantics. For free-text methods this is a descriptive diagnostic, not a theorem-backed error rate. Lower is better.

$\varepsilon_{\mathrm{tot}}$	EmitRate $\uparrow$	UnsupEmit $\downarrow$	FalseEmit $\downarrow$	MeanSupport $\uparrow$	Interval	In?
1	0.051	0.0217	0.295	0.275	[0.000, 0.335]	$\checkmark$
4	0.180	0.0085	0.033	0.327	[0.135, 0.335]	$\checkmark$
10	0.220	0.0046	0.014	0.288	[0.162, 0.335]	$\checkmark$
20	0.274	0.0014	0.004	0.250	[0.189, 0.335]	$\checkmark$

Table 2: Privacy-budget sweep on WildChat. Larger budgets improve EmitRate while preserving one-sided honesty. Intervals use the tightened upper bound

p_{\theta}+\beta(1-p_{\theta})

	Sampled $m=200$		Exact-unique
Dataset	PrivCert -Hist	PrivCert -PF	PrivCert -SVT	PrivCert -PF	PrivCert -PF (Gaus)
TAB	0.199	0.404	0.400	0.422	0.444
WildChat	0.183	0.220	0.151	0.151	0.162
Yelp	0.390	0.749	0.796	0.816	0.833

Table 3: Matched comparisons of PrivCert instantiations. Entries show EmitRate. All UnsupportedEmit values remain below

\beta=0.05

. Comparisons are matched within each candidate space.

Appendix figures & tables6 assets

Supplementary material from the paper’s appendix.

Appendix

Method	DP type	Composition unit	Sensitivity	Final guarantee
PrivCert -PF	pure DP	$m$ support queries	$\Delta_{f}\leq 1/\|R\|$	$\varepsilon_{\mathrm{tot}}$ -DP
Document-level DP	pure DP	$d_{\mathrm{doc}}$ aggregates	$\Delta_{\mathrm{doc}}$	$\varepsilon_{\mathrm{tot}}$ -DP
InvisibleInk	zCDP	private decoding	DClip sensitivity	$(\varepsilon_{\mathrm{tot}},10^{-5})$ -DP
Unfiltered LLM	none	no private-data access	n/a	reference only

Appendix

Table 4: Privacy accounting for the main-table methods. Pure-DP mechanisms also satisfy the displayed approximate-DP target.

Dataset	Proposer	#out	EmitRate	UnsupEmit	FalseEmit	MeanSupport
TAB	public LLM	3	0.003	0.003	1.000	0.006
TAB	tag-template	404	0.404	0.008	0.010	0.545
WildChat	public LLM	24	0.024	0.001	0.042	0.132
WildChat	tag-template	220	0.220	0.004	0.014	0.288
Yelp	public LLM	18	0.018	0.002	0.111	0.124
Yelp	tag-template	749	0.749	0.000	0.000	0.239

Appendix

Table 5: Proposer comparison on realistic corpora. Only the proposal distribution changes; the private verifier is fixed.

$\theta$	Method	EmitRate	UnsupEmit	Runs w/ any unsup.	SupportedRecall
0.05	PrivCert -PF	0.823	0.000	$0/150$	0.979
0.05	Aug-PE-style ( $N=1000$ )	0.800	0.000	$0/5$	0.952
0.10	PrivCert -PF	0.695	0.001	$2/150$	0.938
0.10	Aug-PE-style ( $N=1000$ )	0.676	0.092	$4/5$	0.881

Appendix

Table 6: Matched Yelp comparison with a DP synthetic-data backend. UnsupportedEmit for synthetic data is evaluated against support in the original private corpus.

Dataset	UnsupportedEmit	NLI–Qwen Jaccard	In interval
TAB	0.0033	0.94	5/5
WildChat	0.0023	0.33	5/5
Yelp	0.0037	0.78	5/5

Appendix

Table 7: Robustness of PrivCert -PF to a Qwen3-8B support model. Qwen3-8B replaces the default NLI matcher as the operational support predicate. “In interval” reports finite-run consistency with the expectation interval of Theorem 4 .

Dataset	Method	NLI FalseEmit	Qwen FalseEmit
TAB	Document-level DP	0.894	0.470
TAB	PrivCert -PF	0.010	0.040
WildChat	Document-level DP	0.729	0.857
	InvisibleInk (Qwen)	0.619	0.929
	PrivCert -PF	0.014	0.241
Yelp	Document-level DP	0.803	0.239

Appendix

Table 8: Cross-evaluation of exactly recoverable frozen Table 1 outputs. Released claims are fixed and only the operational support evaluator changes from NLI to Qwen3-8B. Qwen FalseEmission is a descriptive diagnostic and carries no

\beta

-guarantee.

Dataset	Per-candidate EmitRate	Family-wise EmitRate
TAB	0.404	0.357
Yelp	0.749	0.565
WildChat	0.220	0.169

Appendix

Table 9: Coverage cost of whole-report control. The family-wise setting uses

\beta_{j}=\beta_{\mathrm{tot}}/m

with

\beta_{\mathrm{tot}}=0.05

Explore similar work

Privacy Cost as Equity Input: A Group Fairness Criterion for Differentially Private Machine Learning
Jul 18, 2026Rakshit NaiduFairness Audits Privacy-Utility Trade-Offs
Georgia Institute of Technology
Tight Auditing of Differential Privacy in MST and AIM
Apr 20, 2026Georgi Ganev, Meenatchi Sundaram Muthu Selva Annamalai, Bogdan KulynychStandard Differential-Privacy Privacy
1UCL · 2SAS · 3Lausanne University Hospital
Plausible Deniability Guarantees for Whistleblowers
Jul 15, 2026Leo Richter, Matt J. KusnerΔ)$-Differential Privacy Model Auditing
University College London · 2 ´Ecole Polytechnique de Montr´eal · 3Mila - Qu´ebec Artificial Intelligence Institute

Jul 18, 2026, cs.LGJ/K move · Enter open · S save

Privacy Cost as Equity Input: A Group Fairness Criterion for Differentially Private Machine Learning

Rakshit Naidu

Georgia Institute of Technology

Fairness Audits Privacy-Utility Trade-Offs Algorithmic Fairness Privacy Membership Inference Attacks

Open paper AskPDF arXiv

Differential privacy (DP) is increasingly deployed to limit membership inference risk in machine-learning systems. Prior work has shown that DP-SGD can widen accuracy disparities across demographic groups, but this framing treats fairness as a purely outcome-side concern. We argue that privacy cost, the information leakage borne by each group, is itself a form of harm, and adopt a compensatory-fairness framework in which a group that involuntarily bears greater privacy exposure is owed proportionally greater benefit from the system. From this principle we derive the \emph{Privacy-Cost Equity Ratio} (PCER), a group fairness metric defined as a group's positive prediction rate normalized by its per-group overfitting gap. By a standard membership inference bound, this overfitting gap upper-bounds each group's vulnerability to inference attacks, making PCER a conservative measure of benefit relative to exposure. PCER needs only per-group train and test accuracy (no shadow models), making it a practical post-hoc audit tool. We evaluate PCER alongside standard fairness metrics across six benchmark--attribute combinations spanning tabular and NLP domains, under DP-SGD at a range of privacy budgets, and validate the overfitting-gap proxy against a direct threshold membership-inference attack. The results reveal patterns that outcome-based metrics miss. On COMPAS, PCER uncovers a persistent double disadvantage: the protected group bears both greater privacy exposure and worse predictive outcomes, something demographic parity gap masks entirely. Sensitivity analysis shows very strong privacy guarantees collapse both groups' overfitting to a numerical floor, rendering exposure-based audits uninformative in that regime. Together, these findings show that fairness audits of privacy-preserving systems must account for who bears the cost of protection, not only who benefits from its outcomes.

Abstract

Explore similar work

Privacy Cost as Equity Input: A Group Fairness Criterion for Differentially Private Machine Learning

Tight Auditing of Differential Privacy in MST and AIM

Plausible Deniability Guarantees for Whistleblowers