Local Pan-privacy for Federated Analytics
Authors: Vitaly Feldman, Audra Mcmillan, Guy N. Rothblum, Kunal Talwar
ICML 2025 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We show that local pan-privacy is severely limited if we insist on providing (information-theoretic) differential privacy in the face of intrusions. Our lower bound shows that for the COUNTNONZERO task, the error of any algorithm must be T times larger than that needed for local differential privacy alone. This lower bound holds even when the event occurs at most once on each device. Theorem 1 (Informal version of Theorem 9)... We then show that under standard cryptographic assumptions, local pan-privacy can be ensured without this overhead. We present algorithms for all of the aforementioned problems... Theorem 2 (Informal version of Theorem 10)... Theorem 3 (Informal version of Theorem 6.1). Suppose that we have a locally pan-private algorithm for COUNTNONZERO that has additive error less than n/4 with high probability. Then we can build a public key encryption scheme. |
| Researcher Affiliation | Industry | 1Apple, Cupertino, CA, USA. Correspondence to: Kunal Talwar <EMAIL>. |
| Pseudocode | Yes | Algorithm 1 f D Algorithm 2 h Algorithm 3 COUNTNONZERO, Client Algorithm Algorithm 4 Averaging, Client Algorithm Algorithm 5 Counter, Client Algorithm Algorithm 6 COUNTNONZERO, Client Algorithm, Two-server model |
| Open Source Code | No | The paper does not contain any explicit statements or links indicating that open-source code for the described methodology is provided. |
| Open Datasets | No | The paper is theoretical and does not describe experiments that utilize specific datasets. Therefore, no information about open datasets is provided. |
| Dataset Splits | No | The paper does not describe experiments or the use of datasets, and therefore does not provide any information about dataset splits. |
| Hardware Specification | No | The paper is theoretical and does not describe any experimental setup or specific hardware used for running experiments. |
| Software Dependencies | No | The paper is theoretical and focuses on algorithm design and proofs, without detailing any software dependencies with version numbers for practical implementation or experimentation. |
| Experiment Setup | No | The paper is theoretical, presenting algorithms and proofs without conducting empirical experiments. Therefore, no specific experimental setup details, hyperparameters, or training configurations are provided. |