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ε, a system for privacy-preserving estimation of multiple quantiles in a distributed setting without relying on a trusted server. Piquantε operates under the malicious threat model and achieves accuracy of the central DP model. Built on the two-server model, Piquantε uses a novel strategy of releasing carefully chosen intermediate statistics, reducing MPC complexity while preserving end-to-end DP. Empirically, Piquantε estimates 5 quantiles on 1 million records in under a minute with domain size 10⁹, achieving up to 10⁴-fold higher accuracy than LDP, and up to ∼ 10× faster runtime compared to baselines.