Verifiable Exponential Mechanism for Median Estimation
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866912522663100416 |
|---|---|
| author | Kwon, Hyukjun Fan, Chenglin |
| author_facet | Kwon, Hyukjun Fan, Chenglin |
| contents | Differential Privacy (DP) is a rigorous privacy standard widely adopted in data analysis and machine learning. However, its guarantees rely on correctly introducing randomized noise--an assumption that may not hold if the implementation is faulty or manipulated by an untrusted analyst. To address this concern, we propose the first verifiable implementation of the exponential mechanism using zk-SNARKs. As a concrete application, we present the first verifiable differentially private (DP) median estimation scheme, which leverages this construction to ensure both privacy and verifiability. Our method encodes the exponential mechanism and a utility function for the median into an arithmetic circuit, employing a scaled inverse CDF technique for sampling. This design enables cryptographic verification that the reported output adheres to the intended DP mechanism, ensuring both privacy and integrity without revealing sensitive data. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_16246 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Verifiable Exponential Mechanism for Median Estimation Kwon, Hyukjun Fan, Chenglin Cryptography and Security Differential Privacy (DP) is a rigorous privacy standard widely adopted in data analysis and machine learning. However, its guarantees rely on correctly introducing randomized noise--an assumption that may not hold if the implementation is faulty or manipulated by an untrusted analyst. To address this concern, we propose the first verifiable implementation of the exponential mechanism using zk-SNARKs. As a concrete application, we present the first verifiable differentially private (DP) median estimation scheme, which leverages this construction to ensure both privacy and verifiability. Our method encodes the exponential mechanism and a utility function for the median into an arithmetic circuit, employing a scaled inverse CDF technique for sampling. This design enables cryptographic verification that the reported output adheres to the intended DP mechanism, ensuring both privacy and integrity without revealing sensitive data. |
| title | Verifiable Exponential Mechanism for Median Estimation |
| topic | Cryptography and Security |
| url | https://arxiv.org/abs/2505.16246 |