Nearly optimal verifiable data streaming

Krupp J, Schröder D, Simkin M, Fiore D, Ateniese G, Nürnberger S (2016)

Publication Language: English

Publication Status: Published

Publication Type: Authored book, Volume of book series

Publication year: 2016

Publisher: Springer Verlag

Series: Public-Key Cryptography - PKC 2016

Book Volume: 9614

Pages Range: 417-445

ISBN: 9783662493830

DOI: 10.1007/978-3-662-49384-7_16


The problem of verifiable data streaming (VDS) considers the setting in which a client outsources a large dataset to an untrusted server and the integrity of this dataset is publicly verifiable. A special property of VDS is that the client can append additional elements to the dataset without changing the public verification key. Furthermore, the client may also update elements in the dataset. All previous VDS constructions follow a hash-tree-based approach, but either have an upper bound on the size of the database or are only provably secure in the random oracle model. In this work, we give the first unbounded VDS constructions in the standard model. We give two constructions with different trade-offs. The first scheme follows the line of hash-tree-constructions and is based on a new cryptographic primitive called Chameleon Vector Commitment (CVC), that may be of independent interest. A CVC is a trapdoor commitment scheme to a vector of messages where both commitments and openings have constant size. Due to the tree-based approach, integrity proofs are logarithmic in the size of the dataset. The second scheme achieves constant size proofs by combining a signature scheme with cryptographic accumulators, but requires computational costs on the server-side linear in the number of update-operations.

Authors with CRIS profile

How to cite


Krupp, J., Schröder, D., Simkin, M., Fiore, D., Ateniese, G., & Nürnberger, S. (2016). Nearly optimal verifiable data streaming. Springer Verlag.


Krupp, Johannes, et al. Nearly optimal verifiable data streaming. Springer Verlag, 2016.

BibTeX: Download