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 error under selective dropout is a factor of smaller than under output manipulation, where 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 time. Each HST client sends one bit and uses public random bits; explicitly distributing these vectors incurs downlink communication per client. The underlying PI-RAPPOR and Hadamard Response mechanisms have logarithmic-size reports and admit aggregation. Our verification protocols introduce additional cryptographic messages, whose full communication costs and contribution to modeled latency are evaluated in Section 7.
| Protocol | OM | SD | CC | Agg. |
| RAPPOR | ||||
| PI-RAPPOR | ||||
| HR | ||||
| HST |
Table 1. Histogram estimation for . OM: output manipulation; SD: selective dropout; CC: consistency check; Agg.: baseline aggregation. HR denotes Hadamard Response. Error entries omit a common factor and the honest-sampling term . OM and SD give tight rates; CC gives upper bounds under the assumptions of Section 6. Aggregation entries denote 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 error is smaller by a factor of 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 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 users and malicious users, Verity allows client-chosen inputs but prevents selection based on the noise, giving an error bound of . 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 be the data domain and let be the output space of a local randomizer. We write for the output of a fresh execution of the randomized mechanism on input .
Definition 2.1 (-local differential privacy (LDP)) [12, 15]. A randomized mechanism with input domain and output space satisfies -local differential privacy if, for every pair and every measurable set ,
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 (-computational local differential privacy) [15, 23]. Let denote the server’s view of an execution with an honest client holding input . The protocol satisfies -computational local differential privacy if, for every pair and every PPT distinguisher , there is a negligible function such that
In the local model, client applies to its own value and sends only the resulting report 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 , the true histogram is
where denotes the th standard basis vector. Unless stated otherwise, each honest client uses fresh, independent randomness when executing . 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 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 and . For each client with input , both mechanisms encode bits satisfying and for . The server decodes them as , where
With RAPPOR, the client samples each independently by flipping with probability and sends the bits as its report. Two one-hot inputs differ in two coordinates, so using randomized response with privacy parameter per coordinate gives -LDP.
PI-RAPPOR instead encodes the bits in two elements of a prime-order field , where the field order upper bounds the number of classes . Assuming is an integer, define
where is the canonical representative in . On input , the client samples its report uniformly from with probability , or from its complement with probability . Since ,
Each probability changes by a factor of at most between inputs, so PI-RAPPOR is also -LDP. Decoding the pair as yields the stated marginals: membership in has probability , while for the bijection gives probability . In either mechanism, . Writing for client ’s decoded vector, the server uses the same unbiased histogram estimator
For RAPPOR, computing this estimator takes time. For PI-RAPPOR, as noted in [16], dynamic programming with the chosen hash function yields an aggregation time of .
Hadamard Response
This mechanism makes use of the Sylvester Hadamard matrix, defined as
where . We associate input with row , thereby excluding the all-one row. With Hadamard Response, the client samples a column index as its report according to
The likelihood ratio between any two inputs is at most , so the mechanism is -LDP. Given reports , the server uses
for each . Orthogonality of the Hadamard rows gives . Hadamard Response is asymptotically optimal for discrete distribution estimation in the high privacy regime and requires only communicated bits per report. Using fast Hadamard matrix multiplication, one can compute the estimator in time.
HST
HST is a public-randomness histogram protocol described by Bassily et al. [4]. For each client with input , the protocol independently samples a public vector uniformly at random. Client applies binary randomized response to the th bit of the public vector, , sending
Write and decode the bit as . The count estimator is
The public vectors are fixed by the protocol, not chosen by the reporting clients. Conditional on these vectors, binary randomized response is -LDP; averaging also over the public randomness gives . HST attains an optimal error rate when all clients follow the protocol [32]. In this explicit form it uses public random bits and 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 for a commitment to , where is the commitment randomness used to hide . 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 that takes public input and private input and outputs , let be the public statement and be the private witness. Define the relation
A ZKPoK for is a proof protocol
in which the prover P convinces the verifier V that it knows a witness such that , without revealing the witness. For security parameter , we use the following standard properties:
Completeness. If and both parties follow , then V accepts except with negligible probability in .
Knowledge soundness. For any PPT prover that makes V accept with non-negligible probability, acceptance guarantees that the prover knows a witness satisfying .
Zero knowledge. The verifier learns nothing about the private witness beyond the validity of the public statement .
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 can be represented by a deterministic function , where and are randomness shares contributed by the client and server, respectively.
Distributed Randomness for an LDP Mechanism
A deterministic function and prescribed distributions for the client and server randomness shares implement an -LDP mechanism through distributed randomness if they satisfy the following requirements:
(1) (Integrity) For every fixed input and valid client share , sampling the server’s share from its prescribed distribution makes computationally indistinguishable from .
(2) (Privacy) When the client samples its share honestly and independently of the server’s share, the joint view satisfies -computational LDP with respect to .
Given integrity, a sufficient condition for privacy is that and are independent for every fixed when the shares are sampled honestly and independently. Indeed, integrity ensures that the marginal distribution of the output is computationally indistinguishable from , and independence ensures that revealing 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 [7, 10]. The client then proves the relation above with private input , public input , and public output .
Problem Setup
We consider one server and clients indexed by . Each client holds one categorical value , and the server seeks to estimate the histogram from reports generated with privacy budget . 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 clients are corrupted, with . 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 for the corrupted clients , where is the report space of the local randomizer . These reports need not follow the distribution prescribed by .
Our goal is twofold: the server’s view of each honest client must reveal no more than the prescribed -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 to denote one client’s randomized report, computed from its input and the client and server randomness shares and . 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 be a correct PPT one-round-trip server–client–server implementation of a randomized mechanism . For a fixed input , write for the server’s challenge, for the client’s randomness, and for the randomized report. Assume there are a PPT algorithm ComputeReport, an efficiently recognizable set , and a polynomial such that, except with negligible probability over the server’s challenge, ComputeReport computes from the client’s local view with negligible error and
Then a PPT client can submit a valid response that the server accepts with with probability . The distribution of the submitted report has total variation distance at least 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 has one report generated by a single execution of the prescribed randomizer on its fixed input . After inspecting these reports, the adversary may choose a subset of clients to drop out; each client in submits its original report 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 than that from output manipulation, where 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 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 bits. In contrast, directly verifying RAPPOR requires generating and proving the randomization of 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 be the deterministic realization of an -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 , the protocol proceeds as follows.
(1) Commitment: Client samples a private randomness share and commitment randomness , and computes , where denotes concatenation. It sends together with a ZKPoK of knowledge of such that , satisfies the mechanism’s validity constraints, and
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 , the server independently samples a randomness share from the distribution prescribed by the distributed-randomness construction and sends it to that client. Sampling only after accepting ensures that the committed pair cannot depend on the server’s share.
(3) Report and verification: Client computes
and sends together with a ZKPoK of knowledge of satisfying
The server accepts if and only if this proof verifies with respect to . 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 is equal to for the input and client randomness share fixed by before was sampled.
(3) Computational privacy. For an honest client, the server’s complete view satisfies -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 -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 , whose evaluation is certified in the final protocol step. We use -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 is the order of the field in which the two report elements are represented; is the number of bits used for a random branch choice. Recall that is the probability that a nonmatching coordinate is encoded as one. We set and define the rounded version of the set in Equation (5) by . We also set ; this threshold determines how often the sampler selects a pair from instead of a uniform pair from .
For each party , an honestly sampled randomness share contains independent uniform values , an integer , and a bit string . The circuit combines the two parties’ values to obtain the sampler’s random choices. The combined value is the second component of the report in both branches, while is the first component in the uniform-pair branch. In the restricted-pair branch, and instead determine a pair in . The combined bit strings select which branch to use. The circuit proceeds as follows:
Lines 1 and 2 add to and to , respectively, using addition in . The resulting and are independent and uniform in when either party samples its share honestly and independently of the other’s share.
Line 3 adds and modulo to obtain a uniform . In the restricted-pair branch, will equal the canonical representative of and thus ensure that the report is in .
Line 4 XORs and and interprets the resulting bits as a uniform integer . Comparing with lets the circuit select the restricted-pair branch with probability .

Figure 1.
Line 5 sets when , selecting the restricted-pair branch, and otherwise, selecting the uniform-pair branch.
Lines 6 and 7 construct the report. When , the report is , so and the pair belongs to . Each pair in corresponds to exactly one choice of and , so uniform, independent choices of these values give a uniform pair in . When , the report is , a uniform pair in . The circuit returns the resulting pair .
Write for the probability of choosing the restricted-pair branch, , and . With the prescribed randomness shares, the client obtains a uniform pair from with probability and a uniform pair from otherwise; the latter branch can also produce a pair in . The resulting probabilities of membership in are for and for , corresponding to the matching and nonmatching probabilities in § 2.1.1. The largest likelihood ratio is at most , so the rounded mechanism satisfies -LDP. Rounding changes the nonmatching and matching coordinate probabilities by less than and , respectively; when , the full report distribution is within in total variation of PI-RAPPOR. The estimator in Equation (7) remains unbiased when membership in and the probabilities are used in Equation (4); we choose so that .
Hadamard Response Circuit
Algorithm 2 implements the Hadamard Response sampler from Section 2.1.2 using distributed randomness. Recall that , input corresponds to row of , and the report is a column index . Let , so both the row and column indices have -bit representations. We write for the -bit representation of an integer , with the least significant bit indexed by zero. In Equation (9), the report is chosen from the columns with with total probability and from those with otherwise. The circuit uses bits to choose between these two sets and rounds the threshold up to .
Each party contributes a randomness share containing an -bit string for choosing a column and a -bit string for choosing the sign of the Hadamard entry. These strings are
Algorithm 2 Hadamard Response circuit
Require: Class Require: Parameters , with Require: Client share Require: Server share Require: For each : , Ensure: Hadamard report
▹ least significant bit first
▹ Combine the randomness shares
▹ Choose the output parity
▹ Select a pivot and collect the remaining parity
▹ Set the pivot bit to enforce parity
;
return
combined to form the candidate column and the scalar parity choice below. For bit representations of a row and column, the Hadamard entry is 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 as an -bit string , least significant bit first. Since , at least one bit of is set.
Line 2 XORs the parties’ column strings to obtain a uniformly random candidate column .
Line 3 XORs their -bit strings and interprets the result as an integer .
Line 4 sets when and otherwise. The value is the desired parity: selects an entry of , and selects an entry of .
Line 5 chooses , the index of the least-significant set bit of , as the pivot.
Line 6 computes , the parity contributed by all row and column bits except the pivot.
Line 7 sets the pivot bit of the output column to and leaves its other bits unchanged. Because , the complete bitwise inner product has parity .
Line 8 converts the resulting column bits to the integer report 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 class with probability , which differs from by less than . The report distribution therefore differs from Hadamard Response by less than in total variation. Rounding the threshold up gives , so the rounded mechanism satisfies -LDP. Replacing the coefficient in Equation (10) by yields an unbiased estimator; we choose so that .
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 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, is the set of corrupted clients. Client holds a committed input and generates an independently randomized valid report . After observing all corrupted clients’ reports, the adversary chooses a subset of clients to drop out. The server applies the mechanism’s usual estimator to the reports from . We measure its expected error against the histogram of the admitted clients’ committed inputs, including those of dropped clients:
The expectation is over mechanism randomness and any internal randomness of the attack; the choice of may be an arbitrary randomized function of the corrupted clients’ reports. For each mechanism, let be the contribution of client ’s report to its usual histogram estimator, including any decoding and scaling. If is the estimate using all prescribed reports, then dropout changes it to . We study the norm of this change due to dropout; the total error also includes the estimation error already present in . 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 , and assume reports are randomized independently across clients. For PI-RAPPOR, assume . For each mechanism and attack below, the worst-case expected count error is , where HR denotes Hadamard Response and is:
| Attack | (PI-)RAPPOR | HR | HST |
| SD | |||
| OM |
For (PI-)RAPPOR, the decoded contribution is as defined in § 2.1.1. For Hadamard Response, , where denotes the entries in row of column . For HST, the decoded contribution is as defined in Section 2.1.3.
The following attacks achieve the attack-dependent rates in the table:
Selective dropout: Sample uniformly from and drop each corrupted report for which . This attack takes arithmetic operations, including field operations for PI-RAPPOR, and changes the estimate by in expected 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 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 with the error without an attack, , gives the threshold . The output-manipulation contribution instead gives . 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
In contrast, output manipulation introduces no additional asymptotic error only when .
The mechanisms in Corollary 5.2 tolerate a larger corruption budget under selective dropout than under output manipulation when . For , the selective-dropout budget saturates at , giving a rather than budget gain. For HST, both attacks are absorbed by the error without an attack at the same threshold . 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 error of the estimated count histogram over ten trials at . 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, is the number of clients and 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 be the decoded RAPPOR reports from (4), with and . For each pair of decoded reports with , the server checks whether
The following lemma bounds the probability that an honest report fails this check against a fixed vector.
Lemma 6.1. Suppose is obtained from an honest execution of RAPPOR, and let be a fixed vector. Then, .
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 . 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 . The server therefore retains exactly the decoded reports whose absolute inner product with every other original decoded report is at most , and sums them to obtain a histogram estimate.
A full check takes time. If an upper bound 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 reports uniformly without replacement, independently of the reports. It compares each of the sampled reports with every other original report and discards both reports in every detected violating pair. This takes time and preserves the full check’s expected-error bound, where the expectation also includes the server’s sampling.
Theorem 6.2. For , the full and sampled RAPPOR consistency checks have expected 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 norm of their sum. Cauchy–Schwarz converts this bound to 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 reports, is at most . This bound suffices to obtain the same expected-error rate. Appendix B.5 gives the full proof. □
Consistency Check for Hadamard Response
Let denote the Hadamard Response reports, and let be their report histogram, where . This histogram counts report symbols, not the clients’ input values. The consistency check limits each count using the threshold
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 are obtained from an honest execution of Hadamard Response. Then, .
Proof sketch of Lemma 6.3. Each count is a sum of independent Bernoulli indicators and has mean at most . Bernstein’s inequality and a union bound over the counts give the claim. See Appendix B.6 for the full proof. □
The server clips each count to , then applies the standard Hadamard Response decoder to the clipped histogram . The resulting estimator has the following expected-error bound under output manipulation:
Theorem 6.4. For , Hadamard Response with the above consistency check has expected error under output manipulation.
Proof sketch of Theorem 6.4. Let be the histogram of honest reports alone. With high probability, every entry of is at most . On this event, clipping leaves the honest counts intact, and the residual has norm at most and norm at most . Hadamard orthogonality bounds its decoded norm, and Cauchy–Schwarz bounds its contribution. Adding honest sampling error gives the result. Appendix B.7 contains the full proof. □
The server-side consistency check adds work to the 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 attack term, and Hadamard Response’s check has an term, compared with under selective dropout.
The full RAPPOR check requires work; given a corruption budget , the sampled variant reduces this to 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 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 , giving Hadamard output alphabets of size . Other domain sizes are supported by padding to and using the first nonzero Hadamard rows. Both circuits use 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 , and truncated Zipf with weights proportional to , normalized over . For the Kosarak clickstream dataset from the SPMF repository2 [18], we count page occurrences, retain the 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 error of the estimated count histogram against all 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 , 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 and . 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 to .
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 Vrity. Vrity [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 Vrity’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 and vary 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 . 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 error. In both attacks, the first 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 and , 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 , whereas output manipulation requires . At a fixed 10% corruption rate, increasing brings selective-dropout error closer to the Clean error while output manipulation remains far above it. Increasing at fixed 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 and , mean error is 1.13–1.15 times the Clean error across the four distributions. At , 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, , and , 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 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 ; 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 and use clients due to computational resource constraints, with 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 and , 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 error of the estimated count histogram for RAPPOR over ten trials at and . 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 . 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 and is consistent with threshold-based filtering of the repeated-report attack. At and , 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 increases, consistent with the threshold scale from Corollary 5.2. For fixed , this corresponds to . For example, at and , selective-dropout error is about 4.0 and 3.6 times the error without an attack for PI-RAPPOR and Hadamard Response, respectively; at , it remains close to that error for both. The HST curves show the same shift with , while its output-manipulation error remains closer to its selective-dropout error.
Figure 4. Mean error of the estimated count histogram over ten trials with uniform inputs, , and .
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 and , this threshold does not depend on . Once the count exceeds the threshold, additional copies are clipped, limiting the growth of the attack’s contribution. As increases, the threshold decreases, so clipping becomes effective at smaller corrupted fractions. At , the check does not reduce the attack’s error over the evaluated range; at , 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 errors of the estimated count histograms at and . For each and , 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 HR | |||
| 1.895–2.711<br>1.742–2.581 | 2.109–2.660<br>1.794–2.268 | 1.919–2.553<br>1.722–2.104 | |
| 1.896–1.960<br>1.625–1.738 | 2.124–2.305<br>1.654–1.800 | 2.081–2.249<br>1.678–1.796 | |
| 1.467–1.607<br>1.253–1.312 | 2.001–2.094<br>1.651–1.743 | 2.166–2.221<br>1.806–1.911 | |
| 1.207–1.259<br>1.084–1.131 | 1.717–1.767<br>1.424–1.483 | 2.148–2.187<br>1.760–1.829 | |
| 1.139–1.190<br>1.027–1.062 | 1.333–1.349<br>1.172–1.195 | 2.000–2.037<br>1.587–1.650 | |
| 1.126–1.136<br>1.035–1.042 | 1.177–1.197<br>1.069–1.076 | 1.570–1.589<br>1.315–1.358 |
Table 2. Ratios of mean errors of the estimated count histograms at with 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 , the malicious client runs the honest client algorithm independently
times, each time with fresh client randomness. For each execution, it uses ComputeReport to compute the corresponding report from its local view. It sends the response from the first trial for which ComputeReport returns a report in ; 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 trials generates a report in is at most
By a union bound over the 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 for that execution’s randomness, so the associated proof remains valid rather than being forged. By correctness of , rejection of an honestly generated response has negligible probability; a union bound over the 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 except with negligible probability. In contrast, after averaging over the server’s challenge, an honest execution generates a report in with probability at most by Equation (15). The difference on the event 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 before the server samples . Binding fixes the committed input and client randomness share. The second proof then guarantees that an accepted satisfies Equation (18) for that same input and randomness share. Therefore, after receiving , 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 . Hiding of the commitment and zero knowledge of the proofs ensure that the commitment and proofs leak no additional information about beyond the public transcript . By the distributed-randomness requirement, is -computationally locally private with respect to . Closure under PPT post-processing gives the same guarantee for the complete server view. □
Proof of Theorem 5.1
Common bounds. Write for a decoded report and . For all four mechanisms and , each centered coordinate has variance and fourth moment : for (PI-)RAPPOR this follows from the Bernoulli marginals, and for HR and HST from , , and . Thus a sum of independent centered coordinates has and . Cauchy–Schwarz and Paley–Zygmund applied to give
Only independence across clients is used; for HST the expectation also includes the public randomness.
Let . Every realized report has . For an independent uniform sign vector , symmetry and Khintchine’s inequality imply
Dropping reports with nonnegative projection therefore gives . Taking gives the other lower bound: for each coordinate, write the sum as , where is centered. Since , Equation (25) yields . Together these imply .
To pass from perturbation to total error, use . An upper bound of the same order on , together with , gives total error. For the lower bound, full participation attains the error without an attack, while the selective dropout attack in Theorem 5.1 satisfies
because is independent of the mean-zero . The maximum of the two lower bounds is at least half their sum. The attack costs operations; when , only the error without an attack remains.
(PI-)RAPPOR
Proof. Set and , so . For RAPPOR, coordinate independence gives . For PI-RAPPOR, let be uniform on . The bijection for maps pairwise independent Bernoulli variables. The report density relative to is at most by Equation (6); hence, for ,
Dividing by gives the same covariance bound for PI-RAPPOR. Both mechanisms also satisfy .
By norm duality, with ,
The covariance bound and give uniformly in . Symmetrization and contraction for [3], with independent Rademacher signs , give
The last step uses . The common lower bounds and total-error argument complete the SD proof.
For OM, each report has norm , so replacing reports changes the estimate by . For a matching lower bound, all corrupted clients submit the all-one bit report (the pair for PI-RAPPOR). Its decoded vector is , where and . The mean error is , whose norm is ; Jensen’s inequality gives the same lower bound on expected error. Honest reporting is also an allowed OM strategy and supplies the lower bound. □
Hadamard Response
Proof. Write , so . Let count corrupted reports equal to , and count those in . Cauchy–Schwarz and Hadamard orthogonality give, for every ,
Since and reports are independent,
Jensen’s inequality, , and yield . The common bounds give equality in order and the SD total-error rate.
Under OM, each decoded column has norm , giving the perturbation bound. Submitting column zero for every corrupted client gives mean error , of norm . 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 or , so flipping it changes the estimate by , twice the change from dropping it. Consequently, for every realization,
Let have columns , . Either attack changes the estimate by with , so its norm is at most . Because is fixed before sampling the public vectors, has independent Rademacher entries and [30].
Thus both perturbations have expected norm , 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 , the products are independent, mean zero, and have interval width at most ; also . Hoeffding’s inequality [30] gives
Set to obtain . □
Proof of Theorem 6.2
Proof. The case follows from the deterministic error bound; assume . Let index honest and malicious reports. By Lemma 6.1, independence of malicious and honest reports, and a union bound, the event that no pair involving an honest report violates the threshold has . On , every honest report survives either check. If is the retained set and counts violating pairs within , then
Indeed, diagonal terms are at most , consistent cross terms at most , and each violating pair contributes at most . The full check has .
For the sampled check, fix reports satisfying and form the graph of violating pairs, all of whose edges join malicious reports. A vertex of degree survives only if the uniform sample , of size , misses all its neighbors. Thus
with numerator zero if . Counting surviving edge endpoints,
since . If , then ; otherwise .
For either check, (29), , and bound the expected squared norm of the retained malicious sum, conditional on the fixed reports in , by . Cauchy–Schwarz and Jensen’s inequality convert this to an bound. Adding the unconditional error from honest clients’ reports and the norm (at most ) of the malicious-input histogram gives
using . On , the deterministic error bound contributes only . The sampled check computes at most inner products, giving time. The argument uses only , so also applies when the supplied budget is an upper bound.
Proof of Lemma 6.3
Proof. Each count is a sum of independent Bernoulli variables with mean at most , where . Bernstein’s inequality [30] gives
For , the exponent is at least . Since , a union bound over counts gives failure probability at most .
Proof of Theorem 6.4
Proof. Write for the decoder, and let be the honest and malicious report histograms. With probability at least , every honest count is at most : the preceding Bernstein argument applies to the honest reports with the same upper bound . On this event , clipping gives a residual with , , and . Consequently , and orthogonality gives
Adding the unconditional error from honest clients’ reports and the malicious-input histogram (of norm ), using and , yields
On , clipping leaves total count at most , so the error is . Its expected contribution is , absorbed by the error from honest clients’ reports.
References
- [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]arkworks contributors. 2022. arkworks zk-SNARK ecosystem. [Online]. Available: https://arkworks.rs. https://arkworks.rs
- [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]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]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]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]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]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]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]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]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]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]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]Ú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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]Justin Thaler. 2022. Proofs, Arguments, and Zero-Knowledge. Found. Trends Priv. Secur. 4, 2–4 (2022), 117–660. doi:10.1561/3300000030DOI
- [30]Roman Vershynin. 2018. High-Dimensional Probability: An Introduction with Applications in Data Science. Cambridge University Press. doi:10.1017/9781108231596DOI
- [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]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



