Nearly optimal verifiable data streaming

Authored book
(Volume of book series)

Publication Details

Author(s): Krupp J, Schröder D, Simkin M, Fiore D, Ateniese G, Nürnberger S
Publisher: Springer Verlag
Publication year: 2016
Title of series: Public-Key Cryptography - PKC 2016
Volume: 9614
Pages range: 417-445
ISBN: 9783662493830
Language: English


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.

FAU Authors / FAU Editors

Schröder, Dominique Prof. Dr.
Lehrstuhl für Informatik 13 (Angewandte Kryptographie)

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.


Last updated on 2018-13-11 at 20:50