一種多伺服器環境下的隱私信息檢索方法
2023-12-07 03:01:51 2
專利名稱：一種多伺服器環境下的隱私信息檢索方法
技術領域：
本發明涉及網絡通信數據保護技術領域，特別涉及一種多伺服器環境下的隱私信息檢索方法，可以用於專利資料庫，醫藥資料庫，在線人口普查，實時股票報價，地址定位服務等對檢索隱私有著較聞要求的場合。
背景技術：
近年來，計算機網絡技術的發展帶動了信息檢索技術的蓬勃發展，同時用戶對信息檢索的需求也越來越多祥化。一部分網絡用戶不僅僅需要在公開的網絡環境裡檢索出自己需要的信息，更需要保障本身查詢信息的隱私性。信息的隱私檢索是信息安全研究的重要課題之一，需要通過秘密共享，同態加密等技術實現。隨著應用需求的廣泛延伸，採用簡單算法實現的單伺服器下隱私信息檢索方案正在朝著需要更加複雜算法解決的多伺服器下的隱私信息檢索方案擴展。一般的，以醫藥資料庫為例。醫藥數據檢索不同於採用百度或者谷歌的檢索方式。後者面對的對象及其巨大，所採用的技術和存儲方式也是前者截然不同的。首先醫藥數據檢索麵向的對象是一小部分人，可能只是某家醫院的醫生和患者。所以，資料庫的建立並不需要採用及其複雜的技術來滿足複雜的網絡環境，它可能只需要採用常規的SQL Server資料庫就可以滿足對所有數據的存儲。但是使用醫藥信息檢索的用戶是ー個特殊的群體，比如患者。患者在第三方的資料庫裡檢索和自己病情相關的信息吋，希望個人病情信息能夠保密，不會被洩露給惡意第三方。這種特殊需求就需要有隱私信息檢索技術來保障。隱私信息檢索，Privateinformation retrieval,簡稱 PIR,最早是由 Chor,Goldreich %=人在「Foes』 95 !Proceedings of the 36th Annual Symposium on theFoundations of Computer Science,pages 41-50」中提出的。他們最初提出的 PIR 實現策略是將整個資料庫全部傳送給用戶，然後讓用戶在本地進行信息檢索，這是在理論上可實現的ー種理想的隱私信息保護方案。之後他們再次證明了在使用加密方法來實現多伺服器的信息理論級PIR時，可以不用考慮絕對的隱私性。他們認為，在當時提出的ー些2-server的算木級隱私性的PIR方案中，可以通過在已存的偽隨機產生器或不可逆函數進行難解性假設來實現。經對現有文獻的研究發現，現階段的研究焦點在於如何提高PIR的通訊效率，因為一般大家認為用戶和伺服器間的通訊是最浪費資源的。儘管研究人員正在努力實現這一目標，但是其他方面的限制也使得PIR的性能不能發揮到最佳狀態。在這些障礙中，最不好解決的就是PIR方案在可計算性方面的要求。對PIR方案在計算複雜度上面的檢測直到最近才開始被關注。在這方面的研究中，Beimel等在「M. Bellare, editor, CRYPTO,volume 1880 of Lecture Notes in Computer Science, pages 55-73,2000」 中提出了一種帶有預處理模式的PIR方案，可以先讓每個資料庫進行預計算，然後存儲ー些額外的比特信息。資料庫可以在這些額外信息的幫助下，用較少的計算消耗來實現用戶的查詢。Aguilar-Melchor 和 Gaborit 在「WETORC 2007 Proceedings of the 2007ffesternEuropean Workshop on Research in Cryptology」中探索了採用晶格技術的線性算法，並提出了一個有效的單伺服器的PIR方案。方案的安全性是基於差分隱藏的晶格難解性問題。他們隨後採用了具有高平行性的商用的GPU，並達到了 2Gbps的資料庫執行速度。這比在CPU上運行快了近10倍，為後續研究帶來了ー些好消息。現實中一般是多伺服器的應用環境，因而研究的主要對象也是多伺服器模式下的PIR方案。但是現已提出的多伺服器模式下的PIR方案有個很大的問題，即沒有考慮伺服器群中的單伺服器對用戶查詢隱私威脅。像是Ian Goldberg提出的多伺服器下的PIR方案，有效的解決了惡意伺服器群對隱私信息的攻擊，提高了 PIR方案的魯棒性。但是它沒有考慮到單伺服器對隱私信息的潛在威脅。
發明內容
本發明要解決的技術問題是提供一種多伺服器環境下的隱私信息檢索方法，該方 法考慮單伺服器端隱私保護，是ー種可行的多伺服器和單個伺服器隱私並重的PIR方案。本發明是通過如下技術方案實現的本發明提供一種多伺服器環境下的隱私信息檢索方法，至少包括以下兩階段第一階段通過SSL協議實現的客戶端和伺服器端的秘密通信；第二階段通過秘密共享協議和ElGamal同態加密算法支持的客戶端和伺服器端的交互。進ー步的，所述多伺服器環境下的隱私信息檢索方法還可以包括第三階段，即客戶端在拉格朗日插值的理論支持下對伺服器端反饋信息的處理。本發明所述的客戶端和伺服器端的秘密通信方法，該方法包括如下步驟步驟一，客戶端建立到服務端的TCP連接，隨後，發送ー個Client Hello消息啟動SSL握手，該消息包含了客戶端支持的算法列表和ー些有用消息；步驟ニ,服務端回應ー個Server Hello,它確定了這次通信所需要的算法，隨後，服務端將自己的X. 509證書發送過去，以便客戶端能夠認證自己；步驟三，客戶端在認證完SSL服務端後，將生成一個秘密消息，然後用伺服器端的公鑰加密後傳送過去；步驟四，服務端用自己的私鑰解密後，會話密鑰協商成功。步驟五，建立起安全連接的服務端和客戶端將會繼而協商使用哪些數據塊來完成整個數據檢索過程。對後續兩個步驟中用到的參數定義如下I :伺服器個數；t :預期的隱私等級，即是允許多少伺服器可以相互串謀；η :資料庫的大小；b :虛擬數據矩陣塊中每個數據塊的大小；I :虛擬數據矩陣塊的序號；w : —個數據塊中的每個單字的大小；R :整個處理流程中所用到的域；H R的索引集；r :虛擬矩陣塊中數據塊的個數；s :數據塊中單字的數量=h/w ；m :每個虛擬數據矩陣的大小。本發明所述的客戶端和伺服器端的交互方法，該方法包括如下步驟步驟ー在客戶端，對查詢語句進行處理。按照秘密共享協議的方法將ー個查詢請求的內容處理成N份(N取決於伺服器的個數)。然後對其每份查詢語句用ElGamal加密算法加密。將加密完成的查詢語句分別發送到對應的N個資料庫。具體步驟如下①.給定有限域Z和秘密σ e Z,需要建立ー個(t+1)-private I-way的秘密共享方案。從Z中選取I個兩兩不同的非零元素ai，a2，-, B1 e {1，2，· · ·，min(pq)_l};再從Z中隨機的選取t個元素σ P σ 2，…，σ t ;構建多項式f (X) = σ + σ ιΧ+ σ 2χ2+··· + σ ノ ；則 I 個分享即為 f ( )，f (a2) ···, f (ax)。②·進ー步，設定i為長度為r的向量[V1, V2,…，Vr] (Vj e Zpq, j e [1，r])。然後可以獨立的為 中的每個元素生成一個共享流。即是，令％，Χ$，…，Xj1為 ' 的I個秘密
共子，那麼[Xll，X21, ...，Xri]，[X12 X22， · · ·，Xr2]， ···，[叉11，叉21，···，^rl-I St 為 V 的秘lS' 共子。③.對上述步驟裡由秘密共享協議生成的查詢語句，用ElGamal加密算法加密，因為ElGamal加密算法具有乘法同態性。此中生成密鑰的方法是令P = 2q+l，其中p和q都是素數。令Gq是QRp的子群，且g是Gq的生成元。則公鑰就是h = g_k，其中kezq，k是對應的私鑰。此中加密的方法是對要加密消息m e Gq，令E(m) = (a, b) = (gr, mhO，其中r e Zq0④.此處，將用戶的查詢信息處理成I個向量秘密共享流，從H中選擇I個隨機序列a1; a2，…，B1 ;其次取r個度為t的隨機多項式f1; f2，…，fr多項式的係數必須是R中的元素；再次對I彡i彡I計算Pi = Lf1 (Bi), f2 (Bi),…，fr(ai)];最後對I彡i彡I將P i發送到對應的伺服器端。步驟ニ 在服務端，對虛擬數據矩陣進行初始化處理。由於採用的資料庫是三維設計的，數據存儲在ニ維矩陣裡，並以獨立數據矩陣塊按一定的編碼方式，空間有序的存放在資料庫中。毎次用戶查詢時，伺服器檢索資料庫並形成虛擬數據矩陣塊，用戶的查詢將會在這些虛擬數據矩陣塊中完成。因而伺服器首先根據第一階段和客戶端的秘密協商結果，即第I個數據矩陣，初始化虛擬數據矩陣。步驟三，根據之前和客戶端的協商，確定虛擬數據矩陣中待查詢的元素所在的數據組，然後對客戶端發送過來的查詢信息和虛擬數據矩陣中的選定的數據組信息進行處理，並將得到的結果發送到客戶端。用參數表示即是，對收到客戶端的向量Pi= [Pil,Pi2,…，P J並結合虛擬數據矩陣塊中待查詢的第jth個模塊的第Cth個元素'。，計算
R ,c ~ p 'Jw Jc (I 彡 C 彡 s);最後將[Ril, Ri2, Ris]發送到客戶端。在這ー步驟中，對每ー個單獨的伺服器來說，它們作為ー個個體處理查詢信息的詳細過程如下為了優化存儲空間，這裡採用的資料庫是三維的，數據存儲在ニ維矩陣裡。在檢索的時候，資料庫會首先根據這些矩陣塊的編號將之提取出來。步驟四清除虛擬數據矩陣，並將之前和客戶端協商所留下的關聯信息一井清理。本發明所述的客戶端對伺服器端反饋信息的處理方法，即客戶端處理服務端反饋結果。由於並不是所有的伺服器都傳送反饋結果給客戶端，所以客戶端對殘缺的反饋結果做出一定的修復，對該階段的設計方法包括如下步驟步驟一由於伺服器可能是惡意伺服器或者伺服器本身出現了ー些問題，所以並不是所有的伺服器都能夠響應客戶端的請求，假設有k個伺服器做出了響應回答，那麼令Y1, Y2,…，Yk為這k個伺服器的數目，同時將不做響應的伺服器j的響應向量[RfRj2,…，Rjs]置為丄。則 G ={ Y 1; Y2,…，Yk},且 H = {(G, ε )}。
步驟ニ 如果k值小於方案要求的最低響應伺服器數量，即對k彡t的情況，客戶端將檢索不到所需要信息。因而，令k為最小數目的可信伺服器的個數，則可信伺服器的個
數h的範圍是(、/反んI。步驟三如果k值大於等於方案要求的最低響應伺服器數量，但響應伺服器數量沒有達到N的情況下，客戶端將會採用拉格朗日插值法對得到的響應信息進行修復。修復成功的結果即為所求。即是在I彡c彡s (查詢內容沒有越界)的情況下，首先做簡單修復處理，如果成功的話，將值返回給H'(用於暫存修覆信息的集合)，如果H'是空集，則要做較為有難度的修復處理，並將值返回給H'，如果H'繼續空集，那麼拋出錯誤「沒有足夠的可信伺服器回復」，將屮賦值給H。步驟四最後得到的結果是H，則客戶端按照反編碼的方法將H中的結果處理成文字的形式返回給用戶。與現有技術相比，本發明具有如下有益效果I、提出虛擬數據矩陣的概念，用於解決資料庫伺服器對用戶查詢信息的惡意留存和窺探。考慮到客戶端雖然可以通過安全技術保證其信息在短時間內安全，但是伺服器留存用戶信息後，可以採用其它方式對其信息進行破解，從而威脅用戶的隱私。虛擬數據矩陣的概念就在於，虛擬數據矩陣需要作為伺服器的一個外設安裝在進行隱私檢索的伺服器上。毎次客戶對伺服器的檢索實際上可以在虛擬數據矩陣上進行，這樣每次查詢結束後，虛擬數據矩陣上的信息將會自動清除，這樣，伺服器也就沒有辦法留存信息了。2、將同態加密技術應用於隱私保護信息檢索方案中。當前在對多伺服器環境下隱私信息檢索的研究中，比較多的考慮伺服器串謀對查詢信息的威脅，卻比較少考慮單伺服器本身對用戶的威脅。通過對查詢信息的秘密共享向量再次加密，大大降低了單伺服器對查詢信息的威脅，同時基於同態加密的特殊性質，此次加密也沒有對執行效率帶來過多的負擔。
圖I是本發明的客戶端和伺服器端的秘密通信階段流程圖；圖2是本發明的客戶端和服務端的交互階段流程圖；圖3是本發明的客戶端處理服務端反饋結果的階段流程圖；圖4是詳細闡述採用三維資料庫處理查詢部分實例示意圖。
具體實施例方式下面結合附圖對本發明的實施例作詳細說明本實施例在以本發明技術方案為前提下進行實施，並以醫藥資料庫為背景，給出了詳細的實施方式和具體的操作過程，但本發明的保護範圍不限於下述的實施例。
實 施例I本實施例提供了一種客戶端和伺服器端秘密通信建立方法，用戶可採用該方法建立起和伺服器的秘密通道。如圖I所示，本實施例包括如下步驟步驟一，用戶申請建立到服務端的連接。用戶向伺服器發送Client-Hello消息，將本機可處理的加密類型等信息傳送給伺服器；步驟ニ,服務端回應給用戶Server-Hello消息,並將自己的X. 509證書發送過去，以便用戶能夠認證自己；步驟三，用戶認證完服務端後，將生成主密鑰，然後採用RSA加密算法，用服務端的公鑰加密後傳送過去；步驟四，服務端用自己的私鑰解密用戶發送過來的信息。用戶傳送會話ID給伺服器，伺服器發送Server-Finished消息給用戶，其中包括以主密鑰加密會話的ID。至此，安全連接建立。步驟五，建立起安全連接的服務端和客戶端將會繼而協商使用哪些數據塊來完成整個數據檢索過程。實施例2本實施例提供了一種客戶端和伺服器端交互流程的方法，用戶可採用該方法與伺服器進行交互。如圖2所示，本實施例包括如下步驟步驟ー在客戶端，需要對發送到伺服器端的查詢語句進行處理。這裡，假設用戶的查詢語句是「高血壓」，然後，採用一定的編碼方式，對其進行編碼，並將以數字流的形式發送，隨後還需要採用秘密共享協議和ElGamal加密算法對之進行處理，具體為①·給定有限域Z和秘密σ e Z,需要建立一個(3+1)-private 6_way的秘密共享方案。這裡將I取6，t取3，即是共有6個伺服器，其中有3個伺服器相互串謀，是惡意伺服器。從Z中選取6個兩兩不同的非零元素a1; a2, ···, a6 e {I, 2, . . . , min (pq)-1} (p和q是任意取的素數)；再從Z中隨機的選取3個元素0l，σ2, σ3;構建多項式f(x)=σ + σ jX+ σ 2χ2+ σ 3x3 6 個分享即為 f (a) , f (a2),…，f (a6)。②·進ー步，設定i為長度為r的向量[V1, V2,…，Vr] (Vj e Zpq, j e [1，r])。這裡r可隨意取。然後可以獨立的為;;中的每個元素生成一個共享流。即是，令Xf x$，…，Xj6 為 V j 白勺 6 個秘 tS' 共子，那麼[XiI，X21 ···，XrI J，[X12，X22， · · ·，Xr2]， ···，[叉16，叉26，· · ·，Xrf]就為卩的秘密共享。這種做法的意義在於進行了雙重的秘密共享處理，為查詢信息加上了雙保險。③.對上面由秘密共享協議生成的查詢語句，用ElGamal加密算法加密，因為ElGamal加密算法具有乘法同態性。此中生成密鑰的方法是令P = 2q+l，其中p和q都是素數。令g是Gq的生成元。貝IJ公鑰就是h = g_k，其中kezq，k是對應的私鑰。此中加密的方法是對要加密消息m e Gq,令E(m) = (a, b) = (gr, mhr),其中r e Zq。④.總結上面的步驟,首先從H中選擇6個隨機序列a1;a2,…，a6;其次取r個度為3的隨機多項式f1; f2，…，fr多項式的係數必須是R中的元素；再次對I彡i彡6計算P i = Lf1 (Bi)，f2(ai)，…，fr(ai)l ;最後對I彡i彡6將P i發送到對應的伺服器端。步驟ニ本用例的三維實驗資料庫設計如下，其資料庫中的數據矩陣塊按照自然數序列進行排序。每ー個數據矩陣塊的大小為IM = IK * 1K。由上文中提到的I取6，則按照邏輯劃分，則每ー個數據矩陣塊存儲了 36 = 6 * 6的信息塊，則每次用戶查詢時，伺服器會首先根據第一階段和客戶端的秘密協商結果-檢索第I個數據矩陣，初始化虛擬數據矩陣，該虛擬數據矩陣將會存儲在資料庫的寄存器裡，以待查詢結束後將其清除；步驟三，對用戶發送過來的查詢信息和虛擬數據矩陣中的選定的數據組信息進行處理。具體為，對收到客戶端的向量
權利要求
1.一種客戶端和伺服器端的秘密通信方法，其特徵在於，包括如下步驟 步驟一，客戶端建立到SSL服務端的TCP連接，隨後，發送一個Client Hello消息啟動SSL握手，該消息包含了客戶端支持的算法列表和一些有用消息； 步驟二，服務端回應一個Server Hello，它確定了這次通信所需要的算法，隨後，服務端將自己的X. 509證書發送過去，以便客戶端能夠認證自己； 步驟三，客戶端在認證完SSL服務端後，將生成一個秘密消息，然後用伺服器端的公鑰加密後傳送過去； 步驟四，服務端用自己的私鑰解密後，會話密鑰協商成功； 步驟五，建立起安全連接的服務端和客戶端將會繼而協商使用哪些數據塊來完成整個數據檢索過程。
2.一種客戶端和伺服器端的交互方法，其特徵在於，包括如下步驟 步驟一在客戶端，對查詢語句進行處理按照秘密共享協議將一個查詢請求的內容處理成N份，N取決於伺服器的個數，然後對其每份查詢語句用ElGamal加密算法加密，將加密完成的查詢語句分別發送到對應的N個資料庫； 步驟二 在服務端，由於採用的實驗資料庫是三維設計的，數據存儲在二維矩陣裡，並以獨立數據矩陣塊按一定的編碼方式，空間有序的存放在資料庫中，每次用戶查詢時，伺服器檢索資料庫並形成虛擬數據矩陣塊，用戶的查詢將會在這些虛擬數據矩陣塊中完成，因而伺服器首先根據第一階段和客戶端的秘密協商結果一第I個數據矩陣，初始化虛擬數據矩陣； 步驟三，根據之前和客戶端的協商，確定虛擬數據矩陣中待查詢的元素所在的數據組，然後對客戶端發送過來的查詢信息和虛擬數據矩陣中的選定的數據組信息進行處理，並將得到的結果發送到客戶端； 步驟四清除虛擬數據矩陣，並將關聯信息一併清理。
3.根據權利要求2所述的客戶端和伺服器端的交互方法，其特徵在於，所述步驟一，具體步驟如下 ①.給定有限域Z和秘密0G Z，需要建立一個(t+1)-private l_way的秘密共享方案，從Z中選取I個兩兩不同的非零元素ai，a2，-,B1 G {1，2，. . .，min(pq)-l};再從Z中隨機的選取t個元素O1, o2，…，0 t ;構建多項式f(x) = 0 + 0 lX+0 2x2+"* +0 txl ;貝1] I個分享即為f Oa1)，f (a2)…，f (ax)； ②.進一步，設定^為長度為r的向量[V1,v2，-,vr] (Vj G Zpq, j G [l，r])，然後以獨立的為^中的每個元素生成一個共享流，即是，令％，Xp，…，Xn為 ' 的I個秘密共享，那麼[Xii，X2J ...，Xrl]，[x12 X22，...，Xr2]，...，[X1I, X2i，...，Xri] /就為; ③.對上述步驟裡由秘密共享協議生成的查詢語句，用ElGamal加密算法加密，ElGamal加密算法具有乘法同態性，此中生成密鑰的方法是令p = 2q+l，其中p和q都是素數；令Gq是QRp的子群，且g是Gq的生成元，則公鑰就是h = g_k，其中k e Z,，k是對應的私鑰；此中加密的方法是對要加密消息mG Gq，令E(m) = (a，b) = (g^mhO，其中r e Zq ； ④.此處，將用戶的查詢信息處理成I個向量秘密共享流，從H中選擇I個隨機序列B1, a2，…，B1 ;其次取r個度為t的隨機多項式f\，f2，…，fr多項式的係數必須是R中的元素；再次對I彡i彡I計算P i = [Kai)，f2 (Bi)，…，fr(ai)];最後對I彡i彡I將P i發送到對應的伺服器端。
4.一種客戶端對伺服器端反饋信息的處理方法，包括如下步驟 步驟一假設有k個伺服器做出了響應回答，那麼將沒有做出響應的伺服器的響應信息設為丄； 步驟二 如果k值小於方案要求的最低響應伺服器數量，那麼客戶端將得不到所需要信息； 步驟三如果k值大於等於方案要求的最低響應伺服器數量，但響應伺服器數量沒有達到N的情況下，客戶端將會採用拉格朗日插值法對得到的響應信息進行修復，修復成功的結果即為所求。
5.一種多伺服器環境下的隱私信息檢索方法，包括兩個階段 第一階段通過SSL協議實現的客戶端和伺服器端的秘密通信；所述客戶端和伺服器端的秘密通信方法採用權利要求I所述方法； 第二階段通過秘密共享協議和ElGamal同態加密算法支持的客戶端和伺服器端的交互；所述客戶端和伺服器端的交互方法採用權利要求2所述方法。
6.根據權利要求5所述的多伺服器環境下的隱私信息檢索方法，其特徵在於，進一步包括第三階段，即客戶端在拉格朗日插值的理論支持下對伺服器端反饋信息的處理。
7.根據權利要求6所述的多伺服器環境下的隱私信息檢索方法，其特徵在於，所述客戶端對伺服器端反饋信息的處理方法採用權利要求4所述方法。
全文摘要
本發明公開一種多伺服器環境下的隱私信息檢索方法，包括通過SSL協議實現的客戶端和伺服器端的秘密通信；通過秘密共享協議和ElGamal同態加密算法支持的客戶端和伺服器端的交互信息檢索；客戶端在拉格朗日插值的理論支持下對伺服器端反饋信息的處理。本發明提出虛擬數據矩陣用於解決資料庫伺服器對用戶查詢信息的惡意留存和窺探，每次客戶對伺服器的檢索實際上可以在虛擬數據矩陣上進行，這樣每次查詢結束後，虛擬數據矩陣上的信息將會自動清除；將同態加密技術應用於隱私保護信息檢索方案中，通過對查詢信息的秘密共享向量再次加密，大大降低了單伺服器對查詢信息的威脅。
文檔編號H04L29/06GK102629924SQ20121009031
公開日2012年8月8日 申請日期2012年3月30日 優先權日2012年3月30日
發明者陳楊楊, 黃徵 申請人:上海交通大學