Efficient verification of differentially-private digital data

Abstract

Embodiments of the present disclosure enable users to efficiently verify digital data produced by queried databases, even when that data is differentially-private (e.g., satisfying the conditions of differential privacy in order to protect sensitive or private data). In addition to the query result, a database computer can provide the client with a non-interactive zero-knowledge proof (NIZK), data that the client can use to verify the digital data contained in the query result, without revealing any private data to the client. Various innovations, including vectorized proofs, enable the database computer to generate proofs that require less data (e.g., when measured in bytes) than most NIZK proof systems. Consequently, these proofs can be transmitted and verified more quickly and efficiently. Embodiments of the present disclosure can make use of partially or homomorphic commitments and efficient vector proof techniques to achieve these performance improvements.