Paper 2022/1028

New Unbounded Verifiable Data Streaming for Batch Query with Almost Optimal Overhead

Jiaojiao Wu, Xidian University
Jianfeng Wang, Xidian University
Xinwei Yong, Xidian University
Xinyi Huang, Fujian Normal University
Xiaofeng Chen, Xidian University

Verifiable Data Streaming (VDS) enables a resource-limited client to continuously outsource data to an untrusted server in a sequential manner while supporting public integrity verification and efficient update. However, most existing VDS schemes require the client to generate all proofs in advance and store them at the server, which leads to a heavy computation burden on the client. In addition, all the previous VDS schemes can perform batch query (i.e., retrieving multiple data entries at once), but are subject to linear communication cost $l$, where $l$ is the number of queried data. In this paper, we first introduce a new cryptographic primitive named Double-trapdoor Chameleon Vector Commitment (DCVC), and then present an unbounded VDS scheme $\mathsf{VDS_1}$ with optimal communication cost in the random oracle model from aggregatable cross-commitment variant of DCVC. Furthermore, we propose, to our best knowledge, the first unbounded VDS scheme $\mathsf{VDS}_2$ with optimal communication and storage overhead in the standard model by integrating Double-trapdoor Chameleon Hash Function (DCH) and Key-Value Commitment (KVC). Both of our schemes enjoy constant-size public key. Finally, we demonstrate the efficiency of our two VDS schemes with a comprehensive performance evaluation.

Available format(s)
Cryptographic protocols
Publication info
Verifiable data streaming Data integrity Batch query Optimal overhead.
Contact author(s)
jiaojiaowujj @ stu xidian edu cn
2022-08-11: revised
2022-08-09: received
See all versions
Short URL
Creative Commons Attribution


      author = {Jiaojiao Wu and Jianfeng Wang and Xinwei Yong and Xinyi Huang and Xiaofeng Chen},
      title = {New Unbounded Verifiable Data Streaming for Batch Query with Almost Optimal Overhead},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1028},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.