【作者】 张亮；

【导师】 蒋文斌；

【作者基本信息】 华中科技大学 ， 计算机系统结构， 2023， 硕士

【摘要】 当前,随着物联网的快速发展和各类移动互联设备的日益普及,空间范围查询技术被广泛地应用到各类复杂的查询需求中。然而在查询处理的过程中,用户的数据隐私面临严重威胁。面向隐私保护的空间范围查询技术常采用数据加密技术,但是加密并不能够完全解决隐私问题。攻击者通过对加密数据的访问模式、搜索模式的分析可以获取数据隐私。同时,数据加密也带来了存储与计算上的性能损耗,使得查询处理与数据共享变得困难。针对上述问题,提出了一种安全的学习型索引SDI以及基于SDI的空间范围查询算法SDBRQ。首先,SDI基于特殊的空间曲线编码对空间数据进行映射,并在映射空间上采用轻量级的线性分段模型对数据分布进行学习;SDI针对经过映射的空间范围查询的特点,对学习模型的作用域以及预测类型进行扩充;同时,SDI通过二叉树的形式组织预测器来加速预测过程,并采用提出的安全索引访问算法CAP,通过半随机的方式遍历SDI。其次,SDBRQ采用CAP算法预测查询对应的数据区域,并在该区域内通过盲取的方式获取查询结果,进一步保护了数据的访问模式。最后,提出了基于密文压缩的优化方案用于提升查询效率,降低通信代价,并形式化地分析了索引构造与所提算法的复杂度和安全性。最后,基于C++实现了索引SDI以及查询算法SDBRQ。在两个真实世界数据集CAR、GOWALLA以及一个合成数据集SYN上,评估了SDI在不同参数设置下的构造时间与存储开销,验证了索引构造的可行性;接着,评估了不同参数对于SDBRQ查询效率的影响。在默认参数设置下,SDBRQ在CAR上的最短查询时延达到了2.49s,在GOWALLA上则达到了2.72s,经过优化后,其查询时延降分别降低至0.75s和0.79s,对比同类工作,该结果表明了所提算法在效率方面的有效性。更多还原

【Abstract】 Nowadays,under the trend of the development of Internet of Things and the popularity of various mobile connected devices,spatial range query technology is widely used in various complex query requirements.However,in the process of query processing,data privacy of users faces serious threats.Privacy-preserving spatial range query technology often uses data encryption to solve security problems,but it does not completely solve the privacy problem.Attackers can infer data privacy by analyzing access patterns and search patterns of encrypted data.At the same time,data encryption also brings performance loss in storage and computation,making query processing and data sharing difficult.Aiming at aforementioned problems,a secure learned index SDI and a secure spatial range query algorithm SDBRQ are proposed.SDI maps spatial data based on space-filling curve encoding method,and uses a lightweight linear segmentation model to learn the data distribution on the mapped space.According to the characteristics of the range query in the mapping space,the domain and prediction type of the learning model are expanded.SDI organizes predictors in the form of binary tree to speed up the prediction process.To access SDI,an algorithm CAP proposes,which semi-randomly traverses SDI.In,SDBRQ,the corresponding data area is predicted based on CAP,and the query results are obtained through blind fetching,further protecting the access pattern.An optimization scheme based on ciphertext compression is proposed to improve query efficiency and reduce communication cost.The complexity and security of the SDI and proposed algorithms are formally analyzed.The SDI and SDBRQ are implemented in C++.The construction time and storage overhead of SDI with different parameter settings are evaluated on two real-world datasets CAR,GOWALLA and a synthetic dataset SYN,and the feasibility of the index is verified.Then,the impact of different parameters on the query efficiency of SDBRQ is evaluated.Under the default parameter settings,SDBRQ achieves query latency of 2.49 s on CAR and2.72 s on GOWALLA.After optimization,the query latency is reduced to 0.75 s and 0.79 s respectively.Compared with similar Work,the results show the effectiveness of the proposed algorithm.更多还原