More Like this

1. Differential Privacy with Multiple Selections

   Goel, Ashish; Jiang, Zhihao; Korolova, Aleksandra; Munagala, Kamesh; Sarmasarkar, Sahasrajit (July 2024, Foundations of Responsible Computing (FORC 2025))

   We consider the setting where a user with sensitive features wishes to obtain a recommendation from a server in a differentially private fashion. We propose a ``multi-selection'' architecture where the server can send back multiple recommendations and the user chooses one from these that matches best with their private features. When the user feature is one-dimensional -- on an infinite line -- and the accuracy measure is defined w.r.t some increasing function 𝔥(.) of the distance on the line, we precisely characterize the optimal mechanism that satisfies differential privacy. The specification of the optimal mechanism includes both the distribution of the noise that the user adds to its private value, and the algorithm used by the server to determine the set of results to send back as a response and further show that Laplace is an optimal noise distribution. We further show that this optimal mechanism results in an error that is inversely proportional to the number of results returned when the function 𝔥(.) is the identity function. 

   more » « less
2. Weakly Private Information Retrieval from Heterogeneously Trusted Servers

   https://doi.org/10.1109/ISIT57864.2024.10619321  

   Huang, Yu-Shin; Zhao, Wenyuan; Zhou, Ruida; Tian, Chao (July 2024, IEEE)

   We study the problem of weakly private information retrieval (PIR) when there is heterogeneity in servers’ trustfulness under the maximal leakage (Max-L) metric. A user wishes to retrieve a desired message from N non-colluding servers efficiently, such that the identity of the desired message is not leaked in a significant manner; however, some servers can be more trustworthy than others. We propose a code construction for this setting and optimize the probability distribution for this construction. It is shown that the optimal probability allocation for the proposed scheme essentially separates the delivery patterns into two parts: a completely private part that has the same download overhead as the capacity-achieving PIR code, and a non-private part that allows complete privacy leakage but has no download overhead by downloading only from the most trustful server. The optimal solution is established through a sophisticated analysis of the underlying convex optimization problem, and a reduction between the homogeneous setting and the heterogeneous setting. 

   more » « less
3. Communication-Efficient Hierarchical Secure Aggregation with Cyclic User Association

   https://doi.org/10.1109/ISIT63088.2025.11195652  

   Zhang, Xiang; Li, Zhou; Wan, Kai; Sun, Hua; Ji, Mingyue; Caire, Giuseppe (June 2025, IEEE)

   Secure aggregation is motivated by federated learning (FL) where a cloud server aims to compute an averaged model (i.e., weights of deep neural networks) from the locally-trained models of numerous clients, while adhering to data security requirements. Hierarchical secure aggregation (HSA) studies secure aggregation of user inputs (an abstraction of the local models) in a three-layer network with clustered users connected to the server through an intermediate layer of relays. In HSA, in addition to the conventional server security, relay security is also imposed so that the relays remain oblivious to the inputs. However, existing studies on HSA have assumed that each user is associated with only one relay, which prevents coding opportunities across inter-cluster users to achieve efficient communication and key generation. In this paper, we consider HSA with a commonly used cyclic association pattern where each user is connected to B relays in a cyclic manner. We aim to determine the best communication and security key rates in such a multi-association network. We show that when B≤K−1 (K is the total number of users), to securely compute one symbol of the desired sum of inputs, each user needs to send at least R∗X=1 symbol to the associated relays, each relay needs to send at least R∗Y=1/B symbols to the server, each user needs to hold at least R∗Z=1/B secret key symbols, and all users need to collectively hold at least R∗ZΣ=max{1,K/B−1} independent key symbols. This reveals a fundamental trade-off between the association number B and the communication and key rates. When B=K, we present a scheme that achieves the optimal communication and source key rates, along with a nearoptimal individual key rate. 

   more » « less
4. Private Vector Mean Estimation in the Shuffle Model: Optimal Rates Require Many Messages

   Asi, Hilal; Feldman, Vitaly; Nelson, Jelani; Nguyen, Huy L; Talwar, Kunal; Zhou, Samson (July 2024, Proceedings of Machine Learning Research)

   We study the problem of private vector mean estimation in the shuffle model of privacy where n users each have a unit vector v^{(i)} in R^d. We propose a new multi-message protocol that achieves the optimal error using O~(min(n*epsilon^2, d)) messages per user. Moreover, we show that any (unbiased) protocol that achieves optimal error requires each user to send Omega(min(n*epsilon^2,d)/log(n)) messages, demonstrating the optimality of our message complexity up to logarithmic factors. Additionally, we study the single-message setting and design a protocol that achieves mean squared error O(dn^{d/(d+2)} * epsilon^{-4/(d+2)}). Moreover, we show that any single-message protocol must incur mean squared error Omega(dn^{d/(d+2)}), showing that our protocol is optimal in the standard setting where epsilon = Theta(1). Finally, we study robustness to malicious users and show that malicious users can incur large additive error with a single shuffler. 

   more » « less
5. Debiasing Functions of Private Statistics in Postprocessing

   https://doi.org/10.4230/LIPIcs.FORC.2025.17  

   Calmon, Flavio; Du, Elbert; Dwork, Cynthia; Finley, Brian; Franguridi, Grigory (January 2025, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

   Bun, Mark (Ed.)

   Given a differentially private unbiased estimate q̃ = q(D) +ν of a statistic q(D), we wish to obtain unbiased estimates of functions of q(D), such as 1/q(D), solely through post-processing of q̃, with no further access to the confidential dataset D. To this end, we adapt the deconvolution method used for unbiased estimation in the statistical literature, deriving unbiased estimators for a broad family of twice-differentiable functions - those that are tempered distributions - when the privacy-preserving noise ν is drawn from the Laplace distribution (Dwork et al., 2006). We further extend this technique to functions other than tempered distributions, deriving approximately optimal estimators that are unbiased for values in a user-specified interval (possibly extending to ± ∞). We use these results to derive an unbiased estimator for private means when the size n of the dataset is not publicly known. In a numerical application, we find that a mechanism that uses our estimator to return an unbiased sample size and mean outperforms a mechanism that instead uses the previously known unbiased privacy mechanism for such means (Kamath et al., 2023). We also apply our estimators to develop unbiased transformation mechanisms for per-record differential privacy, a privacy concept in which the privacy guarantee is a public function of a record’s value (Seeman et al., 2024). Our mechanisms provide stronger privacy guarantees than those in prior work (Finley et al., 2024) by using Laplace, rather than Gaussian, noise. Finally, using a different approach, we go beyond Laplace noise by deriving unbiased estimators for polynomials under the weak condition that the noise distribution has sufficiently many moments. 

   more » « less