In this work, we give a new technique for analyzing individualized privacy accounting via the following simple observation: if an algorithm is one-sided add-DP, then its subsampled variant satisfies two-sided DP. From this, we obtain several improved algorithms for private combinatorial optimization problems, including decomposable submodular maximization and set cover. Our error guarantees are asymptotically tight and our algorithm satisfies pure-DP while previously known algorithms (Gupta et al., 2010; Chaturvedi et al., 2021) are approximate-DP. We also show an application of our technique beyond combinatorial optimization by giving a pure-DP algorithm for the shifting heavy hitter problem in a stream; previously, only an approximate-DP algorithm was known (Kaplan et al., 2021; Cohen & Lyu, 2023).

The Privacy Sandbox Attribution Reporting API has been recently deployed by Google Chrome to support the basic advertising functionality of attribution reporting (aka conversion measurement) after deprecation of third-party cookies. The API implements a collection of privacy-enhancing guardrails including contribution bounding and noise injection. It also offers flexibility for the analyst to allocate the contribution budget. In this work, we present algorithms for optimizing the allocation of the contribution budget for summary reports from the Attribution Reporting API. We develop a synthetic data model that we find to accurately capture real-world conversion data, and extensively evaluate our method on two real-world datasets and two synthetic datasets. We show that optimizing the parameters that can be set by the analyst can significantly improve the utility achieved by querying the API while satisfying the same privacy bounds.

We study the problem of computing pairwise statistics, i.e., ones of the form $\binom{n}{2}^{-1} \sum_{i \ne j} f(x_i, x_j)$, where $x_i$ denotes the input to the $i$th user, with differential privacy (DP) in the local model. This formulation captures important metrics such as Kendall's $\tau$ coefficient, Area Under Curve, Gini's mean difference, Gini's entropy, etc. We give several novel and generic algorithms for the problem, leveraging techniques from DP algorithms for linear queries.

Fitzi, Garay, Maurer, and Ostrovsky (J. Cryptology 2005) showed that in the presence of a dishonest majority, no primitive of cardinality $$n - 1$$ is complete for realizing an arbitrary n-party functionality with guaranteed output delivery. In this work, we introduce a new 2-party primitive $$\mathcal {F}_{\textsf{SyX}}$$ (“synchronizable fair exchange”) and show that it is complete for realizing any n-party functionality with fairness in a setting where all parties are pairwise connected by instances of $$\mathcal {F}_{\textsf{SyX}}$$ . In the $$\mathcal {F}_{\textsf{SyX}}$$ -hybrid model, the two parties load $$\mathcal {F}_{\textsf{SyX}}$$ with some input, and following this, either party can trigger $$\mathcal {F}_{\textsf{SyX}}$$ with a “witness” at a later time to receive the output from $$\mathcal {F}_{\textsf{SyX}}$$ . Crucially the other party also receives output from $$\mathcal {F}_{\textsf{SyX}}$$ when $$\mathcal {F}_{\textsf{SyX}}$$ is triggered. The trigger witnesses allow us to synchronize the trigger phases of multiple instances of $$\mathcal {F}_{\textsf{SyX}}$$ , thereby aiding in the design of fair multiparty protocols. Additionally, a pair of parties may reuse a single a priori loaded instance of $$\mathcal {F}_{\textsf{SyX}}$$ in any number of multiparty protocols (involving different sets of parties). (The authors grant IACR a non-exclusive and irrevocable license to distribute the article under the https://creativecommons.org/licenses/by-nc/3.0/ ), (This work was done in part while all the authors were at MIT).

We give a simple, computationally efficient, and node-differentially-private algorithm for estimating the parameter of an Erdos-Renyi graph---that is, estimating p in a G(n,p)---with near-optimal accuracy. Our algorithm nearly matches the information-theoretically optimal exponential-time algorithm for the same problem due to Borgs et al. (FOCS 2018). More generally, we give an optimal, computationally efficient, private algorithm for estimating the edge-density of any graph whose degree distribution is concentrated in a small interval.

We introduce a model for differentially private analysis of weighted graphs in which the graph topology (υ,ε) is assumed to be public and the private information consists only of the edge weights ω : ε → R+. This can express hiding congestion patterns in a known system of roads. Differential privacy requires that the output of an algorithm provides little advantage, measured by privacy parameters ε and δ, for distinguishing between neighboring inputs, which are thought of as inputs that differ on the contribution of one individual. In our model, two weight functions w,w' are considered to be neighboring if they have l1 distance at most one.