【作者】 王静；

【导师】 鲍海勇；

【作者基本信息】 华东师范大学 ， 电子信息（专业学位）， 2024， 硕士

【摘要】 随着物联网(IoT)技术的快速发展,本地数据的维度和数量日益增多,为提升服务效率与实用性,尤其针对kNN和RkNN等广泛应用的查询服务,本地服务器倾向于将数据外包给第三方服务器进行处理。然而,第三方服务器的不完全可信性增加了数据外包过程中的隐私泄露风险。为此,加密技术被不断研发以保护外包数据隐私。目前,尽管已有研究聚焦于开发高效的基于密文的kNN查询算法,但主要局限于低维数据,对高维数据的可扩展性有限。同时,对于RkNN查询服务,现有算法对用户特征和信誉值的考虑不足,且在用户动态交互场景中的研究有限。因此,本研究致力于开发外包场景下高效且安全的数据查询算法,着重解决第三方服务器提供kNN/RkNN查询服务时的隐私泄露问题。本研究的主要工作包括以下几个方面:(1)提出了基于外包高维数据的隐私保护kNN查询方案——EPPQ,关注从高维数据的安全降维到对降维数据进行安全kNN查询的完整生命周期。具体而言,在安全降维阶段,一方面,EPPQ集成了主成分分析(PCA)技术进行降维,以最小化计算开销。另一方面,为解决执行数据降维过程中的隐私泄露问题,通过整合差分隐私技术,提出了基于PCA的隐私保护数据降维算法(PDDRP)。在安全kNN查询阶段,一方面,EPPQ通过k-d树实现了对降维数据的索引。为提高索引效率,本文创新性地提出了基于明文的距离计算定义(PDC)并构建了高效的k-d树变体(Ek-d树)。另一方面,EPPQ利用Paillier同态加密技术在将Ek-d树外包给不可信云服务器前对数据进行加密。此外,为实现基于密文的距离计算和比较,本文设计了安全的距离预计算协议(SPCD)和安全的数据比较协议(SCOM)。最后,本文提出了基于Ek-d树的隐私保护kNN查询算法(PKQKT),实现了高效而安全的kNN查询。(2)提出了基于外包多属性数据的隐私保护动态RkNN查询方案——DPRQ,关注从安全的密钥交换到对密文进行安全RkNN查询的完整生命周期。具体而言,在安全的密钥交换阶段,一方面,通过结合非交互式密钥交换(NIKE)协议和DiffieHellman两方密钥交换协议,本文提出了多方非交互式密钥交换算法(2K-NIKE),从而实现了感知用户的动态交互。另一方面,通过将衍生的共享密钥与对称加密算法相结合,2K-NIKE实现了对感知数据和用户身份ID的加密。在安全RkNN查询阶段,首先,为加强数据隐私并实现基于密文的RkNN查询,本文结合对称同态加密算法,设计了安全的RkNN查询过滤算法(PRKF)和安全的RkNN查询细化(PRKR)算法,实现了对多属性数据的编码和重加密。然后,中心服务器根据提出的协议计算过滤和细化阶段的查询结果,并将其返回给查询机构。综上,提出的EPPQ方案弥补了当前针对高维数据的隐私保护kNN查询算法研究不足的现状;提出的DPRQ方案解决了群智感知背景下用户的隐私泄露问题以及动态交互需求。安全性分析表明本研究所提出的方案在“诚实但好奇”的模型下满足所需的安全需求。通过与前沿的方案相比较,大量实验证明本研究所提出的方案在计算效率和查询准确性方面均表现出色。更多还原

【Abstract】 With the rapid development of Internet of Things(IoT),the dimensionality and volume of local data are increasing.To enhance service efficiency and practicality,especially for widely used query services such as k-nearest neighbor(kNN)and reverse k-nearest neighbor(RkNN),local servers tend to outsource data processing tasks to third-party servers.However,the incomplete trustworthiness of third-party servers have increased the risk of privacy leakage during data outsourcing.Therefore,encryption technology is continuously developed to protect the privacy of outsourced data.Current research efforts in developing efficient ciphertext-based kNN query algorithms are primarily limited to low-dimensional data,lacking scalability for high-dimensional data.Additionally,existing algorithms for RkNN queries inadequately consider user features and reputation values,and research on dynamic user interaction scenarios remains scant.Consequently,this paper aims to develop efficient and secure query schemes tailored to the outsourcing context,addressing potential privacy leakage issues associated with third-party servers offering kNN/RkNN query services.The main contributions can be summarized as follows:(1)We propose the "Efficient and Privacy-Preserving kNN Query Scheme for Outsourced High-Dimensional Data"(EPPQ),emphasizing the complete lifecycle from secure dimensionality reduction to secure kNN query on reduced-dimensional data.In the secure dimensionality reduction phase: on the one hand,EPPQ integrates principal component analysis(PCA)for dimensionality reduction to minimize computational overhead.On the other hand,addressing privacy concerns during the process of dimensionality reduction,by incorporating differential privacy,we propose the Privacy-Preserving Data Dimensionality Reduction Algorithm based on PCA(PDDRP).In the secure kNN query phase: for one thing,EPPQ facilitates the index of the reduced-dimensional data by k-d tree.To enhance the index efficiency,we innovatively propose plaintexts-based distance calculation definitions(PDC)and construct an efficient variant of k-d tree(Ek-d tree).For another,the Paillier homomorphic encryption technique is leveraged to safeguard privacy when outsourcing Ek-d tree to untrusted cloud servers.Additionally,for ciphertexts-based distance calculations and comparisons,we design the Secure Precomputed Distance protocol(SPCD)and Secure Comparison protocol(SCOM).Finally,we creatively present the Privacy-Preserving kNN Query Algorithm based on Ek-d tree(PKQKT)for efficient and secure kNN query.(2)We propose the "Dynamic and Privacy-Preserving RkNN Query Scheme for Outsourced Multi-Attribute Data"(DPRQ),emphasizing the complete lifecycle from secure key exchange to secure RkNN query.In the secure key exchange phase: on the one hand,leveraging the non-interactive key exchange(NIKE)protocol and the Diffie-Hellman twoparty key exchange algorithm,we devise a multi-party NIKE algorithm(2K-NIKE)to facilitate dynamic interaction of sensing users.On the other hand,by integrating derived shared key with symmetric encryption technique,2K-NIKE ensures encryption of sensing data and user identity IDs.In the secure RkNN query phase: firstly,to enhance data privacy and facilitate ciphertext-based RkNN queries,we integrate symmetric homomorphic encryption algorithm,designing the private RkNN query filtering(PRKF)and refinement(PRKR)algorithms to achieve multi-attribute data encoding and re-encryption.Then,the central server computes query results from filtering and refinement stages according to the proposed protocols,returning them to query agents.In conclusion,the proposed EPPQ scheme addresses the current inadequacy in privacypreserving kNN query algorithms for high-dimensional data,while the DPRQ scheme tackles privacy leakage issues and dynamic interaction demands in the context of crowd sensing.Security analysis indicates that the proposed schemes meet the required security requirements under the "honest-but-curious" model.Comparative experiments with state-of-the-art solutions have demonstrated that the proposed schemes exhibit excellent performance in terms of computational efficiency and query accuracy.更多还原