Search for: All records

ABSTRACT Many deployments of differential privacy in industry are in the local model, where each party releases its private information via a differentially private randomizer. We study triangle counting in the non‐interactive and interactive local model with edge differential privacy (that, intuitively, requires that the outputs of the algorithm on graphs that differ in one edge be indistinguishable). In this model, each party's local view consists of the adjacency list of one vertex. In the non‐interactive model, we prove that additive error is necessary for sufficiently small constant , where is the number of nodes and is the privacy parameter. This lower bound is our main technical contribution. It uses a reconstruction attack with a new class of linear queries and a novel mix‐and‐match strategy of running the local randomizers with different completions of their adjacency lists. It matches the additive error of the algorithm based on Randomized Response, proposed by Imola, Murakami, and Chaudhuri (USENIX2021) and analyzed by Imola, Murakami, and Chaudhuri (CCS2022) for constant . We use different postprocessing techniques for the Randomized Response and provide tight bounds on the variance of the resulting algorithm. In the interactive setting, we prove a lower bound of on the additive error for . Previously, no hardness results were known for interactive, edge‐private algorithms in the local model, except for those that follow trivially from the results for the central model. Our work significantly improves on the state of the art in differentially private graph analysis in the local model. 

We design the first node-differentially private algorithm for approximating the number of connected components in a graph. Given a database representing an\( n \)-vertex graph\( G \)and a privacy parameter\(\varepsilon\), our algorithm runs in polynomial time and, with probability\(1-o(1)\), has additive error\(\widetilde{O}(\frac{\Delta^{*}\ln\ln n}{\varepsilon}),\)where\(\Delta^{*}\)is the smallest possible maximum degree of a spanning forest of\(G.\)Node-differentially private algorithms are known only for a small number of database analysis tasks. A major obstacle for designing such an algorithm for the number of connected components is that this graph statistic is not robust to adding one node with arbitrary connections (a change that node-differential privacy is designed to hide):everygraph is a neighbor of a connected graph. We overcome this by designing a family of efficiently computable Lipschitz extensions of the number of connected components or, equivalently, the size of a spanning forest. The construction of the extensions, which is at the core of our algorithm, is based on the forest polytope of\(G.\)We prove several combinatorial facts about spanning forests, in particular, that a graph with no induced\(\Delta\)-stars has a spanning forest of degree at most\(\Delta\). With this fact, we show that our Lipschitz extensions for the number of connected components equal the true value of the function for the largest possible monotone families of graphs. More generally, on all monotone sets of graphs, the\(\ell_{\infty}\)error of our Lipschitz extensions is nearly optimal.