Cryptology ePrint Archive: Report 2015/333

Nearly Optimal Verifiable Data Streaming (Full Version)

Johannes Krupp and Dominique Schröder and Mark Simkin and Dario Fiore and 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.

Category / Keywords: cryptographic protocols /

Original Publication (with major differences): IACR-PKC-2016

Date: received 13 Apr 2015, last revised 3 Jan 2016

Contact author: krupp at ca cs uni-saarland de

Available format(s): PDF | BibTeX Citation

Note: Add contact information to main body

Version: 20160103:090151 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]