Author Login Editor-in-Chief Peer Review Editor Work Office Work

Computer Engineering ›› 2020, Vol. 46 ›› Issue (3): 114-119,128. doi: 10.19678/j.issn.1000-3428.0054001

• Cyberspace Security • Previous Articles     Next Articles

Spatial Query Authentication Method Based on MIR Tree

REN Dezhi1, CHEN Juguang2, WANG Yong2, DUAN Xiaoran2, HAO Yujie2, WU Xiaohua1   

  1. 1. School of Information and Software Engineering, University of Electronic Science and Technology of China, Chengdu 610054, China;
    2. School of Computer Science and Engineering, University of Electronic Science and Technology of China, Chengdu 611731, China
  • Received:2019-02-25 Revised:2019-04-08 Published:2020-03-14

基于MIR树的空间查询验证方法

任德志1, 陈炬光2, 王勇2, 段晓冉2, 郝玉洁2, 吴晓华1   

  1. 1. 电子科技大学 信息与软件工程学院, 成都 610054;
    2. 电子科技大学 计算机科学与工程学院, 成都 611731
  • 作者简介:任德志(1994-),男,硕士研究生,主研方向为网络信息安全;陈炬光,硕士;王勇(通信作者),副教授、博士;段晓冉,硕士;郝玉洁,教授;吴晓华,副教授、博士。
  • 基金资助:
    国家重点研发计划(2016QY04W0802);四川省科技计划项目(2016JY0007);中央高校基本科研业务费专项资金(ZYGX2016J216)。

Abstract: In the data outsourcing service,Spatial Polynomial Function(SPF) query can ensure the authenticity of the query information returned to users,so it has high application value.In order to solve the problem of high communication cost of Inverted File(IF) in MIR tree,by replacing the IF with bitmap,this paper constructs MRH tree,a data index structure supporting query authentication.On this basis,the generation algorithm of Verification Object(VO) is presented to verify the query results.Experimental results show that MRH tree can significantly reduce the communication overhead and computing time of query compared with MIR tree on the premise of ensuring the reliability,correctness and integrity of query results.

Key words: Spatial Polynomial Function(SPF) query, data outsourcing, query verification, Authentication Data Structure(ADS), Merkle Hash(MH) tree

摘要: 在数据外包服务中,空间多项式函数查询能确保返回用户查询信息的真实性,因而具有较高的应用价值。为解决MIR树中倒排索引文件通信代价过高的问题,采用位图替代倒排索引文件,构造一种支持查询验证的数据索引结构——MRH树,在此基础上构造验证对象生成算法验证查询结果。实验结果表明,在保证查询结果可靠、正确和完整的前提下,相较于MIR树,MRH树能显著地降低通信开销和计算时间。

关键词: 空间多项式函数查询, 数据外包, 查询验证, 认证数据结构, 默克尔哈希树

CLC Number: