Optimal Verifiable Data Streaming Under Concurrent Queries

The rapid development of both hardware and software has promoted the popularization of various real-time applications like health monitoring and intrusion detection that are widely deployed in outsourcing scenarios, e.g., mobile edge computing and cloud computing. In these applications, end devices continuously generate unbounded sequences of data items at a fast rate, i.e., the so-called streaming data. Nevertheless, storing and processing massive amounts of streaming data poses a challenge for resources-restricted end devices. Although outsourcing data items to edge servers or cloud servers is an attractive solution to the above problem, it also brings a new challenge, i.e., how to guarantee the integrity of outsourced data, since streaming data applications are usually sensitive of both location and the corresponding context, and servers are not completely trusted. To this end, the primitive of verifiable data streaming (VDS) protocol was introduced to maintain outsourced streaming data, while preserving its integrity. However, existing VDS constructions mainly use the structure of Merkle hash tree, and inherently have logarithmic costs. Consequently, they are infeasible for real-time applications that are delay sensitive and generate unpredictable size of streaming data. In this paper, we optimize previous VDS protocols from the aspects of communication overhead and computation cost. Specifically, we adopt a technical route different from Merkle hash tree, i.e, combining the digital signature with the cryptographic accumulator. In our construction, we employ Boneh-Lynn-Shacham (BLS) signature to guarantee the integrity of the context and position of each outsourced data item, and adopt an RSA accumulator to invalidate the old signature after the corresponding data item was updated. This immediately yields an optimal VDS construction that has constant costs even under concurrent queries, which is more desirable for those resource-limited mobile devices. In addition, the aggregability of BLS signature makes our VDS construction capable of data auditing, which enables the user to remotely verify the integrity of outsourced streaming data. We provide a formal security proof of the proposed VDS construction under well-studied complexity assumptions in the random oracle model. As a proof-of-concept, we also implement our proposal, and conduct extensive experiments to demonstrate its practicability.