基于最大划分和随机数据块的安全最近邻查询方法及系统

摘要

本发明涉及一种基于最大划分和随机数据块的安全最近邻查询方法及系统，所述方法包括：数据主将包含外包数据库的voronoi图分割成为k个划分，记录划分的边界，在划分中添加随机字节，并根据预设的哈希函数对每个边界建立对应的索引，并将加密后的所有划分及其对应的索引发送给服务器，将所有划分对应的边界发送给数据用户；数据用户将包含真实查询点的划分对应的索引发送给服务器；服务器向数据用户发送加密后的包含真实查询点的划分；数据用户获取加密后的包含所述真实查询点的划分，并解密后计算出最近邻，在数据用户对服务器上存储的外包数据库中进行最近邻查询时，使服务器无法获知外包数据库中的数据、查询点及查询结果，保证数据安全。

主权项

一种基于最大划分和随机数据块的安全最近邻查询方法，其特征在于，包括：数据主生成包含外包数据库的所有真实数据点的voronoi图，其中，每个真实数据点的字节数相同,外包数据库中的真实数据点的个数为N，N为正整数，所述外包数据库为一至三维外包数据库；数据用户或数据主给定参数K，数据主根据所述参数k将所述voronoi图分割成为k个划分，记录每个划分对应的边界，其中，每个划分互不相交，不同划分包含的真实数据点部分重复或完全不重复，k大于等于1且小于等于N，当所述外包数据库为一维外包数据库时，每个划分的边界为两个相邻真实数据点之间的垂直平分线，当所述外包数据库为二维外包数据库时，每个划分的边界为由与所述voronoi图的X坐标轴和Y坐标轴平行的直线围成的格子，用平行于Y坐标轴的直线不断分割当前的最大的划分或用平行X坐标轴的直线不断分割当前的最大的划分以生成所述格子，直至voronoi图中的划分的个数大于或等于所述参数k，其中，每次分割时，使平行于Y坐标轴的直线或平行X坐标轴的直线穿过voronoi图的当前的最大的划分中的多边形的顶点最多；数据主在所述voronoi图中随机添加k’个划分，并在k’个划分中分别添加虚拟数据点，记录每个划分对应的边界，其中，每个划分互不相交，不同划分包含的虚拟数据点部分重复或完全不重复，k’为正整数；数据主获取所有划分中包含最多个真实数据点或虚拟数据点的划分的字节数作为最长字节数，在除包含最多个真实数据点或虚拟数据点的划分之外的每个其它划分中添加随机字节，使除包含最多个真实数据点或虚拟数据点的划分 之外的每个其它划分的字节数等于所述最长字节数；数据主根据预设的哈希函数对每个边界建立对应的索引，并根据一预设的加密算法将加密后的所有划分及其所有与相应的边界对应的索引发送给服务器存储；数据主将所有划分对应的边界、与所述加密算法对应的解密算法和所述哈希函数发送给所述数据用户存储；所述数据用户确定真实查询点，根据所述真实查询点确定包含所述真实查询点的划分的对应的边界，根据所述哈希函数获取与包含所述真实查询点的划分的对应的边界的对应的索引，并将包含所述真实查询点的划分的对应的边界的对应的索引发送给服务器；所述服务器根据接收到的包含所述真实查询点的划分的对应的边界的对应的索引向所述数据用户发送对应的加密后的包含所述真实查询点的划分；所述数据用户根据所述解密算法将接收到的加密后的包含所述真实查询点的划分进行解密，获取包含所述真实查询点的划分，并从包含所述真实查询点的划分中获取所述真实查询点的最近邻的真实数据点；所述数据用户确定伪查询点，根据所述伪查询点确定包含所述虚拟查询点的划分的对应的边界，根据所述哈希函数获取与包含所述伪查询点的划分的对应的边界的对应的索引，并将包含所述虚拟查询点的划分的对应的边界的对应的索引发送给服务器；所述服务器根据接收到的包含所述伪查询点的划分的对应的边界的对应的索引向所述数据用户发送对应的加密后的包含所述伪查询点的划分。