基於最小冗餘劃分和隨機數的安全最近鄰查詢方法及系統的製作方法

2023-06-03 02:13:21

專利名稱：基於最小冗餘劃分和隨機數的安全最近鄰查詢方法及系統的製作方法
技術領域：
本發明涉及安全查詢處理領域，一種基於最小冗餘劃分和隨機數的安全最近鄰查詢方法及系統。
背景技術：
安全查詢處理領域的現有研究涉及加密資料庫上的基本SQL查詢(參見文獻3 H. Hacigumusj B. R. Iyer, C. Li，and S. Mehrotra. Executing SQL overencrypted datain the database service provider model. In SIGMOD，2002)、聚合查詢(參見文獻 4 :
H.Hacigumusj B. R. Iyer, and S. Mehrotra. Efficient execution ofaggregation queriesover encrypted relational databases. In DASFAAj pages 125 - 136，2004 和文獻 5 E. Mykletun and G.Tsudik. Aggregation queries in thedatabase—as—a—servicemodel. In DBSecj 2006)和範圍查詢(參見文獻 6 :B. Horej S. Mehrotra, M. Canimj andM. Kantarcioglu. Secure multidimensional range queriesover outsourced data.VLDBJ. To Appear.和文獻 7 :Ε· Shij J. Bethencourtj H. T. _Η· Chan, D. X. Song, andA. Perrig. Multi-dimensional range query over encrypted data. In IEEE Symposium onSecurity and Privacy, pages 350-364，2007)。正如諸多現有研究(參見文獻 I :H. Hu，J.Xuj C. Renj and B. Choi. Processing private queriesover untrusted data cloud throughprivacy homomorphism. In ICDEj pages 601-612，2011 和文獻 2 W. K. Wong, D. W. _L.Cheung,B. Kaoj and N. Mamoulis. Secure knn computation on encrypted databases. InSIGMOD, pages 139 - 152，2009和文獻6和文獻7)所證明的，為滿足一定的安全性要求和獲得更高的效率，較複雜的查詢類型往往需要一些特殊處理。特別的，針對SNN問題現在已有不少前人所做的研究工作(參見文獻I和文獻2)，然而他們所提出的解決方案最後往往被證明是不安全的，可以被輕而易舉地攻擊成功。Hacigumus 等人首先提出了「外包資料庫」(outsourced database，0DB)模型(參見文獻 8 H. Hacigumusj B. R. Iyer, and S. Mehrotra. Providing database as aservice.In I⑶E，2002)，在這個模型裡，數據擁有者(data owner)將「數據管理」及「查詢應答」兩項服務外包給不可靠的服務提供商(service provider)。關於ODB的安全性研究旨在通過加密及在加密數據上進行查詢處理來確保數據安全。例如，使用一種保序加密法(order-preserving encryption scheme, 0PES,參見文獻 9 :R. Agrawalj J. Kiernanj R.Srikantj and Y. Xu. Order preserving encryption for numeric data. In SIGMOD, 2002),對一序數域(ordinal domain)應用函數E，使得對任一對滿足x < y的值x，y，都有E(x)=d+l,則此等式組可解。對於一 2級攻擊，攻擊者可見DB中的一組點P。由於DPT保留了各維間的相關性，Liu等使用PCA確定點集P中和轉換後所得資料庫中的主成分。通過匹配主成分，攻擊者可以對N和t做出準確估計(參見文獻8)。不可靠平臺上的kNN計算也是「適地性服務」(LBS)系統需要考慮的問題。在LBS模型中，伺服器擁有一個元組集(也即「興趣點」point of interest, Ρ0Ι)ο用戶向伺服器 提交查詢(範圍查詢或kNN查詢),獲取想要的興趣點。其中主要的安全目標即為保護查詢點的位置信息，另外一些模型也會考慮POI的隱私問題。「k匿名」模型是常被使用，以將查詢點的位置轉換為一個空間範圍，如此這一範圍中至少包含了其他k-Ι的點，伺服器則難以在其中確定出用戶(查詢點)的位置。儘管這一模型可以用來解決我們的問題，但它也有一定缺陷。首先，匿名後的數據會近似地暴露出原始數據值；其次，在特定模型中(參見文獻15 G. Ghinita, P. Kalnis, A. Khoshgozaran, C. Shahabi, and K. L. Tan. Privatequeries inlocation based services:Anonymizers are not necessary. In SIGMOD, 2008),資料庫被假定為伺服器所有，因此伺服器能看到原始數據；再次，在一些系統(諸如「粗索引」系統)中，伺服器通常返回查詢結果的超集以供用戶進行後處理，這增添了用戶負擔，對於一些「輕量級」(light-weight)用戶端,這甚至是不可承受的。Khoshgozaran等人提出了一個可以為kNN查詢進行加密的LBS模型(參見文獻16 :A. Khoshgozaran and C. Shahabi. Blindevaluation ofnearest neighbor queries using space transformation to preservelocation privacy. InSSTD, 2007)。其主要思想是使用Hilbert曲線來對數據點和查詢進行「加密」。各點的Hilbert值被送往伺服器。然後在Hilbert轉換後所得的空間中計算kNN得出近似結果。這種方法除了返回的是近似結果，還存在DPT類似的問題，容易被攻擊成功。

發明內容
本發明的目的在於提供一種基於最小冗餘劃分和隨機數的安全最近鄰查詢方法及系統，能夠在數據用戶對伺服器上存儲的外包資料庫中進行最近鄰查詢時，使伺服器無法獲知外包資料庫中的數據、數據用戶的查詢點及最近鄰的查詢結果，保證數據安全。為解決上述問題，本發明提供一種基於最小冗餘劃分和隨機數的安全最近鄰查詢方法，包括數據主生成包含外包資料庫的所有真實數據點的voronoi圖,其中，每個真實數據點的字節數相同，外包資料庫中的真實數據點的個數為N，N為正整數，所述外包資料庫為一至三維外包資料庫；
數據用戶或數據主給定參數K，數據主根據所述參數k將所述VOTonoi圖分割成為k個劃分，記錄每個劃分對應的邊界，每個劃分互不相交，不同劃分包含的數據點部分重複或完全不重複，k大於等於I且小於等於N，其中，當所述外包資料庫為一維外包資料庫時，每個劃分的邊界為兩個相鄰真實數據點之間的垂直平分線，當所述外包資料庫為二維外包資料庫時，每個劃分的邊界為由與所述voronoi圖的X坐標軸和Y坐標軸平行的直線圍成的格子，用平行於Y坐標軸的直線不斷分割當前的最大的劃分和與所述最大的劃分在同一條平行Y坐標軸的直線上的相鄰的劃分，或用平行X坐標軸的直線不斷分割當前的最大的劃分和與所述最大的劃分在同一條平行X坐標軸的直線上的相鄰的劃分以生成所述格子，直至VOTonoi圖中的劃分的個數大於或等於所述參數，其中，每次分割時，使平行於Y坐標軸的直線或平行X坐標軸的直線穿過voixmoi圖中的多邊形的頂點最多，當劃分的個數大於所述參數k時，通過逐步合併最小劃分的方式將voronoi圖中的劃分的個數減至所述參數k ;數據主在所述VOTonoi圖中隨機添加k』個劃分，並在k』個劃分中分別添加虛擬數據點，記錄每個劃分對應的邊界，其中，每個劃分互不相交，不同劃分包含的虛擬數據點 部分重複或完全不重複，k』為正整數；數據主獲取所有劃分中包含最多個真實數據點或虛擬數據點的劃分的字節數作為最長字節數，在除包含最多個真實數據點或虛擬數據點的劃分之外的每個其它劃分中添加隨機字節，使除包含最多個真實數據點或虛擬數據點的劃分之外的每個其它劃分的字節數等於所述最長字節數；數據主根據預設的哈希函數對每個邊界建立對應的索引，並根據一預設的加密算法將加密後的所有劃分及其所有與相應的邊界對應的索引發送給伺服器存儲；數據主將所有劃分對應的邊界、與所述加密算法對應的解密算法和所述哈希函數發送給所述數據用戶存儲；所述數據用戶確定真實查詢點，根據所述真實查詢點確定包含所述真實查詢點的劃分的對應的邊界，根據所述哈希函數獲取與包含所述真實查詢點的劃分的對應的邊界的對應的索引，並將包含所述真實查詢點的劃分的對應的邊界的對應的索引發送給伺服器；所述伺服器根據接收到的包含所述真實查詢點的劃分的對應的邊界的對應的索引向所述數據用戶發送對應的加密後的包含所述真實查詢點的劃分；所述數據用戶根據所述解密算法將接收到的加密後的包含所述真實查詢點的劃分進行解密，獲取包含所述真實查詢點的劃分，並從包含所述真實查詢點的劃分中獲取所述真實查詢點的最近鄰的真實數據點；所述數據用戶確定偽查詢點，根據所述偽查詢點確定包含所述虛擬查詢點的劃分的對應的邊界，根據所述哈希函數獲取與包含所述偽查詢點的劃分的對應的邊界的對應的索引，並將包含所述虛擬查詢點的劃分的對應的邊界的對應的索引發送給伺服器；所述伺服器根據接收到的包含所述偽查詢點的劃分的對應的邊界的對應的索引向所述數據用戶發送對應的加密後的包含所述偽查詢點的劃分。根據本發明的另一面，提供一種基於最小冗餘劃分和隨機數的安全最近鄰查詢系統，包括
數據主，用於給定所述參數k，生成包含外包資料庫的所有真實數據點的voronoi圖，其中，每個真實數據點的字節數相同，外包資料庫中的真實數據點的個數為N，N為正整數，所述外包資料庫為一至三維外包資料庫；根據參數k將所述VOTonoi圖分割成為k個劃分，記錄每個劃分對應的邊界，其中，每個劃分互不相交，不同劃分包含的數據點部分重複或完全不重複，k大於等於I且小於等於N，當所述外包資料庫為一維外包資料庫時，每個劃分的邊界為兩個相鄰真實數據點之間的垂直平分線，當所述外包資料庫為二維外包資料庫時，每個劃分的邊界為由與所述voronoi圖的X坐標軸和Y坐標軸平行的直線圍成的格子，所述數據主用平行於Y坐標軸的直線不斷分割當前的最大的劃分和與所述最大的劃分在同一條平行Y坐標軸的直線上的相鄰的劃分，或用平行X坐標軸的直線不斷分割當前的最大的劃分和與所述最大的劃分在同一條平行X坐標軸的直線上的相鄰的劃分以生成所述格子，直至voronoi圖中的劃分的個數大於或等於所述參數k，其中，每次分割時，使平行於Y坐標軸的直線或平行X坐標軸的直線穿過voronoi圖中的多邊形的頂點最多，當劃分的個數大於所述參數k時，通過逐步合併最小劃分的方式將voronoi圖中的劃分的個數減至所述參數k ;在所述voronoi圖中隨機添加k』個劃分，並在k』個劃分中分別添加虛擬數 據點，記錄每個劃分對應的邊界，其中，每個劃分互不相交，不同劃分包含的虛擬數據點部分重複或完全不重複，k』為正整數；獲取所有劃分中包含最多個真實數據點或虛擬數據點的劃分的字節數作為最長字節數，在除包含最多個真實數據點或虛擬數據點的劃分之外的每個其它劃分中添加隨機字節，使除包含最多個真實數據點或虛擬數據點的劃分之外的每個其它劃分的字節數等於所述最長字節數；根據預設的哈希函數對每個邊界建立對應的索弓丨，並根據一預設的加密算法將加密後的所有劃分及其所有與相應的邊界對應的索引發送給伺服器存儲；將所有劃分對應的邊界、與所述加密算法對應的解密算法和所述哈希函數發送給所述數據用戶存儲；數據用戶，用於給定所述參數k，確定真實查詢點，根據所述真實查詢點確定包含所述真實查詢點的劃分的對應的邊界，根據所述哈希函數獲取與包含所述真實查詢點的劃分的對應的邊界的對應的索引，並將包含所述真實查詢點的劃分的對應的邊界的對應的索引發送給伺服器；根據所述解密算法將接收到的加密後的包含所述真實查詢點的劃分進行解密，獲取包含所述真實查詢點的劃分，並從包含所述真實查詢點的劃分中獲取所述真實查詢點的最近鄰的數據點；確定偽查詢點，根據所述偽查詢點確定包含所述虛擬查詢點的劃分的對應的邊界，根據所述哈希函數獲取與包含所述偽查詢點的劃分的對應的邊界的對應的索引，並將包含所述虛擬查詢點的劃分的對應的邊界的對應的索引發送給伺服器；伺服器，用於根據接收到的包含所述真實查詢點的劃分的對應的邊界的對應的索引向所述數據用戶發送對應的加密後的包含所述真實查詢點的劃分；根據接收到的包含所述偽查詢點的劃分的對應的邊界的對應的索引向所述數據用戶發送對應的加密後的包含所述偽查詢點的劃分。與現有技術相比，本發明通過數據主生成包含外包資料庫的所有真實數據點的voronoi圖，其中，每個真實數據點的字節數相同，外包資料庫中的真實數據點的個數為N，N為正整數，所述外包資料庫為一至三維外包資料庫；數據用戶或數據主給定參數K，數據主根據所述參數k將所述VOTonoi圖分割成為k個劃分，記錄每個劃分對應的邊界，每個劃分互不相交，不同劃分包含的數據點部分重複或完全不重複，k大於等於I且小於等於N，其中，當所述外包資料庫為一維外包資料庫時，每個劃分的邊界為兩個相鄰真實數據點之間的垂直平分線，當所述外包資料庫為二維外包資料庫時，每個劃分的邊界為由與所述VOTonoi圖的X坐標軸和Y坐標軸平行的直線圍成的格子，用平行於Y坐標軸的直線不斷分割當前的最大的劃分和與所述最大的劃分在同一條平行Y坐標軸的直線上的相鄰的劃分，或用平行X坐標軸的直線不斷分割當前的最大的劃分和與所述最大的劃分在同一條平行X坐標軸的直線上的相鄰的劃分以生成所述格子，直至voronoi圖中的劃分的個數大於或等於所述參數，其中，每次分割時，使平行於Y坐標軸的直線或平行X坐標軸的直線穿過VOTonoi圖中的多邊形的頂點最多，當劃分的個數大於所述參數k時，通過逐步合併最小劃分的方式將voronoi圖中的劃分的個數減至所述參數k ;數據主在所述voronoi圖中隨機添加k』個劃分，並 在k』個劃分中分別添加虛擬數據點，記錄每個劃分對應的邊界，其中，每個劃分互不相交，不同劃分包含的虛擬數據點部分重複或完全不重複，k』為正整數；數據主獲取所有劃分中包含最多個真實數據點或虛擬數據點的劃分的字節數作為最長字節數，在除包含最多個真實數據點或虛擬數據點的劃分之外的每個其它劃分中添加隨機字節，使除包含最多個真實數據點或虛擬數據點的劃分之外的每個其它劃分的字節數等於所述最長字節數；數據主根據預設的哈希函數對每個邊界建立對應的索引，並根據一預設的加密算法將加密後的所有劃分及其所有與相應的邊界對應的索引發送給伺服器存儲；數據主將所有劃分對應的邊界、與所述加密算法對應的解密算法和所述哈希函數發送給所述數據用戶存儲；所述數據用戶確定真實查詢點，根據所述真實查詢點確定包含所述真實查詢點的劃分的對應的邊界，根據所述哈希函數獲取與包含所述真實查詢點的劃分的對應的邊界的對應的索引，並將包含所述真實查詢點的劃分的對應的邊界的對應的索引發送給伺服器；所述伺服器根據接收到的包含所述真實查詢點的劃分的對應的邊界的對應的索引向所述數據用戶發送對應的加密後的包含所述真實查詢點的劃分；所述數據用戶根據所述解密算法將接收到的加密後的包含所述真實查詢點的劃分進行解密，獲取包含所述真實查詢點的劃分，並從包含所述真實查詢點的劃分中獲取所述真實查詢點的最近鄰的真實數據點；所述數據用戶確定偽查詢點，根據所述偽查詢點確定包含所述虛擬查詢點的劃分的對應的邊界，根據所述哈希函數獲取與包含所述偽查詢點的劃分的對應的邊界的對應的索引，並將包含所述虛擬查詢點的劃分的對應的邊界的對應的索引發送給伺服器；所述伺服器根據接收到的包含所述偽查詢點的劃分的對應的邊界的對應的索引向所述數據用戶發送對應的加密後的包含所述偽查詢點的劃分，能夠在數據用戶對伺服器上存儲的外包資料庫中進行最近鄰查詢時，使伺服器無法獲知外包資料庫中的數據、數據用戶的查詢點及最近鄰的查詢結果，保證數據安全。


圖I是本發明一實施例的基於最小冗餘劃分和隨機數的安全最近鄰查詢方法的流程圖；圖2是本發明一實施例的基於最小冗餘劃分和隨機數的安全最近鄰查詢方法的劃分示意圖；圖3是本發明一實施例的一維空間下劃分示意圖；圖4是本發明一實施例的MinDp方法的劃分示意圖5a是本發明一實施例的MinDp劃分方法下k對劃分時間代價的影響圖；圖5b是本發明一實施例的MinDp劃分方法下| D |對劃分時間代價的影響圖；圖6a是本發明一實施例的劃分大小的平均值、最大值和最小值隨參數k變化情況圖；圖6b是本發明一實施例的劃分大小的平均值、最大值和最小值隨|d|變化情況7a是本發明一實施例的MinDp劃分方法的總運行時間隨參數k變化情況圖；圖7b是本發明一實施例的MinDp劃分方法的總運行時間隨ID |變化情況圖；圖8a是本發明一實施例的MinDp劃分方法下| E⑶|隨k變化情況圖；圖8b是本發明一實施例的MinDp劃分方法下| E⑶|隨| D |變化情況圖； 圖9a是本發明一實施例的MinDp劃分方法下查詢通信代價隨k變化情況圖；圖9b是本發明一實施例的MinDp劃分方法下查詢通信代價隨ID |變化情況圖；圖IOa是本發明一實施例的MinDp劃分方法下查詢時間隨ID |變化情況圖；圖IOb是本發明一實施例的MinDp劃分方法下查詢時間隨k變化情況圖；圖11是本發明一實施例的基於最小冗餘劃分和隨機數的安全最近鄰查詢系統的功能模塊示意圖。
具體實施例方式為使本發明的上述目的、特徵和優點能夠更加明顯易懂，下面結合附圖和具體實施方式
對本發明作進一步詳細的說明。隨著「雲計算」概念及其應用的日益普及，針對「雲」上的加密數據集E⑶的「安全查詢問題」得到了越來越多的關注。本發明即對其中的「安全最近鄰」(secure nearestneighbor, SNN)問題進行了較為深入的研究；該問題涉及數據主(data owner)、數據用戶(client)和伺服器(server)三方,數據用戶會向伺服器發送查詢密文(encrypted query,E (q))來獲取查詢點在E⑶中的最近數據點(B卩「最近鄰」)的密文，但要保證不能讓伺服器獲知數據和查詢的具體內容。具體說，SNN問題涉及數據主、數據用戶和伺服器三方及所述三方其相應的動作(I)數據主擁有由d維歐式點或對象構成的外包資料庫D，並會將D外包給不完全可靠的伺服器。(2)數據用戶需要對所述外包資料庫D進行查詢。(3)伺服器不完全可靠，會因為自身原因或第三方原因而窺探來自數據主的數據內容和來自數據用戶的查詢內容。為了讓數據用戶能在外包資料庫D上進行最近鄰(NN, nearest neighbor),查詢，卻不會讓伺服器獲知數據主的外包資料庫D中的數據、數據用戶的真實查詢及查詢結果的具體信息，數據主須對外包資料庫D應用某種加密算法E進行加密，可以用E(D)代表D的密文，用E—1代表相應的解密算法。相似的，數據用戶應將其查詢點q (具體代表一個查詢點)加密得到E (q)發送給伺服器，這裡需要力圖保證SNN方法在安全性上同數據主使用的加密算法E是一樣的，也就是說，所有E在SNN方法中被證明是安全(在選擇明文攻擊下是不可分辨的，或在選擇密文攻擊下是不可分辨的)的攻擊模型。事實上可以證明，在只給定E(q)和E(D)的條件下，伺服器不可能查找到精準的查詢點最近鄰。但若不要求伺服器給出SNN查詢結果的精準定位，而只需給出查詢結果的一個「大致定位」呢？不妨設想一個非常簡單直接的查詢處理方法數據主將外包資料庫D看做一個整體進行加密得到E(D)後，傳送給伺服器；而伺服器可以將整個E(D)作為查詢結果返回給數據用戶；數據用戶再用E_htE(D)進行解密(假定數據主與數據用戶共享E—1)得到D，從而可以在本地計算出SNN查詢的結果一可將這一 「樸素」的方法稱為「(直接)傳送D」(Send-D方法)算法。顯然，這種算法具有與E相同的安全性，但卻十分低效。於是在此基礎上，如圖I所示，進一步提出了更為高效的SNN處理方法，即本發明提供的一種基於最小冗餘劃分和隨機數的安全最近鄰查詢方法(secure voronoidiagram, SVD),包括預處理階段步驟SI S5，查詢階段包括步驟S6 S8，步驟S6 S8可以根據實際需要不斷重複其中，步驟SI，數據主生成包含外包資料庫D的所有真實 數據點Pi的voronoi圖，其中，每個真實數據點Pi的字節數相同，外包資料庫中的真實數據點的個數為N，N為正整數，所述外包資料庫為一至三維外包資料庫。由於在後續步驟S2中要產生外包資料庫D的k個劃分，這裡一個關鍵問題就是如何產生外包資料庫D的(可能存在重疊的)「劃分」G(D)HG1, . . .，GJ，考慮到的目標是有兩個(I)SNN查詢結果(查詢點的最近鄰)至少應被包含於某一划分中，且(2)數據用戶能夠用儘可能小的信息量確定出Gi以降低查詢代價，因此一個自然的選擇就是用基於外包資料庫D的VOTonoi圖來構建G(D)，其中每個數據點Pi M一個 voronoi cell 表不。本發明需要針對以下四個問題問題一邊界P (D)用voronoi cell來描述空間代價太大。例如，當所述外包資料庫D為二維即d=2時,每個voronoi cell是一個任意形狀的凸多邊形,並且這些多邊形平均會有6個頂點。因此，如此表示邊界P(D)所佔的存儲空間將比存儲外包資料庫D本身的
大得多。問題二 如何給邊界P(D)建立索引以使數據用戶能夠迅速地確定所需要的原始索引值i。這一問題在邊界P(D)中元素具有不規則邊界時會顯得尤為突出，例如當Bj e P(D)為一 voronoi cell時(此時Bj即是任意形狀的的凸多邊形)。問題三保證IE(Gi) =Ie(Gj) I (i Φ j)，如此伺服器才不會根據劃分(密文)的大小情況區分出它們，進而了解劃分情況。在任意安全加密算法E中我們都需保證這一點，因此需對G (D)加以強制約束GiIb=IGjIb (i關j)，其中Gi |b表示劃分Gi的字節數(注意區分表示Gi中數據點的個數為|G」)。問題四數據用戶在本地計算出滿足nn(q，D) e Gi的原始索引值i後，不應將i直接送至伺服器獲取E (Gi)，這樣方可保證伺服器不會在查詢處理過程中獲知任何關於劃分情況的信息。若數據用戶只向伺服器發送i的密文，那麼這一問題就不存在了 ；但這意味著伺服器必須能通過i的密文查找到E(Gi)。步驟S2，數據用戶或數據主給定參數K，數據主根據所述參數k將所述VOTonoi圖G(D)分割成為k個劃分G1,, Gk,記錄每個劃分對應的邊界P (D) = {B」 . . .，BJ，其中，每個劃分互不相交，不同劃分包含的數據點部分重複或完全不重複，k大於等於I且小於等於N。具體的，根據用戶給定的參數k將D分割為k部分，每個這樣的部分稱為一個「劃分」(各劃分之間允許相交，即各劃分可含有相同數據點)，即有G(D)HG1,. . .，Gk}，然後將傳送至所述伺服器。在這個過程中，還需對各劃分的「幾何邊界」P⑶=取，...，BJ (其中Bi為劃分Gi的幾何邊界)進行存儲，這樣的信息在保證足夠描述出劃分情況的前提下，所佔空間當然是越小越好。這裡先考慮一種極端情形如果令k=N (N為數據集D的數據點的個數，S卩|D| )，那麼每個Gi即由單一數據點Pi e D構成的集合,而邊界P (D)即為D的voronoi cell的集合。設Pi的 voronoi cell為VcJpi為Vci所包含),那麼給定任意查詢點q,數據用戶需查找包含q的voronoi cell ;假定qVCi，則數據用戶需向伺服器請求獲取E(Gi);這裡顯然有nn (q, D) =Pi 以及 Gi= {pj ,而算法返回 nn (q, E—1 (E (Gi))) =nn (q, {pj) =Pi,可見為正確結果。可以考慮把上述思想推廣應用到k〈〈N的一般情形。步驟S2具體包括步驟S21和步驟S22 步驟S21，當所述外包資料庫為一維外包資料庫時，每個劃分的邊界為兩個相鄰真實數據點之間的垂直平分線；具體的，當所述外包資料庫為一維外包資料庫時，每個劃分的邊界為兩個相鄰真實數據點之間的垂直平分線。為了解決問題一和問題二，規定G(D)中的各個劃分必須具有規則形狀。如圖3所示，在一維情形下存在一個「最優方案」的，它可以產生大小平衡且互不相交的劃分，這是因為一維數據點的voronoi圖都是由連續而不相交的區間構成，為生成「完全平衡」(即大小相等)的劃分，只需在D中找到其1/k，. . .，(k-1)/k分位點,然後用它們產生G(D),這些分位點所對應voronoi cell的邊界以及土 00確定了P(D) = IB1,. . . , Bj ο上述查找(k-Ι)個分位點並通過它們對D的voronoi圖進行劃分的過的程可通過對D的一次線性掃描完成。因此，該算法在外存模型中的10 (輸入/輸出)代價為0(N log N)。由於每個劃分大小均為|0|八=~1^，因此61大小均為IE (N/k) |，故而E (D)大小為k|E(N/k)| ;並且顯然P(D)的大小是0(k)的。步驟S22，當所述外包資料庫為二維外包資料庫時，每個劃分的邊界為由與所述voronoi圖的X坐標軸和Y坐標軸平行的直線圍成的格子，用平行於Y坐標軸的直線不斷分割當前的最大的劃分和與所述最大的劃分在同一條平行Y坐標軸的直線上的相鄰的劃分，或用平行X坐標軸的直線不斷分割當前的最大的劃分和與所述最大的劃分在同一條平行X坐標軸的直線上的相鄰的劃分以生成所述格子，直至voronoi圖中的劃分的個數大於或等於所述參數，其中，每次分割時，使平行於Y坐標軸的直線或平行X坐標軸的直線穿過voronoi圖中的多邊形的頂點最多，當劃分的個數大於所述參數k時，通過逐步合併最小劃分的方式將voronoi圖中的劃分的個數減至所述參數k。具體的，為了解決上述問題一和問題二，規定G(D)中的各個劃分必須具有規則形狀，具體來說就是，每個劃分必須被限定在一個由與坐標軸(X坐標軸或Y坐標軸)平行的邊圍成的「格子」(box)中。然而，這意味著劃分Gi的邊界Bi可能包含或貫穿多個voronoi cell，如圖2所示，其中虛線為劃分的邊界B1和B2,代表不同數據點P1^P16的凸多邊形為voronoi cell。為了解決上述問題二,設D中點Pi對應的voronoi cell為Vci,為保證數據用戶能夠為P(D)編制索引以及輕鬆高效地確定出滿足nn(q，D) e Gi的索引值i，可以確定如下劃分原則設Gi的幾何邊界由Bi表示，那麼原則一 =Bi是一個由與坐標軸平行的邊圍成的「格子」；原則二 =BpBl= 0 ( 1>j ),即G(D)中不同的劃分其對應的邊界是互不相交的；原則三如果Bi完全包含或相交於一個voronoi cell集\^,那麼Gi= (PjlVcj e Vj ,但不同的Gi可能會含重複的數據點。如在圖2中，深色的voronoi cell裡面的數據點會被同時加入到劃分 G1 和 G2 中，即 G1= {ρ1； P2, P3, P4, P5, P6, P7, P8. PiJ，G2= {p5, P6, P7, P8. Pi。，Pu,
Pl2> Pl3> Pl4> Pl5> Pl6> P9}。引理I.如圖2所示，依照上述劃分原則，若nn (q, D) =Pi且q e Bj,則有Pi e G」。證明若有查詢點q e Bj,即q屬於B」所框定的區域，那麼q必屬於一個被B」完全包含或貫穿的voronoi cell。依照上述劃分原則,這一 voronoi cell必屬於V」,而Vj確定了 Gj的元素。假設q包含在Vei中(則有nn(q，D)=Pi)，由上可知，vci e V」，繼而Pi e Gj。
由上述引理I可知，步驟S6中，對於任意查詢點q，數據用戶端的工作就是找到滿Mqe e P (D)，即在P (D)中找到一個包含q的格子，這實際上是一個「點位置查詢」(point location query)的過程。由於P (D)中的格子都是不相交的,但會覆蓋整個外包資料庫D的VOTonoi圖的空間，因此有且只有一個格子包含點q ;另外，由於這些格子的邊都是與坐標軸平行的，因此數據用戶能夠方便地為P(D)編制原始索引值i。之後，數據用戶便可以向伺服器請求獲取E(Gj),這是因為由所述引理I告，只要q被包含在Bj中，那麼就有nn (q, D) e Gj。通過步驟S7，一旦E(Gj)被伺服器返回，步驟S8中數據用戶便可以由E—1對E(Gj)解密得到Gy之後，數據用戶通過識別隨機字符*，可以輕鬆地將之前數據主通過「隨機填補操作」添加在中的隨機字節序列去除；最後，數據用戶可得nn(q，D)=nn(q, Gj)。然而別忘了，數據用戶在向伺服器請求獲取E(Gj)時需要解決問題四，通過步驟S4數據主根據預設的哈希函數對每個劃分建立對應的索引，並將加密後的所有劃分及其對應的加密後的所有索引發送給伺服器存儲之後，在步驟S6中，讓數據用戶向伺服器發送E(g(j))。步驟S7中在伺服器端，數據主發送來的E(g(i))與E(Gi)存在配對關係，伺服器在接收到數據主發送來的E(D)後，便會建立一個含k個記錄的哈希表T，將E(g(i))映射到E (Gi)。如此，數據用戶給定一個請求E (g⑴)，伺服器便可以通過在T中查找，最終找到E(Gi),這個過程的時間複雜度僅為0(1)，因此伺服器可以通過上述過程由E(g(j))高效地查找到E (Gj)。步驟S31，數據主在所述VOTonoi圖中隨機添加k』個劃分，並在k』個劃分中分別添加虛擬數據點，記錄每個劃分對應的邊界，其中，每個劃分互不相交，不同劃分包含的虛擬數據點部分重複或完全不重複，k』為正整數。具體的，在數據主生成G(D)和P(D)後，只需在G(D)中添加k'個隨機劃分，然後加密傳送給伺服器，如此伺服器得到的劃分數為k+k/，從而k值得到了隱蔽。步驟S3，數據主獲取所有劃分中包含最多個真實數據點或虛擬數據點的劃分的字節數作為最長字節數，在除包含最多個真實數據點或虛擬數據點的劃分之外的每個其它劃分中添加隨機字節，使除包含最多個真實數據點或虛擬數據點的劃分之外的每個其它劃分的字節數等於所述最長字節數。具體的，假設數據主已經生成了 G(D)及P(D)為了上述解決問題三，數據主需保證IGiMGjI設GxSG(D)中具有最多個數據點(下稱為「大小」，size)的劃分，即對於任意i e [l，k]，都有IGiI ( |GX|。對於各個劃分Gi (i關X)，對其添加(IGxIb-IGiIb)個隨機字節，這裡可用字符*代表任意隨機字節以與匕中的實際數據點進行區分(*代表的這些隨機字符都不會在Gi中實際出現)，可稱此過程為「隨機填補操作」。顯然，經此「隨機填補操作」，對於任意劃分Gi，都有IGxIb=IGiIbtj這樣，在後續步驟S4中，無論數據主使用何種安全加密算法生成{E (G1)，. . .，E (Gk)}，都有IE (Gi) | b= | E (Gj) | b(i幸j)，從而保證伺服器無法在G (D)中區分出任意某個劃分，從而了解到劃分情況。步驟S4，數據主根據預設的哈希函數對每個邊界建立對應的索引，並根據一預設的加密算法將加密後的所有劃分及其所有與相應的邊界對應的索引發送給伺服器存儲。具體的，為了解決上述問題四，數據主應用一秘密隨機哈希函數g:[l，N] — Z+，最終將E(D) = {(E (g (I))，E (G1) )，...，(E (g (k) )，E (Gk))}發布給伺服器，將P (D) 'E-1 和 g發布給數據用戶。步驟S5，數據主將所有劃分對應的邊界、與所述加密算法對應的解密算法和所述哈希函數發送給所述數據用戶存儲，具體的，數據主將所有劃分對應的邊界P(D)發送給所述數據用戶存儲。將P(D)存儲在數據用戶端，這樣對於任意查詢點q，數據用戶能夠高效地確定出原始索引值i滿足rm(q，D) e Gi,根據所述哈希函數計算出與該原始索引值i(邊界)對應的索引，然後根據該索引向伺服器提出請求獲取到E (Gi)，這個過程完全可以在伺服器不知道具體原始索引值i值的情況下進行，如此可以保證伺服器不會在答覆查詢的過程中了解到劃分情況；最後，數據用戶自然能夠輕鬆得出rm (q, D) =nn (q, Γ1 (Ε (Gi)) )。步驟S6，所述數據用戶確定真實查詢點q，根據所述真實查詢點確定包含所述真實查詢點的劃分的對應的邊界，根據所述哈希函數獲取與包含所述真實查詢點的劃分的對應的邊界的對應的索引，並將包含所述真實查詢點的劃分的對應的邊界的對應的索引E(g(j))發送給伺服器，即數據用戶將 E0)) = {(E(g⑴)，Ε%))，···，(E(g(k))，E(Gk))}傳送給伺服器。步驟S7，所述伺服器根據接收到的包含所述真實查詢點的劃分的對應的邊界的對應的索引向所述數據用戶發送對應的加密後的包含所述真實查詢點的劃分。步驟S8，所述數據用戶根據所述解密算法將接收到的加密後的包含所述真實查詢點的劃分進行解密，獲取包含所述真實查詢點的劃分，並從包含所述真實查詢點的劃分中獲取所述真實查詢點的最近鄰的真實數據點；步驟S9，所述數據用戶確定偽查詢點，根據所述偽查詢點確定包含所述虛擬查詢點的劃分的對應的邊界，根據所述哈希函數獲取與包含所述偽查詢點的劃分的對應的邊界的對應的索引，並將包含所述虛擬查詢點的劃分的對應的邊界的對應的索引發送給伺服器。具體的，伺服器可能會通過統計對各個劃分的查詢頻度，結合相關「背景知識」，大致判斷出該劃分所對應的實際地理區域，例如，假設D代表紐約地區，基於對紐約某些區域實際被「關注」程度的了解，伺服器便可以推斷出被最頻繁查詢的劃分對應的很可能就是曼哈頓，為避免此類隱私洩露，還是可以使用「偽查詢」的辦法，讓數據用戶隨機地發出「偽查詢」，如此使得各劃分在整體上有較為接近的查詢頻度即可以讓數據用戶發出一些針對上述隨機劃分的「偽查詢」請求，即數據用戶隨機地向伺服器請求E (g (j))，而這裡j e [k+l,k+k/ ]，這樣伺服器便無法確定哪些是添加的隨機劃分，從而不能確定出k值。步驟S10，所述伺服器根據接收到的包含所述偽查詢點的劃分的對應的邊界的對應的索引向所述數據用戶發送對應的加密後的包含所述偽查詢點的劃分。上述步驟S6至SlO的查詢過程可以根據實際需要不斷重複，直至無查詢需求。通過步驟S31、步驟S9和步驟S10，可以很容易地使k對伺服器透明。本實施例中提供一種MinDp劃分方法，這種方法遵循了上述提出的劃分原則一至三，由於加入了 「隨機填補操作」，因此很顯然，本實施例的通信代價以及伺服器端的存儲代價是由最大劃分與各劃分的大小之差，即IGjJGil，或更準確地，IE(Gx) I-IE(Gi) I)決定的，也就是說，為了降低通信代價以及伺服器端的存儲代價，在設計劃分方法時還應儘可能地遵循原則四儘可能生成大小「平衡」(相等或接近)的劃分。MinDp方法為數據主根據所述參數K將所述VOTonoi圖分割成為k個劃分的步驟中，用平行於Y坐標軸的直線不斷分割當前的最大的劃分和與所述最大的劃分在同一條平行Y坐標軸的直線上的相鄰的劃分，或用平行X坐標軸的直線不斷分割當前的最大的劃分和與所述最大的劃分在同一條平行X坐標軸的直線上的相鄰的劃分以生成所述格子，直至voronoi圖中的劃分的個數大於或等於所述參數k，其中，每次分割時，使平行於Y坐標軸 的直線或平行X坐標軸的直線穿過voronoi圖中的多邊形的頂點最多，當劃分的個數大於所述參數k時，通過逐步合併最小劃分的方式將voronoi圖中的劃分的個數減至所述參數k。具體的，MinDp方法中為了使G(D)中的(IGjJ-IGil)值達到最小，可以採用一種「貪心」策略。具體來說，初始時令ΡΦ) = {Ω}，其中Ω代表D對應voronoi圖的全部區域；隨後，迭代地用垂直直線(平行於Y坐標軸的貫穿Ω的直線，下同)或水平直線(平行於X坐標軸的貫穿Ω的直線MfP(D)中格子逐步切小，直至P(D)中格子數達到k。為簡明起見，下面將此構造過程中處於第i步驟狀態的P(D)表示為Pi(D)。在任意的第i步，用MinCs中提到的方式為PJD)中的格子編制索引對{x，y}。現在假設切至第i步時，已用了％條垂直線和匕條水平線，那麼在Pi (D)中便有了(ai+l) (bi+1)個格子，即 Pi (D) = IC1, 」···，
Cl』bi+l，· · ·，Cai+1，1，· · ·，Cai+1，bi+1} ο 那麼如果把接下來MinDp的切割過程看做一個函數的話，就相當於以Pi(D)(或％條垂直線和匕條水平線)為其輸入狀態，而輸出一條新的分割線I (水平線或垂直線)。這裡用到的基本思路是每一步中總是選取當前最大的劃分進行切割，此即為「貪心」策略。這裡，將格子Cx，y e Pi(D)對應的劃分表示為Gx, y。如圖2所示，需注意每個格子Cx，y通過MinDp方法總可以產生一個對應的劃分Gx，y。假設當前最大劃分為Ga，e(a e [l,ai+l], β e [l，bi+l])，那麼下一條切割線I的選取範圍即為Ga，e對應的XY坐標範圍。然而，即使我們只考慮Ga，e的XY坐標範圍，I的選擇範圍應是無窮的。這是因為，如果假設Ga，e由其左下角點(xl，yl)和右上角點(xu, yu)給定；那麼，[xl, xu]範圍內的任意垂直線和[yl，yu]範圍內的任意水平線都可以作為Ga，e的切割線加以考慮。為解決以上問題，如圖2所示，可以發現如引理2。引理2.當一個格子通過MinDp方法產生一個劃分時,其邊界線穿過的voronoi頂點(相對該邊界線只是從「中間」穿過一個voronoi cell)越多,產生的劃分越小。證明如若邊界線I穿過某voronoi cell (設為Vci),但並非穿過Vci的頂點,那麼VCi對應的點Pi必會同時分配給I兩側的劃分，由此可得引理2的正確性。引理2的一個例子就是，在圖2中，p9隻被分配給了劃分G2，而沒有分配給匕。由引理2，可以通過一種進一步的「貪心」策略確定切割線I。令V(Ga，e)表示這樣的voronoi頂點集合其所屬的voronoi cell的坐標範圍完全在[xl, xu]和[yl, yu]之中，點(xl, yl)和點(xu, yu)分別為Ga，e左下角和右上角。那麼在確定I時只需考慮其水平或垂直穿過V e V(Ga,0)的情形。這樣的I將Ga，e及其對應的最大劃分Ga,e切割開來，得Pi+1(D)。不難得知，這樣的I可有2|V(Ga，e)|個可能的選擇；從中選擇一個，使之滿足Pi+1(D)中的最大劃分的數據點數最小。一旦I確定，即將PJD)更新為Pi+1(D)，並如此繼續，直至Pi+1(D)中格子數達到k。由於上述劃分方法是基於儘可能減少「重複點」的思想，因此稱之為「MinDp(Minimum Duplicate Points)方法」。這裡需注意的是,劃分至最後一步時，MinDp方法產生的劃分數可能會大於k ;如若這樣，可以通過逐步合併最小劃分的方式將劃分數減至k，對此我們這裡不做贅述。圖4給出了 MinDp方法應用的一個示例，其中，圖4中虛線I代表試切割過程。MinDp方法最多需進行(k_l) 步劃分，例如，所有劃分線均為水平或垂直時；在每一步，需試驗2 I V(Ga，e) I條可能的劃分線。由於平均單個voronoi cell的頂點數小於6,並且有N個voronoi cell，因此O(| V(Ga，e) |) =N。對於每條切割線1，需找出與其相交的voronoi cell以便後續產生劃分,這在最壞情況下需要O(N)的複雜度。綜上，最壞情形下MinDp的複雜度為0(kN2)。需注意，現實中幾乎不會出現上述最壞情形，而往往是要麼只是
V(Ga；0)為0(N)，要麼只是I穿過的VOTonoi cell數為O (N)，兩者只佔其一，故總的複雜度僅為0(kN)。最後特別值得一提的是，P(D)的大小顯然是0(k)的。更詳細的，可用C++語言對上述MinDp方法進行實現。本實現的實驗中，使用Qhull庫對數據集D進行了 voronoi劃分；使用最新的Crypto++庫進行了加密。隨後實驗的進行是在一臺配置為Intel Xeon 3.07GHz CPU、8GB內存的Linux機上。針對二維外包資料庫D，實驗時具體數據集使用了取樣自美國加利福尼亞州(CA)和德克薩斯州(TX)的千萬個數據點作為原始數據集，這些數據都來自OpenStreetMap項目。在CA和TX數據集中，各隨機選取2，000，000個數據點作為最大實驗數據集Dmax，並基於Dmax形成了較小規模的數據集。這裡需特別一提的是，當改變數據集大小以測試本實施例的劃分方法的可擴展性時，會確保小數據集總是大數據集的子集，這樣是為了避免D中具體數據點變化帶來的影響，從而單單體現出|D|的影響。對實驗所涉及參數的默認設置如下|D|=106，k=625 ( |D|、k分別為數據點的個數和最後的劃分數)；數據點的個數默認使用來自CA的數據；使用AES加密算法進行加密，其key大小和塊大小均為256比特。這裡需特別一提的是，實驗過其他加密算法後，發現不同加密算法對本實施例的性能幾乎不構成影響。因此任何安全的公共密鑰或對稱密鑰加密算法都可用於實現本實施例，並且不同加密算法實現本實施例性能都可由實驗說明。最後要說明的是，在全部實驗中，除非特別聲明，當將某個參數作為變量進行研究時，其他參數均為默認值。具體實驗結果如下I.預處理階段在預處理階段，數據主端需進行劃分和加密兩項工作，它們均主要受劃分數k和數據集大小|D|的影響。圖5a、5b所示分別為不同劃分方法下k和IdI對運行時間的影響。其中，圖5a顯示MinDp方法的劃分時間代價(partition time)均隨k線性增長。圖5b顯示的是數據大小|D I變化(從250，000到2，000, 000)對劃分時間代價的影響。但儘管MinDp方法在最壞情況下的複雜度是O (kN2)，但在現實(實驗)中，它的處理時間與N也是呈線性關係，這是因為所述最壞情形一一條分割線會同全部Nf VOTonoi cell相交一在實際數據集中幾乎是不可能發生的。事實上，在MinDp的每一步分割中，與分割線相交的voixmoi cell數幾乎可以認為是常數個，因此它們的複雜度可認為是0(kN)的。下面來看MinDp方法下產生的劃分G(D) = {G1，. . .，Gk}的大小(進行「隨機填補操作」前)。由於「隨機填補操作」會通過填補隨機字節將所有劃分的大小增至與最大劃分一樣大，因此以下兩個數值對於評估本實施例的劃分方法的性能至關重要最大劃分的大小IgJ和(IgxI-IgJ)的方差(i e [i，k])。IGx決定了伺服器端的存儲代價和每次查詢的通信代價；(IGxI-IGiI)的方差決定了填補操作本身的代價。為了將這些數值在一個圖中簡
單直觀地呈現，圖6a、6b分別顯示了劃分大小的平均值2]|Gi (avg partition size)、最
大值IGxI=HiaxieLldIGiI和最小值IGyI=IninietuldIGiI隨參數k和|D|的變化情況。最後，如圖6a、6b所示，MinDp方法,其劃分大小的平均值和最大值隨k增加是遞減的。下面通過圖7a、7b來看在預處理階段MinDp方法的總運行時間(totalrunningtime)。所謂總運行時間，具體含劃分和加密兩個步驟的時間(voronoi劃分時間和「隨機填補操作」時間也包含在內，不過它們相對劃分和加密時間來說要小一些)。在圖7a、7b中，還加入了所述Send-D方法的預處理時間以作參照，Send-D方法的預處理時間就是將D看做一個整體進行加密的時間。另外，從圖7a、7b中可見，MinDp方法預處理階段的總時間隨k或|D|增加都是線性增長的。再來看最終產生的E(D)的大小，這是影響伺服器端存儲代價和數據主至伺服器通信代價的關鍵因素。進行過隨機填補操作後，每個劃分都具有了與最大劃分相同的大小，因此，Ie(D) I =kIE(Gx) I =kIE(Gi) I (i e [l，k])。圖8a、8b分別顯示了 MinDp方法下E(D) (size of E(D))隨k或D變化的情況。類似於針對圖7a、7b的討論，也把D的大小和將D作為一個整體進行加密得到的E (D)的大小(即Send-D的代價)加入圖8a、8b中以作參照。顯然，MinDp方法中E(D)的大小隨k或|D|增加都是線性增長的。Send-D對應的E(D)大小也是隨|D|線性增長的，但卻與k無關。自然，相對直接傳送外包資料庫D的明文本身，MinDp方法會引入數據主至伺服器的通信代價和伺服器端的存儲代價。數據用戶端的存儲代價是取決於P (D)的大小的，並且這一代價在MinDp方法中是o(k)。由於k相對數據點的個數|d|來說小得多(對於一個包含幾百萬個點的數據集來說，分割出幾百個劃分即已足夠)，因此上述存儲代價幾乎是可以忽略的。最後需聲明的是，在實驗中觀察到使用哪種數據集(CA數據集或TX數據集)對實驗結果幾乎沒有什麼明顯的差別，因此為簡便起見，這裡沒有討論TX數據集上的實驗結果O2.查詢處理代價首先，對任意查詢點q，採用本發明的方法，伺服器至數據用戶端的通信代價僅僅取決於|E(Gp|。然而，正如上述對圖8a、8b結果的分析，由於進行了隨機填補操作，因此每個劃分有了相同的大小，並且IE(Gi) | = |E(D) |/k (i e [l，k])。相反，在Send-D方法中，伺服器至數據用戶端的通信代價就是對數據集D整體加密的大小，S卩|E(D as onemessage)!。因此，雖然|E(D as one message)比MinDp方法生成的|E(D)|小得多(如圖8a、8b所示)，如圖9a、9b所示，本發明的方法中伺服器至數據用戶端的查詢通信代價(query communication)仍然比 Send-D 的小得多。下面，再來看數據用戶端的查詢處理代價。每次實驗，都隨機進行了 100次查詢，然後得到如圖10a、10b所示的MinDp方法的平均處理時間。圖IOa顯示MinDp方法的查詢時間(query time)是隨k增大而遞減的，這顯然是因為k增大導致了劃分變小。相比Send-D，MinDp方法的性能要好得多。圖IOb所示，而當|D|增加時，MinDp的查詢時間都隨之線性增長。
本發明的算法效率包括預處理階段的時空代價和查詢階段的查詢代價，所述預處理階段的時空代價包括時間代價和存儲代價，查詢階段的查詢代價包括時間代價和通信代價I. SVD算法進行預處理時的時間代價主要體現在以下三階段(I)得到 D 的 voronoi 圖；(2)對D進行劃分；(3)生成 E(D)。針對一維和二維的外包資料庫，階段(I)的代價是O(NlogN)的。而在第(2)階段(對D進行劃分)，一維情形下，很顯然可以在對數據進行排序後通過一次遍歷得到所需的分位點，因此階段2的代價也是O(NlogN)的；二維情形下，該階段的代價取決於我們所選用的劃分方法。MinDp方法的代價分別為0(kN)。階段(3)的代價同加密代價呈線性關係。假設通過加密算法E對信息m進行加密的代價為e(m);由於「隨機填補操作」將每個劃分的大小都增至最大，因此可得生成E (D)的
時間複雜度是 ο(ke( IGx |b))的，其中 Gx = argmaxG_eG(￡)) | Gi |2.預處理階段的存儲代價伺服器端的存儲代價為IE(D) I，是0(k|E(Gx) I)的。數據用戶端的存儲代價為P (D)和索引i所佔的空間。對於同類型的大部分的索引結構(如kd樹、R樹、線段樹等)，i的大小是與Ip(D) I線性相關的，因此數據用戶端的存儲代價是0( IP (D) I)的；至於P(D)，一維情形下，P (D)僅僅含有(k-Ι)個數值，因此Ip(D) =k-i ；二維情形下，Ip(D) I由所選用的劃分方法所決定。MinDp方法的IP(D) I分別是0(k)。3.查詢階段的查詢代價查詢階段的時間代價主要體現在兩端數據用戶端和伺服器端。其中，數據用戶需通過P(D)的索引i查找包含查詢點q的Bi e P(D)，其中任意Bi都是由平行於坐標軸的邊圍成的d維(一至三維)格子；由於已保證P (D)中的任意兩個格子不會相交，且必有一個格子包含q，因此這種查找實際是一個輸出大小為I (結果有且只有一個)的典型「點位置查詢」過程；在一二維情形下，以上過程的代價僅是O(Iogk)的。在伺服器端，數據用戶給定一個請求E (g(j))，伺服器便通過查詢哈希表T來找到E(Gj),這個過程是O (I)的。系統中的單次通信代價為|e(d)|和Ip⑶|，這可由我們上面對存儲代價的討論自然得出。查詢的通信代價為|E(g(j)) +IE(Gj) I,或|E(g(j)) +IE(Gx) I,或E(g(j)) | + |E(Gj) |/k。在本發明的安全性方面，由於本實施例中數據用戶僅僅是把E(D) = {(E(g(l))，E(G1))，…，(E(g(k))，E(Gk)M傳送給伺服器，並且在查詢處理過程中，只有E (g(j))是對伺服器可見的，由此我們可證得下述定理I。定理I.假設E是某種已在標準安全模型M (如，IND-CPA)中被證明安全的加密算法，那麼在M中SVD算法與E具有相同的安全性。證明在整個處理過程中，伺服器只能看到來自數據主的E(D)和來自數據用戶的E(g(j))隨機序列，因此，伺服器只能了解到劃分個數k。由於「隨機填補操作」保證了Ie(Gj) =IE(Gi) I (i Φ j)，如果E在M中是安全的，那麼顯然，伺服器不會了解到關於任意劃分Gi的邊界信息。再者，因為隨機哈希函數g: [I, N] — Z+不為伺服器所知，因此伺服器 不可能在僅僅被給定E (g (j))的情況下還原出原始索引值i，也即，伺服器不可能知道E (D)中(E(g⑴，E(Gi))對的索引值i。通過步驟S31、步驟S9和步驟S10，可以很容易地使k對伺服器透明。綜上，本實施例能夠在數據用戶對伺服器上存儲的外包資料庫中進行最近鄰查詢時，使伺服器無法獲知外包資料庫中的數據、數據用戶的查詢點及最近鄰的查詢結果，保證數據安全。如圖11所示，本發明還提供另一種基於最小冗餘劃分和隨機數的安全最近鄰查詢系統，包括數據主I、數據用戶2和伺服器3。數據主1，用於給定所述參數k，生成包含外包資料庫的所有真實數據點的voronoi圖，其中，每個真實數據點的字節數相同，外包資料庫中的真實數據點的個數為N，N為正整數，所述外包資料庫為一至三維外包資料庫；根據參數k將所述voronoi圖分割成為k個劃分，記錄每個劃分對應的邊界，其中，每個劃分互不相交，不同劃分包含的數據點部分重複或完全不重複，k大於等於I且小於等於N，當所述外包資料庫為一維外包資料庫時，每個劃分的邊界為兩個相鄰真實數據點之間的垂直平分線，當所述外包資料庫為二維外包資料庫時，每個劃分的邊界為由與所述voronoi圖的X坐標軸和Y坐標軸平行的直線圍成的格子，所述數據主用平行於Y坐標軸的直線不斷分割當前的最大的劃分和與所述最大的劃分在同一條平行Y坐標軸的直線上的相鄰的劃分，或用平行X坐標軸的直線不斷分割當前的最大的劃分和與所述最大的劃分在同一條平行X坐標軸的直線上的相鄰的劃分以生成所述格子，直至voronoi圖中的劃分的個數大於或等於所述參數k，其中，每次分割時，使平行於Y坐標軸的直線或平行X坐標軸的直線穿過voronoi圖中的多邊形的頂點最多，當劃分的個數大於所述參數k時，通過逐步合併最小劃分的方式將VOTonoi圖中的劃分的個數減至所述參數k ;在所述voronoi圖中隨機添加k』個劃分，並在k』個劃分中分別添加虛擬數據點，記錄每個劃分對應的邊界，其中，每個劃分互不相交，不同劃分包含的虛擬數據點部分重複或完全不重複，k』為正整數；獲取所有劃分中包含最多個真實數據點或虛擬數據點的劃分的字節數作為最長字節數，在除包含最多個真實數據點或虛擬數據點的劃分之外的每個其它劃分中添加隨機字節，使除包含最多個真實數據點或虛擬數據點的劃分之外的每個其它劃分的字節數等於所述最長字節數；根據預設的哈希函數對每個邊界建立對應的索引，並根據一預設的加密算法將加密後的所有劃分及其所有與相應的邊界對應的索引發送給伺服器存儲；將所有劃分對應的邊界、與所述加密算法對應的解密算法和所述哈希函數發送給所述數據用戶存儲；數據用戶2，用於給定所述參數k，確定真實查詢點，根據所述真實查詢點確定包含所述真實查詢點的劃分的對應的邊界，根據所述哈希函數獲取與包含所述真實查詢點的劃分的對應的邊界的對應的索引，並將包含所述真實查詢點的劃分的對應的邊界的對應的索引發送給伺服器；根據所述解密算法將接收到的加密後的包含所述真實查詢點的劃分進行解密，獲取包含所述真實查詢點的劃分，並從包含所述真實查詢點的劃分中獲取所述真實查詢點的最近鄰的數據點；確定偽查詢點，根據所述偽查詢點確定包含所述虛擬查詢點的劃分的對應的邊界，根據所述哈希函數獲取與包含所述偽查詢點的劃分的對應的邊界的對應的索引，並將包含所述虛擬查詢點的劃分的對應的邊界的對應的索引發送給伺服器；伺服器3，用於根據接收到的包含所述真實查詢點的劃分的對應的邊界的對應的索引向所述數據用戶發送對應的加密後的包含所述真實查詢點的劃分；根據接收到的包含所述偽查詢點的劃分的對應的邊界的對應的索引向所述數據用戶發送對應的加密後的包 含所述偽查詢點的劃分。綜上所述，本發明通過數據主生成包含外包資料庫的所有真實數據點的voronoi圖，其中，每個真實數據點的字節數相同，外包資料庫中的真實數據點的個數為N，N為正整數，所述外包資料庫為一至三維外包資料庫；數據用戶或數據主給定參數K，數據主根據所述參數k將所述voronoi圖分割成為k個劃分，記錄每個劃分對應的邊界，每個劃分互不相交，不同劃分包含的數據點部分重複或完全不重複，k大於等於I且小於等於N，其中，當所述外包資料庫為一維外包資料庫時，每個劃分的邊界為兩個相鄰真實數據點之間的垂直平分線，當所述外包資料庫為二維外包資料庫時，每個劃分的邊界為由與所述voronoi圖的X坐標軸和Y坐標軸平行的直線圍成的格子，用平行於Y坐標軸的直線不斷分割當前的最大的劃分和與所述最大的劃分在同一條平行Y坐標軸的直線上的相鄰的劃分，或用平行X坐標軸的直線不斷分割當前的最大的劃分和與所述最大的劃分在同一條平行X坐標軸的直線上的相鄰的劃分以生成所述格子，直至voronoi圖中的劃分的個數大於或等於所述參數，其中，每次分割時，使平行於Y坐標軸的直線或平行X坐標軸的直線穿過voronoi圖中的多邊形的頂點最多，當劃分的個數大於所述參數k時，通過逐步合併最小劃分的方式將voronoi圖中的劃分的個數減至所述參數k ;數據主在所述voronoi圖中隨機添加k』個劃分，並在k』個劃分中分別添加虛擬數據點，記錄每個劃分對應的邊界，其中，每個劃分互不相交，不同劃分包含的虛擬數據點部分重複或完全不重複，k』為正整數；數據主獲取所有劃分中包含最多個真實數據點或虛擬數據點的劃分的字節數作為最長字節數，在除包含最多個真實數據點或虛擬數據點的劃分之外的每個其它劃分中添加隨機字節，使除包含最多個真實數據點或虛擬數據點的劃分之外的每個其它劃分的字節數等於所述最長字節數；數據主根據預設的哈希函數對每個邊界建立對應的索引，並根據一預設的加密算法將加密後的所有劃分及其所有與相應的邊界對應的索引發送給伺服器存儲；數據主將所有劃分對應的邊界、與所述加密算法對應的解密算法和所述哈希函數發送給所述數據用戶存儲；所述數據用戶確定真實查詢點，根據所述真實查詢點確定包含所述真實查詢點的劃分的對應的邊界，根據所述哈希函數獲取與包含所述真實查詢點的劃分的對應的邊界的對應的索引，並將包含所述真實查詢點的劃分的對應的邊界的對應的索引發送給伺服器；所述伺服器根據接收到的包含所述真實查詢點的劃分的對應的邊界的對應的索引向所述數據用戶發送對應的加密後的包含所述真實查詢點的劃分；所述數據用戶根據所述解密算法將接收到的加密後的包含所述真實查詢點的劃分進行解密，獲取包含所述真實查詢點的劃分，並從包含所述真實查詢點的劃分中獲取所述真實查詢點的最近鄰的真實數據點；所述數據用戶確定偽查詢點，根據所述偽查詢點確定包含所述虛擬查詢點的劃分的對應的邊界，根據所述哈希函數獲取與包含所述偽查詢點的劃分的對應的邊界的對應的索引，並將包含所述虛擬查詢點的劃分的對應的邊界的對應的索引發送給伺服器；所述伺服器根據接收到的包含所述偽查詢點的劃分的對應的邊界的對應的索引向所述數據用戶發送對應的加密後的包含所述偽查詢點的劃分。，能夠在數據用戶對伺服器上存儲的外包資料庫中進行最近鄰查詢時，使伺服器無法獲知外包數 據庫中的數據、數據用戶的查詢點及最近鄰的查詢結果，保證數據安全。本說明書中各個實施例採用遞進的方式描述，每個實施例重點說明的都是與其他實施例的不同之處，各個實施例之間相同相似部分互相參見即可。對於實施例公開的系統而言，由於與實施例公開的方法相對應，所以描述的比較簡單，相關之處參見方法部分說明即可。專業人員還可以進一步意識到，結合本文中所公開的實施例描述的各示例的單元及算法步驟，能夠以電子硬體、計算機軟體或者二者的結合來實現，為了清楚地說明硬體和軟體的可互換性，在上述說明中已經按照功能一般性地描述了各示例的組成及步驟。這些功能究竟以硬體還是軟體方式來執行，取決於技術方案的特定應用和設計約束條件。專業技術人員可以對每個特定的應用來使用不同方法來實現所描述的功能，但是這種實現不應認為超出本發明的範圍。顯然，本領域的技術人員可以對發明進行各種改動和變型而不脫離本發明的精神和範圍。這樣，倘若本發明的這些修改和變型屬於本發明權利要求及其等同技術的範圍之內，則本發明也意圖包括這些改動和變型在內。
權利要求
1.一種基於最小冗餘劃分和隨機數的安全最近鄰查詢方法，其特徵在於，包括 數據主生成包含外包資料庫的所有真實數據點的voronoi圖,其中，每個真實數據點的字節數相同，外包資料庫中的真實數據點的個數為N，N為正整數，所述外包資料庫為一至三維外包資料庫； 數據用戶或數據主給定參數K，數據主根據所述參數k將所述VOTonoi圖分割成為k個劃分，記錄每個劃分對應的邊界，每個劃分互不相交，不同劃分包含的數據點部分重複或完全不重複，k大於等於I且小於等於N，其中，當所述外包資料庫為一維外包資料庫時，每個劃分的邊界為兩個相鄰真實數據點之間的垂直平分線，當所述外包資料庫為二維外包資料庫時，每個劃分的邊界為由與所述voronoi圖的X坐標軸和Y坐標軸平行的直線圍成的格子，用平行於Y坐標軸的直線不斷分割當前的最大的劃分和與所述最大的劃分在同一條平行Y坐標軸的直線上的相鄰的劃分，或用平行X坐標軸的直線不斷分割當前的最大的劃分和與所述最大的劃分在同一條平行X坐標軸的直線上的相鄰的劃分以生成所述格子，直至voronoi圖中的劃分的個數大於或等於所述參數，其中，每次分割時，使平行於Y坐標軸的直線或平行X坐標軸的直線穿過voronoi圖中的多邊形的頂點最多，當劃分的個數大於所 述參數k時，通過逐步合併最小劃分的方式將voronoi圖中的劃分的個數減至所述參數k ；數據主在所述voronoi圖中隨機添加k』個劃分，並在k』個劃分中分別添加虛擬數據點，記錄每個劃分對應的邊界，其中，每個劃分互不相交，不同劃分包含的虛擬數據點部分重複或完全不重複，k』為正整數； 數據主獲取所有劃分中包含最多個真實數據點或虛擬數據點的劃分的字節數作為最長字節數，在除包含最多個真實數據點或虛擬數據點的劃分之外的每個其它劃分中添加隨機字節，使除包含最多個真實數據點或虛擬數據點的劃分之外的每個其它劃分的字節數等於所述最長字節數； 數據主根據預設的哈希函數對每個邊界建立對應的索引，並根據一預設的加密算法將加密後的所有劃分及其所有與相應的邊界對應的索引發送給伺服器存儲； 數據主將所有劃分對應的邊界、與所述加密算法對應的解密算法和所述哈希函數發送給所述數據用戶存儲； 所述數據用戶確定真實查詢點，根據所述真實查詢點確定包含所述真實查詢點的劃分的對應的邊界，根據所述哈希函數獲取與包含所述真實查詢點的劃分的對應的邊界的對應的索引，並將包含所述真實查詢點的劃分的對應的邊界的對應的索引發送給伺服器； 所述伺服器根據接收到的包含所述真實查詢點的劃分的對應的邊界的對應的索引向所述數據用戶發送對應的加密後的包含所述真實查詢點的劃分； 所述數據用戶根據所述解密算法將接收到的加密後的包含所述真實查詢點的劃分進行解密，獲取包含所述真實查詢點的劃分，並從包含所述真實查詢點的劃分中獲取所述真實查詢點的最近鄰的真實數據點； 所述數據用戶確定偽查詢點，根據所述偽查詢點確定包含所述虛擬查詢點的劃分的對應的邊界，根據所述哈希函數獲取與包含所述偽查詢點的劃分的對應的邊界的對應的索弓丨，並將包含所述虛擬查詢點的劃分的對應的邊界的對應的索引發送給伺服器； 所述伺服器根據接收到的包含所述偽查詢點的劃分的對應的邊界的對應的索引向所述數據用戶發送對應的加密後的包含所述偽查詢點的劃分。
2.一種基於最小冗餘劃分和隨機數的安全最近鄰查詢系統，其特徵在於，包括 數據主，用於給定所述參數k，生成包含外包資料庫的所有真實數據點的VOTonoi圖，其中，每個真實數據點的字節數相同，外包資料庫中的真實數據點的個數為N，N為正整數，所述外包資料庫為一至三維外包資料庫；根據參數k將所述VOTonoi圖分割成為k個劃分，記錄每個劃分對應的邊界，其中，每個劃分互不相交，不同劃分包含的數據點部分重複或完全不重複，k大於等於I且小於等於N，當所述外包資料庫為一維外包資料庫時，每個劃分的邊界為兩個相鄰真實數據點之間的垂直平分線，當所述外包資料庫為二維外包資料庫時，每個劃分的邊界為由與所述voronoi圖的X坐標軸和Y坐標軸平行的直線圍成的格子，所述數據主用平行於Y坐標軸的直線不斷分割當前的最大的劃分和與所述最大的劃分在同一條平行Y坐標軸的直線上的相鄰的劃分，或用平行X坐標軸的直線不斷分割當前的最大的劃分和與所述最大的劃分在同一條平行X坐標軸的直線上的相鄰的劃分以生成所述格子，直至voronoi圖中的劃分的個數大於或等於所述參數k，其中，每次分割時，使平行於Y坐標軸的直線或平行X坐標軸的直線穿過voronoi圖中的多邊形的頂點最多，當劃分的個數大於所述參數k時，通過逐步合併最小劃分的方式將voronoi圖中的劃分的個數減至所述參數k ;在所述voronoi圖中隨機添加k』個劃分，並在k』個劃分中分別添加虛擬數據點，記錄每個劃分對應的邊界，其中，每個劃分互不相交，不同劃分包含的虛擬數據點部分重複或完全不重複，k』為正整數；獲取所有劃分中包含最多個真實數據點或虛擬數據點的劃分的字節數作為最長字節數，在除包含最多個真實數據點或虛擬數據點的劃分之外的每個其它劃分中添加隨機字節，使除包含最多個真實數據點或虛擬數據點的劃分之外的每個其它劃分的字節數等於所述最長字節數；根據預設的哈希函數對每個邊界建立對應的索引，並根據一預設的加密算法將加密後的所有劃分及其所有與相應的邊界對應的索引發送給伺服器存儲；將所有劃分對應的邊界、與所述加密算法對應的解密算法和所述哈希函數發送給所述數據用戶存儲； 數據用戶，用於給定所述參數k，確定真實查詢點，根據所述真實查詢點確定包含所述真實查詢點的劃分的對應的邊界，根據所述哈希函數獲取與包含所述真實查詢點的劃分的對應的邊界的對應的索引，並將包含所述真實查詢點的劃分的對應的邊界的對應的索引發送給伺服器；根據所述解密算法將接收到的加密後的包含所述真實查詢點的劃分進行解密，獲取包含所述真實查詢點的劃分，並從包含所述真實查詢點的劃分中獲取所述真實查詢點的最近鄰的數據點；確定偽查詢點，根據所述偽查詢點確定包含所述虛擬查詢點的劃分的對應的邊界，根據所述哈希函數獲取與包含所述偽查詢點的劃分的對應的邊界的對應的索引，並將包含所述虛擬查詢點的劃分的對應的邊界的對應的索引發送給伺服器； 伺服器，用於根據接收到的包含所述真實查詢點的劃分的對應的邊界的對應的索引向所述數據用戶發送對應的加密後的包含所述真實查詢點的劃分；根據接收到的包含所述偽查詢點的劃分的對應的邊界的對應的索引向所述數據用戶發送對應的加密後的包含所述偽查詢點的劃分。
全文摘要
本發明涉及一種基於最小冗餘劃分和隨機數的安全最近鄰查詢方法及系統，所述方法包括數據主將包含外包資料庫的voronoi圖分割成為k個劃分，記錄劃分的邊界，在劃分中添加隨機字節，並根據預設的哈希函數對每個邊界建立對應的索引，並將加密後的所有劃分及其對應的索引發送給伺服器，將所有劃分對應的邊界發送給數據用戶；數據用戶將包含真實查詢點的劃分對應的索引發送給伺服器；伺服器向數據用戶發送加密後的包含真實查詢點的劃分；數據用戶獲取加密後的包含所述真實查詢點的劃分，並解密後計算出最近鄰，在數據用戶對伺服器上存儲的外包資料庫中進行最近鄰查詢時，使伺服器無法獲知外包資料庫中的數據、查詢點及查詢結果，保證數據安全。
文檔編號G06F17/30GK102968477SQ20121046653
公開日2013年3月13日 申請日期2012年11月16日 優先權日2012年11月16日
發明者姚斌, 李飛飛, 肖小奎 申請人:上海交通大學