关键词: 数据流, 查询验证, 外包数据, Merkle哈希树（MHT）

Abstract: Data stream range query authentication problem has been receiving widespread attention. The main query authentication method is based on Merkle Hash tree (MHT), which has disadvantages such as large verification object (VO), redundant verification procedures, low security and disability to locate tampering quickly. To overcome the above disadvantages, this paper proposes a new data stream range query authentication method based on partially materialized digest (PMD) scheme, where the PMD scheme is embedded in the traditional MHT, and some internal nodes and the root node in MHT are signed, instead of only the root node. Thus in the process of query results authentication, there is no need to compute much redundant hash value when reconstructing the MHT and verifying the authenticity and completeness of the query answers. Finally, the proposed scheme is applied into one-shot and sliding window range queries over data stream, where the authenticity and completeness of the query answers can be proved efficiently.

Key words: data stream, query authentication, outsourced database, Merkle Hash tree (MHT)