betaFeedback

WorksComputer Science

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

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.

Introduction

Local differential privacy (LDP) enables clients to report sensitive data to an untrusted server by randomizing their inputs locally [12, 13, 15]. We study histogram estimation, where each client holds a categorical value and the server estimates category counts from randomized reports, a basic task in locally private data collection [31]. Malicious clients can bypass the prescribed randomizer and submit arbitrary reports, substantially distorting the estimated histogram [9, 11]. Verifiable LDP protocols address this threat by requiring clients to prove that their reports were generated according to the prescribed computation.

Correct report generation, however, does not ensure unbiased submission. Even when a protocol enforces correct randomization, a malicious client that can inspect its report may submit it only when the result is favorable. Otherwise, it can withhold the report or send an invalid proof that the server rejects. An adversary controlling multiple clients can coordinate these decisions to bias the aggregate.

All accepted reports may therefore be valid, while their distribution is altered by selective dropout. The proof certifies how a submitted report was computed, but not why the client chose to submit it.

The Verity protocol [5] prevents selection based on the realized report by hiding it from the client. It supports client-chosen inputs in a single server–client–server round trip. The server supplies encrypted randomness, and the client evaluates the mechanism homomorphically, returning an encrypted report with zero-knowledge proofs of the required cryptographic operations. The client cannot inspect the report before deciding whether to submit it. The computational cost is substantial, however: in the reported binary randomized response configuration, client and server computation each exceed 20 minutes. This raises our central question: Is eliminating selective dropout necessary to obtain meaningful robustness, or can a lightweight protocol retain a substantial benefit while allowing it?

The answer depends on the underlying LDP mechanism. If selective dropout and unrestricted output manipulation have the same asymptotic effect, restricting malicious clients to selective dropout does not improve the asymptotic error rate. Binary randomized response illustrates this difficulty, but does not settle the question for larger categorical domains. We show that RAPPOR [14], PI-RAPPOR [17], and Hadamard Response [1] exhibit an asymptotic separation: the attack-dependent term in the worst-case expected ℓ1\ell_1 error under selective dropout is a factor of k\sqrt{k} smaller than under output manipulation, where kk is the number of categories. In contrast, HST [4, 11] has the same asymptotic error rate under both attacks. Thus, verification can improve robustness for (PI-)RAPPOR and Hadamard Response even when selective dropout remains possible.

This separation motivates a lightweight verification framework that prevents output manipulation while allowing selective dropout. The client first commits to its input and randomness share. The server then supplies an independent randomness share, after which the client returns its report and a zero-knowledge proof of correct evaluation. The commitment fixes the client’s choices before the server’s share is revealed, preventing the client from repeatedly generating reports and selecting a favorable one. The resulting three-message, 1.5-round-trip protocol requires proofs of plaintext computation rather than homomorphic operations. Clients can still withhold their fixed reports, but our analysis quantifies the resulting error. We instantiate the framework for PI-RAPPOR and Hadamard Response using compact verification circuits.

When adding verification to the client is impractical, we pursue a complementary route: server-side consistency checks that reduce the effects of output manipulation without changing the client protocol. For RAPPOR, the check detects unusually large pairwise correlations between reports. For Hadamard Response, it clips unusually large counts in the report histogram. These checks can be applied post-hoc to collected reports. They require no client-side cryptography, though their error guarantees are weaker than those under selective dropout with verification.

Table 1 summarizes the error guarantees and aggregation costs. HST provides a useful contrast: its error rate under output manipulation matches the selective-dropout rate of the verified mechanisms asymptotically, while its explicit aggregation procedure takes O(nk)O(nk) time. Each HST client sends one bit and uses kk public random bits; explicitly distributing these vectors incurs O(k)O(k) downlink communication per client. The underlying PI-RAPPOR and Hadamard Response mechanisms have logarithmic-size reports and admit O(n+klog⁡k)O(n+k\log k) aggregation. Our verification protocols introduce additional cryptographic messages, whose full communication costs and contribution to modeled latency are evaluated in Section 7.

ProtocolOMSDCCAgg.
RAPPORmkmkmkm\sqrt{k}mk34(log⁡n)14mk^{\frac{3}{4}}(\log n)^{\frac{1}{4}}nknk
PI-RAPPORmkmkmkm\sqrt{k}−-n+klog⁡kn+k\log k
HRmkmkmkm\sqrt{k}km(n+klog⁡(nk))\sqrt{km(n+k\log(nk))}n+klog⁡kn+k\log k
HSTmkm\sqrt{k}mkm\sqrt{k}−-nknk

Table 1. Histogram estimation for 0<ε≤10<\varepsilon\le1. OM: output manipulation; SD: selective dropout; CC: consistency check; Agg.: baseline aggregation. HR denotes Hadamard Response. Error entries omit a common factor 1ε\frac{1}{\varepsilon} and the honest-sampling term O(knε)O\left(\frac{k\sqrt{n}}{\varepsilon}\right). OM and SD give tight rates; CC gives upper bounds under the assumptions of Section 6. Aggregation entries denote O(⋅)O(\cdot) costs, excluding verification and consistency checks. HST uses explicit public vectors.

We summarize our contributions as follows:

  • A lightweight verification framework and instantiations. We formalize a resampling vulnerability in one-round-trip protocols with client-visible reports: under suitable conditions, clients can repeatedly generate valid reports and submit a favorable one (§ 3.1). We give a three-message framework that fixes the client’s input and randomness before the server reveals its share, preventing resampling while allowing selective dropout. We instantiate the framework for PI-RAPPOR and Hadamard Response using proofs of plaintext evaluation (§ 4).

  • A mechanism-dependent separation between attacks. We establish tight error bounds under selective dropout for RAPPOR, PI-RAPPOR, Hadamard Response, and HST. For the first three mechanisms, the attack-dependent term in the worst-case expected ℓ1\ell_1 error is smaller by a factor of k\sqrt{k} than under output manipulation. HST exhibits no such asymptotic separation. These results identify when the restriction enforced by verification improves robustness (§ 5).

  • Robustness without cryptography. We develop post-hoc consistency checks for RAPPOR and Hadamard Response, with error bounds under output manipulation. The checks operate entirely at the server and require no changes to the client protocol (§ 6).

  • Empirical robustness and efficient verification. Our experiments illustrate the mechanism-dependent separation between attacks and evaluate the consistency checks. Our PI-RAPPOR and Hadamard Response implementations achieve mean modeled per-client online latency below 0.5 seconds across the evaluated settings, combining computation measured on server hardware with modeled network transmission. Additionally, in our experiments at ε=1\varepsilon=1 with 10% corrupted clients, HST under output manipulation has up to 2.7 times the mean error of verified PI-RAPPOR under selective dropout and up to 2.6 times that of verified Hadamard Response under selective dropout (§ 7).

Related Work

Manipulation attacks and defenses for LDP. Cheu, Smith, and Ullman [11] distinguish input manipulation, in which clients randomize chosen false inputs, from attacks that manipulate reports directly. They show that LDP can amplify manipulation and that robustness depends on the mechanism, including HST. Cao, Jia, and Gong [9] study input and output poisoning attacks on frequency estimation and heavy-hitter protocols, and evaluate countermeasures. Song, Xu, and Zhu [27] propose interactive verifiable defenses against output poisoning for generalized randomized response and optimized unary encoding. Our work builds on these studies by establishing tight selective-dropout error bounds and developing server-side consistency checks for RAPPOR and Hadamard Response.

Verifiable LDP. Kato et al. [22] propose interactive protocols for verifiable randomized response. Bontekoe et al. [8] give verifiable local and shuffle protocols assuming authenticated raw inputs. Most relevant to our work, Verity [5] provides verifiable binary randomized response for client-chosen inputs and hides reports using HE and proofs of HE operations in a single server–client–server round trip. The same work analyzes zero dropout attacks in verifiable LDP. For nn users and mm malicious users, Verity allows client-chosen inputs but prevents selection based on the noise, giving an error bound of O~(m+nε)\widetilde{O}\left(m+\frac{\sqrt{n}}{\varepsilon}\right). We instead allow clients to observe their reports and quantify the resulting selective-dropout error for categorical histogram mechanisms. Our analysis identifies when verification improves robustness over unrestricted output manipulation despite selective dropout, motivating verification through plaintext rather than homomorphic evaluation.

Verifiable central and distributed DP. Verifiable DP has also been studied in central and distributed settings [24]. Biswas and Corrmode [7] give interactive zero-knowledge proofs for differentially private counting with the binomial mechanism, combining committed private randomness with public randomness. Confidential-DPproof [26] certifies differentially private training without revealing the training data or model. Neiswanger [25] develops certifiable lookup-table evaluation for discrete DP noise sampling and extends its approach to continuous sampling with end-to-end privacy guarantees under floating-point arithmetic. Sun and He [28] formalize verifiable distributed DP in a client–server–verifier model and construct a verifiable distributed discrete Laplace mechanism, accounting for collusion and finite-precision sampling.

Preliminaries

Local Differential Privacy

Let X={0,…,k−1}\mathcal{X} = \{0, \ldots, k-1\} be the data domain and let Y\mathcal{Y} be the output space of a local randomizer. We write M(x)∈Y\mathcal{M}(x) \in\mathcal{Y} for the output of a fresh execution of the randomized mechanism M\mathcal{M} on input x∈Xx \in\mathcal{X}.

Definition 2.1 (ε\varepsilon-local differential privacy (LDP)) [12, 15]. A randomized mechanism M\mathcal{M} with input domain X\mathcal{X} and output space Y\mathcal{Y} satisfies ε\varepsilon-local differential privacy if, for every pair x,x′∈Xx, x' \in\mathcal{X} and every measurable set S⊆YS \subseteq\mathcal{Y},

Pr⁡[M(x)∈S]≤eεPr⁡[M(x′)∈S].(1)\Pr[\mathcal{M}(x) \in S] \le e^\varepsilon\Pr[\mathcal{M}(x') \in S]. \tag*{(1)}

For a cryptographic protocol, the server observes not only the LDP report but also commitments, proofs, and other protocol messages. We therefore use the computational analogue of LDP [23] to reason about the server’s entire view.

Definition 2.2 (ε\varepsilon-computational local differential privacy) [15, 23]. Let View⁡Ser(x)\operatorname{View}_{\mathrm{Ser}}(x) denote the server’s view of an execution with an honest client holding input xx. The protocol satisfies ε\varepsilon-computational local differential privacy if, for every pair x,x′∈Xx, x' \in\mathcal{X} and every PPT distinguisher A\mathcal{A}, there is a negligible function ν\nu such that

Pr⁡[A(View⁡Ser(x))=1]≤eεPr⁡[A(View⁡Ser(x′))=1]+ν(κ).(2)\Pr[\mathcal{A}(\operatorname{View}_{\mathrm{Ser}}(x)) = 1] \le e^\varepsilon\Pr[\mathcal{A}(\operatorname{View}_{\mathrm{Ser}}(x')) = 1] + \nu(\kappa). \tag*{(2)}

In the local model, client ii applies M\mathcal{M} to its own value xix_i and sends only the resulting report yiy_i to the server. Thus, the privacy guarantee holds before reports from different clients are aggregated. Our statistical task is to estimate frequencies from the clients’ reports. For inputs x=(x0,…,xn−1)∈Xnx = (x_0, \ldots, x_{n-1}) \in\mathcal{X}^n, the true histogram is

F(x)=∑i=0n−1exi∈Rk,(3)F(x) = \sum_{i=0}^{n-1} e_{x_i} \in\mathbb{R}^k, \tag*{(3)}

where eje_j denotes the jjth standard basis vector. Unless stated otherwise, each honest client uses fresh, independent randomness when executing M\mathcal{M}. Logarithms are natural unless a base is specified.

We study four representative LDP mechanisms for frequency estimation over large domains: RAPPOR [14], PI-RAPPOR [17], Hadamard Response [1], and HST [4, 11]. With RAPPOR, each client independently randomizes a one-hot vector and sends the result; RAPPOR was deployed by Google for privacy-preserving telemetry [14]. PI-RAPPOR uses pairwise independent hash functions to represent reports compactly, reducing communication from linear to logarithmic in the domain size. With Hadamard Response, each client reports one index from an enlarged output domain, also requiring logarithmic communication. Each HST client uses a public random vector of length kk and sends a single randomized bit. Projective Geometry Response [16] also achieves optimal error guarantees, but implementing its sampler in our proof system requires non-native field arithmetic; Section 4 discusses this overhead and our choice of verification mechanisms.

RAPPOR and PI-RAPPOR

RAPPOR [14] and PI-RAPPOR [17] use different report formats but the same decoded-coordinate marginals. Let α0=(1+eε/2)−1\alpha_0 = (1 + e^{\varepsilon/2})^{-1} and α1=1−α0\alpha_1 = 1 - \alpha_0. For each client with input x∈Xx \in\mathcal{X}, both mechanisms encode bits Z0,…,Zk−1Z_0, \ldots, Z_{k-1} satisfying Pr⁡[Zx=1∣x]=α1\Pr[Z_x = 1 \mid x] = \alpha_1 and Pr⁡[Zj=1∣x]=α0\Pr[Z_j = 1 \mid x] = \alpha_0 for j≠xj \ne x. The server decodes them as y=(y0,…,yk−1)∈Rky = (y_0, \ldots, y_{k-1}) \in\mathbb{R}^k, where

yj=Zj−α0α1−α0∈{1eε/2−1,eε/2eε/2−1}.(4)y_j = \frac{Z_j - \alpha_0}{\alpha_1 - \alpha_0} \in\left\{\frac{1}{e^{\varepsilon/2} - 1}, \frac{e^{\varepsilon/2}}{e^{\varepsilon/2} - 1}\right\}. \tag*{(4)}

With RAPPOR, the client samples each ZjZ_j independently by flipping ex[j]e_x[j] with probability α0\alpha_0 and sends the bits Z0,…,Zk−1Z_0, \ldots, Z_{k-1} as its report. Two one-hot inputs differ in two coordinates, so using randomized response with privacy parameter ε/2\varepsilon/2 per coordinate gives ε\varepsilon-LDP.

PI-RAPPOR instead encodes the bits in two elements of a prime-order field Fq\mathbb{F}_q, where the field order qq upper bounds the number of classes kk. Assuming α0q\alpha_0q is an integer, define

B(j)={(u,v)∈Fq2:int⁡(u+vj)<α0q},(5)B(j) = \{(u,v) \in\mathbb{F}_q^2 : \operatorname{int}(u + vj) < \alpha_0q\}, \tag*{(5)}

where int⁡\operatorname{int} is the canonical representative in {0,…,q−1}\{0, \ldots, q-1\}. On input xx, the client samples its report Y∈Fq2Y \in\mathbb{F}_q^2 uniformly from B(x)B(x) with probability α1\alpha_1, or from its complement with probability α0\alpha_0. Since ∣B(x)∣=α0q2|B(x)| = \alpha_0q^2,

Pr⁡[Y=y∣x]={eε/2q2,y∈B(x),e−ε/2q2,y∉B(x).(6)\Pr[Y = y \mid x] = \begin{cases} \dfrac{e^{\varepsilon/2}}{q^2}, & y \in B(x),\\ \dfrac{e^{-\varepsilon/2}}{q^2}, & y \notin B(x). \end{cases} \tag*{(6)}

Each probability changes by a factor of at most eεe^\varepsilon between inputs, so PI-RAPPOR is also ε\varepsilon-LDP. Decoding the pair as Zj←{1if Y∈B(j),0otherwiseZ_j \leftarrow\begin{cases}1 & \text{if } Y \in B(j),\\0 & \text{otherwise}\end{cases} yields the stated marginals: membership in B(x)B(x) has probability α1\alpha_1, while for j≠xj \ne x the bijection (u,v)↦(u+vx,u+vj)(u,v) \mapsto(u + v x, u + v j) gives probability α0\alpha_0. In either mechanism, E[Y∣x]=ex\mathbb{E}[Y \mid x] = e_x. Writing yiy_i for client ii’s decoded vector, the server uses the same unbiased histogram estimator

F^=∑i=0n−1yi.(7)\widehat{F} = \sum_{i=0}^{n-1} y_i. \tag*{(7)}

For RAPPOR, computing this estimator takes O(nk)O(nk) time. For PI-RAPPOR, as noted in [16], dynamic programming with the chosen hash function yields an aggregation time of O(n+klog⁡k)O\left(n + k \log k\right).

Hadamard Response

This mechanism makes use of the Sylvester Hadamard matrix, defined as

HK=[111−1]⊗log⁡2K∈{−1,1}K×K(8)H_K = \begin{bmatrix} 1 & 1\\ 1 & -1 \end{bmatrix}^{\otimes\log_2 K} \in\{-1,1\}^{K \times K} \tag*{(8)}

where K=2⌈log⁡2(k+1)⌉K = 2^{\lceil\log_2(k+1)\rceil}. We associate input x∈Xx \in\mathcal{X} with row x+1x+1, thereby excluding the all-one row. With Hadamard Response, the client samples a column index y∈{0,…,K−1}y \in\{0, \ldots, K-1\} as its report according to

Pr⁡[MHR(x)=y]={2eεK(eε+1),HK[x+1,y]=1,2K(eε+1),HK[x+1,y]=−1.(9)\Pr[\mathcal{M}_{\mathrm{HR}}(x) = y] = \begin{cases} \dfrac{2e^\varepsilon}{K(e^\varepsilon+ 1)}, & H_K[x+1,y] = 1,\\ \dfrac{2}{K(e^\varepsilon+ 1)}, & H_K[x+1,y] = -1. \end{cases} \tag*{(9)}

The likelihood ratio between any two inputs is at most eεe^{\varepsilon}, so the mechanism is ε\varepsilon-LDP. Given reports y0,…,yn−1y_0,\ldots,y_{n-1}, the server uses

F^x=eε+1eε−1∑i=0n−1HK[x+1,yi](10)\widehat{F}_x=\frac{e^{\varepsilon}+1}{e^{\varepsilon}-1}\sum_{i=0}^{n-1}H_K[x+1,y_i] \tag*{(10)}

for each x∈Xx\in\mathcal{X}. Orthogonality of the Hadamard rows gives E[F^x]=F(x)x\mathbb{E}[\widehat{F}_x]=F(x)_x. Hadamard Response is asymptotically optimal for discrete distribution estimation in the high privacy regime and requires only log⁡2K\log_2 K communicated bits per report. Using fast Hadamard matrix multiplication, one can compute the estimator in O(n+klog⁡k)O(n+k\log k) time.

HST

HST is a public-randomness histogram protocol described by Bassily et al. [4]. For each client ii with input xi∈Xx_i\in\mathcal{X}, the protocol independently samples a public vector si∈{−1,1}k\mathbf{s}_i\in\{-1,1\}^k uniformly at random. Client ii applies binary randomized response to the xix_ith bit of the public vector, si,xis_{i,x_i}, sending

yi={si,xi,with probability eεeε+1,−si,xi,with probability 1eε+1.(11)y_i= \begin{cases} s_{i,x_i}, & \text{with probability }\dfrac{e^{\varepsilon}}{e^{\varepsilon}+1},\\ -s_{i,x_i}, & \text{with probability }\dfrac{1}{e^{\varepsilon}+1}. \end{cases} \tag*{(11)}

Write λε=eε+1eε−1\lambda_{\varepsilon}=\dfrac{e^{\varepsilon}+1}{e^{\varepsilon}-1} and decode the bit as yi=λεyisi,xiy_i=\lambda_{\varepsilon}y_i s_{i,x_i}. The count estimator is

F^=∑i=0n−1yi.(12)\widehat{F}=\sum_{i=0}^{n-1}y_i. \tag*{(12)}

The public vectors are fixed by the protocol, not chosen by the reporting clients. Conditional on these vectors, binary randomized response is ε\varepsilon-LDP; averaging also over the public randomness gives E[yi∣xi]=exi\mathbb{E}[y_i\mid x_i]=e_{x_i}. HST attains an optimal error rate when all clients follow the protocol [32]. In this explicit form it uses nknk public random bits and O(nk)O(nk) aggregation time, although each client sends only one bit.

Zero-Knowledge Proofs of Knowledge

A commitment scheme allows a sender to bind itself to a value without revealing that value. We write c←Commit⁡(x;ω)c\leftarrow\operatorname{Commit}(x;\omega) for a commitment to xx, where ω\omega is the commitment randomness used to hide xx. We require the scheme to be computationally binding, meaning that no probabilistic polynomial-time (PPT) sender can open one commitment to two different values, and hiding, meaning that commitments to any two values are computationally indistinguishable. These properties let the protocol refer to a fixed client value while keeping that value private [29].

We use zero-knowledge proofs of knowledge (ZKPoKs) to establish that a committed computation was performed correctly [6, 19, 29]. For a deterministic function ff that takes public input xpubx_{\mathrm{pub}} and private input xprivx_{\mathrm{priv}} and outputs yy, let z=(xpub,y,c)z=(x_{\mathrm{pub}},y,c) be the public statement and w=(xpriv,ω)w=(x_{\mathrm{priv}},\omega) be the private witness. Define the relation

Rf={(z,w):c=Commit⁡(xpriv;ω)∧y=f(xpriv,xpub)}(13)R_f=\left\{(z,w):c=\operatorname{Commit}(x_{\mathrm{priv}};\omega)\land y=f(x_{\mathrm{priv}},x_{\mathrm{pub}})\right\} \tag*{(13)}

A ZKPoK for RfR_f is a proof protocol

Π(z,w):=⟨P(z,w),V(z)⟩,(14)\Pi(z,w):=\langle P(z,w),V(z)\rangle, \tag*{(14)}

in which the prover P convinces the verifier V that it knows a witness ww such that (z,w)∈Rf(z,w)\in R_f, without revealing the witness. For security parameter κ∈N\kappa\in\mathbb{N}, we use the following standard properties:

  • Completeness. If (z,w)∈Rf(z,w)\in R_f and both parties follow Π\Pi, then V accepts except with negligible probability in κ\kappa.

  • Knowledge soundness. For any PPT prover that makes V accept with non-negligible probability, acceptance guarantees that the prover knows a witness ww satisfying (z,w)∈Rf(z,w)\in R_f.

  • Zero knowledge. The verifier learns nothing about the private witness ww beyond the validity of the public statement zz.

In our protocols, the witness contains both the client’s input and its private randomness share. The client first proves knowledge of a valid commitment opening before receiving the server’s randomness share. It later proves that the submitted report was computed using an opening of the same commitment. Together with commitment binding, these proofs tie every accepted report to the client’s input and randomness share fixed before the server’s share was revealed.

Verifiable Randomized Computation via Distributed Randomness

A randomized mechanism M(x)\mathcal{M}(x) can be represented by a deterministic function f(x,rCli,rSer)f(x,r^{\mathrm{Cli}},r^{\mathrm{Ser}}), where rClir^{\mathrm{Cli}} and rSerr^{\mathrm{Ser}} are randomness shares contributed by the client and server, respectively.

Distributed Randomness for an LDP Mechanism

A deterministic function ff and prescribed distributions for the client and server randomness shares implement an ε\varepsilon-LDP mechanism M\mathcal{M} through distributed randomness if they satisfy the following requirements:

(1) (Integrity) For every fixed input xx and valid client share rClir^{\mathrm{Cli}}, sampling the server’s share rSerr^{\mathrm{Ser}} from its prescribed distribution makes f(x,rCli,rSer)f(x,r^{\mathrm{Cli}},r^{\mathrm{Ser}}) computationally indistinguishable from M(x)\mathcal{M}(x).

(2) (Privacy) When the client samples its share honestly and independently of the server’s share, the joint view (rSer,f(x,rCli,rSer))(r^{\mathrm{Ser}},f(x,r^{\mathrm{Cli}},r^{\mathrm{Ser}})) satisfies ε\varepsilon-computational LDP with respect to xx.

Given integrity, a sufficient condition for privacy is that f(x,rCli,rSer)f(x,r^{\mathrm{Cli}},r^{\mathrm{Ser}}) and rSerr^{\mathrm{Ser}} are independent for every fixed xx when the shares are sampled honestly and independently. Indeed, integrity ensures that the marginal distribution of the output is computationally indistinguishable from M(x)\mathcal{M}(x), and independence ensures that revealing rSerr^{\mathrm{Ser}} does not affect its privacy. Our instantiations satisfy this condition. The server’s contribution prevents a malicious client from selecting all of the random coins and biasing its report; the client’s contribution prevents the server from determining those coins by itself and learning xx [7, 10]. The client then proves the relation above with private input xpriv=(x,rCli)x_{\mathrm{priv}}=(x,r^{\mathrm{Cli}}), public input xpub=rSerx_{\mathrm{pub}}=r^{\mathrm{Ser}}, and public output y←f(x,rCli,rSer)y\leftarrow f(x,r^{\mathrm{Cli}},r^{\mathrm{Ser}}).

Problem Setup

We consider one server and nn clients indexed by 0,…,n−10,\ldots,n-1. Each client ii holds one categorical value xi∈Xx_i\in\mathcal{X}, and the server seeks to estimate the histogram F(x)F(x) from reports generated with privacy budget ε\varepsilon. The server acts as the verifier in the cryptographic protocols. It is semi-honest: it follows the prescribed protocol but may attempt to infer additional information from its view. Without loss of generality, the first mm clients are corrupted, with C={0,…,m−1}C=\{0,\ldots,m-1\}. An adversary may coordinate the corrupted clients, which can deviate arbitrarily from the client algorithm; the remaining clients follow the protocol with independent randomness. In particular, the adversary may coordinate the corrupted clients’ reports through output manipulation, as defined in Definition 3.1.

Definition 3.1 (Output manipulation). The adversary may jointly choose arbitrary reports y~i∈Y\widetilde{y}_i \in\mathcal{Y} for the corrupted clients i∈Ci \in C, where Y\mathcal{Y} is the report space of the local randomizer M\mathcal{M}. These reports need not follow the distribution prescribed by M\mathcal{M}.

Our goal is twofold: the server’s view of each honest client must reveal no more than the prescribed ε\varepsilon-LDP guarantee, and every accepted report must be consistent with some committed input and the prescribed randomization procedure. However, consistency with a valid execution alone does not prevent manipulation of the submitted report distribution: a client may try multiple valid executions and submit only a favorable report. § 3.1 examines this resampling attack in one-round-trip designs with client-visible reports. We then introduce a commitment step that fixes the client’s input and randomness before the server reveals its share, preventing resampling while still allowing selective dropout.

Limitations of One-Round-Trip Protocols

An appealing approach is to verify an LDP report in a single round trip: the server sends one challenge, the client returns one response based on the challenge and input data, and the server verifies the response before using the report to estimate the histogram. We use y=f(x,rCli,rSer)∈Yy = f(x,r^{\mathrm{Cli}},r^{\mathrm{Ser}}) \in\mathcal{Y} to denote one client’s randomized report, computed from its input xx and the client and server randomness shares rClir^{\mathrm{Cli}} and rSerr^{\mathrm{Ser}}. The client’s response is the full protocol message carrying this report, either in plaintext or encrypted, together with the required proof. The server uses accepted reports to compute the histogram estimate. This communication-efficient server–client–server pattern is used in Vεrity [5]. However, if the client can compute the report from its local view, it may try multiple executions locally for the same server challenge and submit only a favorable report with its proof, enabling output manipulation. We first analyze this attack, then explain how output hiding via encryption prevents it, and finally discuss alternative design choices that allow lightweight plaintext evaluation.

Why Output Visibility Enables Output Manipulation

In a one-round-trip server–client–server protocol, a client that can compute its report from its local view may repeatedly sample client randomness for the same input and server challenge. It can then submit a favorable report together with a valid proof for the selected execution. Each candidate is computed correctly, but selection changes the submitted report distribution. The following theorem formalizes this resampling attack when favorable reports occur with inverse-polynomial probability.

Theorem 3.2 (Output Manipulation from Client-Visible Outputs). Let Π\Pi be a correct PPT one-round-trip server–client–server implementation of a randomized mechanism M\mathcal{M}. For a fixed input x∈Xx \in\mathcal{X}, write rSerr^{\mathrm{Ser}} for the server’s challenge, rClir^{\mathrm{Cli}} for the client’s randomness, and y=f(x,rCli,rSer)∈Yy = f(x,r^{\mathrm{Cli}},r^{\mathrm{Ser}}) \in\mathcal{Y} for the randomized report. Assume there are a PPT algorithm ComputeReport, an efficiently recognizable set S⊆YS \subseteq\mathcal{Y}, and a polynomial pp such that, except with negligible probability over the server’s challenge, ComputeReport computes yy from the client’s local view with negligible error and

1p(k)≤Pr⁡rCli[y∈S∣x,rSer]≤12.(15)\frac{1}{p(k)} \leq\Pr_{r^{\mathrm{Cli}}}[y \in S \mid x,r^{\mathrm{Ser}}] \leq\frac{1}{2}. \tag*{(15)}

Then a PPT client can submit a valid response that the server accepts with y∈Sy \in S with probability 1−negl⁡(k)1-\operatorname{negl}(k). The distribution of the submitted report has total variation distance at least 12−negl⁡(k)\frac{1}{2}-\operatorname{negl}(k) from the honest report distribution.

Proof sketch. Rejection sampling finds a favorable report in polynomial time with overwhelming probability. See Appendix B.1 for the proof. □

Hiding Reports with Encryption and Its Cost

Output visibility also enables a distinct attack: even when restricted to a single prescribed report, a client may withhold it after inspection, resulting in selective dropout (Definition 3.3).

Definition 3.3 (Selective dropout). Each corrupted client i∈Ci \in C has one report yiy_i generated by a single execution of the prescribed randomizer on its fixed input xix_i. After inspecting these reports, the adversary may choose a subset D⊆CD \subseteq C of clients to drop out; each client in C∖DC \setminus D submits its original report yiy_i unchanged. The adversary may coordinate this choice across corrupted clients, but may not modify the reports or repeat their randomization.

Hiding candidate reports throughout the client’s computation prevents selection based on their realized values, addressing both resampling and selective dropout. However, to achieve this while retaining a single round trip, the protocol must let the server verify the report without revealing it to the client during computation. The client therefore cannot simply evaluate the mechanism in plaintext and send a proof of the result. A natural approach is to evaluate the mechanism on encrypted data and use zero-knowledge proofs to certify the required cryptographic operations. Verity follows this approach: the server encrypts its randomness, the client computes an encryption of its report using HE, and zero-knowledge proofs certify the required HE operations [5]. The server decrypts the report after verifying the proofs of the HE operations.

This design incurs the cost of computation using HE and of proving HE operations. The proofs certify the arithmetic of encryption and partial decryption, rather than just the comparatively small plaintext LDP computation. Proving these cryptographic operations compounds the cost of HE itself: the client must not only perform expensive cryptographic operations but also prove their correctness. This makes report generation substantially more costly than evaluating and proving the plaintext LDP mechanism. For binary randomized response, Verity reports 1,423.50 s of online client computation and 1,472.7 s of server computation, approximately 23.7 and 24.5 minutes, respectively [5 Section 9.2].

Lightweight Design Choices

Although output hiding prevents selection based on the realized report, the cost of this encrypted construction makes it impractical for large-scale telemetry. We therefore pursue two alternatives, depending on how the client protocol can be changed.

First, our lightweight construction adds a commitment message before the server reveals its randomness share. The commitment fixes the client’s input and randomness share before the server supplies its share, which then determines a single report that can pass verification. The client can then compute its report in plaintext and prove correct evaluation without HE. It cannot resample this fixed report, but it can still decide whether to submit it after inspecting it, enabling selective dropout.

§ 4.1 presents the framework, followed by concrete instantiations in § 4.2. Although malicious clients may still withhold their reports after inspecting them, § 5 shows that, for (PI-)RAPPOR and Hadamard Response, this selective dropout causes asymptotically less attack-dependent error than output manipulation. The extra message therefore lets us avoid the overhead caused by HE while retaining a meaningful robustness benefit. Rather than hiding every report from its client, we enforce correct randomization and quantify the remaining error from selective dropout.

Second, when adding commitments and proofs to the client protocol is not feasible, the server can instead check the statistical consistency of the collected reports. § 6 develops such post-hoc checks for RAPPOR and Hadamard Response. These checks do not certify each client’s computation, but they can limit the aggregate damage from output manipulation without any client-side changes.

An Efficient and Secure Construction of Verifiable LDP Mechanisms

We construct efficient verifiable LDP protocols that prevent output manipulation while allowing selective dropout. As we show in § 5, for (PI-)RAPPOR and Hadamard Response, the attack-dependent error from selective dropout is smaller by a factor of k\sqrt{k} than that from output manipulation, where kk is the domain size. Thus, verification can improve robustness without preventing dropout.

For our implementations, we choose PI-RAPPOR and Hadamard Response because their report-generation computations are sublinear in kk and admit compact circuits over the fixed prime field used by our ZKPoK backend. PI-RAPPOR generates a report consisting of two field elements, while Hadamard Response generates an index represented by O(log⁡k)O(\log k) bits. In contrast, directly verifying RAPPOR requires generating and proving the randomization of kk report bits. For HST, restricting output manipulation to selective dropout does not improve the worst-case asymptotic error rate, as shown in § 5. Accordingly, HST serves as a comparison mechanism in our analysis and experiments.

Projective Geometry Response [16] is another frequency-estimation mechanism with optimal error guarantees, but its sampler uses a finite field different from the backend’s native field. Implementing its field operations would require repeated non-native modular arithmetic, including modular reduction and range constraints, adding circuit overhead. We leave its efficient verification to future work.

We first present a general three-message framework that fixes the client’s input and randomness before the server supplies its randomness share. We then instantiate it for PI-RAPPOR and Hadamard Response, using plaintext evaluation and compact zero-knowledge proofs to enforce correct randomization without HE.

A Framework for Verifiable LDP Against Output Manipulation

Our protocol uses one additional client message to enable substantially cheaper plaintext computation and proofs. The key ordering constraint is that the client commits to both its input and its randomness share before learning the server’s randomness share. For that fixed commitment, the server’s share determines the only report that the client can prove valid. Thus, a malicious client can submit that report or submit nothing, but it cannot choose among multiple valid reports for the same commitment after seeing the server’s randomness share.

Let f(x,riCli,riSer)f(x,r_i^{\mathrm{Cli}},r_i^{\mathrm{Ser}}) be the deterministic realization of an ε\varepsilon-LDP mechanism described in § 2.3. The protocol uses a commitment scheme Commit and two ZKPoKs, with the statements specified in the steps below.

For each client ii, the protocol proceeds as follows.

(1) Commitment: Client ii samples a private randomness share riClir_i^{\mathrm{Cli}} and commitment randomness ωi\omega_i, and computes ci=Commit⁡(xi∥riCli;ωi)c_i=\operatorname{Commit}(x_i\mathbin\Vert r_i^{\mathrm{Cli}};\omega_i), where ∥\Vert denotes concatenation. It sends cic_i together with a ZKPoK πiin\pi_i^{\mathrm{in}} of knowledge of (xi,riCli,ωi)(x_i,r_i^{\mathrm{Cli}},\omega_i) such that xi∈Xx_i\in\mathcal{X}, riClir_i^{\mathrm{Cli}} satisfies the mechanism’s validity constraints, and

ci=Commit⁡(xi∥riCli;ωi).(16)c_i=\operatorname{Commit}(x_i\mathbin\Vert r_i^{\mathrm{Cli}};\omega_i). \tag*{(16)}

The server verifies the proof. A client enters the protocol only if this first proof is accepted; otherwise, the client is considered to have exited before the server generates its randomness share.

(2) Server randomness: For every admitted client ii, the server independently samples a randomness share riSerr_i^{\mathrm{Ser}} from the distribution prescribed by the distributed-randomness construction and sends it to that client. Sampling riSerr_i^{\mathrm{Ser}} only after accepting cic_i ensures that the committed pair (xi,riCli)(x_i,r_i^{\mathrm{Cli}}) cannot depend on the server’s share.

(3) Report and verification: Client ii computes

yi=f(xi,riCli,riSer)(17)y_i=f(x_i,r_i^{\mathrm{Cli}},r_i^{\mathrm{Ser}}) \tag*{(17)}

and sends yiy_i together with a ZKPoK πieval\pi_i^{\mathrm{eval}} of knowledge of (xi,riCli,ωi)(x_i,r_i^{\mathrm{Cli}},\omega_i) satisfying

ci=Commit⁡(xi∥riCli;ωi),yi=f(xi,riCli,riSer).(18)\begin{aligned} c_i&=\operatorname{Commit}(x_i\mathbin\Vert r_i^{\mathrm{Cli}};\omega_i),\\ y_i&=f(x_i,r_i^{\mathrm{Cli}},r_i^{\mathrm{Ser}}). \tag*{(18)} \end{aligned}

The server accepts yiy_i if and only if this proof verifies with respect to (ci,riSer,yi)(c_i,r_i^{\mathrm{Ser}},y_i). It then aggregates all accepted reports using the estimator associated with the underlying LDP mechanism.

Theorem 4.1 (Protocol guarantees). Assume that the commitment scheme is binding and hiding, both ZKPoKs are complete, knowledge sound, and zero knowledge, and the distributed randomness construction satisfies Definition 2.3. Then the protocol above has the following properties:

(1) Completeness. Every honest client that remains online is accepted except with negligible probability.

(2) Accepted-output integrity. Except with negligible probability, every accepted report yiy_i is equal to f(xi,riCli,riSer)f(x_i,r_i^{\mathrm{Cli}},r_i^{\mathrm{Ser}}) for the input and client randomness share fixed by cic_i before riSerr_i^{\mathrm{Ser}} was sampled.

(3) Computational privacy. For an honest client, the server’s complete view satisfies ε\varepsilon-computational local differential privacy as in Definition 2.2.

Proof sketch. The guarantees follow from the commitment, ZKPoK, and distributed-randomness properties. See Appendix § 11.§ 2 for the proof. □

Circuit Instantiations for Frequency Estimation

We instantiate the framework of § 4.1 for PI-RAPPOR and Hadamard Response by expressing their samplers as deterministic circuits over client and server randomness shares. The constructions show how to combine these shares and implement the sampling probabilities at finite precision while preserving ε\varepsilon-LDP. For either mechanism, the combined randomness has the prescribed distribution whenever either party’s shares are sampled honestly and independently of the other party’s shares.

The circuits below compute f(x,rCli,rSer)f(x,r^{\mathrm{Cli}},r^{\mathrm{Ser}}), whose evaluation is certified in the final protocol step. We use γ\gamma-bit integer thresholds for probabilistic choices, with conservative rounding to preserve the privacy guarantee. The proofs additionally enforce input ranges, bitness, commitment openings, and consistency with the public outputs; we omit these constraints from the pseudocode.

PI-RAPPOR Circuit

Algorithm 1 implements the PI-RAPPOR sampler from § 2.1.1 using distributed randomness. The prime q≥kq \ge k is the order of the field Fq\mathbb{F}_q in which the two report elements are represented; γ\gamma is the number of bits used for a random branch choice. Recall that α0=11+ε2\alpha_0 = \frac{1}{1+\varepsilon^2} is the probability that a nonmatching coordinate is encoded as one. We set τPI=⌈qα0⌉\tau_{\mathrm{PI}} = \lceil q\alpha_0\rceil and define the rounded version of the set in Equation (5) by Bτ(j)={(u,v)∈Fq2:int⁡(u+vj)<τPI}B_{\tau}(j) = \{(u,v) \in\mathbb{F}_q^2 : \operatorname{int}(u+vj) < \tau_{\mathrm{PI}}\}. We also set θPI=⌊2γ(1−e−ε/2)⌋\theta_{\mathrm{PI}} = \lfloor2^\gamma(1-e^{-\varepsilon/2})\rfloor; this threshold determines how often the sampler selects a pair from Bτ(x)B_{\tau}(x) instead of a uniform pair from Fq2\mathbb{F}_q^2.

For each party P∈{Cli,Ser}P \in\{\mathrm{Cli},\mathrm{Ser}\}, an honestly sampled randomness share contains independent uniform values r0P,r1P∈Fqr_0^P,r_1^P \in\mathbb{F}_q, an integer zP∈{0,…,τPI−1}z^P \in\{0,\ldots,\tau_{\mathrm{PI}}-1\}, and a bit string dP∈{0,1}γd^P \in\{0,1\}^{\gamma}. The circuit combines the two parties’ values to obtain the sampler’s random choices. The combined value r1r_1 is the second component of the report in both branches, while r0r_0 is the first component in the uniform-pair branch. In the restricted-pair branch, zz and r1r_1 instead determine a pair in Bτ(x)B_{\tau}(x). The combined bit strings select which branch to use. The circuit proceeds as follows:

  • Lines 1 and 2 add r0Clir_0^{\mathrm{Cli}} to r0Serr_0^{\mathrm{Ser}} and r1Clir_1^{\mathrm{Cli}} to r1Serr_1^{\mathrm{Ser}}, respectively, using addition in Fq\mathbb{F}_q. The resulting r0r_0 and r1r_1 are independent and uniform in Fq\mathbb{F}_q when either party samples its share honestly and independently of the other’s share.

  • Line 3 adds zCliz^{\mathrm{Cli}} and zSerz^{\mathrm{Ser}} modulo τPI\tau_{\mathrm{PI}} to obtain a uniform z∈{0,…,τPI−1}z \in\{0,\ldots,\tau_{\mathrm{PI}}-1\}. In the restricted-pair branch, zz will equal the canonical representative of y0+y1xy_0+y_1x and thus ensure that the report is in Bτ(x)B_{\tau}(x).

  • Line 4 XORs dClid^{\mathrm{Cli}} and dSerd^{\mathrm{Ser}} and interprets the resulting bits as a uniform integer U∈{0,…,2γ−1}U \in\{0,\ldots,2^\gamma-1\}. Comparing UU with θPI\theta_{\mathrm{PI}} lets the circuit select the restricted-pair branch with probability θPI2γ\frac{\theta_{\mathrm{PI}}}{2^\gamma}.

Algorithm 1 PI-RAPPOR circuit

Figure 1.

  • Line 5 sets b=0b=0 when U<θPIU < \theta_{\mathrm{PI}}, selecting the restricted-pair branch, and b=1b=1 otherwise, selecting the uniform-pair branch.

  • Lines 6 and 7 construct the report. When b=0b=0, the report is (z−r1x,r1)(z-r_1x,r_1), so int⁡(y0+y1x)=z<τPI\operatorname{int}(y_0+y_1x)=z<\tau_{\mathrm{PI}} and the pair belongs to Bτ(x)B_{\tau}(x). Each pair in Bτ(x)B_{\tau}(x) corresponds to exactly one choice of zz and r1r_1, so uniform, independent choices of these values give a uniform pair in Bτ(x)B_{\tau}(x). When b=1b=1, the report is (r0,r1)(r_0,r_1), a uniform pair in Fq2\mathbb{F}_q^2. The circuit returns the resulting pair y=(y0,y1)y=(y_0,y_1).

Write δ~=θPI2γ\widetilde{\delta}=\frac{\theta_{\mathrm{PI}}}{2^\gamma} for the probability of choosing the restricted-pair branch, α~0=τPIq\widetilde{\alpha}_0=\frac{\tau_{\mathrm{PI}}}{q}, and α~1=δ~+(1−δ~)α~0\widetilde{\alpha}_1=\widetilde{\delta}+(1-\widetilde{\delta})\widetilde{\alpha}_0. With the prescribed randomness shares, the client obtains a uniform pair from Bτ(x)B_{\tau}(x) with probability δ~\widetilde{\delta} and a uniform pair from Fq2\mathbb{F}_q^2 otherwise; the latter branch can also produce a pair in Bτ(x)B_{\tau}(x). The resulting probabilities of membership in Bτ(j)B_{\tau}(j) are α~1\widetilde{\alpha}_1 for j=xj=x and α~0\widetilde{\alpha}_0 for j≠xj\ne x, corresponding to the matching and nonmatching probabilities in § 2.1.1. The largest likelihood ratio is at most 1+δ~α~0(1−δ~)≤eε1+\frac{\widetilde{\delta}}{\widetilde{\alpha}_0(1-\widetilde{\delta})}\le e^\varepsilon, so the rounded mechanism satisfies ε\varepsilon-LDP. Rounding changes the nonmatching and matching coordinate probabilities by less than 1q\frac{1}{q} and 1q+2−γ\frac{1}{q}+2^{-\gamma}, respectively; when qα0∈Nq\alpha_0\in\mathbb{N}, the full report distribution is within 2−γ2^{-\gamma} in total variation of PI-RAPPOR. The estimator in Equation (7) remains unbiased when membership in Bτ(j)B_{\tau}(j) and the probabilities α~0,α~1\widetilde{\alpha}_0,\widetilde{\alpha}_1 are used in Equation (4); we choose γ\gamma so that δ~>0\widetilde{\delta}>0.

Hadamard Response Circuit

Algorithm 2 implements the Hadamard Response sampler from Section 2.1.2 using distributed randomness. Recall that K=2⌈log⁡2(k+1)⌉K=2^{\lceil\log_2(k+1)\rceil}, input xx corresponds to row x+1x+1 of HKH_K, and the report is a column index yy. Let ℓ=log⁡2K\ell=\log_2 K, so both the row and column indices have ℓ\ell-bit representations. We write Bits⁡ℓ(t)\operatorname{Bits}_{\ell}(t) for the ℓ\ell-bit representation of an integer tt, with the least significant bit indexed by zero. In Equation (9), the report is chosen from the columns with HK[x+1,y]=−1H_K[x+1,y]=-1 with total probability 11+eε\frac{1}{1+e^\varepsilon} and from those with HK[x+1,y]=1H_K[x+1,y]=1 otherwise. The circuit uses γ\gamma bits to choose between these two sets and rounds the threshold up to τHR=⌈2γ1+eε⌉\tau_{\mathrm{HR}}=\left\lceil\frac{2^\gamma}{1+e^\varepsilon}\right\rceil.

Each party P∈{Cli,Ser}P\in\{\mathrm{Cli},\mathrm{Ser}\} contributes a randomness share containing an ℓ\ell-bit string cPc^P for choosing a column and a γ\gamma-bit string aPa^P for choosing the sign of the Hadamard entry. These strings are

Algorithm 2 Hadamard Response circuit

Require: Class x∈{0,…,k−1}x \in\{0,\ldots,k-1\} Require: Parameters (ℓ,γ,τHR)(\ell,\gamma,\tau_{\mathrm{HR}}), with K=2ℓK=2^\ell Require: Client share rCli=(cCli,aCli)r_{\mathrm{Cli}}=(c^{\mathrm{Cli}},a^{\mathrm{Cli}}) Require: Server share rSer=(cSer,aSer)r_{\mathrm{Ser}}=(c^{\mathrm{Ser}},a^{\mathrm{Ser}}) Require: For each P∈{Cli,Ser}P \in\{\mathrm{Cli},\mathrm{Ser}\}: cP∈{0,1}ℓc^P \in\{0,1\}^{\ell}, aP∈{0,1}γa^P \in\{0,1\}^{\gamma} Ensure: Hadamard report y∈{0,…,K−1}y \in\{0,\ldots,K-1\}

  1. b←Bits⁡ℓ(x+1)b \leftarrow\operatorname{Bits}_{\ell}(x+1) &nbsp;&nbsp;▹ least significant bit first

  2. c←cCli⊕cSerc \leftarrow c^{\mathrm{Cli}} \oplus c^{\mathrm{Ser}} &nbsp;&nbsp;▹ Combine the randomness shares

  3. U←∑i=0γ−12i(aiCli⊕aiSer)U \leftarrow\sum_{i=0}^{\gamma-1}2^i(a_i^{\mathrm{Cli}}\oplus a_i^{\mathrm{Ser}}) &nbsp;&nbsp;▹ Choose the output parity

  4. a←1[U<τHR]a \leftarrow\mathbf{1}[U<\tau_{\mathrm{HR}}] &nbsp;&nbsp;▹ Select a pivot and collect the remaining parity

  5. j⋆←min⁡{i:bi=1}j^\star\leftarrow\min\{i:b_i=1\}

  6. ρ←⨁0≤i<ℓi≠j⋆bici\rho\leftarrow\bigoplus_{\substack{0\le i<\ell\\i\ne j^\star}}b_i c_i &nbsp;&nbsp;▹ Set the pivot bit to enforce parity aa

  7. c′←cc' \leftarrow c; cj⋆′←a⊕ρc'_{j^\star}\leftarrow a\oplus\rho

  8. return y←∑i=0ℓ−12ici′y\leftarrow\sum_{i=0}^{\ell-1}2^i c'_i

combined to form the candidate column cc and the scalar parity choice aa below. For bit representations of a row and column, the Hadamard entry is (−1)(-1) raised to the parity of their bitwise inner product. The circuit chooses the sign, then adjusts one column bit so that this parity agrees with the chosen sign:

  • Line 1 writes the row index x+1x+1 as an ℓ\ell-bit string bb, least significant bit first. Since x+1≠0x+1\ne0, at least one bit of bb is set.

  • Line 2 XORs the parties’ column strings to obtain a uniformly random candidate column cc.

  • Line 3 XORs their γ\gamma-bit strings and interprets the result as an integer U∈{0,…,2γ−1}U\in\{0,\ldots,2^\gamma-1\}.

  • Line 4 sets a=1a=1 when U<τHRU<\tau_{\mathrm{HR}} and a=0a=0 otherwise. The value aa is the desired parity: a=1a=1 selects an entry of −1-1, and a=0a=0 selects an entry of 11.

  • Line 5 chooses j⋆j^\star, the index of the least-significant set bit of bb, as the pivot.

  • Line 6 computes ρ\rho, the parity contributed by all row and column bits except the pivot.

  • Line 7 sets the pivot bit of the output column to a⊕ρa\oplus\rho and leaves its other bits unchanged. Because bj⋆=1b_{j^\star}=1, the complete bitwise inner product has parity ρ⊕(a⊕ρ)=a\rho\oplus(a\oplus\rho)=a.

  • Line 8 converts the resulting column bits to the integer report yy and returns it.

The unchanged column bits are uniform, so the resulting report is uniform among the columns with the selected sign. The circuit selects the −1-1 class with probability α~HR=τHR2γ\widetilde{\alpha}_{\mathrm{HR}}=\frac{\tau_{\mathrm{HR}}}{2^\gamma}, which differs from 11+eε\frac{1}{1+e^\varepsilon} by less than 2−γ2^{-\gamma}. The report distribution therefore differs from Hadamard Response by less than 2−γ2^{-\gamma} in total variation. Rounding the threshold up gives 1−α~HRα~HR≤eε\frac{1-\widetilde{\alpha}_{\mathrm{HR}}}{\widetilde{\alpha}_{\mathrm{HR}}}\le e^\varepsilon, so the rounded mechanism satisfies ε\varepsilon-LDP. Replacing the coefficient in Equation (10) by 11−2α~HR\frac{1}{1-2\widetilde{\alpha}_{\mathrm{HR}}} yields an unbiased estimator; we choose γ\gamma so that α~HR<12\widetilde{\alpha}_{\mathrm{HR}}<\frac{1}{2}.

Analysis of Selective Dropout Attacks

The protocol in § 4 prevents output manipulation but leaves malicious clients free to withhold their prescribed reports. We now quantify the error caused by this selective dropout and compare it with the error under output manipulation. For (PI)-RAPPOR and Hadamard Response, the attack-dependent error from selective dropout is smaller by a factor of k\sqrt{k} than under output manipulation. For HST, selective dropout and output manipulation have the same asymptotic effect. This comparison establishes when the restriction enforced by the protocol improves robustness and explains the choice of PI-RAPPOR and Hadamard Response for our instantiations. Thus, verification can reduce the damage from malicious clients even when selective dropout remains possible.

As in § 3, C={0,…,m−1}C=\{0,\ldots,m-1\} is the set of corrupted clients. Client i∈Ci\in C holds a committed input xix_i and generates an independently randomized valid report yiy_i. After observing all corrupted clients’ reports, the adversary chooses a subset D⊆CD\subseteq C of clients to drop out. The server applies the mechanism’s usual estimator to the reports from {0,…,n−1}∖D\{0,\ldots,n-1\}\setminus D. We measure its expected ℓ1\ell_1 error against the histogram F(x)F(x) of the nn admitted clients’ committed inputs, including those of dropped clients:

Err⁡1=E[∥F^−F(x)∥1].(19)\operatorname{Err}_1=\mathbb{E}\left[\left\|\widehat{F}-F(x)\right\|_1\right]. \tag*{(19)}

The expectation is over mechanism randomness and any internal randomness of the attack; the choice of DD may be an arbitrary randomized function of the corrupted clients’ reports. For each mechanism, let viv_i be the contribution of client ii’s report to its usual histogram estimator, including any decoding and scaling. If F^all=∑i=0n−1vi\widehat{F}_{\mathrm{all}}=\sum_{i=0}^{n-1}v_i is the estimate using all prescribed reports, then dropout changes it to F^all−∑i∈Dvi\widehat{F}_{\mathrm{all}}-\sum_{i\in D}v_i. We study the norm of this change due to dropout; the total error also includes the estimation error already present in F^all\widehat{F}_{\mathrm{all}}. For HST, the committed inputs and corrupted identities are fixed before sampling the public randomness, which is also included in the expectation. We abbreviate selective dropout as SD and output manipulation as OM.

Theorem 5.1 (Selective dropout and output manipulation). Let 0<ε≤10<\varepsilon\le1, and assume reports are randomized independently across clients. For PI-RAPPOR, assume α0q∈Z\alpha_0q\in\mathbb{Z}. For each mechanism and attack below, the worst-case expected ℓ1\ell_1 count error is Θ(knε+T)\Theta\left(\frac{k\sqrt{n}}{\varepsilon}+T\right), where HR denotes Hadamard Response and TT is:

Attack(PI-)RAPPORHRHST
SDmkε\frac{m\sqrt{k}}{\varepsilon}mkε\frac{m\sqrt{k}}{\varepsilon}mkε\frac{m\sqrt{k}}{\varepsilon}
OMmkε\frac{mk}{\varepsilon}mkε\frac{mk}{\varepsilon}mkε\frac{m\sqrt{k}}{\varepsilon}

For (PI-)RAPPOR, the decoded contribution is vi=yiv_i=y_i as defined in § 2.1.1. For Hadamard Response, vi=eε+1eε−1Hk[1:k,yi]v_i=\frac{e^\varepsilon+1}{e^\varepsilon-1}H_k[1:k,y_i], where Hk[1:k,yi]H_k[1:k,y_i] denotes the entries in row 1,…,k1,\ldots,k of column yiy_i. For HST, the decoded contribution is vi=yiv_i=y_i as defined in Section 2.1.3.

The following attacks achieve the attack-dependent rates in the table:

  • Selective dropout: Sample ss uniformly from {−1,1}k\{-1,1\}^k and drop each corrupted report for which ⟨s,vi⟩≥0\langle s,v_i\rangle\ge0. This attack takes O(mk)O(mk) arithmetic operations, including field operations for PI-RAPPOR, and changes the estimate by Ω(mkε)\Omega\left(\frac{m\sqrt{k}}{\varepsilon}\right) in expected ℓ1\ell_1 norm.

  • Output manipulation: For (PI-)RAPPOR and Hadamard Response, have all corrupted clients submit the same report. For HST, flip the report bits selected by the selective-dropout attack.

The common knε\frac{k\sqrt{n}}{\varepsilon} term results from the error when all clients submit correctly generated reports. The output-manipulation comparison builds on prior analyses [9, 11]; we analyze the selective dropout attack described above for these mechanisms. For HST, the public vectors constrain forged reports to client-specific directions, so preventing output manipulation improves the worst-case rate by at most a constant factor.

Proof sketch. For (PI-)RAPPOR, covariance bounds and symmetrization control adaptive selection; for Hadamard Response, orthogonality bounds it through report collisions. For HST, flipping a bit changes its contribution by twice the amount of dropping it, and a random-matrix bound controls the error. Moment bounds and the selective dropout attack above give matching lower bounds. Appendix B.3 gives the proofs and bounds on the change to the estimator before combining it with the error without an attack. □

Comparison with Output Manipulation

For RAPPOR, PI-RAPPOR, and Hadamard Response, comparing the selective dropout term mkε\frac{m\sqrt{k}}{\varepsilon} with the error without an attack, knε\frac{k\sqrt{n}}{\varepsilon}, gives the threshold m=O(nk)m=O\left(\sqrt{nk}\right). The output-manipulation contribution Θ(mkε)\Theta\left(\frac{mk}{\varepsilon}\right) instead gives m=O(n)m=O\left(\sqrt{n}\right). These comparisons yield Corollary 5.2.

Corollary 5.2 (Comparison with output manipulation). For RAPPOR, PI-RAPPOR, and Hadamard Response, selective dropout introduces no additional asymptotic error when

m=O(nk).(20)m=O\left(\sqrt{nk}\right). \tag*{(20)}

In contrast, output manipulation introduces no additional asymptotic error only when m=O(n)m=O\left(\sqrt{n}\right).

The mechanisms in Corollary 5.2 tolerate a k\sqrt{k} larger corruption budget under selective dropout than under output manipulation when k≤nk\le n. For k>nk>n, the selective-dropout budget saturates at nn, giving a n\sqrt{n} rather than k\sqrt{k} budget gain. For HST, both attacks are absorbed by the error without an attack at the same threshold m=O(nk)m=O\left(\sqrt{nk}\right). Thus, the benefit of verification depends on the mechanism: (PI-)RAPPOR and Hadamard Response exhibit an asymptotic gap between the two attacks, whereas the worst-case error rate is unchanged for HST. The experiments in Section 7, Figure 2, illustrate this distinction: for PI-RAPPOR and Hadamard Response, the gap grows with the domain, whereas the errors under output manipulation and selective dropout remain within a constant factor for HST.

Figure 2. Mean ℓ1\ell_1 error of the estimated count histogram over ten trials at ε=1\varepsilon= 1. In attack trials, the adversary controls 10% of clients. OM and SD denote output manipulation and selective dropout; OM-CC adds the histogram-clipping consistency check for Hadamard Response.

Post-Hoc Consistency Checks

The preceding sections improve robustness by requiring clients to prove correct randomization. When changing the client protocol is not feasible, the server must instead work with reports that may have been manipulated. We develop two consistency checks for RAPPOR and Hadamard Response that mitigate output manipulation using statistical properties of honest reports. Unlike verification, these checks do not certify each report’s computation; they improve robustness through server-side processing alone. They require no client-side changes or cryptography and can be applied post-hoc, at any time after collection, including to reports from existing deployments.

As in Section 3, nn is the number of clients and mm bounds the number of corrupted clients. For the RAPPOR check, we assume that malicious reports are fixed independently of the honest clients’ random reports. The checks use statistical properties that hold with high probability for honest reports. The RAPPOR check removes reports with unusually large pairwise correlations; the Hadamard Response check clips unusually large counts in the response histogram. The guarantees below quantify the remaining error under output manipulation. As in Equation (19), error is measured against the count histogram of all clients’ inputs, including those of corrupted clients. The concentration arguments use Hoeffding’s and Bernstein’s inequalities [30].

Consistency Check for RAPPOR

Let y0,…,yn−1∈{a,b}ky_0,\ldots,y_{n-1}\in\{a,b\}^{k} be the decoded RAPPOR reports from (4), with a=−1eε/2−1a=-\frac{1}{e^{\varepsilon/2}-1} and b=eε/2eε/2−1b=\frac{e^{\varepsilon/2}}{e^{\varepsilon/2}-1}. For each pair of decoded reports with i≠ji\ne j, the server checks whether

∣⟨yi,yj⟩∣≤τ,τ=b2+b(b−a)2klog⁡n.(21)\lvert\langle y_i,y_j\rangle\rvert\le\tau,\qquad\tau=b^2+b(b-a)\sqrt{2k\log n}. \tag*{(21)}

The following lemma bounds the probability that an honest report fails this check against a fixed vector.

Lemma 6.1. Suppose y∈{a,b}ky\in\{a,b\}^{k} is obtained from an honest execution of RAPPOR, and let z∈{a,b}kz\in\{a,b\}^{k} be a fixed vector. Then, Pr⁡[∣⟨y,z⟩∣≥τ]≤2n4\Pr[\lvert\langle y,z\rangle\rvert\ge\tau]\le\frac{2}{n^4}.

Proof sketch of Lemma 6.1. All but the input coordinate give independent mean-zero randoms. Hoeffding’s inequality controls their sum, while the input coordinate contributes at most b2b^2. See Appendix B.4 for the full proof. □

For malicious reports fixed independently of the honest clients’ random reports, a union bound shows that no pair involving an honest report fails the check except with probability at most 2n2\frac{2}{n^2}. The server therefore retains exactly the decoded reports whose absolute inner product with every other original decoded report is at most τ\tau, and sums them to obtain a histogram estimate.

A full check takes O(n2k)O(n^2k) time. If an upper bound 1≤m≤n1\le m\le n on the number of corrupted clients is known, the server can reduce the number of pairs it checks as follows. After all reports are fixed, the server samples s=min⁡{n,nkm}s=\min\left\{n,\frac{n\sqrt{k}}{m}\right\} reports uniformly without replacement, independently of the reports. It compares each of the ss sampled reports with every other original report and discards both reports in every detected violating pair. This takes O(n2kmin⁡{1,kn})O\left(n^2k\min\left\{1,\frac{\sqrt{k}}{\sqrt{n}}\right\}\right) time and preserves the full check’s expected-error bound, where the expectation also includes the server’s sampling.

Theorem 6.2. For 0<ε≤10<\varepsilon\le1, the full and sampled RAPPOR consistency checks have O(knε+mk14log⁡(n)14ε)O\left(\frac{k\sqrt{n}}{\varepsilon}+\frac{mk^{\frac{1}{4}}\log(n)^{\frac{1}{4}}}{\varepsilon}\right) expected ℓ1\ell_1 error under output manipulation, with malicious reports fixed independently of the honest reports.

Proof sketch of Theorem 6.2. With high probability, no pair involving an honest report violates the check, so honest reports survive. In the full check, the retained malicious reports have bounded pairwise correlations, which control the ℓ2\ell_2 norm of their sum. Cauchy–Schwarz converts this bound to ℓ1\ell_1 error, to which we add honest sampling error. For the sampled check, fix reports for which no pair involving an honest report violates the check. The expected number of violating pairs whose reports both survive, over the server’s sample of ss reports, is at most mn2εs\frac{m n}{2\varepsilon s}. This bound suffices to obtain the same expected-error rate. Appendix B.5 gives the full proof. □

Consistency Check for Hadamard Response

Let y=(y0,…,yn−1)∈{0,…,K−1}ny=(y_0,\ldots,y_{n-1})\in\{0,\ldots,K-1\}^n denote the Hadamard Response reports, and let c(y)∈Z≥0Kc(y)\in\mathbb{Z}_{\ge0}^K be their report histogram, where c(y)j=∑i=0n−11[yi=j]c(y)_j=\sum_{i=0}^{n-1}\mathbf{1}[y_i=j]. This histogram counts report symbols, not the clients’ input values. The consistency check limits each count using the threshold

THR=2n(2eε(eε+1)K)+5log⁡(nK).(22)T_{\mathrm{HR}}=2n\left(\frac{2e^\varepsilon}{(e^\varepsilon+1)K}\right)+5\log(nK). \tag*{(22)}

This limits the contribution of any one report symbol to the estimator. Concentration of independent report indicators gives the following guarantee.

Lemma 6.3. Suppose y0,…,yn−1y_0,\ldots,y_{n-1} are obtained from an honest execution of Hadamard Response. Then, Pr⁡[∀j∈{0,…,K−1}, c(y)j≤THR]≥1−1n\Pr\left[\forall j\in\{0,\ldots,K-1\},\ c(y)_j\le T_{\mathrm{HR}}\right]\ge1-\frac{1}{n}.

Proof sketch of Lemma 6.3. Each count is a sum of independent Bernoulli indicators and has mean at most 2neε(eε+1)K\frac{2ne^\varepsilon}{(e^\varepsilon+1)K}. Bernstein’s inequality and a union bound over the KK counts give the claim. See Appendix B.6 for the full proof. □

The server clips each count to c~(y)j=min⁡{c(y)j,THR}\tilde{c}(y)_j=\min\{c(y)_j,T_{\mathrm{HR}}\}, then applies the standard Hadamard Response decoder to the clipped histogram c~(y)\tilde{c}(y). The resulting estimator has the following expected-error bound under output manipulation:

Theorem 6.4. For 0<ε≤10<\varepsilon\le1, Hadamard Response with the above consistency check has O(knε+kmlog⁡(nk)ε+kmnε)O\left(\frac{k\sqrt{n}}{\varepsilon}+\frac{k\sqrt{m\log(nk)}}{\varepsilon}+\frac{\sqrt{kmn}}{\varepsilon}\right) expected ℓ1\ell_1 error under output manipulation.

Proof sketch of Theorem 6.4. Let cHc_H be the histogram of honest reports alone. With high probability, every entry of cHc_H is at most THRT_{\mathrm{HR}}. On this event, clipping leaves the honest counts intact, and the residual c~(y)−cH\tilde{c}(y)-c_H has ℓ1\ell_1 norm at most mm and ℓ∞\ell_\infty norm at most THRT_{\mathrm{HR}}. Hadamard orthogonality bounds its decoded ℓ2\ell_2 norm, and Cauchy–Schwarz bounds its ℓ1\ell_1 contribution. Adding honest sampling error gives the result. Appendix B.7 contains the full proof. □

The server-side consistency check adds O(n+k)O(n+k) work to the O(n+klog⁡k)O(n+k\log k) runtime of standard Hadamard Response. The check also generalizes to protocols based on other design matrices, such as Projective Geometry Response [16].

Discussions and Limitations

Server-side consistency checks offer an alternative when changing client implementations is impractical. They require no client-side cryptography and can be applied to reports already collected. Their error guarantees are weaker than those under selective dropout with verification: RAPPOR’s check has an O(mk3/4(log⁡n)1/4ε)O\left(\frac{m k^{3/4}(\log n)^{1/4}}{\varepsilon}\right) attack term, and Hadamard Response’s check has an O(kmn+kmlog⁡(nk)ε)O\left(\frac{\sqrt{kmn}+k\sqrt{m\log(nk)}}{\varepsilon}\right) term, compared with Θ(mkε)\Theta\left(\frac{m\sqrt{k}}{\varepsilon}\right) under selective dropout.

The full RAPPOR check requires O(n2k)O(n^2k) work; given a corruption budget m≥1m\ge1, the sampled variant reduces this to O(n2kmin⁡{1,km})O\left(n^2k\min\left\{1,\frac{\sqrt{k}}{m}\right\}\right) with the same expected-error bound. Even this cost can be substantial for large populations or domains. Constant-factor distance approximations need not preserve the much smaller inner-product tolerance used by the RAPPOR check. The RAPPOR analysis also relies on independent report coordinates, so its guarantee does not directly extend to PI-RAPPOR. By contrast, the Hadamard check adds only O(n+k)O(n+k) work to aggregation. Further reducing the server-side cost and developing better checks for both mechanisms, as well as comparable guarantees for PI-RAPPOR and other LDP mechanisms, remain open questions.

Experiments

We show that our verifiable PI-RAPPOR and Hadamard Response implementations from Section 4 are lightweight and efficient. We also evaluate the effects of selective dropout and output manipulation on the accuracy of PI-RAPPOR, Hadamard Response, and HST across input distributions, as well as the accuracy obtained using the server-side consistency checks for RAPPOR and Hadamard Response from Section 6.

Experimental Setup

Implementation and platform. We implement the mechanisms and verification circuits in Rust, using arkworks 0.4 [2], Groth16 [21] over BLS12-381, and Poseidon-based commitments [20]. The per-client benchmark requests 32 CPUs and 64 GiB of memory on an Ubuntu 22.04 machine with two Intel Xeon Platinum 8358 processors at 2.60 GHz (64 physical cores). We evaluate k∈{3,15,63,255,1023,4095}k\in\{3,15,63,255,1023,4095\}, giving Hadamard output alphabets of size K=k+1K=k+1. Other domain sizes are supported by padding to K=2⌈log⁡2(k+1)⌉K=2^{\lceil\log_2(k+1)\rceil} and using the first kk nonzero Hadamard rows. Both circuits use γ=12\gamma=12 bits for random threshold comparisons, and the accuracy estimators correct for the resulting rounded probabilities.

Input distributions. We use uniform, truncated geometric with weights proportional to 0.8⋅2j0.8\cdot2^j, and truncated Zipf with weights proportional to (j+1)−1.1(j+1)^{-1.1}, normalized over j∈{0,…,k−1}j\in\{0,\ldots,k-1\}. For the Kosarak clickstream dataset from the SPMF repository2 [18], we count page occurrences, retain the k−1k-1 most frequent pages, and pool the rest into an Other category. Client inputs are sampled independently with replacement from these distributions; within each trial, all mechanisms use the same input seed, independently of mechanism randomness.

Error metric. We measure the ℓ1\ell_1 error ∥F^−F(x)∥1\lVert\widehat{F}-F(x)\rVert_1 of the estimated count histogram against all nn inputs, including those of dropped clients. We sum the decoded reports that are submitted without normalizing by their number or projecting onto a probability simplex.

Per-client Latency

Measurement procedure. We benchmark the verifiable protocols for PI-RAPPOR and Hadamard Response from § 4 over the six domain sizes and ε∈{18,14,12,1,2,4,8}\varepsilon\in\{\frac{1}{8}, \frac{1}{4}, \frac{1}{2}, 1, 2, 4, 8\}, repeating each of the 84 configurations 100 times. Each trial performs a fresh Groth16 setup and verification-key preprocessing for both proofs, followed by one report-generation and verification execution. Setup is measured separately and excluded from online latency. Prover time includes commitment computation, native report computation, and generation of the input-commitment and evaluation proofs; verifier time includes verification of both proofs but excludes aggregation.

Communication model. We combine measured computation with modeled transmission for the three messages: client commitments and their knowledge proof, server randomness shares, and the report and its evaluation proof. The symmetric network profiles are WAN (20 ms RTT, 20 Mbit/s), mobile (50 ms, 10 Mbit/s), and constrained mobile (100 ms, 1 Mbit/s). Messages use canonical compressed serialization, with server bit shares represented as field elements; the model excludes connection establishment and transport overhead.

Results. Figure 1 shows modest variation across kk and ε\varepsilon. Across configurations, mean prover and verifier times are 233.2–247.5 ms and 13.8–15.5 ms for PI-RAPPOR, and 104.2–113.5 ms and 9.1–10.6 ms for Hadamard Response, respectively. The two proof circuits together contain 6,941–7,001 constraints for PI-RAPPOR and 2,374–2,544 for Hadamard Response, explaining the small change in cryptographic costs from k=3k=3 to k=4095k=4095.

Total communication is 992 bytes for PI-RAPPOR and 928–1,248 bytes for Hadamard Response. Mean online latency on WAN, mobile, and constrained mobile is 277.8–293.1 ms, 323.2–338.5 ms, and 405.3–420.7 ms for PI-RAPPOR; the respective Hadamard Response ranges are 143.7–154.1 ms, 189.0–199.6 ms, and 270.7–283.6 ms. On slower networks, the 1.5 round trips account for much of the increased latency because messages remain small. Setup takes 268.6–284.2 ms for PI-RAPPOR and 139.7–148.7 ms for Hadamard Response.

Comparison with Vε\varepsilonrity. Vε\varepsilonrity [5 Section 9.2] reports 1,423.50 s of online client computation and 1,472.7 s of server computation for binary randomized response, approximately 23.7 and 24.5 minutes, respectively, per client. Our plaintext verification circuits instead handle categorical inputs with up to 4,095 values at millisecond-scale prover and verifier costs.

At the server, one million separate invocations at Vε\varepsilonrity’s reported server time would take about 50 years of serial execution; extending an HE-based design to our more complex categorical randomizers could increase this to the scale of a century. Projecting our measured verification times for both proofs to one million reports gives approximately 2.5–4.3 hours, illustrating the computational advantage while retaining the quantified robustness benefit against selective dropout.

Figure 1 (PDF p. 11). Mean modeled per-client online latency (ms) over 100 trials, including both the input-commitment and evaluation proofs. Setup and aggregation are excluded.

Robustness Against Different Attacks

For the class-size sweep, we fix ε=1\varepsilon=1 and vary kk over the domain sizes above. Appendix A.§ 1 reports the RAPPOR results, including the full and sampled consistency checks. For PI-RAPPOR, Hadamard Response, and HST, we vary n∈{104,105,106}n \in\{10^4,10^5,10^6\}. For each configuration and input distribution, we run ten independent randomized trials comparing a no-attack setting (Clean), selective dropout (SD), and output manipulation (OM) using the same inputs and valid randomized reports; we report the mean ℓ1\ell_1 error. In both attacks, the first m=0.1nm=0.1n clients are corrupted before reports or HST public vectors are sampled. We use this corruption rate to make the attacks visible and apply the strategies in Theorem 5.1.

The Clean setting measures estimation error when all clients submit correctly randomized reports. The SD setting evaluates the attack permitted by our verification framework (§ 4), while the OM setting evaluates unrestricted output manipulation without verification. For Hadamard Response, we also evaluate the histogram-clipping consistency check from § 6, labeled OM-CC.

Results. Figure 2 shows the mechanism-dependent distinction predicted by our analysis. PI-RAPPOR and Hadamard Response show a much larger separation than HST as the domain grows. At n=106n=10^6 and k=4095k=4095, across all four distributions, PI-RAPPOR’s selective-dropout error is only 1.18–1.19 times the Clean error, whereas output manipulation produces 121.5–122.3 times the Clean error. For Hadamard Response, selective dropout and output manipulation produce 1.26–1.29 and 125–126 times the Clean error, respectively. Thus, by restricting the adversary to selective dropout rather than output manipulation, our proposed verification framework reduces the error by about two orders of magnitude in these settings, bringing it close to the Clean error.

These trends follow Corollary 5.2: for (PI-)RAPPOR and Hadamard Response, selective dropout preserves the error rate without an attack when the corrupted fraction is O(kn)O\left(\sqrt{\frac{k}{n}}\right), whereas output manipulation requires O(1n)O\left(\frac{1}{\sqrt{n}}\right). At a fixed 10% corruption rate, increasing kk brings selective-dropout error closer to the Clean error while output manipulation remains far above it. Increasing nn at fixed kk lowers both tolerable fractions, making the attacks more pronounced relative to the baseline.

For Hadamard Response, the histogram-clipping consistency check substantially reduces the error from the repeated-report attack: at n=106n = 10^6 and k=4095k = 4095, mean error is 1.13–1.15 times the Clean error across the four distributions. At k=3k = 3, the clipping threshold is too large to suppress the attack at the evaluated corruption rate, so the checked and unchecked errors coincide. As the output alphabet grows, the threshold decreases relative to the number of repeated malicious reports, making clipping more effective.

For HST, the errors under selective dropout and output manipulation remain within a constant factor: with uniform inputs, n=106n = 10^6, and k=4095k = 4095, their mean errors are 1.17 and 1.70 times the Clean error, respectively.

Appendix A.§ 2 presents results for varying the corrupted fraction. As the domain size increases, selective-dropout error remains close to the Clean error over a wider range of corrupted fractions, consistent with Corollary 5.2.

Comparison with HST. At ε=1\varepsilon= 1 and a 10% corruption rate, HST’s mean output-manipulation error is 1.13–2.71 times the selective-dropout error of verified PI-RAPPOR and 1.03–2.58 times that of verified Hadamard Response across our evaluated configurations. Appendix A.§ 3 reports the full ratios. Our current verified implementations transmit more bytes than bit-packed HST over the evaluated domain sizes, reflecting a tradeoff between accuracy and communication.

Conclusion

Correct execution does not prevent selective withholding of valid outputs. For (PI-)RAPPOR and Hadamard Response, restricting the adversary to selective dropout rather than output manipulation reduces the attack-dependent error by a factor of Θ(k)\Theta\left(\sqrt{k}\right); HST exhibits no such asymptotic separation.

Thus, verification can improve robustness without eliminating selective dropout, with mechanism-dependent benefits. Our lightweight framework uses commitments and proofs of plaintext evaluation to prevent output manipulation while allowing selective dropout. When client changes are impractical, server-side consistency checks offer a post-hoc alternative with weaker error guarantees.

Future work includes extending our selective-dropout analysis to other LDP mechanisms and developing stronger and more scalable consistency checks. More broadly, our findings highlight the need for robustness analyses of verifiable DP to account for selective dropout.

References

A Additional Experiments

Additional Results for RAPPOR

We evaluate RAPPOR using the domain sizes, input distributions, error metric, and attack strategies described in § 7. We fix ε=1\varepsilon= 1 and use n=104n = 10^{4} clients due to computational resource constraints, with m=0.1nm = 0.1n corrupted clients in attack trials. Each configuration is evaluated over ten independent randomized trials. We compare a no-attack setting (Clean), selective dropout (SD), and output manipulation (OM), and evaluate the full and sampled consistency checks from § 6, labeled OM-CC and OM-CC-S, respectively.

At n=104n = 10^{4} and k=4095k = 4095, Figure 3 shows that selective-dropout error is close to the Clean error across the four distributions, while output manipulation produces about 12.1 times that error.

Figure 3. Mean ℓ1\ell_1 error of the estimated count histogram for RAPPOR over ten trials at n=104n = 10^{4} and ε=1\varepsilon= 1. In attack trials, the adversary controls 10% of clients. OM and SD denote output manipulation and selective dropout; OM-CC and OM-CC-S add the full and sampled consistency checks, respectively.

Both the full and sampled consistency checks yield mean errors approximately 5% below the Clean error at k=4095k = 4095. Filtering removes noisy contributions as well as malicious reports; at these parameters, the reduction in sampling noise can outweigh the missing-input bias. The sharp improvement between k=63k = 63 and k=255k = 255 is consistent with threshold-based filtering of the repeated-report attack. At n=104n = 10^{4} and ε=1\varepsilon= 1, the expected squared norm of the repeated report increases from approximately 248 to 1,000, while the correlation threshold increases from approximately 360 to 718. This makes repeated reports much more likely to violate the check.

Varying the Corrupted Fraction

In Figure 4, the selective-dropout curve separates from the Clean curve at larger corrupted fractions as kk increases, consistent with the threshold scale m=Θ(nk)m = \Theta\left(\sqrt{nk}\right) from Corollary 5.2. For fixed nn, this corresponds to mn=Θ(kn)\frac{m}{n} = \Theta\left(\sqrt{\frac{k}{n}}\right). For example, at mn=1%\frac{m}{n} = 1\% and k=3k = 3, selective-dropout error is about 4.0 and 3.6 times the error without an attack for PI-RAPPOR and Hadamard Response, respectively; at k=4095k = 4095, it remains close to that error for both. The HST curves show the same shift with kk, while its output-manipulation error remains closer to its selective-dropout error.

Figure 4. Mean ℓ1\ell_1 error of the estimated count histogram over ten trials with uniform inputs, n=106n = 10^{6}, and ε=1\varepsilon= 1.

For Hadamard Response, the error with the consistency check matches the unchecked output-manipulation error while the total count in the attacked report bin remains below the clipping threshold. For fixed nn and kk, this threshold does not depend on mm. Once the count exceeds the threshold, additional copies are clipped, limiting the growth of the attack’s contribution. As kk increases, the threshold decreases, so clipping becomes effective at smaller corrupted fractions. At k=3k = 3, the check does not reduce the attack’s error over the evaluated range; at k=4095k = 4095, checked error remains approximately 1.13–1.17 times the Clean error throughout the sweep.

Comparison with HST

Table 2 compares HST under output manipulation with verified PI-RAPPOR and Hadamard Response under selective dropout, using the class-sweep experiments in § 7. Each ratio is computed from the corresponding ten-trial mean ℓ1\ell_1 errors of the estimated count histograms at ε=1\varepsilon= 1 and m=0.1nm = 0.1n. For each nn and kk, the table gives the minimum and maximum across the four input distributions. Within each cell, the upper line gives the ratio for PI-RAPPOR and the lower line gives the ratio for Hadamard Response. These results describe the evaluated attacks and parameter settings; they do not establish an asymptotic separation between HST and the verified mechanisms.

PI-RAPPOR HRn=104n = 10^{4}n=105n = 10^{5}n=106n = 10^{6}
k=3k = 31.895–2.711<br>1.742–2.5812.109–2.660<br>1.794–2.2681.919–2.553<br>1.722–2.104
k=15k = 151.896–1.960<br>1.625–1.7382.124–2.305<br>1.654–1.8002.081–2.249<br>1.678–1.796
k=63k = 631.467–1.607<br>1.253–1.3122.001–2.094<br>1.651–1.7432.166–2.221<br>1.806–1.911
k=255k = 2551.207–1.259<br>1.084–1.1311.717–1.767<br>1.424–1.4832.148–2.187<br>1.760–1.829
k=1023k = 10231.139–1.190<br>1.027–1.0621.333–1.349<br>1.172–1.1952.000–2.037<br>1.587–1.650
k=4095k = 40951.126–1.136<br>1.035–1.0421.177–1.197<br>1.069–1.0761.570–1.589<br>1.315–1.358

Table 2. Ratios of mean ℓ1\ell_1 errors of the estimated count histograms at ε=1\varepsilon= 1 with m=0.1nm = 0.1n corrupted clients. In each cell, the upper line divides HST’s output-manipulation error by the selective-dropout error of verified PI-RAPPOR; the lower line uses verified Hadamard Response (HR). Each range gives the minimum and maximum across Uniform, Geometric(0.8), Zipf(1.1), and Kosarak inputs, computed from ten-trial means for each distribution; the ranges are not confidence intervals. Inputs are matched across mechanisms. A ratio above one indicates lower error for the verified mechanism. Errors include sampling error.

Proofs

Proof of Theorem 3.2

Proof. After receiving rSerr^{\mathrm{Ser}}, the malicious client runs the honest client algorithm independently

T=κp(κ)(23)T = \kappa p(\kappa) \tag*{(23)}

times, each time with fresh client randomness. For each execution, it uses ComputeReport to compute the corresponding report yy from its local view. It sends the response from the first trial for which ComputeReport returns a report in SS; if no such response is found, it sends the response from the first trial. Each trial follows the prescribed report and proof computations; the deviation is choosing which trial to submit rather than submitting the result of a single trial.

For each server challenge satisfying the assumptions, the probability that none of the TT trials generates a report in SS is at most

(1−1p(κ))T≤e−κ.(24)\left(1-\frac{1}{p(\kappa)}\right)^T \leq e^{-\kappa}. \tag*{(24)}

By a union bound over the TT trials, the probability that ComputeReport computes any report incorrectly remains negligible. The selected response is generated by the honest client algorithm and its report satisfies y=f(x,rCli,rSer)y=f(x,r^{\mathrm{Cli}},r^{\mathrm{Ser}}) for that execution’s randomness, so the associated proof remains valid rather than being forged. By correctness of Π\Pi, rejection of an honestly generated response has negligible probability; a union bound over the TT trials preserves this guarantee for the selected response. Accounting also for the negligible probability of a server challenge that fails the assumptions, the server accepts the selected response with report y∈Sy\in S except with negligible probability. In contrast, after averaging over the server’s challenge, an honest execution generates a report in SS with probability at most 12+negl⁡(κ)\frac{1}{2}+\operatorname{negl}(\kappa) by Equation (15). The difference on the event SS gives the claimed total-variation-distance bound. □

Proof of Theorem 4.1

Proof. Completeness follows directly from correctness of the commitment and completeness of the two ZKPoKs. For accepted-output integrity, the first proof establishes knowledge of a valid opening of cic_i before the server samples riSerr_i^{\mathrm{Ser}}. Binding fixes the committed input and client randomness share. The second proof then guarantees that an accepted yiy_i satisfies Equation (18) for that same input and randomness share. Therefore, after receiving riSerr_i^{\mathrm{Ser}}, a client has only one report that can be accepted for its commitment: it may submit that report or drop out.

For privacy, the server’s view of an honest client consists of (ci,πiin,riSer,yi,πieval)(c_i,\pi_i^{\mathrm{in}},r_i^{\mathrm{Ser}},y_i,\pi_i^{\mathrm{eval}}). Hiding of the commitment and zero knowledge of the proofs ensure that the commitment and proofs leak no additional information about (xi,riCli)(x_i,r_i^{\mathrm{Cli}}) beyond the public transcript (riSer,yi)(r_i^{\mathrm{Ser}},y_i). By the distributed-randomness requirement, (riSer,yi)(r_i^{\mathrm{Ser}},y_i) is ϵ\epsilon-computationally locally private with respect to xix_i. Closure under PPT post-processing gives the same guarantee for the complete server view. □

Proof of Theorem 5.1

Common bounds. Write vˉi\bar{v}_i for a decoded report and E0=∑i=0n−1(vi−ϵxi)E_0=\sum_{i=0}^{n-1}(v_i-\epsilon x_i). For all four mechanisms and 0<ϵ≤10<\epsilon\leq1, each centered coordinate has variance Θ(ϵ−2)\Theta(\epsilon^{-2}) and fourth moment O(ϵ−4)O(\epsilon^{-4}): for (PI-)RAPPOR this follows from the Bernoulli marginals, and for HR and HST from vi,j∈{−λe,λe}v_{i,j}\in\{-\lambda_e,\lambda_e\}, λe=eϵ+1eϵ−1\lambda_e=\frac{e^{\epsilon}+1}{e^{\epsilon}-1}, and E[vi,j]=1[xi=j]\mathbb{E}[v_{i,j}]=1[x_i=j]. Thus a sum WW of r≥1r\geq1 independent centered coordinates has E[W2]=Θ(rϵ2)\mathbb{E}[W^2]=\Theta\left(\frac{r}{\epsilon^2}\right) and E[W4]=O(r2ϵ4)\mathbb{E}[W^4]=O\left(\frac{r^2}{\epsilon^4}\right). Cauchy–Schwarz and Paley–Zygmund applied to W2W^2 give

E∣W∣=Θ(rϵ),E∥E0∥1=Θ(knϵ).(25)\mathbb{E}|W|=\Theta\left(\frac{\sqrt{r}}{\epsilon}\right),\qquad\mathbb{E}\|E_0\|_1=\Theta\left(\frac{k\sqrt{n}}{\epsilon}\right). \tag*{(25)}

Only independence across clients is used; for HST the expectation also includes the public randomness.

Let L=max⁡D⊆C∥∑i∈Dvi∥1L=\max_{D\subseteq C}\|\sum_{i\in D}v_i\|_1. Every realized report has ∥vi∥2=Θ(kϵ)\|v_i\|_2=\Theta\left(\frac{\sqrt{k}}{\epsilon}\right). For an independent uniform sign vector s∈{−1,1}ks\in\{-1,1\}^k, symmetry and Khintchine’s inequality imply

Es(⟨s,vi⟩)+=12Es∣⟨s,vi⟩∣=Θ(kϵ).(26)\mathbb{E}_s(\langle s,v_i\rangle)_+=\frac{1}{2}\mathbb{E}_s|\langle s,v_i\rangle|=\Theta\left(\frac{\sqrt{k}}{\epsilon}\right). \tag*{(26)}

Dropping reports with nonnegative projection therefore gives EL=Ω(mkϵ)\mathbb{E}L=\Omega\left(\frac{m\sqrt{k}}{\epsilon}\right). Taking D=CD=C gives the other lower bound: for each coordinate, write the sum as μ+W\mu+W, where WW is centered. Since E∣μ+W∣≥max⁡{∣μ∣,E∣W∣}≥12E∣W∣\mathbb{E}|\mu+W|\geq\max\{|\mu|,\mathbb{E}|W|\}\geq\frac{1}{2}\mathbb{E}|W|, Equation (25) yields EL=Ω(kmϵ)\mathbb{E}L=\Omega\left(\frac{k\sqrt{m}}{\epsilon}\right). Together these imply EL=Ω(mk+kmϵ)\mathbb{E}L=\Omega\left(\frac{m\sqrt{k}+k\sqrt{m}}{\epsilon}\right).

To pass from perturbation to total error, use F^−F(x)=E0−∑i∈Dvi\widehat{F}-F(x)=E_0-\sum_{i\in D}v_i. An upper bound of the same order on EL\mathbb{E}L, together with m≤nm\leq n, gives O(kn+mkϵ)O\left(\frac{k\sqrt{n}+m\sqrt{k}}{\epsilon}\right) total error. For the lower bound, full participation attains the error without an attack, while the selective dropout attack in Theorem 5.1 satisfies

Err⁡1≥E[−⟨s,F^−F(x)⟩]=∑i∈CE(⟨s,vi⟩)+=Ω(mkϵ),(27)\begin{aligned} \operatorname{Err}_1\geq\mathbb{E}[-\langle s,\widehat{F}-F(x)\rangle] \\ &=\sum_{i\in C}\mathbb{E}(\langle s,v_i\rangle)_+=\Omega\left(\frac{m\sqrt{k}}{\epsilon}\right), \tag*{(27)} \end{aligned}

because ss is independent of the mean-zero E0E_0. The maximum of the two lower bounds is at least half their sum. The attack costs O(mk)O(mk) operations; when m=0m=0, only the error without an attack remains.

(PI-)RAPPOR

Proof. Set a=α0=(1+eϵ/2)−1a=\alpha_0=(1+e^{\epsilon/2})^{-1} and Δ=1−2a=Θ(ϵ)\Delta=1-2a=\Theta(\epsilon), so yj=Zj−aΔy_j=\frac{Z_j-a}{\Delta}. For RAPPOR, coordinate independence gives ∥Cov⁡(y∣x)∥op=O(ϵ−2)\|\operatorname{Cov}(y\mid x)\|_{\mathrm{op}}=O(\epsilon^{-2}). For PI-RAPPOR, let UU be uniform on Rk\mathbb{R}^k. The bijection (u,v)↦(u+v,u+vℓ)(u,v)\mapsto(u+v,u+v\ell) for j≠ℓj\ne\ell maps I=1[U∈B(j)]I=1[U\in B(j)] pairwise independent Bernoulli(a)(a) variables. The report density relative to UU is at most eϵ/2e^{\epsilon/2} by Equation (6); hence, for w∈Rkw\in\mathbb{R}^k,

Var⁡(⟨w,Z⟩∣x)≤E[⟨w,Z−a1⟩2∣x]≤eϵ/2a(1−a)∥w∥22.\operatorname{Var}(\langle w,Z\rangle\mid x)\leq\mathbb{E}[\langle w,Z-a1\rangle^2\mid x]\leq e^{\epsilon/2}a(1-a)\|w\|_2^2.

Dividing by Δ2\Delta^2 gives the same covariance bound for PI-RAPPOR. Both mechanisms also satisfy ∥y∥∞=O(ϵ−1)\|y\|_\infty=O(\epsilon^{-1}).

By norm duality, with ϕi(s)=⟨s,vi⟩\phi_i(s)=\langle s,v_i\rangle,

L=max⁡s∈{−1,1}k∑i∈Cϕi(s).L=\max_{s\in\{-1,1\}^k}\sum_{i\in C}\phi_i(s).

The covariance bound and Eyi=exi\mathbb{E}y_i=e_{x_i} give Eϕi(s)=O(kε)\mathbb{E}\phi_i(s)=O\left(\frac{\sqrt{k}}{\varepsilon}\right) uniformly in ss. Symmetrization and contraction for t↦t+t\mapsto t_+ [3], with independent Rademacher signs σi\sigma_i, give

EL≤O(mkε)+Emax⁡s∑i∈C(ϕi(s)−Eϕi(s))≤O(mkε)+O(∑j=0k−1E∣∑i∈Cσiyi,j∣)=O(mk+kmε).\begin{aligned} \mathbb{E}L\le O\left(\frac{m\sqrt{k}}{\varepsilon}\right)+\mathbb{E}\max_s\sum_{i\in C}(\phi_i(s)-\mathbb{E}\phi_i(s)) \\ &\le O\left(\frac{m\sqrt{k}}{\varepsilon}\right)+O\left(\sum_{j=0}^{k-1}\mathbb{E}\left|\sum_{i\in C}\sigma_i y_{i,j}\right|\right) \\ &=O\left(\frac{m\sqrt{k}+k\sqrt{m}}{\varepsilon}\right). \end{aligned}

The last step uses Eσ(∑iσiyi,j)2=∑iyi,j2=O(mε2)\mathbb{E}_{\sigma}\left(\sum_i\sigma_i y_{i,j}\right)^2=\sum_i y_{i,j}^2=O\left(\frac{m}{\varepsilon^2}\right). The common lower bounds and total-error argument complete the SD proof.

For OM, each report has norm O(kε)O\left(\frac{k}{\varepsilon}\right), so replacing mm reports changes the estimate by O(mkε)O\left(\frac{mk}{\varepsilon}\right). For a matching lower bound, all corrupted clients submit the all-one bit report (the pair (0,0)(0,0) for PI-RAPPOR). Its decoded vector is b1b\mathbf{1}, where b=1−aΔb=\frac{1-a}{\Delta} and b−1=Θ(ε−1)b-1=\Theta(\varepsilon^{-1}). The mean error is mb1−∑i∈Ceximb\mathbf{1}-\sum_{i\in C}e_{x_i}, whose norm is mbk−m=Ω(mkε)mbk-m=\Omega\left(\frac{mk}{\varepsilon}\right); Jensen’s inequality gives the same lower bound on expected error. Honest reporting is also an allowed OM strategy and supplies the knε\frac{k\sqrt{n}}{\varepsilon} lower bound. □

Hadamard Response

Proof. Write h(y)=HK[1:k,y]h(y)=H_K[1:k,y], so vi=λεh(yi)v_i=\lambda_\varepsilon h(y_i). Let AyA_y count corrupted reports equal to yy, and AyDA_y^D count those in DD. Cauchy–Schwarz and Hadamard orthogonality give, for every DD,

∥∑i∈Dh(yi)∥≤k∥HKAD∥2≤kK(∑y(AyD)2)1/2.\left\|\sum_{i\in D}h(y_i)\right\|\le\sqrt{k}\|H_KA^D\|_2\le\sqrt{kK}\left(\sum_y(A_y^D)^2\right)^{1/2}.

Since Pr⁡[yi=y]≤2K\Pr[y_i=y]\le\frac{2}{K} and reports are independent,

E∑yAy2=m+∑i≠i′Pr⁡[yi=yi′]≤m+2m(m−1)K.\mathbb{E}\sum_y A_y^2=m+\sum_{i\ne i'}\Pr[y_i=y_{i'}]\le m+\frac{2m(m-1)}{K}.

Jensen’s inequality, K=Θ(k)K=\Theta(k), and λε=Θ(ε−1)\lambda_\varepsilon=\Theta(\varepsilon^{-1}) yield EL=O(mk+kmε)\mathbb{E}L=O\left(\frac{m\sqrt{k}+k\sqrt{m}}{\varepsilon}\right). The common bounds give equality in order and the SD total-error rate.

Under OM, each decoded column has norm λεk\lambda_\varepsilon k, giving the O(mkε)O\left(\frac{mk}{\varepsilon}\right) perturbation bound. Submitting column zero for every corrupted client gives mean error mλε1−∑i∈Cexim\lambda_\varepsilon\mathbf{1}-\sum_{i\in C}e_{x_i}, of norm mλεk−m=Ω(mkε)m\lambda_\varepsilon k-m=\Omega\left(\frac{mk}{\varepsilon}\right). Jensen’s inequality and the strategy in which all clients report honestly give the two total-error lower bounds. □

HST

Proof. A forged bit either equals yiy_i or −yi-y_i, so flipping it changes the estimate by −2vi-2v_i, twice the change from dropping it. Consequently, for every realization,

max⁡(yi′)i∈C∈{−1,1}m∥λε∑i∈C(yi′−yi)si∥1=2L.(28)\max_{(y'_i)_{i\in C}\in\{-1,1\}^m}\left\|\lambda_\varepsilon\sum_{i\in C}(y'_i-y_i)s_i\right\|_1=2L. \tag*{(28)}

Let SCS_C have columns sis_i, i∈Ci\in C. Either attack changes the estimate by λεSCu\lambda_\varepsilon S_Cu with ∥u∥2≤2m\|u\|_2\le2\sqrt{m}, so its norm is at most 2λεkm∥SC∥op2\lambda_\varepsilon\sqrt{km}\|S_C\|_{\mathrm{op}}. Because CC is fixed before sampling the public vectors, SCS_C has independent Rademacher entries and E∥SC∥op=O(k+m)\mathbb{E}\|S_C\|_{\mathrm{op}}=O(\sqrt{k}+\sqrt{m}) [30].

Thus both perturbations have expected norm O(km+mkε)O\left(\frac{k\sqrt{m}+m\sqrt{k}}{\varepsilon}\right), proving the total-error upper bounds. The common argument proves the SD lower bound. Flipping precisely the bits selected by the selective dropout attack doubles the sum in Equation (27), proving the OM attack term. Honest reporting supplies the remaining lower bound. □

Proof of Lemma 6.1

Proof. Outside the input coordinate xx, the products yjzjy_jz_j are independent, mean zero, and have interval width at most b(b−a)b(b-a); also ∣yxzx∣≤b2|y_xz_x|\le b^2. Hoeffding’s inequality [30] gives

Pr⁡[∣⟨y,z⟩∣≥b2+t]≤2exp⁡(−2t2kb2(b−a)2).\Pr\left[|\langle y,z\rangle|\ge b^2+t\right]\le2\exp\left(-\frac{2t^2}{kb^2(b-a)^2}\right).

Set t=b(b−a)2klog⁡nt=b(b-a)\sqrt{2k\log n} to obtain 2n4\frac{2}{n^4}. □

Proof of Theorem 6.2

Proof. The case n=1n=1 follows from the deterministic O(kε)O\left(\frac{k}{\varepsilon}\right) error bound; assume n≥2n\ge2. Let H,M\mathcal{H},\mathcal{M} index honest and malicious reports. By Lemma 6.1, independence of malicious and honest reports, and a union bound, the event EE that no pair involving an honest report violates the threshold has Pr⁡[Ec]≤2n2\Pr[E^c]\le\frac{2}{n^2}. On EE, every honest report survives either check. If VV is the retained set and BB counts violating pairs within V∩MV\cap\mathcal{M}, then

∥∑i∈V∩Myi∥22≤mkb2+m2τ+2kb2B.(29)\left\|\sum_{i\in V\cap\mathcal{M}}y_i\right\|_2^2\le mkb^2+m^2\tau+2kb^2B. \tag*{(29)}

Indeed, diagonal terms are at most kb2kb^2, consistent cross terms at most τ\tau, and each violating pair contributes at most 2kb22kb^2. The full check has B=0B=0.

For the sampled check, fix reports satisfying EE and form the graph of violating pairs, all of whose edges join malicious reports. A vertex of degree did_i survives only if the uniform sample SS, of size s=min⁡{n,⌈nkm⌉}s=\min\{n,\lceil\frac{n\sqrt{k}}{m}\rceil\}, misses all its neighbors. Thus

Pr⁡S[i survives]≤(n−dis)(ns)≤e−sdi/n,\Pr_S[i\text{ survives}]\le\frac{\binom{n-d_i}{s}}{\binom{n}{s}}\le e^{-sd_i/n},

with numerator zero if s>n−dis>n-d_i. Counting surviving edge endpoints,

ESB≤12∑i∈Mdie−sdi/n≤mn2s.(30)\mathbb{E}_SB\le\frac{1}{2}\sum_{i\in\mathcal{M}}d_ie^{-sd_i/n}\le\frac{mn}{2s}. \tag*{(30)}

since ue−su/n≤nesue^{-su/n}\le\frac{n}{es}. If s=ns=n, then B=0B=0; otherwise ESB=O(m2k)\mathbb{E}_SB=O\left(\frac{m^2}{\sqrt{k}}\right).

For either check, (29), b=O(ε−1)b=O(\varepsilon^{-1}), and τ=O(klog⁡nn)\tau=O\left(\frac{\sqrt{k\log n}}{n}\right) bound the expected squared norm of the retained malicious sum, conditional on the fixed reports in EE, by O(mk+m2klog⁡nε2)O\left(\frac{mk+m^2\sqrt{k\log n}}{\varepsilon^2}\right). Cauchy–Schwarz and Jensen’s inequality convert this to an ℓ1\ell_1 bound. Adding the unconditional error from honest clients’ reports and the norm (at most mm) of the malicious-input histogram gives

E[∥F^−F(x)∥11E]=O(knε+mk34(log⁡n)14ε).\mathbb{E}\left[\left\|\widehat{F}-F(x)\right\|_{1}\mathbf{1}_{E}\right]=O\left(\frac{k\sqrt{n}}{\varepsilon}+\frac{mk^{\frac{3}{4}}(\log n)^{\frac{1}{4}}}{\varepsilon}\right).

using m≤nm \le n. On EcE^{c}, the deterministic error bound nkb+n=O(nkε)nkb+n=O\left(\frac{nk}{\varepsilon}\right) contributes only O(knε)O\left(\frac{k}{n\varepsilon}\right). The sampled check computes at most nSnS inner products, giving O(n2kmin⁡{1,km})O\left(n^{2}k\min\left\{1,\frac{\sqrt{k}}{m}\right\}\right) time. The argument uses only ∣M∣≤m|\mathcal{M}| \le m, so also applies when the supplied budget is an upper bound. □\square

Proof of Lemma 6.3

Proof. Each count is a sum of independent Bernoulli variables with mean at most μ=np1\mu=np_{1}, where p1=2eε(eε+1)Kp_{1}=\frac{2e^{\varepsilon}}{(e^{\varepsilon}+1)K}. Bernstein’s inequality [30] gives

Pr⁡[c(y)j≥μ+t]≤exp⁡(−t22μ+2t3).\Pr\left[c(y)_{j}\ge\mu+t\right]\le\exp\left(-\frac{t^{2}}{2\mu+\frac{2t}{3}}\right).

For t=max⁡{μ,5log⁡(nK)}t=\max\{\mu,5\log(nK)\}, the exponent is at least 3t8≥158log⁡(nK)\frac{3t}{8}\ge\frac{15}{8}\log(nK). Since THR=2μ+5log⁡(nK)≥μ+tT_{\mathrm{HR}}=2\mu+5\log(nK)\ge\mu+t, a union bound over KK counts gives failure probability at most 1n\frac{1}{n}. □\square

Proof of Theorem 6.4

Proof. Write D(v)=λεHK[1:k,:]vD(v)=\lambda_{\varepsilon}H_{K}[1:k,:]v for the decoder, and let cH,cMc_{\mathcal{H}},c_{\mathcal{M}} be the honest and malicious report histograms. With probability at least 1−1n1-\frac{1}{n}, every honest count is at most THRT_{\mathrm{HR}}: the preceding Bernstein argument applies to the n−mn-m honest reports with the same upper bound μ=np1\mu=np_{1}. On this event EE, clipping gives a residual r=c~(y)−cHr=\widetilde{c}(y)-c_{\mathcal{H}} with 0≤r≤cM0\le r\le c_{\mathcal{M}}, ∥r∥1≤m\|r\|_{1}\le m, and ∥r∥∞≤THR\|r\|_{\infty}\le T_{\mathrm{HR}}. Consequently ∥r∥22≤mTHR\|r\|_{2}^{2}\le mT_{\mathrm{HR}}, and orthogonality gives

∥D(r)∥1≤λεk∥HKr∥2≤λεkmTHR.\|D(r)\|_{1}\le\lambda_{\varepsilon}\sqrt{k}\|H_{K}r\|_{2}\le\lambda_{\varepsilon}\sqrt{k mT_{\mathrm{HR}}}.

Adding the unconditional error from honest clients’ reports and the malicious-input histogram (of norm mm), using K=Θ(k)K=\Theta(k) and THR=O(nK+log⁡(nK))T_{\mathrm{HR}}=O\left(\frac{n}{K}+\log(nK)\right), yields

E[∥D(c~(y))−F(x)∥11E]=O(kn+kmn+kmlog⁡(nK)ε).\mathbb{E}\left[\left\|D(\widetilde{c}(y))-F(x)\right\|_{1}\mathbf{1}_{E}\right] =O\left(\frac{k\sqrt{n}+\sqrt{k m n}+k\sqrt{m\log(nK)}}{\varepsilon}\right).

On EcE^{c}, clipping leaves total count at most nn, so the error is O(nkε)O\left(\frac{nk}{\varepsilon}\right). Its expected contribution is O(kε)O\left(\frac{k}{\varepsilon}\right), absorbed by the error from honest clients’ reports. □\square

References

  1. [1]Jayadev Acharya, Ziteng Sun, and Huanyu Zhang. 2019. Hadamard Response: Estimating Distributions Privately, Efficiently, and with Little Communication. In Proc. 22nd Int. Conf. Artif. Intell. Stat. (AISTATS) (Proceedings of Machine Learning Research, Vol. 89), Kamilaka Chaudhuri and Masashi Sugiyama (Eds.). PMLR, 1120–1129. http://proceedings.mlr.press/v89/acharya19a.htmlarxiv.org/abs/1802.04705
  2. [2]arkworks contributors. 2022. arkworks zk-SNARK ecosystem. [Online]. Available: https://arkworks.rs. https://arkworks.rs
  3. [3]Peter L. Bartlett and Shahar Mendelson. 2002. Rademacher and Gaussian Complexities: Risk Bounds and Structural Results. J. Mach. Learn. Res. 3 (2002), 463–482. https://jmlr.org/papers/v3/bartlett02a.html
  4. [4]Raef Bassily, Kobbi Nissim, Uri Stemmer, and Aabhdeep Thakurta. 2020. Practical Locally Private Heavy Hitters. J. Mach. Learn. Res. 21 (2020), 16:1–16:42. https://jmlr.org/papers/v21/18-786.html
  5. [5]James Bell-Clar, Adria Gascón, Baiyu Li, Mariana Raykova, and Amrita Roy Chowdhury. 2025. Verity: Verifiable Local Differential Privacy. IACR Cryptol. ePrint Arch. 2025 (2025), 851. https://eprint.iacr.org/2025/851DOI
  6. [6]Mihir Bellare and Oded Goldreich. 1992. On Defining Proofs of Knowledge. In Proc. 12th Int. Cryptol. Conf. (CRYPTO) (Lecture Notes in Computer Science, Vol. 740), Ernest F. Brickell (Ed.). Springer, 390–420. doi:10.1007/3-540-48071-4_28
  7. [7]Ari Biswas and Graham Cormode. 2023. Interactive Proofs for Differentially Private Counting. In Proc. ACM Conf. Comput. Commun. Security (CCS), Weizhi Meng, Christian Damsgaard Jensen, Cas Cremers, and Engin Kirda (Eds.). ACM, 1919–1933. doi:10.1145/3576915.3616681DOI
  8. [8]Tariq Bontekoe, Hassan Jameel Asghar, and Fatih Turkmen. 2025. Efficient Verifiable Differential Privacy with Input Authenticity in the Local and Shuffle Model. Proc. Priv. Enhancing Technol. 2025, 2 (2025), 543–563. doi:10.56553/popets-2025-0076
  9. [9]Xiaoyu Cao, Jinyuan Jia, and Neil Zhenqiang Gong. 2021. Data Poisoning Attacks to Local Differential Privacy Protocols. In Proc. 30th USENIX Security Symp., Michael D. Bailey and Rachel Greenstadt (Eds.). USENIX Association, 947–964. https://www.usenix.org/conference/usenixsecurity21/presentation/cao-xiaoyu
  10. [10]Jeffrey Champion, Abhi Shelat, and Jonathan R. Ullman. 2019. Securely Sampling Biased Coins with Applications to Differential Privacy. In Proc. ACM Conf. Comput. Commun. Security (CCS), Lorenzo Cavallaro, Johannes Kinder, XiaoFeng Wang, and Jonathan Katz (Eds.). ACM, 603–614. doi:10.1145/3319535.3354256DOI
  11. [11]Albert Cheu, Adam D. Smith, and Jonathan R. Ullman. 2021. Manipulation Attacks in Local Differential Privacy. J. Priv. Confidentiality 11, 1 (2021), doi:10.29012/JP-C.754arxiv.org/abs/1909.09630
  12. [12]Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam D. Smith. 2006. Calibrating Noise to Sensitivity in Private Data Analysis. In Proc. 3rd Theory Cryptogr. Conf. (TCC) (Lecture Notes in Computer Science, Vol. 3876), Shai Halevi and Tal Rabin (Eds.). Springer, 265–284. doi:10.1007/11681878_14DOI
  13. [13]Cynthia Dwork and Aaron Roth. 2014. The Algorithmic Foundations of Differential Privacy. Found. Trends Theor. Comput. Sci. 9, 3–4 (2014), 211–407. doi:10.1561/0400000042DOI
  14. [14]Úlfar Erlingsson, Vasyl Pihur, and Aleksandra Korolova. 2014. RAPPOR: Randomized Aggregatable Privacy-Preserving Ordinal Response. In Proc. ACM Conf. Comput. Commun. Security (CCS), Gail-Joon Ahn, Moty Yung, and Ninghui Li (Eds.). ACM, 1054–1067. doi:10.1145/2660267.2660348
  15. [15]Alexander Evfimievski, Johannes Gehrke, and Ramakrishnan Srikant. 2003. Limiting privacy breaches in privacy preserving data mining. In Proc. 22nd ACM Symp. Principles Database Syst. (PODS), Frank Neven, Catriel Beeri, and Tova Milo (Eds.). ACM, 211–222. doi:10.1145/773153.773174
  16. [16]Vitaly Feldman, Jelani Nelson, Huy L. Nguyen, and Kunal Talwar. 2022. Private frequency estimation via projective geometry. In Proc. Int. Conf. Mach. Learn. (ICML) (Proceedings of Machine Learning Research), Kamilaka Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvári, Gang Niu, and Sivan Sabato (Eds.). PMLR, 6418–6433. https://proceedings.mlr.press/v162/feldman22a.htmlarxiv.org/abs/2203.00194
  17. [17]Vitaly Feldman and Kunal Talwar. 2021. Lossless Compression of Efficient Private Local Randomizers. In Proc. 38th Int. Conf. Mach. Learn. (ICML) (Proceedings of Machine Learning Research, Vol. 139), Marina Meila and Tong Zhang (Eds.). PMLR, 3208–3219. http://proceedings.mlr.press/v139/feldman21a.htmlarxiv.org/abs/2102.12099
  18. [18]Philippe Fournier-Viger, Antonio Gomariz, Ted Gueniche, Azadeh Soltani, Cheng-Wei Wu, and Vincent S. Tseng. 2014. SPMF: A Java open-source pattern mining library. J. Mach. Learn. Res. 15, 1 (2014), 3389–3393. doi:10.5555/2627435.2750353
  19. [19]Shafi Goldwasser, Silvio Micali, and Charles Rackoff. 1985. The Knowledge Complexity of Interactive Proof-Systems (Extended Abstract). In Proc. 17th ACM Symp. Theory Comput. (STOC), Robert Sedgewick (Ed.). ACM, 291–304. doi:10.1.1.145.22178
  20. [20]Lorenzo Grassi, Dmitry Khovratovich, Christian Rechberger, Arnab Roy, and Markus Schofnegger. 2021. Poseidon: A New Hash Function for Zero-Knowledge Proof Systems. In Proc. 30th USENIX Security Symp., Michael D. Bailey and Rachel Greenstadt (Eds.). USENIX Association, 519–535. https://www.usenix.org/conference/usenixsecurity21/presentation/grassi
  21. [21]Jens Groth. 2016. On the Size of Pairing-Based Non-interactive Arguments. In Proc. 35th Int. Conf. Theory Appl. Cryptogr. Techn. (EUROCRYPT), Part II (Lecture Notes in Computer Science, Vol. 9666), Marc Fischlin and Jean-Sébastien Coron (Eds.). Springer, 305–326. doi:10.1007/978-3-662-49896-5_11DOI
  22. [22]Fumiyuki Kato, Yang Cao, and Masatoshi Yoshikawa. 2021. Preventing Manipulation Attack in Local Differential Privacy Using Verifiable Randomization Mechanism. In Proc. 35th IFIP Conf. Data Appl. Security Privacy (DBSec) (Lecture Notes in Computer Science, Vol. 12840), Ken Barker and Kambiz Ghazinour (Eds.). Springer, 43–60. doi:10.1007/978-3-030-81242-3_3
  23. [23]Ilya Mironov, Omkant Pandey, Omer Reingold, and Salil P. Vadhan. 2009. Computational Differential Privacy. In Proc. 29th Int. Cryptol. Conf. (CRYPTO) (Lecture Notes in Computer Science, Vol. 5677), Shai Halevi (Ed.). Springer, 126–142. doi:10.1007/978-3-642-03356-8_8DOI
  24. [24]Arjun Narayan, Ariel Feldman, Antonis Papadimitriou, and Andreas Haeberlen. 2015. Verifiable differential privacy. In Proc. 10th European Conf. Comput. Syst. (EuroSys), Laurent Réveillère, Tim Harris, and Maurice Herlihy (Eds.). ACM, 28:1–28:14. doi:10.1145/2741948.2741978DOI
  25. [25]Qi Pang, Radhika Garg, Ziling Liu, Hanshen Xiao, Virginia Smith, Wenting Zheng, and Xiao Wang. 2026. Noisette: Certifying Differential Privacy Mechanisms Efficiently. IACR Cryptol. ePrint Arch. 2026 (2026), 74. https://eprint.iacr.org/2026/074
  26. [26]Ali Shahin Shamsabadi, Gefei Tan, Tudor Cebere, Aurélien Bellet, Hamed Haddadi, Nicolas Papernot, Xiao Wang, and Adrian Weller. 2024. Confidential-DPProof: Confidential Proof of Differentially Private Training. In Proc. 12th Int. Conf. Learn. Representations (ICLR). OpenReview.net. https://openreview.net/forum?id=PQ2V6VtGe
  27. [27]Shaorui Song, Lei Xu, and Liehuang Zhu. 2023. Efficient Defenses Against Output Poisoning Attacks on Local Differential Privacy. IEEE Trans. Inf. Forensics Security 18 (2023), 5506–5521. doi:10.1109/TIFS.2023.3305873DOI
  28. [28]Haochen Sun and Xi He. 2025. VDPP: Verifiable Distributed Differential Privacy under the Client-Server-Verifier Setup. CoRR abs/2504.21752 (2025). arXiv:2504.21752. doi:10.48550/ARXIV.2504.21752
  29. [29]Justin Thaler. 2022. Proofs, Arguments, and Zero-Knowledge. Found. Trends Priv. Secur. 4, 2–4 (2022), 117–660. doi:10.1561/3300000030DOI
  30. [30]Roman Vershynin. 2018. High-Dimensional Probability: An Introduction with Applications in Data Science. Cambridge University Press. doi:10.1017/9781108231596DOI
  31. [31]Tianhao Wang, Jeremiah Blocki, Ninghui Li, and Somesh Jha. 2017. Locally Differentially Private Protocols for Frequency Estimation. In Proc. 26th USENIX Security Symp., Engin Kirda and Thomas Ristenpart (Eds.). USENIX Association, 729–745. https://www.usenix.org/conference/usenixsecurity17/technical-sessions/presentation/wang-tianhao
  32. [32]Min Ye and Alexander Barg. 2018. Optimal Schemes for Discrete Distribution Estimation Under Locally Differential Privacy. IEEE Trans. Inf. Theory 64, 8 (2018), 5662–5676. doi:10.1109/TIT.2018.2809709arxiv.org/abs/1702.00610

Paper details

vlnc:W_3swwbv3d
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 7

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents