作为机器学习中最基础的算法之一，k-NN 查询在各个领域有着广泛的应用。近 年来，随着云计算的快速发展，将 k-NN 查询服务外包给云服务器成为当下的发展趋 势。由于云服务器是不完全可信的，因此，直接将敏感数据上传到云端进行 k-NN 查 询将不可避免地带来安全问题。为了解决这个问题，现有的 k-NN 查询方案通常对数 据加密后上传。然而，服务器在密文数据上进行查询将产生额外的计算开销，且方案 中多个参与方共享密钥具有极大的安全隐患。本文针对 k-NN 查询中存在的数据安全、 密钥共享以及查询效率等问题做出了以下的研究工作。

1、提出了基于 PaillierTD 密码系统的在多密钥环境下可验证的 k-NN 隐私保护查 询方案。首先，该方案将 PaillierTD 的私钥随机拆分为互不相关的多组，为每个询问 用户分配唯一的部分私钥，并将与之对应的另一部分私钥保存在云服务器。每个询问 用户的部分私钥只能解密自己的结果密文，而不能解密密文数据库、其他用户的询问 密文和查询的结果密文，完成多密钥设置，实现密钥保密的功能。其次，该方案采用 “K-D”树和“优先队列”相结合的方式优化 k-NN 查询的过程，提出了对密文数据 创建和调整优先队列的算法，减少了密文状态下欧氏距离的计算和比较操作，有效提 高了查询的效率。最后，考虑到服务器可能受到经济诱惑返回给询问用户伪造、篡改 的数据或数据库中询问数据的非 k 近邻数据，该方案实现了结果验证的功能，允许询 问用户验证结果的正确性和完备性。本方案的理论分析和实验测试表明，该方案是一 个隐私保护、可验证且支持多密钥的 k-NN 查询方案。

2、提出了基于随机映射森林的支持多密钥的高效安全 k-NN 查询方案。首先，该 方案对数据库中的数据创建随机映射森林，利用其随机性和集成性提高 k-NN 查询的 效率。然后，基于数据打包技术和 DT-PKC 密码系统，该方案提出安全的点乘计算协 议。该协议可以计算询问数据在节点中的投影系数，进而选择询问数据在森林中每棵 随机映射树所属的某个叶子节点。此外，该协议还可以帮助云服务器实现在随机映射 森林中密文数据的插入、删除操作，使得云服务器按照数据拥有者的要求完成云端密 文数据库的动态可更新。该方案提出的安全的最小 k 距离协议使得服务器能够在数据 集中找到询问数据的 k 近邻数据却无法获得这 k 条数据的索引信息，有效保护访问模 式隐私。最后，该方案对 DT-PKC 密码系统的主私钥进行拆分，同样完成了多密钥设 置，实现密钥保密的功能。本方案的理论分析和实验测试表明，该方案是一个支持多 密钥、安全高效且数据可更新的 k-NN 查询方案。

As one of the most fundamental algorithms in machine learning, the k-Nearest Neighbor (kNN) query has been widely used in various fields. In recent years, with the rapid development of cloud computing, it is a current development trend to outsource k-NN query services to cloud servers. Since cloud servers are not completely trusted, it will inevitably lead to security issue if sensitive data is uploaded directly to the cloud for k-NN query. In order to address this issue, the existing k-NN query schemes usually encrypt the data and then upload it. However, querying the encrypted data will incur additional computational overhead on the servers, and there is a great security risk for multiple participants to share the key in the scheme. In this thesis, we make the following research work on the data security, key sharing and query efficiency in k-NN query.

1. This thesis proposes a verifiable and privacy-preserving k-NN query scheme based on PaillierTD cryptosystem in a multiple key environment. First of all, the scheme randomly splits the private key of PaillierTD into multiple unrelated groups, assigns a unique partial private key to each query user, and stores the corresponding partial private key in the cloud server. The partial private key of each query user can only decrypt its own encrypted result, but can not decrypt the encrypted database, the encrypted query and the encrypted result of other users, which completes the setting of multiple key and realizes the key confidentiality. Secondly, the scheme adopts the combination of K-D tree and priority queue to optimize the query process. Therefore, this scheme proposes the algorithm of creating and adjusting the priority queue for encrypted data, which reduces the number of operations to calculate and compare the Euclidean distance and effectively improves the query efficiency. Finally, considering that the server may be tempted by the economy to return the falsified or tampered data, or non-k-nearest neighbors of the query in the database, the scheme implements the function of result verification, allowing the query user to verify the correctness and completeness of the result. The theoretical analysis and experimental test of this scheme indicate that it is a privacy-preserving and verifiable k-NN query scheme that supports multiple keys.

2. This thesis proposes an efficient and secure k-NN query scheme that supports multiple keys based on random projection forests. First of all, the scheme creates a random projection forests for data in the database and uses its randomness and integration to improve the efficiency of k-NN query. Then, the scheme proposes a secure dot product calculation protocol based on the data packing technique and DT-PKC cryptosystem to calculate the projection coefficients of the query data in each node and further find a certain leaf node in each random projection tree to which the query data belongs. In addition, the secure dot product calculation protocol can also help the cloud server to achieve inserting and deleting encrypted data in the random projection forests, so that the cloud server can complete the dynamic updateability of the encrypted database in the cloud as requested by the data owner. The secure minimum k-distance protocol proposed by this scheme enables the server to find the k-nearest neighbors of the query in the dataset without knowing the index information of these data, which effectively protects the privacy of access pattern. Finally, the scheme splits the master private key of the DT-PKC cryptosystem, which also completes the setting of multiple key and achieves key confidentiality. The theoretical analysis and experimental tests of this scheme indicate that it is a secure and efficient k-NN query scheme that supports multiple keys and data update.