### Nearly Optimal Verifiable Data Streaming (Full Version)

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

##### Abstract

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)
Category
Cryptographic protocols
Publication info
A major revision of an IACR publication in PKC 2016
Contact author(s)
krupp @ ca cs uni-saarland de
History
2016-01-03: last of 2 revisions
See all versions
Short URL
https://ia.cr/2015/333

CC BY

BibTeX

@misc{cryptoeprint:2015/333,
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{https://eprint.iacr.org/2015/333}},
url = {https://eprint.iacr.org/2015/333}
}

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