Propose-Filter-Release: Scaling Noise to Typical Sensitivity via Private Filtering

Moshe Shenfeld; Eliad Tsfadia; Katrina Ligett

cs.LGOct 29, 2026

Propose-Filter-Release: Scaling Noise to Typical Sensitivity via Private Filtering

Authors: Moshe Shenfeld, Eliad Tsfadia, Katrina Ligett

Organizations: School of Computer Science and Engineering, The Hebrew University of Jerusalem. · Department of Computer Science and Artificial Intelligence, Bar-Ilan University.

Abstract

An estimator can be accurate and stable on typical data, yet sensitive to a few possible records. Differentially private mechanisms commonly scale their noise to the worst-case influence of a single record, which lets these records dictate the noise even when the remaining data would allow far less. Removing them first would restore the smaller scale, but the removal must itself be private. We introduce propose-filter-release (PFR), which, by privately filtering its input, turns a mechanism that protects the addition or removal of a typical record, one that fits the remaining data, into one that is differentially private in the standard sense, on every input. Using our novel filtering step, PFR requires only a concave friendliness score, which measures how well a record fits a dataset, and a release mechanism that is friendly-DP, that is, private when the changed record fits the remaining data. For every such score and release mechanism, it guarantees differential privacy under public conditions on the number of records, so it is a general privacy primitive, comparable to propose-test-release, and FriendlyCore can be viewed as one of its implementations. We illustrate the generality of PFR by instantiating it for scalar statistics, principal subspace estimation, the KL divergence of user histograms, the effective resistances of a graph, and treatment-rule selection.

Figures & tables

Panel of Figure 1 — Figure 1: Propose-filter-release. (a) The general scheme, whose guarantee is the PFR theorem ( Theorem 4.4 ): the application specifies the release mechanism $M$ and a condition between the changed record and the remaining data under which $M$ is private. The filtering step is jointly differentially private (JDP), that is, its outputs on two neighboring inputs are indistinguishable once the changed slot is nulled in both, and it establishes the condition of the release mechanism, with high probability, for each changed record. The complete mechanism, whose only output is the answer of the release mechanism, is then differentially private on every input. (b) Element–block filtering, the filtering step of this paper, whose condition is that the changed record is friendly with the remaining filtered data; other filtering steps that meet the same interface, such as that of FriendlyCore, can take its place in (a). It fills a matrix of tests, one for every record and every reference block of a random partition, each asking whether the score of the record against the block is at least $2\tau$ , twice the threshold of the release mechanism. The friend count $c_{i}$ of a record, its number of friendly blocks, plus noise, is compared with a fixed threshold $t$ , and the records that fail are nulled. The colored square next to a record marks the block that contains it.

Figure 2: In this example, comparing a record with blocks of records captures structure that a distance test between single records misses. The data are 100 samples from an anisotropic Gaussian distribution, the probes A and B are not records, and the test noise is omitted. (a) Compared with the records one by one, and friendly with those within a fixed distance, A, which lies along the data, has few friends, and B, which lies off the data near the origin, has many. (b) An ellipse with the shape of the second moment of one block of records, long along the directions in which the block varies and short across them, contains A but not B. (c) Tests against several blocks separate the outliers C1–C3 from the data.

Symbol	Meaning
$n$	number of slots of a dataset, null records included
$b$	block size: the filter splits the dataset into reference blocks of $b$ records, where $b$ divides $n$
$m$	number of reference blocks, $m\coloneqq n/b$
$t$	acceptance threshold: the filter retains a record if the number of blocks that are friendly with it, plus Laplace noise, exceeds $t$
${\tilde{K}}$	noisy cap: the filter aborts once it has rejected ${\tilde{K}}=\lceil 2{\sigma_{1}}L+\operatorname{Lap}({\sigma_{1}})\rceil$ records
${\sigma_{m}}$ , ${\sigma_{1}}$	scales of these two Laplace noises: ${\sigma_{m}}$ for the noise that is added to the number of friendly blocks, which is at most $m$ , and ${\sigma_{1}}$ for the noise that is added to the cap

Table 1: Recurring notation. The filter is defined in Section 3.2 and friendliness scores in Section 4.1 .

Figure 4

Appendix figures & tables2 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 3: The target

{g_{\mathrm{KL}}}

on three users with

T=6

observations over

d=4

categories. (a) The counts of the users, and their average counts

{\bar{H}}_{j}

; no user has an observation in the fourth category. (b) The smoothed pooled frequencies

{\hat{p}}_{j}

for the pseudocount

\lambda=1

, of which the hatched part comes from the pseudocount, against the uniform reference

1/d

. The divergence

D_{\mathrm{KL}}(u\|{\hat{p}})\approx 0.12

is computed from the formula for data without null records.

Figure 4: Effective resistance and leverage on two cliques of five vertices joined by a bridge, with unit weights. (a) Each clique edge has leverage

0.4

, since its endpoints are also joined by many parallel paths, while the bridge has leverage

1

and its removal disconnects the graph; a graph with a bridge is therefore outside the low-leverage regime of the utility guarantee. (b) One draw of the Gaussian potentials: vertices joined by many parallel paths receive similar potentials, and the expected squared difference of two potentials is the resistance between their vertices, which is

0.4

within a clique and

1.8

between two vertices of different cliques that are not endpoints of the bridge.

Differential Privacy

Differential privacy limits how much an algorithm’s outputs can reveal about any one person’s data, with formal guarantees.

See all 280 papers

ScoreShield: Differentially Private Release of Similarity Scores
Jul 27, 2026Behrooz Razeghi, Parsa RahimiPrivacy-Preserving ML Differential Privacy
School of Engineering and Applied Sciences, Harvard University · School of Engineering, École Polytechnique Fédérale de Lausanne (EPFL)
Limits of Personalizing Differential Privacy Budgets
May 13, 2026Edwige Cyffers, Juba ZianiDifferential Privacy Personalized Differential Privacy
CNRS, LAMSADE, Dauphine-PSL · Georgia Institute of Technology.
Enhancing Differentially Private Mechanisms via Empirical Bayes
Jun 19, 2026Minwoo Kim, Junyong Park, Sungkyu JungEmpirical Bayes Differential Privacy
Department of Statistics Seoul National University Seoul, 08826, South Korea · Department of Statistics and Institute for Data Innovation in Science Seoul National University Seoul, 08826, South Korea

Jul 27, 2026J/K move · Enter open · S save

ScoreShield: Differentially Private Release of Similarity Scores

Behrooz Razeghi, Parsa Rahimi

School of Engineering and Applied Sciences, Harvard University · School of Engineering, École Polytechnique Fédérale de Lausanne (EPFL)

Privacy-Preserving ML Differential Privacy

Open paper AskPDF arXiv

A growing number of applications, such as biometrics and retrieval-augmented generation (RAG), rely on cosine similarity scores computed between vector embeddings of text, images, or audio. These systems return similarity scores through their APIs for ranking and verification. However, such releases can leak information about individual records and enable membership inference attacks. While differential privacy (DP) provides a principled metric for quantifying attack risks, naïve application of DP mechanisms---such as adding i.i.d. Gaussian noise to vector entries---leads to excessive distortion (i.e., low utility) at a given privacy constraint that scales poorly with the number of released scores. We propose ScoreShield, a perturb-then-project mechanism that adds Gaussian noise calibrated to global sensitivity of the chosen score release regime and then projects the result onto the feasibility set of valid cosine objects. ScoreShield satisfies

(\varepsilon,δ)

-DP for releasing similarity score vectors and Gram matrices. We provide utility guarantees for the exact Frobenius metric projection used in the risk analysis, and prove convergence to feasibility for the practical averaged alternating-projection solver used for large-scale Gram releases. For full pairwise cosine Gram release under record-level replacement adjacency, the exact-projection bound improves the

n

-dependence of squared Frobenius risk from

Θ(n^3)

for the naïve Gaussian baseline to

\mathcal{O}(n^2)

for fixed privacy parameters, with sharper local bounds at low-rank Grams. We evaluate the mechanism across RAG, face recognition, semantic retrieval, image similarity, and recommender-system tasks.

Abstract

Differential Privacy

Explore similar work

ScoreShield: Differentially Private Release of Similarity Scores

Limits of Personalizing Differential Privacy Budgets

Enhancing Differentially Private Mechanisms via Empirical Bayes