Communication-Efficient Verifiable Data Streaming Protocol in the Multi-User Setting

Verifiable data streaming (VDS) protocols enable end users with limited storage space to continuously stream data items to an untrusted cloud server, while preserving the capacity of verifying the integrity of those retrieved data items for downstream tasks. Although there has been plenty of research around the construction of VDS, we observe that they all focus on the scenario of single-user. When deploying these VDS protocols into more common applications that involve multiple users' data (e.g., network data monitoring and stock trends analysis), the size of the proof used to prove the integrity of retrieved data items grows linearly with the number of involved users. This would bring tremendous communication overhead, especially for lightweight users. To this end, we initiate the study of VDS protocols that are suitable for multi-user (or cross-user) setting. Specifically, we first introduce a new primitive called aggregatable chameleon vector commitment (ACVC) that allows to aggregate multiple proofs from different commitments into a single proof. Then, based on ACVC, we present a communication-efficient VDS protocol for the multi-user setting. That is, when querying data items from multiple users, the size of corresponding proof is constant and independent of the number of involved users. Theoretical analysis indicates that the proposed VDS protocol outperforms previous VDS protocols in terms of communication overhead. We also implement the proposed ACVC, and conduct extensive experiments to demonstrate its practicability.