Robust, Lightweight Locally Differentially Private Histogram Estimation and the Role of Dropout Attacks

Local differential privacy (LDP) is vulnerable to output manipulation by malicious clients. Zero-knowledge proofs can enforce correct report computation, but clients may still selectively drop out after inspecting their outputs. Prior work combines zero-knowledge proofs with homomorphic encryption to hide reports from clients and prevent selective dropout, but incurs substantial computational cost. We instead develop a three-message lightweight verification framework for robust histogram estimation that uses proofs of plaintext evaluation to restrict output manipulation to selective dropout. Across the evaluated settings for PI-RAPPOR and Hadamard Response, mean per-client online latency remains below 500 milliseconds. We further establish tight error bounds showing that, for RAPPOR, PI-RAPPOR, and Hadamard Response, restricting malicious clients to selective dropout reduces attack-dependent error by a factor proportional to the square root of the domain size compared with output manipulation. Additionally, when client protocols cannot be modified, we propose server-side consistency checks for RAPPOR and Hadamard Response. These checks improve robustness without client-side cryptography and can be applied post-hoc to collected reports, offering an alternative under different deployment constraints. Experiments demonstrate that both verification and consistency checks substantially reduce attack error for certain mechanisms, with consistency checks yielding errors intermediate between those obtained with verification and those under unrestricted output manipulation.

Authors

Publication Details

Journal
arXiv (Cornell University)
Published
2026-11-18
DOI
https://doi.org/10.48550/arxiv.2611.24623
Primary Topic
Privacy-Preserving Technologies in Data
Type
preprint
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
preprint

Robust, Lightweight Locally Differentially Private Histogram Estimation and the Role of Dropout Attacks

Jacob Imola, Haochen Sun, Xi He
arXiv (Cornell University)
Privacy-Preserving Technologies in Data
preprint

Robust, Lightweight Locally Differentially Private Histogram Estimation and the Role of Dropout Attacks

Jacob Imola, Haochen Sun, Xi He
preprint en

Abstract

Local differential privacy (LDP) is vulnerable to output manipulation by malicious clients. Zero-knowledge proofs can enforce correct report computation, but clients may still selectively drop out after inspecting their outputs. Prior work combines zero-knowledge proofs with homomorphic encryption to hide reports from clients and prevent selective dropout, but incurs substantial computational cost. We instead develop a three-message lightweight verification framework for robust histogram estimation that uses proofs of plaintext evaluation to restrict output manipulation to selective dropout. Across the evaluated settings for PI-RAPPOR and Hadamard Response, mean per-client online latency remains below 500 milliseconds. We further establish tight error bounds showing that, for RAPPOR, PI-RAPPOR, and Hadamard Response, restricting malicious clients to selective dropout reduces attack-dependent error by a factor proportional to the square root of the domain size compared with output manipulation. Additionally, when client protocols cannot be modified, we propose server-side consistency checks for RAPPOR and Hadamard Response. These checks improve robustness without client-side cryptography and can be applied post-hoc to collected reports, offering an alternative under different deployment constraints. Experiments demonstrate that both verification and consistency checks substantially reduce attack error for certain mechanisms, with consistency checks yielding errors intermediate between those obtained with verification and those under unrestricted output manipulation.

arXiv (Cornell University)
Privacy-Preserving Technologies in Data
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon