CAJ | 학술논문

数据流外包服务验证问题受到广泛的关注。目前主流的外包数据查询验证技术是基于Merkle哈希树（Merkle Hash tree，MHT）的，但是其具有验证对象较大，验证过程存在冗余，安全性低，无法快速实现篡改定位的不足。针对这些不足，提出了一种基于偏序实体化摘取（partially materialized digest，PMD）策略的外包数据流范围查询验证新方案。该方案将PMD嵌入到传统MHT中，来选择MHT的部分中间节点以及根节点进行签名，那么在数据验证阶段重构MHT时无需计算大量冗余哈希值，即可验证查询结果的真实性和完整性。最后将所提方案具体应用到数据流单次和滑动窗口范围查询中，使得客户端能够高效率地验证由第三方所提供的结果是真实和完整的。
수거류외포복무험증문제수도엄범적관주。목전주류적외포수거사순험증기술시기우Merkle합희수（Merkle Hash tree，MHT）적，단시기구유험증대상교대，험증과정존재용여，안전성저，무법쾌속실현찬개정위적불족。침대저사불족，제출료일충기우편서실체화적취（partially materialized digest，PMD）책략적외포수거류범위사순험증신방안。해방안장PMD감입도전통MHT중，래선택MHT적부분중간절점이급근절점진행첨명，나요재수거험증계단중구MHT시무수계산대량용여합희치，즉가험증사순결과적진실성화완정성。최후장소제방안구체응용도수거류단차화활동창구범위사순중，사득객호단능구고효솔지험증유제삼방소제공적결과시진실화완정적。
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 over-come 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.