[發(fā)明專利]基于最大劃分和隨機數(shù)據(jù)塊的安全最近鄰查詢方法及系統(tǒng)

有效

• 申請?zhí)枺?/td>: 201210465742.2
• 申請日: 2012-11-16
• 公開（公告）號: CN102999594A
• 公開（公告）日: 2013-03-27
• 發(fā)明（設(shè)計）人: 姚斌;李飛飛;肖小奎
• 申請（專利權(quán)）人: 上海交通大學(xué)
• 主分類號: G06F17/30
• 分類號: G06F17/30;G06F21/60
• 代理公司: 上海思微知識產(chǎn)權(quán)代理事務(wù)所(普通合伙) 31237
• 代理人: 鄭瑋

1.一種基于最大劃分和隨機數(shù)據(jù)塊的安全最近鄰查詢方法，其特征在于，包括：

數(shù)據(jù)主生成包含外包數(shù)據(jù)庫的所有真實數(shù)據(jù)點的voronoi圖，其中，每個真實數(shù)據(jù)點的字節(jié)數(shù)相同,外包數(shù)據(jù)庫中的真實數(shù)據(jù)點的個數(shù)為N，N為正整數(shù)，所述外包數(shù)據(jù)庫為一至三維外包數(shù)據(jù)庫；

數(shù)據(jù)用戶或數(shù)據(jù)主給定參數(shù)K，數(shù)據(jù)主根據(jù)所述參數(shù)k將所述voronoi圖分割成為k個劃分，記錄每個劃分對應(yīng)的邊界，其中，每個劃分互不相交，不同劃分包含的真實數(shù)據(jù)點部分重復(fù)或完全不重復(fù)，k大于等于1且小于等于N，當(dāng)所述外包數(shù)據(jù)庫為一維外包數(shù)據(jù)庫時，每個劃分的邊界為兩個相鄰真實數(shù)據(jù)點之間的垂直平分線，當(dāng)所述外包數(shù)據(jù)庫為二維外包數(shù)據(jù)庫時，每個劃分的邊界為由與所述voronoi圖的X坐標(biāo)軸和Y坐標(biāo)軸平行的直線圍成的格子，用平行于Y坐標(biāo)軸的直線不斷分割當(dāng)前的最大的劃分或用平行X坐標(biāo)軸的直線不斷分割當(dāng)前的最大的劃分以生成所述格子，直至voronoi圖中的劃分的個數(shù)大于或等于所述參數(shù)k，其中，每次分割時，使平行于Y坐標(biāo)軸的直線或平行X坐標(biāo)軸的直線穿過voronoi圖的當(dāng)前的最大的劃分中的多邊形的頂點最多；

數(shù)據(jù)主在所述voronoi圖中隨機添加k’個劃分，并在k’個劃分中分別添加虛擬數(shù)據(jù)點，記錄每個劃分對應(yīng)的邊界，其中，每個劃分互不相交，不同劃分包含的虛擬數(shù)據(jù)點部分重復(fù)或完全不重復(fù)，k’為正整數(shù)；

數(shù)據(jù)主獲取所有劃分中包含最多個真實數(shù)據(jù)點或虛擬數(shù)據(jù)點的劃分的字節(jié)數(shù)作為最長字節(jié)數(shù)，在除包含最多個真實數(shù)據(jù)點或虛擬數(shù)據(jù)點的劃分之外的每個其它劃分中添加隨機字節(jié)，使除包含最多個真實數(shù)據(jù)點或虛擬數(shù)據(jù)點的劃分之外的每個其它劃分的字節(jié)數(shù)等于所述最長字節(jié)數(shù)；

數(shù)據(jù)主根據(jù)預(yù)設(shè)的哈希函數(shù)對每個邊界建立對應(yīng)的索引，并根據(jù)一預(yù)設(shè)的加密算法將加密后的所有劃分及其所有與相應(yīng)的邊界對應(yīng)的索引發(fā)送給服務(wù)器存儲；

數(shù)據(jù)主將所有劃分對應(yīng)的邊界、與所述加密算法對應(yīng)的解密算法和所述哈希函數(shù)發(fā)送給所述數(shù)據(jù)用戶存儲；

所述數(shù)據(jù)用戶確定真實查詢點，根據(jù)所述真實查詢點確定包含所述真實查詢點的劃分的對應(yīng)的邊界，根據(jù)所述哈希函數(shù)獲取與包含所述真實查詢點的劃分的對應(yīng)的邊界的對應(yīng)的索引，并將包含所述真實查詢點的劃分的對應(yīng)的邊界的對應(yīng)的索引發(fā)送給服務(wù)器；

所述服務(wù)器根據(jù)接收到的包含所述真實查詢點的劃分的對應(yīng)的邊界的對應(yīng)的索引向所述數(shù)據(jù)用戶發(fā)送對應(yīng)的加密后的包含所述真實查詢點的劃分；

所述數(shù)據(jù)用戶根據(jù)所述解密算法將接收到的加密后的包含所述真實查詢點的劃分進行解密，獲取包含所述真實查詢點的劃分，并從包含所述真實查詢點的劃分中獲取所述真實查詢點的最近鄰的真實數(shù)據(jù)點；

所述數(shù)據(jù)用戶確定偽查詢點，根據(jù)所述偽查詢點確定包含所述虛擬查詢點的劃分的對應(yīng)的邊界，根據(jù)所述哈希函數(shù)獲取與包含所述偽查詢點的劃分的對應(yīng)的邊界的對應(yīng)的索引，并將包含所述虛擬查詢點的劃分的對應(yīng)的邊界的對應(yīng)的索引發(fā)送給服務(wù)器；

所述服務(wù)器根據(jù)接收到的包含所述偽查詢點的劃分的對應(yīng)的邊界的對應(yīng)的索引向所述數(shù)據(jù)用戶發(fā)送對應(yīng)的加密后的包含所述偽查詢點的劃分。

2.一種基于最大劃分和隨機數(shù)據(jù)塊的安全最近鄰查詢系統(tǒng)，其特征在于，包括：

數(shù)據(jù)主，用于給定所述參數(shù)k，生成包含外包數(shù)據(jù)庫的所有真實數(shù)據(jù)點的voronoi圖，其中，每個真實數(shù)據(jù)點的字節(jié)數(shù)相同,外包數(shù)據(jù)庫中的真實數(shù)據(jù)點的個數(shù)為N，N為正整數(shù)，所述外包數(shù)據(jù)庫為一至三維外包數(shù)據(jù)庫；根據(jù)所述參數(shù)k將所述voronoi圖分割成為k個劃分，記錄每個劃分對應(yīng)的邊界，其中，每個劃分互不相交，不同劃分包含的真實數(shù)據(jù)點部分重復(fù)或完全不重復(fù)，k大于等于1且小于等于N，當(dāng)所述外包數(shù)據(jù)庫為一維外包數(shù)據(jù)庫時，每個劃分的邊界為兩個相鄰真實數(shù)據(jù)點之間的垂直平分線，當(dāng)所述外包數(shù)據(jù)庫為二維外包數(shù)據(jù)庫時，每個劃分的邊界為由與所述voronoi圖的X坐標(biāo)軸和Y坐標(biāo)軸平行的直線圍成的格子，用平行于Y坐標(biāo)軸的直線不斷分割當(dāng)前的最大的劃分或用平行X坐標(biāo)軸的直線不斷分割當(dāng)前的最大的劃分以生成所述格子，直至voronoi圖中的劃分的個數(shù)大于或等于所述參數(shù)k，其中，每次分割時，使平行于Y坐標(biāo)軸的直線或平行X坐標(biāo)軸的直線穿過voronoi圖的當(dāng)前的最大的劃分中的多邊形的頂點最多；在所述voronoi圖中隨機添加k’個劃分，并在k’個劃分中分別添加虛擬數(shù)據(jù)點，記錄每個劃分對應(yīng)的邊界，其中，每個劃分互不相交，不同劃分包含的虛擬數(shù)據(jù)點部分重復(fù)或完全不重復(fù)，k’為正整數(shù)；獲取所有劃分中包含最多個真實數(shù)據(jù)點或虛擬數(shù)據(jù)點的劃分的字節(jié)數(shù)作為最長字節(jié)數(shù)，在除包含最多個真實數(shù)據(jù)點或虛擬數(shù)據(jù)點的劃分之外的每個其它劃分中添加隨機字節(jié)，使除包含最多個真實數(shù)據(jù)點或虛擬數(shù)據(jù)點的劃分之外的每個其它劃分的字節(jié)數(shù)等于所述最長字節(jié)數(shù)；根據(jù)預(yù)設(shè)的哈希函數(shù)對每個邊界建立對應(yīng)的索引，并根據(jù)一預(yù)設(shè)的加密算法將加密后的所有劃分及其所有與相應(yīng)的邊界對應(yīng)的索引發(fā)送給服務(wù)器存儲；將所有劃分對應(yīng)的邊界、與所述加密算法對應(yīng)的解密算法和所述哈希函數(shù)發(fā)送給所述數(shù)據(jù)用戶存儲；

數(shù)據(jù)用戶，用于給定所述參數(shù)k，確定真實查詢點，根據(jù)所述真實查詢點確定包含所述真實查詢點的劃分的對應(yīng)的邊界，根據(jù)所述哈希函數(shù)獲取與包含所述真實查詢點的劃分的對應(yīng)的邊界的對應(yīng)的索引，并將包含所述真實查詢點的劃分的對應(yīng)的邊界的對應(yīng)的索引發(fā)送給服務(wù)器；根據(jù)所述解密算法將接收到的加密后的包含所述真實查詢點的劃分進行解密，獲取包含所述真實查詢點的劃分，并從包含所述真實查詢點的劃分中獲取所述真實查詢點的最近鄰的真實數(shù)據(jù)點；確定偽查詢點，根據(jù)所述偽查詢點確定包含所述虛擬查詢點的劃分的對應(yīng)的邊界，根據(jù)所述哈希函數(shù)獲取與包含所述偽查詢點的劃分的對應(yīng)的邊界的對應(yīng)的索引，并將包含所述虛擬查詢點的劃分的對應(yīng)的邊界的對應(yīng)的索引發(fā)送給服務(wù)器；

服務(wù)器，用于根據(jù)接收到的包含所述真實查詢點的劃分的對應(yīng)的邊界的對應(yīng)的索引向所述數(shù)據(jù)用戶發(fā)送對應(yīng)的加密后的包含所述真實查詢點的劃分；接收到的包含所述偽查詢點的劃分的對應(yīng)的邊界的對應(yīng)的索引向所述數(shù)據(jù)用戶發(fā)送對應(yīng)的加密后的包含所述偽查詢點的劃分。