VDDP: Verifiable Distributed Differential Privacy under the Client-Server-Verifier Setup

Although differential privacy (DP) is widely regarded as the de facto standard for data privacy, its implementation remains vulnerable to unfaithful execution by servers, particularly in distributed settings. In such cases, servers may sample noise from incorrect distributions or generate correlated noise while appearing to follow established protocols. This work addresses these malicious behaviours in a distributed client-server-verifier setup under Verifiable Distributed Differential Privacy (VDDP), a novel framework for the verifiable execution of distributed DP mechanisms. We systematically capture end-to-end security and privacy guarantees against potentially colluding adversarial behaviours of clients, servers, and verifiers by characterizing the connections and distinctions between VDDP and zero-knowledge proofs (ZKPs). As our primary instantiation of VDDP, the Verifiable Distributed Discrete Laplace Mechanism (VDDLM) achieves a proving-time speedup ranging from 50x to 4,000,000x over existing solutions, with larger gains in stronger-privacy regimes. Furthermore, the VDDLM sampling circuit achieves asymptotically lower overhead than prior constructions and is applicable to a broad range of cryptography-based DP applications.