Paper 2022/1393

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

Dario Fiore, IMDEA Software Institute
Ida Tucker, IMDEA Software Institute

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)
Cryptographic protocols
Publication info
Published elsewhere. ACM CCS 2022
zero-knowledge proofs homomorphic signatures verifiable computation data stream
Contact author(s)
dario fiore @ imdea org
idatucker91 @ gmail com
2022-11-07: revised
2022-10-14: received
See all versions
Short URL
Creative Commons Attribution


      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{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.