### Efficient Zero-Knowledge Proofs on Signed Data with Applications to Verifiable Computation on Data Streams

##### Abstract

We study the problem of privacy-preserving proofs on streamed authenticated data. In this setting, a server receives a continuous stream of data from a trusted data provider, and is requested to prove computations over the data to third parties in a correct and private way. In particular, the third party learns no information on the data beyond the validity of claimed results. A challenging requirement here, is that the third party verifies the validity with respect to the specific data authenticated by the provider, while communicating only with the server. This problem is motivated by various application areas, ranging from stock-market monitoring and prediction services; to the publication of government-ran statistics on large healthcare databases. All of these applications require a reliable and scalable solution, in order to see practical adoption. In this paper, we identify and formalize a key primitive allowing one to achieve the above: homomorphic signatures which evaluate non-deterministic computations (HSNP). We provide a generic construction for an HSNP evaluating universal relations; instantiate the construction; and implement a library for HSNP. This in turn allows us to build SPHINX: a system for proving arbitrary computations over streamed authenticated data in a privacy-preserving manner. SPHINX improves significantly over alternative solutions for this model. For instance, compared to corresponding solutions based on Marlin (Eurocrypt'20), the proof generation of SPHINX is between $15\times$ and $1\,300\times$ faster for various computations used in sliding-window statistics.

Available format(s)
Category
Cryptographic protocols
Publication info
Published elsewhere. ACM CCS 2022
DOI
10.1145/3548606.3560630
Keywords
zero-knowledge proofs homomorphic signatures verifiable computation data stream
Contact author(s)
dario fiore @ imdea org
idatucker91 @ gmail com
History
2022-11-07: revised
See all versions
Short URL
https://ia.cr/2022/1393

CC BY

BibTeX

@misc{cryptoeprint:2022/1393,
author = {Dario Fiore and Ida Tucker},
title = {Efficient Zero-Knowledge Proofs on Signed Data with Applications to Verifiable Computation on Data Streams},
howpublished = {Cryptology ePrint Archive, Paper 2022/1393},
year = {2022},
doi = {10.1145/3548606.3560630},
note = {\url{https://eprint.iacr.org/2022/1393}},
url = {https://eprint.iacr.org/2022/1393}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.