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)

摘要： 数据流外包服务验证问题受到广泛的关注。目前主流的外包数据查询验证技术是基于Merkle哈希树（Merkle Hash tree，MHT）的，但是其具有验证对象较大，验证过程存在冗余，安全性低，无法快速实现篡改定位的不足。针对这些不足，提出了一种基于偏序实体化摘取（partially materialized digest，PMD）策略的外包数据流范围查询验证新方案。该方案将PMD嵌入到传统MHT中，来选择MHT的部分中间节点以及根节点进行签名，那么在数据验证阶段重构MHT时无需计算大量冗余哈希值，即可验证查询结果的真实性和完整性。最后将所提方案具体应用到数据流单次和滑动窗口范围查询中，使得客户端能够高效率地验证由第三方所提供的结果是真实和完整的。

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