Piquant$\varepsilon$: Private Quantile Estimation in the Two-Server Model

• URL: http://arxiv.org/abs/2509.14035v1
• Date: Wed, 17 Sep 2025 14:34:40 GMT
• Title: Piquant$\varepsilon$: Private Quantile Estimation in the Two-Server Model
• Authors: Hannah Keller, Jacob Imola, Fabrizio Boninsegna, Rasmus Pagh, Amrita Roy Chowdhury,
• Abstract summary: We present Piquant$varepsilon$, a system for privacy-preserving estimation of multiple quantiles in a distributed setting without relying on a trusted server.<n>Built on the two-server model, Piquant$varepsilon$ uses a novel strategy of releasing carefully chosen intermediate statistics, reducing MPC complexity while preserving end-to-end DP.
• Score: 13.87825190149209
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Quantiles are key in distributed analytics, but computing them over sensitive data risks privacy. Local differential privacy (LDP) offers strong protection but lower accuracy than central DP, which assumes a trusted aggregator. Secure multi-party computation (MPC) can bridge this gap, but generic MPC solutions face scalability challenges due to large domains, complex secure operations, and multi-round interactions. We present Piquant$\varepsilon$, a system for privacy-preserving estimation of multiple quantiles in a distributed setting without relying on a trusted server. Piquant$\varepsilon$ operates under the malicious threat model and achieves accuracy of the central DP model. Built on the two-server model, Piquant$\varepsilon$ uses a novel strategy of releasing carefully chosen intermediate statistics, reducing MPC complexity while preserving end-to-end DP. Empirically, Piquant$\varepsilon$ estimates 5 quantiles on 1 million records in under a minute with domain size $10^9$, achieving up to $10^4$-fold higher accuracy than LDP, and up to $\sim 10\times$ faster runtime compared to baselines.

Related papers

• DP-CSGP: Differentially Private Stochastic Gradient Push with Compressed Communication [71.60998478544028]
  We propose Differentially Private Gradient Push with Compressed communication (termedfrac-CSGP) for decentralized learning graphs.<n>For general non-math and smooth objective functions, we show that our algorithm is designed to maintain high accuracy and efficient communication.
  arXiv  Detail & Related papers  (2025-12-15T17:37:02Z)
• Perfectly-Private Analog Secure Aggregation in Federated Learning [51.61616734974475]
  In federated learning, multiple parties train models locally and share their parameters with a central server, which aggregates them to update a global model.<n>In this paper, a novel secure parameter aggregation method is proposed that employs the torus rather than a finite field.
  arXiv  Detail & Related papers  (2025-09-10T15:22:40Z)
• Lightweight Protocols for Distributed Private Quantile Estimation [12.586899971090277]
  We consider two emphadaptive algorithms for estimating one quantile when each user holds a single data point lying in a domain $[B]$.<n>In the adaptive setting we present an $varepsilon$-LDP algorithm which can estimate any quantile within error $alpha$ only requiring $O(fraclog Bvarepsilon2alpha2)$ users.
  arXiv  Detail & Related papers  (2025-02-05T08:39:02Z)
• Correlated Privacy Mechanisms for Differentially Private Distributed Mean Estimation [8.660393575612169]
  Local differential privacy (LDP) and distributed DP with secure aggregation (SA) are the most common notions of DP used in DP-DME settings with an untrusted server.<n>LDP provides strong resilience to dropouts, colluding users, and adversarial attacks, but suffers from poor utility.<n>In this work, we present a generalized framework for DP-DME, that captures LDP and SA-based mechanisms as extreme cases.
  arXiv  Detail & Related papers  (2024-07-03T17:22:33Z)
• Private Mean Estimation with Person-Level Differential Privacy [6.621676316292624]
  We study person-level differentially private mean estimation in the case where each person holds multiple samples. We give computationally efficient algorithms under approximate-DP and computationally inefficient algorithms under pure DP, and our nearly matching lower bounds hold for the most permissive case of approximate DP.
  arXiv  Detail & Related papers  (2024-05-30T18:20:35Z)
• Private Fine-tuning of Large Language Models with Zeroth-order Optimization [51.19403058739522]
  Differentially private gradient descent (DP-SGD) allows models to be trained in a privacy-preserving manner.<n>We introduce DP-ZO, a private fine-tuning framework for large language models by privatizing zeroth order optimization methods.
  arXiv  Detail & Related papers  (2024-01-09T03:53:59Z)
• Analyzing Privacy Leakage in Machine Learning via Multiple Hypothesis Testing: A Lesson From Fano [83.5933307263932]
  We study data reconstruction attacks for discrete data and analyze it under the framework of hypothesis testing. We show that if the underlying private data takes values from a set of size $M$, then the target privacy parameter $epsilon$ can be $O(log M)$ before the adversary gains significant inferential power.
  arXiv  Detail & Related papers  (2022-10-24T23:50:12Z)
• TAN Without a Burn: Scaling Laws of DP-SGD [70.7364032297978]
  Differentially Private methods for training Deep Neural Networks (DNNs) have progressed recently. We decouple privacy analysis and experimental behavior of noisy training to explore the trade-off with minimal computational requirements. We apply the proposed method on CIFAR-10 and ImageNet and, in particular, strongly improve the state-of-the-art on ImageNet with a +9 points gain in top-1 accuracy.
  arXiv  Detail & Related papers  (2022-10-07T08:44:35Z)
• Distributed Differential Privacy in Multi-Armed Bandits [9.51828574518325]
  We consider the standard $K$-armed bandit problem under a distributed trust model of differential privacy (DP) We aim to obtain a pure-DP guarantee under distributed trust model while sacrificing no more regret than that under central trust model.
  arXiv  Detail & Related papers  (2022-06-12T15:37:36Z)
• Large Scale Transfer Learning for Differentially Private Image Classification [51.10365553035979]
  Differential Privacy (DP) provides a formal framework for training machine learning models with individual example level privacy. Private training using DP-SGD protects against leakage by injecting noise into individual example gradients. While this result is quite appealing, the computational cost of training large-scale models with DP-SGD is substantially higher than non-private training.
  arXiv  Detail & Related papers  (2022-05-06T01:22:20Z)
• The Fundamental Price of Secure Aggregation in Differentially Private Federated Learning [34.630300910399036]
  We characterize the fundamental communication cost required to obtain the best accuracy under $varepsilon$ central DP. Our results show that $tildeOleft( min(n2varepsilon2, d) right)$ bits per client are both sufficient and necessary. This provides a significant improvement relative to state-of-the-art SecAgg distributed DP schemes.
  arXiv  Detail & Related papers  (2022-03-07T22:56:09Z)
• Frequency Estimation Under Multiparty Differential Privacy: One-shot and Streaming [10.952006057356714]
  We study the fundamental problem of frequency estimation under both privacy and communication constraints, where the data is distributed among $k$ parties. We adopt the model of multiparty differential privacy (MDP), which is more general than local differential privacy (LDP) and (centralized) differential privacy. Our protocols achieve optimality (up to logarithmic factors) permissible by the more stringent of the two constraints.
  arXiv  Detail & Related papers  (2021-04-05T08:15:20Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.