Optimal Verifiable Data Streaming Protocol with Data Auditing

Publication Name

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)


As smart devices connected to networks like Internet of Things and 5G become popular, the volume of data generated over time (i.e., stream data) by them is growing rapidly. As a consequence, for these resources-limited client-side devices, it becomes very challenging to store the continuously generated stream data locally. Although the cloud storage provides a perfect solution to this problem, the data owner still needs to ensure the integrity of the outsourced stream data, since various applications built upon stream data are sensitive of both its context and order. To this end, the notion of verifiable data streaming (VDS) was proposed to effectively append and update stream data outsourced to an untrusted cloud server, and has received significant attention. However, previous VDS constructions adopt Merkle hash tree to capture the integrity of outsourced data, and thus inevitably have logarithmic costs. In this paper, we further optimize the construction of VDS in terms of communication and computation costs. Specifically, we use the digital signature scheme to ensure the integrity of outsourced stream data, and employ a recently proposed RSA accumulator (v.s. Merkle hash tree) to invalidate the corresponding signature after each data update operation. Benefited from this approach, the resulted VDS construction achieves optimal, i.e., having constant costs. Furthermore, by specifying the underly signature scheme with the BLS short signature and carefully combining it with the RSA accumulator, we finally obtain an optimal verifiable data streaming protocol with data auditing. We prove the security of the proposed VDS construction in the random oracle model.

Open Access Status

This publication is not available as open access


12973 LNCS

First Page


Last Page


Funding Number


Funding Sponsor

National Natural Science Foundation of China



Link to publisher version (DOI)