Paper 2015/333

Nearly Optimal Verifiable Data Streaming (Full Version)

Johannes Krupp, Dominique Schröder, Mark Simkin, Dario Fiore, Giuseppe Ateniese, and Stefan Nuernberger


The problem of verifiable data streaming (VDS) considers a client with limited computational and storage capacities that streams an a-priori unknown number of elements to an untrusted server. The client may retrieve and update any outsourced element. Other parties may verify each outsourced element's integrity using the client's public-key. All previous VDS constructions incur a bandwidth and computational overhead on both client and server side, which is at least logarithmic in the number of transmitted elements. We propose two novel, fundamentally different approaches to constructing VDS. The first scheme is based on a new cryptographic primitive called Chameleon Vector Commitment (CVC). A CVC is a trapdoor commitment scheme to a vector of messages where both commitments and openings have constant size. Using CVCs we construct a tree-based VDS protocol that has constant computational and bandwidth overhead on the client side. The second scheme shifts the workload to the server side by combining signature schemes with cryptographic accumulators. Here, all computations are constant, except for queries, where the computational cost of the server is linear in the total number of updates.

Note: Add contact information to main body

Available format(s)
Cryptographic protocols
Publication info
A major revision of an IACR publication in PKC 2016
Contact author(s)
krupp @ ca cs uni-saarland de
2016-01-03: last of 2 revisions
2015-04-19: received
See all versions
Short URL
Creative Commons Attribution


      author = {Johannes Krupp and Dominique Schröder and Mark Simkin and Dario Fiore and Giuseppe Ateniese and Stefan Nuernberger},
      title = {Nearly Optimal Verifiable Data Streaming (Full Version)},
      howpublished = {Cryptology ePrint Archive, Paper 2015/333},
      year = {2015},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.