Shared-Noise Mechanisms for Verifiable Differentially Private Counting

Verifiable differential privacy enables public auditing of privacy-preserving aggregate computations, addressing the trust deficit in standard implementations. However, existing verifiable counting approaches that distribute trust across multiple provers often require each prover to contribute independent noise. This duplicates the noise added to the aggregate and substantially degrades utility, making accurate private counting difficult in distributed settings. We introduce a shared-noise paradigm for verifiable differentially private counting. Instead of duplicating noise across provers, our approach generates a single noise sample in additive-shared form among mutually distrustful provers, while Pedersen commitments let a public verifier audit consistency without learning the noise. This yields shared-noise, verifier-auditable instantiations of two standard noise families: the Shared-Noise Verifiable Binomial Mechanism (SN-VBM) and the Shared-Noise Verifiable Laplace Mechanism (SN-VLM). We prove that both mechanisms satisfy differential privacy and public verifiability, including completeness, soundness against malicious provers, and zero knowledge against a malicious verifier colluding with corrupted provers. Among the two instantiations, SN-VLM is the more scalable option: it avoids the quadratic growth in shared randomness required by the binomial construction under strict privacy budgets. Experiments on preprocessing load, randomness-generation time, and noise error show that SN-VLM substantially reduces cryptographic overhead while improving empirical accuracy in the evaluated privacy regimes.