Verifying Differentially Private Median Estimation

Hyukjun Kwon, Chenglin Fan · 2025

Read Verifying Differentially Private Median Estimation by Hyukjun Kwon, Chenglin Fan (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-16246.txt.

Introduction

Data teams can promise privacy, but users must trust that the noise hiding their data was added honestly. Hyukjun Kwon and Chenglin Fan tackle that trust gap in their 2025 paper on the median, the middle value of a data set. They build the first checkable version of the exponential mechanism, a standard tool for private answers.

Their method turns the mechanism and a median score rule into an arithmetic circuit that a zk-SNARK proof can verify. A scaled inverse distribution trick handles the random draw inside the circuit. The result lets anyone confirm that a reported private median came from the stated method, with no peeking at the raw data. Privacy and proof of honest work, the authors argue, can travel together, which matters when the analyst is not trusted.

Catalog record

CREATORHyukjun Kwon, Chenglin Fan
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE50 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2505-16246

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Verifying Differentially Private Median Estimation Hyukjun Kwon, Chenglin Fan Abstract Differential Privacy (DP) is a robust privacy guarantee that is widely employed in private data analysis today, finding broad application in domains such as statistical query release and machine learning. However, DP achieves privacy by introducing noise into data or query answers, which malicious actors could exploit during analysis. To address this concern, we propose the first verifiable differentially private median estimation scheme based on zk-SNARKs. Our scheme combines the exponential mechanism and a utility function for median estimation into an arithmetic circuit, leveraging a scaled version of the inverse cumulative distribution function (CDF) method for precise sampling from the distribution derived from the utility function. This approach not only ensures privacy but also provides a mechanism to verify that the algorithm achieves DP guarantees without revealing sensitive information in the process. 1 Introduction Modern digital services collect personal fine-grained information more than ever—from our GPS location status and health data to shopping and public transportation usage history. These kinds of information collections help tailor convenient services to our needs, such as personalized healthcare and automatic product recommendations at online store. However, they often work in exchange for our privacy Zang and Bolot 2011 . Our personal information remains at risk while we use modern, convenience-driven services. Companies have attempted to protect privacy by anonymizing user data before analysis. However, even anonymized datasets can reveal personal information. For instance, in the 2006 Netflix Prize competition, Netflix released a dataset of 100 million movie ratings from 500,000 anonymized users. Narayanan and Shmatikov 2008 showed that such anonymization was insufficient: using statistical de-anonymization techniques, they re-identified users based on approximate knowledge of a few ratings and timestamps. To counter such vulnerabilities, the framework of Differential Privacy (DP) was introduced ( Dwork et al. 2006b ; Dwork and Roth 2014 ) . DP provides formal privacy guarantees by adding carefully calibrated random noise to data or query outputs, ensuring that the inclusion or exclusion of a single individual’s data has only a limited effect on the overall result. This protects against a wide range of inference attacks and has been adopted in various domains, including optimization ( Gupta et al. 2010 ) , reinforcement learning ( Vietri et al. 2020 ) , and deep learning ( Abadi et al. 2016 ) . However, DP introduces a new challenge: since the output is intentionally randomized, it becomes difficult to determine whether a privacy-preserving computation was executed correctly. A malicious party could distort outputs and attribute discrepancies to DP noise, undermining trust in the system. This opens up an integrity gap—while DP protects privacy, it does not inherently guarantee correctness or transparency of the computation. To bridge this gap, researchers have explored the concept of Verifiable Differential Privacy , which enables third parties to verify whether a computation satisfies DP without compromising privacy. These methods often leverage cryptographic tools such as zero-knowledge proofs (ZKPs) ( Goldwasser et al. 1985 ) , particularly zk-SNARKs ( Bitansky et al. 2012 ) (Zero-Knowledge Succinct Non-Interactive Arguments of Knowledge), to prove compliance with DP guarantees without revealing sensitive information. ZKP is a cryptographic method in which one party (the Prover) can prove to another party (the Verifier) that they know a piece of information or that a statement is true without revealing any information about the piece of information itself. Additionally, Local Differential Privacy (LDP) ( Kasiviswanathan et al. 2011 ; Evfimievski et al. 2003 ) offers an alternative model where users perturb their data locally before sharing it, eliminating the need for a trusted data curator. While LDP inherently provides stronger individual privacy, it often comes at the cost of degraded utility. Verifiability in LDP has also been explored by combining local randomizers with cryptographic proofs, enabling users to prove that they applied a valid LDP mechanism ( Kato et al. 2021 ; Garrido et al. 2022 ; Bontekoe et al. 2024 ) . These verifiable LDP schemes are naturally suited to categorical queries via randomized response ( Warner 1965 ; Ambainis et al. 2003 ) , but they incur substantial computational overheads and often remain impractical for large-scale deployment. In summary, while verifiable LDP protocols support categorical queries, their high computational cost and limited utility reduce practical applicability. On the other hand, in the central DP setting, verifiability has largely been limited to numerical queries (e.g., via the Laplace mechanism), and no general verifiable mechanism has been proposed for categorical queries that require the exponential mechanism. This work aims to close that gap by designing a verifiable exponential mechanism for categorical data in the central DP setting, combining cryptographic soundness with practical efficiency. Our Contributions. We extend verifiable differential privacy in the central setting to categorical queries by introducing the first verifiable Exponential Mechanism (EM) for median estimation using zk-SNARKs. Our contributions are as follows: 1. Circuit Design for Verifiable Exponential Mechanism: We construct an arithmetic circuit for the exponential mechanism tailored to median estimation. Our design includes modular subcircuits that collectively implement a scaled inverse CDF sampling algorithm over the distribution defined by the utility function and EM. 2. Public Verifiability: We integrate zk-SNARKs with the Poseidon hash function to enable any public or private Verifier to efficiently confirm that the reported median was sampled correctly, without malicious tampering. 3. Fully Non-Interactive Protocol: We ensure non-interactivity by leveraging a public bulletin board and non-interactive randomness supplied by the Verifier, removing the need for any online interaction between Prover and Verifier. 4. Formal Guarantees: We provide formal proofs establishing the security, differential privacy, and strong utility guarantees of our proposed scheme. 5. Practical Implementation: We implement our scheme using Groth16 zk-SNARKs and Poseidon hash function, and demonstrate its practicality by showing that, for datasets of size up to 7,000, proof generation completes within a few minutes and verification takes less than a second. 1.1 Related Works Differential Privacy (DP) was first introduced by Dwork et al. 2006b ; Dwork et al. 2006a as a robust framework for protecting individual privacy in statistical data analysis. To implement DP for numerical queries, they proposed the Laplace Mechanism Dwork et al. 2006b , which adds noise drawn from the Laplace distribution to query results. The magnitude of the noise is carefully calibrated to the sensitivity of the query to ensure a formal privacy guarantee while retaining utility. To address categorical queries, McSherry and Talwar 2007 proposed the Exponential Mechanism . Instead of perturbing the output directly, this mechanism introduces a utility function over possible outputs and samples a response from a distribution biased toward higher-utility outcomes. This enables privacy-preserving data analysis in scenarios where outputs are not numeric. Verifiable Differential Privacy (VDP) extends DP by enabling third parties to verify whether a computation satisfies differential privacy. This concept was first formalized by Narayan et al. 2015 , though their approach did not support categorical queries and lacked experimental validation. To provide cryptographic guarantees for DP enforcement, Biswas and Cormode 2023 proposed using zero-knowledge proofs (ZKPs), particularly zk-SNARKs, to verify differentially private computations. Their interactive protocol focuses on counting queries by combining binomial noise with homomorphic commitments. This allows privacy-preserving proofs of compliance without revealing any sensitive data. However, their method

Read the complete text