Nearly Optimal Verifiable Data Streaming

Johannes Krupp, Dominique Schröder, Mark Simkin, Dario Fiore, Giuseppe Ateniese, Stefan Nürnberger

In: Chen-Mou Cheng , Kai-Min Chung , Giuseppe Persiano , Bo-Yin Yang (Hrsg.). 19th IACR International Conference on Practice and Theory in Public-Key Cryptography, Proceedings. IACR International Conference on Practice and Theory in Public-Key Cryptography (PKC-2016) March 6-9 Taipei Taiwan I Security and Cryptology 9614 ISBN 978-3-662-49383-0 Springer 2016.


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 tradeoffs. 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.

Deutsches Forschungszentrum für Künstliche Intelligenz
German Research Center for Artificial Intelligence