ADSNARK: Nearly Practical and Privacy-Preserving Proofs on Authenticated Data

### Overview This talk introduces ADSNARK (Succinct Non-Interactive Arguments of Knowledge on Authenticated Data), a cryptographic system enabling privacy-preserving proofs over authenticated data. The work is presented by Dario (joint work with Michael Backes, Manuel Barbosa, and Rafael Dowsley / Rafael Ryu). The core problem centers on a three-party application model: a trusted source (e.g., a biosensor or smart meter) authenticates raw data; a data owner (e.g., a patient or household) seeks privacy over that raw data while proving legitimate aggregation; and a service provider (e.g., an insurance company or utility provider) requires integrity guarantees without being able to see private inputs.

### Key Topics - **Motivating Scenarios**: Real-world use cases include health insurance models (such as Generali in Germany using biosensor data for premium discounts) and smart metering for utility billing, as well as pay-as-you-drive insurance and loyalty programs. - **Limitations of Prior Approaches**: Standard zero-knowledge SNARKs do not natively verify data authenticity from third parties. A generic combination involves embedding digital signature verification algorithms directly into an arithmetic circuit ($C'$ instead of $C$), but this incurs an estimated overhead of at least 1,000 multiplication gates per authenticated input, severely harming scalability. - **ADSNARK Core Concept**: Instead of augmenting the SNARK circuit with expensive in-circuit signature checks, ADSNARK leverages state-of-the-art zk-SNARKs based on quadratic arithmetic programs (Pinocchio) and delegates the verification of authenticated inputs using a randomized homomorphic message authentication code (MAC) technique.

### Technical Details - **Verification Outsourcing**: In standard Pinocchio-style zk-SNARK verification, a linear combination over inputs $vk_x$ is computed by the verifier. Since input $x$ is private to the prover in this setting, ADSNARK shifts the computation of $vk_x$ to the prover. - **Homomorphic MACs over Group Elements**: To ensure the prover does not cheat and to authenticate the input, ADSNARK uses homomorphic message authenticators where coefficients are group elements rather than simple integers. - **Input Randomization**: Releasing $vk_x$ directly would reveal private data. ADSNARK resolves this by randomizing $vk_x$ and employing homomorphic authenticators tailored for randomized computations. - **Implementation & Performance**: ADSNARK was implemented as an extension of the `libsnark` library, reusing existing compiler toolchains, with additional cryptographic primitives sourced from the `SUPERCOP` framework. Benchmarks evaluated on constraint systems of 50,000 constraints with 100 to 1,000 inputs demonstrated that key generation and prover runtimes match plain zk-SNARK performance without signature verification overhead. - **Verification Modes**: ADSNARK supports secret-key verification (comparable speed to plain SNARKs) and public-key verification. In public-key mode, verification time and proof size scale with the number of inputs (~100 bytes per input overhead), remaining below one second in practice.

### Takeaways ADSNARK bridges zero-knowledge proofs and data authentication, allowing resource-constrained trusted devices (like sensors) to merely stream and authenticate data without performing heavy onboard computations or remaining online. Key open directions highlighted include achieving constant-size proofs in the public-key setting and extending these techniques to the RAM model of computation.