盲化索引表產生方法和設備、聯合關鍵字搜索方法和設備的製作方法

2023-09-22 02:21:30 2

專利名稱：盲化索引表產生方法和設備、聯合關鍵字搜索方法和設備的製作方法
技術領域：
本發明涉及計算機通信網絡安全領域，更具體地，涉及一種盲化索引表產生方法 和設備、以及一種秘密密鑰設置下的聯合關鍵字搜索方法和設備。
背景技術：
數據存儲外包是當前網際網路上的一種趨勢，即以全球存檔服務而不是使用自身的 本地存儲器來存儲數據。現在，基於網際網路的在線存檔服務為其終端用戶提供大量的存儲 空間，其終端用戶包括個人用戶和企業。存在提供各種用戶數據的存儲的存檔服務。例 如，Amazon Simple Storage Service (Amazon S3)(參考文獻[1])提供一種網絡服務接 口，可用於存儲和檢索不限量的分類數據，以GB/月和數據傳輸量來計費。還存在提供特 定數據類型的存儲的其它存檔服務，尤其是敏感數據類型，例如健康記錄。例如，Google Health (參考文獻[2])和Microsoft HealthVault (參考文獻[3])兩者均提供個人健康信 息集中化服務，有助於其用戶將分離的健康記錄合併為一個集中的檔案。儘管這些存檔服務帶來了便捷和易用的優點，但是它們也引起了對安全性的深度 擔憂。儘管所有這些服務提供商都提出了適當的書面安全和隱私策略，並且採取一些信息 安全和系統安全措施來執行這些策略，但是，用戶僅僅依賴於存檔服務提供商來確保其數 據安全和隱私是危險的。無疑服務提供商可能會無法適當地執行它們的書面安全和隱私策 略。以存儲客戶的信用卡數據的企業為例。在2008年6月，BBC新聞報導了服裝廠 Cotton Traders的多達3. 8萬名客戶的信用卡細目被盜(參考文獻[4])。這種情況並不 少見，而且也不是最嚴重的事件。Securityfocus.com(參考文獻[5])報導了在2005年7 月至2007年1月間，未知攻擊者入侵TJX公司的計算機交易處理系統，盜取了至少4560萬 張信用卡的數據。信用卡信息被認為至少與分類數據或健康記錄同樣敏感。因而，可以推斷出，存儲 信用卡信息的公司具有適當的書面安全和隱私策略並且應該運用了表面上有力的安全措 施來執行其策略。這些安全措施至少應該與用於保護分類數據或健康記錄的安全措施一樣 有力。由於信用卡信息被披露的多次報導，同時注意到大量用戶數據的高價值，因此，沒有 理由堅持認為存檔服務提供商所存儲的數據不會被盜和被暴露。無論如何，存在一種應對數據安全入侵的簡單對策，即在輸出敏感數據之前對其 加密。結果，即使存檔服務受到危害，所暴露的也只是大量密文，攻擊者無法從中獲利。然 而，這種簡單對策的代價是可用性。具體地說，難以搜索輸出到外部的數據。例如，如果健 康記錄的所有方對健康記錄進行了加密，則允許授權用戶搜索健康有關信息的Microsoft Live Search Health (Microsoft HealthVault的搜索組件)無法工作。(當然，我們假定 數據的所有方對其隱私充分關注，因此不會與Microsoft共享他們的解密密鑰。)我們所關注的系統有三方，即數據所有方、伺服器和搜索方。數據所有方對其數據 文件進行索引、對其數據文件進行加密並將索引和文件輸出到伺服器。伺服器存儲加密的文件及其索引(索引表)，並提供對加密文件的搜索。搜索伺服器的搜索方通常不是數據所 有方自己，但是，當然，搜索方也可以是數據所有方自己。為了能夠搜索加密數據，搜索方需 要獲得從數據所有方發出的搜索權限(SC)，並且搜索方需要將SC提交給伺服器。伺服器可 以通過將SC運用於索引來搜索加密數據。除了 SC之外，搜索方還需要獲得數據所有方發 出的解密權限(DC)。在從伺服器接收到搜索結果時，搜索方將使用DC來對搜索結果進行解 密，從而將數據文件恢復為明文。一些基本的安全要求包括1)伺服器不知道搜索方查找什麼，例如，如果搜索方正在搜索包含關鍵字「網絡」 的文獻，伺服器應該不知道。2)搜索方無法根據經驗偽造搜索權限，例如，如果搜索方曾經被發給了搜索包含 關鍵字「網絡」的文獻的SC，他應該不能夠製造針對關鍵字「網」或「絡」的Sc。這同樣適用 於伺服器，即使搜索 方與伺服器串通。3)解密權限與SC唯一關聯，例如，如果SC允許搜索包含關鍵字「網絡」的文獻，DC 則僅能夠對該特定SC的搜索結果進行解密。這同樣適用於伺服器，即使搜索方與伺服器串 通，即，伺服器也許對其所存儲的所有加密文件嘗試使用DC，但是除了 SC的搜索結果之外， 都沒用。除了上述安全要求之外，還有效率要求，例如SC的大小、索引的大小以及搜索所 花費的時間等。自從Song等人(參考文獻[6])首次提出了關於如何有效地對加密數據進行關鍵 字搜索的問題以來，加密數據的搜索引起了廣泛的關注。加密數據的搜索是不同領域的技術的融合，因而具有不同的分類標準。1)從加密技術角度看，在秘密密鑰設置中和公共密鑰設置中考慮關鍵字搜索的加 密，在秘密密鑰設置中這被稱為可搜索對稱加密(SSE)(參考文獻[6])，在公共密鑰設置中 這被稱為公共密鑰加密搜索(PEKS)(參考文獻[7])。然而，值得注意的是，通過使公共密鑰 保密，任何PEKS方案都簡單地在SSE設置中也行得通。2)從索引技術角度看，在正向索引設置中和倒排索引設置中考慮關鍵字索引的加 密，在正向索引設置中這被稱為盲化正向索引表(BFT)，在倒排索引設置中這被稱為盲化倒 排索引表(BIT)。3)從搜索權限角度看，在單個關鍵字搜索(SKS)和聯合關鍵作搜索(CKS)中考慮 關鍵字搜索的加密。4)從搜索關鍵字角度看，在域特定關鍵字(DSK)和非限定域關鍵字(DH0中考慮 關鍵字搜索的加密。就我們所知，現有技術大多數符合SSE、BFT、SKS和DH(。也就是說，現有技術是秘 密密鑰設置的、基於盲化正向索引表、利用非限定域關鍵字、僅能夠單個關鍵字搜索。然而， 存在一些另外情況。參考文獻[8]、[9]和[10]提出了公共密鑰設置(PEKS)的方案，可以實現對盲化 正向索引表(BFT)的域特定關鍵字(DSK)的聯合關鍵字檢索(CKS)。值得再次注意的是，通過使公共密鑰保密，公共密鑰設置(PEKS)的任何方案都簡 單地在秘密密鑰設置(SSE)中也行得通。
參考文獻[8]並未公開如何對搜索結果進行解密，因為所公開的方案並未考慮解 密權限。因此，儘管搜索方可以對伺服器進行搜索，但是在從伺服器接收到聯合關鍵字搜索 結果時，搜索方無法對搜索結果進行解密。參考文獻[10]同樣並未考慮解密權限。儘管所公開的方案包括解密過程，但是該解密過程的目的是使伺服器測試可能的搜索結果，而不是使搜索方對搜索結果進行解密。 實際上，在參考文獻[10]的方案中並未構想解密權限。參考文獻[9]在聯合關鍵字搜索和解密搜索結果方面是完備的。根據參考文獻 [9]的方案，搜索方將不僅需要被發給搜索權限，而且需要被發給解密權限。具體地，圖1和圖2以兩個階段示出了參考文獻[9]的詳細過程，即索引階段(圖 1)和搜索階段(圖2)。參考圖1和圖2，數據所有方、搜索方和伺服器的各個單元如下 盲化單元101以公共密鉬和(明文)正向索引表作為輸入，輸出盲化正向索引 表(BFT)和數據的加密密鑰。 加密單元102以加密密鑰和數據作為輸入，輸出加密數據(EF)。 權限發布單元201以秘密密鑰和關鍵字作為輸入，輸出搜索權限(SC)和解密權 限(DC)。 域杳找單元202以關鍵字和域知識作為輸入，輸出每個關鍵字的輔助域信息 (ADI)。
BFT匹配單元203以SC、ADI和BFT作為輸入，輸出BFT匹配結果，BFT匹配結 果包括BFT的每個匹配行的相應Aij和Bij以及指向與匹配行相對應的匹配EF的指針。
EF獲取單元204以BFT匹配結果和EF作為輸入，輸出具有相應Aij和Bij的匹 配EF。 解密單元205以DC和所產生的具有相應Aij和Bij的EF作為輸入，輸出解密的 數據F。表1 示例明文正向索引表
域1域2域3
"Name""City"『『Degree，，
F1"Alice""Beijing""Bachelor"...
F2"Bob""Shanghai""Master 「...
F3"Cindy""Tokyo""Ph. D.「...在表1中，每一行可由不同的文件標識符Fi標識。下面除非特別指出，否則使用 Fi來表示文件自身及其唯一文件標識符(例如文件名)。表1的每一列由唯一域名標識。根據參考文獻[9]，盲化單元101輸出的BFT如下表1-1所示。表1-1示例盲化正向索引表
匹配指示符γ^ rw2 ρ^
EF1 T1A11 j B11A12，B12A13J B13 · · ·
EF2 T2A2I，B21A22，B22A23，B23 · · ·
EF3 T3A31，B31A32，B32A33，B33 · · ·簡而言之，參考文獻[9]公開了以下方法。設置 PK = {PX,P2,SXiYi= P；'}}，i = 1，2，· · ·，m，}；+, = P；- ,Ym+2 二 P11-，其中 m 確定了系
統可以容納的域的數量。加密選擇IrJ並計算5,，i = 1，2，· · ·，m(由盲化單元101執行)；選擇sk 來加密 F，計算 rQ = H (F，{Bj，sk)，尺=Ym+；" ,S = H(gr")和= H(hr") Θ sk (由加密單元102執行)；計算4 =C^ZfwY1 P；·(由盲化單元101執行)。儘管標記不同，但是Ai和Bi都是如表1-1所示的索引項，而S是匹配指示符。注 意，還產生了第二隨機數發生器K。產牛SC 禾口 DC 選擇隨機數u和V，並計算
L0049」 SC = JcJ '.『 ''',SC = SC Ι/Λ,"+Ι , = u ；DC| =』DC: =，DC3 = ν(由權限發布單元 201 執行)。捭索
(( ^ e對於每一行，測試是否// -γ^- = S (由域查找單元202和BFT匹配
V V ^ ) J
單元203執行)。解密捭索結果 f \ e HAirKDC\ DCx計算= -yj並恢復(由EF獲取單元204和解密單
e\Y\Bi ,DC1 { 『 )sk = H(hr") R元205執行)。搜索方(例如查找包含關鍵字「Alice」和「Beijing」的文獻的搜索方)將進行如 下動作1)聯繫數據所有方、請求所需的關於關鍵字集合的搜索權限和解密權限、並在數 據所有方願意的情況下從數據所有方接收這些權限。該步驟涉及權限發布單元201、域查找 單元202和附加的通信單元(圖1中未示出)。2)搜索方將搜索權限，即SCnSC2* SC3，遞交給伺服器。伺服器然後針對每個EFi, 測試是否與聯合關鍵字搜索匹配。最後，伺服器將所有的匹配EFiS回給搜索方。該步驟 涉及BFT匹配單元203、EF獲取單元204和附加的通信單元(圖1中未示出)。3)在接收到匹配EFi時，搜索方可以使用解密權限，即DC1, DC2，和DC3，對EFi進行 解密並恢復相應的文件標識符F」該步驟涉及解密單元205。然而，上述參考文獻[9]的方案具有多個缺點，如下 1)每個搜索項具有至少兩個部分，一個用於盲化關鍵字(下面稱為盲化索引)，另 一個用於檢測關鍵字(下面稱為隨機數發生器)。由於可能存在大量的索引項，所以非常希 望在搜索項中省略隨機數發生器。2)為了測試加密文獻是否包含聯合關鍵字，伺服器需要進行2次配對評估。非常 希望將配對評估的次數減少為僅有一次。3)該方案要求每個關鍵字屬於唯一域，例如關鍵字「Alice」屬於域「用戶名」。這 種類似資料庫的要求當前在正向索引表的設置下是可以達到的。但是，在倒排索引表的設 置下，例如類似Google搜尋引擎的設置，多數關鍵字沒有域的聯繫，換言之，文獻是無結構 的，關鍵字的域是不定的。因此，該方案在文獻是無結構的、包含非限定域關鍵字的情況下 不可行。4)搜索權限和解密權限每個均消耗3個群成員。非常希望每個權限僅消耗1個群 成員。最後但並非最不重要的，現有技術均沒有涉及「非關鍵字」搜索，例如搜索包含關 鍵字「Alice」但是不包含「網絡」的文獻。在這種情況下，如果一篇文獻包含關鍵字「網絡」， 則即使它包含關鍵字「Alice」它也不是搜索結果。

發明內容
鑑於現有技術的上述缺點，本發明提出了一種盲化索引表產生方法和設備、以及 一種秘密密鑰設置下的聯合關鍵字搜索方法和設備。根據本發明的第一方案，一種用於產生盲化索引表的設備包括初始化單元，用於 執行初始化過程以獲得秘密密鑰和公共密鑰；關鍵字預處理單元，用於利用秘密密鑰，根據 關鍵字索引項，產生私密關鍵字；盲化單元，用於對於索引表的每一行隨機地選擇種子； 利用公共密鑰和種子來產生匹配指示符；利用公共密鑰、秘密密鑰和種子來產生加密密鑰； 利用加密密鑰來加密該行中的文件標識符項，以獲得加密的文件標識符；利用秘密密鑰和 種子來盲化該行中的私密關鍵字，以獲得盲化索引集合；通過排列加密的文件標識符、匹配 指示符和盲化索引集合，形成盲化索引表的一行。優選地，所述設備還包括加密單元，用於針對索引表的每一行，用加密密鑰來加密與該行對應的文件，以獲得加密的文件數據。優選地，每一個關鍵字索引項屬於一個域，並且與一個盲化索引相對應。更優選 地，用另一個秘密密鑰來加密每個域的域名。優選地，盲化索引表的每一行至少包括一個匹配指示符和一個盲化索引集合。優選地，索引表是正向索引表，域的名稱反映了屬於該域的索引項的公共屬性。優選地，索引表是轉換自正向索引表的倒排索引表，在該倒排索引表中，域的名稱 被定義為正向索引表的一個索引項，域的每一項為布爾型。根據本發明的第二方案，一種用於產生盲化索引表的方法包括步驟執行初始化 過程以獲得秘密密鑰和公共密鑰；對於索引表的每一行隨機地選擇種子；利用公共密鑰 和種子來產生匹配指示符；利用公共密鑰、秘密密鑰和種子來產生加密密鑰；利用加密密 鑰來加密該行中的文件標識符項，以獲得加密的文件標識符；利用秘密密鑰從該行中的關 鍵字索引項中產生私密關鍵字；利用秘密密鑰和種子來盲化該行中的私密關鍵字，以獲得 盲化索引集合；通過排列加密的文件標識符、匹配指示符和盲化索引集合，形成盲化索引表 的一 行。優選地，加密密鑰還用於加密與該行對應的文件，以獲得加密的文件數據。優選地，每一個關鍵字索引項屬於一個域，並且與一個盲化索引相對應。更優選 地，用另一個秘密密鑰來加密每個域的域名。優選地，盲化索引表的每一行至少包括一個匹配指示符和一個盲化索引集合。優選地，索引表是正向索引表，域的名稱反映了屬於該域的索引項的公共屬性。優選地，索引表是轉換自正向索引表的倒排索引表，在該倒排索引表中，域的名稱 被定義為正向索引表的一個索引項，域的每一項為布爾型。根據本發明的第三方案，一種在盲化索引表中執行聯合關鍵字搜索的設備包括 關鍵字預處理單元，用於通過使用秘密密鑰，針對所查詢的關鍵字集合中的每個關鍵字產 生私密關鍵字，所產生的私密關鍵字形成了與所查詢的關鍵字集合相對應的私密關鍵字集 合，私密關鍵字和所查詢的關鍵字的數量都是正整數；權限發布單元，用於利用公共密鑰、 秘密密鑰和私密關鍵字集合來產生所查詢關鍵字集合的搜索權限，搜索權限標識了所查詢 關鍵字集合所屬的域，以及用於利用搜索權限和秘密密鑰來產生解密權限；命中項匹配單 元，如果盲化索引表中一行的匹配指示符與從屬於該行中的所標識的域的各個索引項和搜 索權限而聯合產生的值相同，則確定該行是命中行；解密單元，用於利用屬於命中行中的所 標識的域的各個索引項和解密權限來產生每一命中行的解密密鑰，以及用於利用解密密鑰 來解密每一命中行的已加密文件標識符和已加密文件數據，以獲得搜索結果。優選地，盲化索引表的每一行至少包括一個匹配指示符和一個盲化索引集合。優選地，索引表是正向索引表，域的名稱反映了屬於該域的索引項的公共屬性。優選地，索引表是轉換自正向索引表的倒排索引表，在該倒排索引表中，域的名稱 被定義為正向索引表的一個索引項，域的每一項為布爾型。優選地，所述的設備還包括域加密單元，用於用另一個秘密密鑰來加密每個域的 域名。根據本發明的第四方案，一種在盲化索引表中執行聯合關鍵字搜索的方法包括步 驟通過使用秘密密鑰，針對所查詢的關鍵字集合中的每個關鍵字產生私密關鍵字，所產生的私密關鍵字形成了與所查詢的關鍵字集合相對應的私密關鍵字集合，私密關鍵字和所查 詢的關鍵字的數量都是正整數；利用公共密鑰、秘密密鑰和私密關鍵字集合來產生所查詢 關鍵字集合的搜索權限，搜索權限標識了所查詢關鍵字集合所屬的域；利用搜索權限和秘 密密鑰來產生解密權限；如果盲化索引表中一行的匹配指示符與從屬於該行中的所標識的 域的各個索引項和搜索權限而聯合產生的值相同，則確定該行是命中行；利用屬於命中行 中的所標識的域的各個索引項和解密權限來產生每一命中行的解密密鑰；以及利用解密密 鑰來解密每一命中行的已加密文件標識符和已加密文件數據，以獲得搜索結果。優選地，盲化索引表的每一行至少包括一個匹配指示符和一個盲化索引集合。優選地，索引表是正向索引表，域的名稱反映了屬於該域的索引項的公共屬性。優選地，索引表是轉換自正向索引表的倒排索引表，在該倒排索引表中，域的名稱被定義為正向索引表的一個索引項，域的每一項為布爾型。優選地，用另一個秘密密鑰來加密每個域的域名。與最接近的現有技術相比，本發明的積極效果包括(I)伺服器存儲的索引表的大小近似減半；(II)聯合關鍵字搜索的速度提高兩倍；(III)能夠進行涉及非限定域關鍵字的聯合關鍵字搜索；(IV)能夠進行涉及「非關鍵字」的聯合關鍵字搜索；(V) SC和DC的大小被最小化。


結合附圖，根據下面對本發明的非限制性實施例的詳細描述，本發明的上述及其 他目的、特徵和優點將變得更加清楚，附圖中圖1是示出了根據參考文獻[9]、在索引階段工作的各個單元的框圖；圖2是示出了根據參考文獻[9]、在搜索階段工作的各個單元的框圖；圖3是示出了根據本發明第一實施例、在索引階段工作的各個單元的框圖；圖4是示出了根據本發明第一實施例、在搜索階段工作的各個單元的框圖；圖5是示出了根據本發明第二實施例、在索引階段工作的各個單元的框圖；以及圖6是示出了根據本發明第二實施例、在搜索階段工作的各個單元的框圖。
具體實施例方式下面，根據附圖描述本發明。在以下描述中，一些具體實施例僅用於描述目的，而 不應該理解為對本發明有任何限制，而只是本發明的示例。省略了常規結構或構造，以免導 致對本發明的理解不清楚。[第一實施例]根據本發明的第一實施例，圖3和圖4以兩個階段示出了在秘密密鑰設置(CKSS 方案)下所提出的聯合關鍵字搜索方案的詳細過程，即索引階段(圖3)和搜索階段(圖 4)。參考圖3，數據所有方、搜索方和伺服器的各個單元如下 關鍵字預處理單元303和406以秘密密鑰和(明文)正向索引表中的關鍵字作 為輸入，輸出私密關鍵字。
盲化單元301以秘密密鉬、(明文)正向索引表、私密關鍵字作為輸入，輸出盲化 正向索引表(BFT)和數據的加密密鑰。BFT不再對於表的每一項都有隨機數發生器(Bij), 而是對於每個EF有匹配指示符(1\)。 權限發布單元401以秘密密鑰和私密關鍵字作為輸入，輸出搜索權限(SC)和解 密權限(DC)。
BFT匹配單元403以SC、ADI和BFT作為輸入，輸出BFT匹配結果，BFT匹配結 果包括BFT的每一匹配行的相應Aij和指向與匹配行相對應的匹配EF的指針。 所有其它單元(302、402、404和405)按照在本發明「背景技術」部分描述的單 元(102、202、204和205) —樣工作，因此在此為了簡明而省略這些單元的詳細說明。場景說明
首先給出在秘密密鑰設置(CKSS方案)下所提出的聯合關鍵字搜索方案的概述。不失一般性地，以示例的明文正向索引表開始。示例的明文正向索引表如表1，與 在本發明的「背景技術」部分中所述的表一樣。表1示例明文正向索引表 在表1中，每一行可由不同的文件標識符Fi標識。下面除非特別指出，否則使用 Fi來表示文件自身及其唯一文件標識符(例如文件名)。表1的每一列由唯一域名標識。使用CKSS方案，上表1將由盲化單元301轉換為下表2 表2示例盲化正向索引表 首先，表2中的域名可以與表1中的域名相同。例如，可以將表2中的域2表示為 「City」。在表2中，每一個表項都被盲化，例如，表1中的「Alice」由所謂的盲化索引A11代 替。盲化索引被構造成(在計算上)不會洩漏任何關於「Alice」的信息。盲化索引僅消耗 1個群成員。此夕卜，可以看出，Fi 代替，EFi是關於Fi的密文。利用正確的DC，搜索方可以 解密EFi以恢復Fi。與現有技術相比，尤其是與參考文獻[9]相比，存儲複雜度方面的益處是明顯的。 每個盲化索引僅消耗1個群成員。CKSS方案不需要存儲附加信息，例如參考文獻[9]所需 的隨機數發生器。每次嘗試的計算複雜度減少為1次配對評估，例如為了測試EF1是否包含聯合關鍵字，將使伺服器僅進行ι次配對評估。此外，根據CKSS方案的SC和DC的大小也分別減 小為1個群成員。後面將描述計算複雜度分析的細節以及SC和DC的大小。搜索方(例如搜索包含關鍵字「Alice」和「Beijing」的文獻的搜索方)將進行如 下動作1)聯繫數據所有方、請求所需的關於關鍵字集合的SC和DC、並在數據所有方願意 的情況下從數據所有方接收SC和DC。SC應該包括所需的域信息。在上述示例的設置中， SC中包含域名「Name」和「City」。該步驟涉及權限發布單元401、關鍵字預處理單元406和 域查找單元402。2)搜索方將SC遞交給伺服器。伺服器然後針對每個EFi,測試是否與聯合關鍵字 搜索匹配。最後，伺服器將所有的匹配EFiS回給搜索方。該步驟涉及BFT匹配單元403、 EF獲取單元404。3)在接收到匹配EFi時，搜索方可以使用DC，對EFi進行解密並恢復相應的文件標 識符F」在上述示例的設置中，搜索方將接收到EFJt為搜索結果，並且搜索方可以使用DC 來對EF1進行解密並恢復F1。該步驟涉及解密單元405。[第二實施例]上述第一實施例僅涉及結構化數據(類似資料庫)。第二實施例將處理無結構數 據(類似Google)。此外，第二實施例可以處理「非關鍵字」查詢，例如搜索包含關鍵字 「Alice」但是不包含「Music」的文獻。在第二實施例中，關鍵字在邏輯上被當作域，列號產生單元用於定位BFT中的與 關鍵字相對應的列(邏輯域)。根據本發明的第二實施例，圖5和圖6以兩個階段示出了秘密密鑰設置(CKSS方 案)下所提出的聯合關鍵字搜索方案的詳細過程，即索引階段(圖5)和搜索階段(圖6)。 參考圖5和圖6，數據所有方、搜索方和伺服器的各個單元如下 除了列號產生單元504和607之外的所有單元與第一實施例中的單元一樣工 作，因此為了簡明，省略這些單元的詳細說明。 列號產生單元504和607以秘密密鑰和關鍵字作為輸入，輸出BFT中明確針對 該關鍵字的列號。
場景描述除了在第一實施例中所述的CKSS的基本方案，下面在第二實施例中示出如何實 現聯合關鍵字搜索和「非」關鍵字搜索。下表3示出了在非限定域情況下的正向索引表的構造。與表1相比，可以將其解 釋為「邏輯上將密鑰當作域」。熟悉倒排索引表的人也可以將表3解釋為由倒排索引表的 旋轉得來。無論如何解釋表3，都需要注意的是，如果文件不包含一關鍵字，則用特殊詞語 「NULL」 填充相應的表項("Alice =NULL", "Beijing =NULL", "Music :NULL」)。例如，對於 列關鍵字「Alice」，該詞語「NULL」是「Alice」的160比特的帶有密鑰的散列。因此，實際上 不可能在文獻中遇到相同的詞語「Alice :NULL」。表3示例正向索引(非限定域) 使用CKSS方案，上表3將被轉換為下表4 表4示例盲化正向索引表(非限定域) 除了針對表2所解釋的內容之外，表4還需要一個代替。表3中的所有關鍵字在 表4中都由列號產生單元504所產生的列號代替。具體地，該過程規定了使用數據所有方 的秘密密鑰。作為簡單示例，可以計算列1作為「Alice」的帶有密鑰的散列。需要重申的是，表2可以並不經過域名的替換。例如，可以將表2中的域2表示為 「City」。然而，表4必須通過使用秘密密鑰和正確的措施，例如帶有密鑰的散列、加密等，經 過域名的替換，以隱藏關鍵字。
此外，考慮搜索包含關鍵字「Alice」和「Beijing」的文獻的搜索方。該搜索方將 從數據所有方接收所需的SC和DC，還從列號產生單元607接收列號。SC應該包含所需的 列信息。在該特定示例中，列信息是列1和列2。在搜索方將SC提交給伺服器之後，伺服器 針對每個EFi測試是否與聯合關鍵字搜索匹配。在接收到EFJt為搜索結果時，搜索方可以 使用DC來對EF1進行解密並恢復F1。現在離實現「非」關鍵字搜索僅有一步之遙。如果搜索方查找包含關鍵字「Alice」 和「非Bei jing」的文獻，搜索方接收到的實際上是與分別在列1和列2下的關鍵字「Alice」 和關鍵字「Beijing :NULL」有關的SC。[詳細原理說明]使用傳統的乘法群標記，代替通常在橢圓曲線設置中使用的加法標記。假設G1 = *G2 = 是兩個有限循環群，具有附加的群G = ^〉，使得
Kl = |g2| =間=P，其中P是某個大的素數。雙線性映射e G1 χ G2 — g是具有如下效果的 函數■雙線性的對於所有 e G1 A2 6 G2，對於所有α，δ € Zp ,e(h； ,h；) = e^hj'1' ■■非退化的3爾G G1 Sh2 G G2，使得eQ^，h2)乒I，其中I是g的單位元素；以及■可計算的存在計算e的有效算法。假設存在針對輸入安全參數Ik的設置算法Setup( ·)，輸出雙線性映射的上述設 置。該過程被表示為(P，G]，G2，g鳴，馬，e) — Setup(Ik)。由於巧、Gjpg都具有相同的素數階，因此根據雙線性特性以及非退化特性，很 容易可以看出6(仏，52)=議。現在，詳細描述CKSS方案。假設明文索引表構造如下對於每個明文文件(文獻) Fj，其明文文件名是FNj,存在一行匹配關鍵字IwjJ，其中每一個都唯一地屬於域Rp這裡， 「唯一」意味著文件一定不包含屬於多於一個域的單個關鍵字。我們注意到，有可能一個字 出現在不只一個域下。例如，「Alice」可以同時是患者的「親戚」和「聯繫人」。在這種情況 下，常用的方案是將關鍵字構造成「域關鍵字」，例如「親戚:Alice」和「聯繫人Alice」。 這樣獲得了下表5。表5示例明文正向索引表 密鉬產牛 b)選擇ζ3。c)選擇安全的單向散列函數Fk : G — K。d)選擇帶有密鑰的散列函數Ek K G Ζ； X {0,1}* — Z；，其中K是密鑰。公共密鑰是(p，G1,G2^J1,5.2，e)、Hk 和 Ηκ。秘密密鑰是(x，y，z)。BFT 產牛a)對於每個FNj,隨機地選擇種子~ ^ G1。例如，首先選擇\ €β ζ，然後計算 h:丨=g^' G G1。b)計算匹配標識符7； = Hk ^Zv52))和加密密鑰& = Hk (e(hv:g2))(由盲化單元 301執行)。C)使用密鑰&和適當的加密方案來加密h和FNp獲得加密的文件標識符Eh (由 加密單元302執行)。EFj具有彼此不同的特性，因此，在使用密鑰&對Eh進行解密時，將獲得h和FNj。 例如，首先選擇隨機加密密鑰fk來加密文件Fp此外，可以使用fk來加密F 並獲得密文 形式的FNj,即CF 。在這種情況下，EFj是朋=EncJfk,CFNJ唭中EnCkey(*)是以key
作為加密密鑰的某種對稱加密機制。很容易知道，利用密鑰Kj,可以對EFj進行解密以獲得 fk和CF 。利用CF 來定位和檢索加密文件，文件密鑰fk最終可以對加密文件和CFNj.進 行解密，CFNj揭示了。和FNj。d)對於Fj的每個Wji，計算盲化索引％ = h2+We G1。這裡，Hx(Wji)是「私密關 鍵字」(從關鍵字預處理單元303到盲化單元301)。最終，對於每個EFj,輸出(EFj :Tj; (WjJ)(以存儲在伺服器中)。因此，獲得下表 6 表6示例盲化正向索引表
Γ\
加密文件名 xXR1R2R3...
指示符
EF1T1WjiW12W13...
EF2T2W21W22 W23...
EF3T3W31W32 W33...
權限發布進行以下動作以計算目標關鍵字fhl的搜索權限，其中 <屬於域R 和 a)計算搜索權限 b)計算解密權限 該過程涉及權限發布單元401和關鍵字預處理單元406。最終，權限是SC和DC。SC中包括關於所屬的域{R }的信息。這裡，不需要 通過附加的隨機數來將SC和DC隨機化。如果pj包括關鍵字 然而&並不屬於任何域(如域查找單元402的輸出所指示 的)時，立即拒絕授予Sc。或者可選地，對於關鍵字 ，選擇某個域，以便可以計算Sc。這種 可選方案最終導致空的搜索結果集。捭索對於BFT的由EFj標識的每一行，以Wju表示屬於域Ru的盲化索引。 a)計算若且唯若丑時，EFj被當作聯合關
鍵字搜索結果。注意，對於所有的υ，若且唯若,= <時 該過程涉及BFT匹配單元403。最終，聯合關鍵字搜索的輸出是匹配集· efMw^。該過程涉及EF獲取單元
404。解密a)對於每一個搜索結果EFj和11 ，計算解密密鑰 b)使用Kj來對EFj進行解密並獲得CFNj和文件密鑰fk。該過程涉及解密單元 在Hk e Π 沉=iiK(e(/^2))的前提下，可以容易地驗證 [改進]可詵方案1 上表6以明文揭示了域信息。可選地，域信息可以被盲化，因此對於伺服器隱藏域 fn息ο例如，數據所有方具有附加的私密密鑰Ph ζ,，數據所有方可以計算ERi = Hp (Domain)，例如Hp (「 City")。下表7示出了具有盲化的域信息的BFT。現在，在上述權限發布過程最後，SC應該包含與盲化的域{ER )相關的信息，而不 是與域{R }相關的信息。表7示例可選盲化正向索引表 可詵方案2 除了在可選方案1中公開的相反之外，數據所有方可以邏輯上將關鍵字當作域， 即虛擬域。例如，表5可以被解釋為下表8:表8示例重解譯明文正向索引表 不難看出，表8也可以被當作倒排索引表。NULL表項，例如「wn :NULL」，表示該關鍵字並不包含在文件中。為了避免文件 的確包含諸如「Alice :NULL」的關鍵字的少數情況，數據所有方可以使用附加的私密密鑰 V^r ζ來處理NULL表項。例如，在表8中用「Wll (W11) 」代替「Wll :NULL」。現在假設數據所有方具有附加的私密密鑰W、ζ並且數據所有方可以計算虛擬 域五K = H/keyword)，例如凡(Mke1')。使用CKSS機制，重解譯的BFT可以構造成如下所 示(表9)表9示例重解譯盲化正向索引表 該可選方案所關注的在於能夠進行「非關鍵字」搜索。例如，搜索方以聯合關鍵 字「Alice且非Beijing」搜索文獻。數據所有方可以向搜索方發出搜索權限「Alice且 Beijing =NULL再次需要注意，「Beijing :NULL」實際上可以以私密密鑰η預處理為 Beijing :Hn (Beijing)。最終，很容易設計基於CKSS方案、可選方案1和可選方案2的混合方案。例如， BFT可以構造成一些域信息以明文形式揭示而其它域信息被盲化。再例如，BFT可以構造成 半結構化文獻，即既具有盲化域也具有虛擬域。以上描述僅給出了本發明的優選實施例，而並不是要以任何方式限制本發明。因 此，在本發明精神和原理內進行的任何修改、替換、改進等應該由本發明範圍所涵蓋。參考文獻列表[l]Amazon Simple Storage Service(Amazon S3)，http //aws. amazon. com/s3 ；[2]Googgle Health, https://www, google, com/health ；[3]Microsoft HealthVault, http://www, healthvault. com ；[4]Card details stolen in web hack, BBC news,http://news, bbc. co. uk/2/hi/technoloRy/7446871. stm [5]TJX theft tops 45. 6million card numbers, reported bySecurityFocus. com,http://www, securityfocus. com/news/11455 ；
[6]D. Song, D. Wagner, A. Perrig, Practical techniques for searches onencrypted data, in Proceedings of IEEE Symposium on Securityand Privacy' 00， pp.44-55，2000 ；[7]D. Boneh, G. D. Crescenzo, R. Ostrovsky, G. Persiano. Public KeyEncryption with Keyword Search. In Proceeding of EuroCrypt^ 04, LNCS 3027, pp.506-522,2004 ；[8]D. J. Park, K. Kim, P. J. Lee, Public Key Encryption withConjunctive Field Keyword Search. In Chae Hoon Lim and MotiYung，editors，Information Security Applicatiohs :5th InternationalWorkshop, WISA 2004， Jeju Island， Korea， August 23-25，LNCSvo 1. 3325，pp. 73—86. Springer-Verlag, 2004 ；[9]D. J. Park, J. Cha, P. J. Lee, Searchable Keyword-BasedEncryption, Report 2005/367, Cryptology ePrint Archive(2005)；[10]S. S. Μ. Chow,Exclusion-Intersection Encryption andItsApplication to Searchable Encryption. Report 2005/377, Cryptology ePrint Archive(2005).
權利要求
一種用於產生盲化索引表的設備，包括初始化單元，用於執行初始化過程以獲得秘密密鑰和公共密鑰；關鍵字預處理單元，用於利用秘密密鑰，根據關鍵字索引項，產生私密關鍵字；盲化單元，用於對於索引表的每一行隨機地選擇種子；利用公共密鑰和種子來產生匹配指示符；利用公共密鑰、秘密密鑰和種子來產生加密密鑰；利用加密密鑰來加密該行中的文件標識符項，以獲得加密的文件標識符；利用秘密密鑰和種子來盲化該行中的私密關鍵字，以獲得盲化索引集合；通過排列加密的文件標識符、匹配指示符和盲化索引集合，形成盲化索引表的一行。
2.根據權利要求1所述的設備，還包括 加密單元，用於針對索引表的每一行，用加密密鑰來加密與該行對應的文件，以獲得加密的文件數據。
3.根據權利要求1或2所述的設備，其中每一個關鍵字索引項屬於一個域，並且與一個盲化索引相對應。
4.根據權利要求1或2所述的設備，其中盲化索引表的每一行至少包括一個匹配指示符和一個盲化索引集合。
5.根據權利要求1或2所述的設備，其中索引表是正向索引表，域的名稱反映了屬於該域的索引項的公共屬性。
6.根據權利要求1或2所述的設備，其中索引表是轉換自正向索引表的倒排索引表，在該倒排索引表中，域的名稱被定義為正 向索引表的一個索引項，域的每一項為布爾型。
7.根據權利要求3所述的設備，其中 用另一個秘密密鑰來加密每個域的域名。
8.一種用於產生盲化索引表的方法，包括步驟 執行初始化過程以獲得秘密密鑰和公共密鑰； 對於索引表的每一行隨機地選擇種子；利用公共密鑰和種子來產生匹配指示符；利用公共密鑰、秘密密鑰和種子來產生加密密鑰；利用加密密鑰來加密該行中的文件標識符項，以獲得加密的文件標識符；利用秘密密鑰從該行中的關鍵字索引項中產生私密關鍵字；利用秘密密鑰和種子來盲化該行中的私密關鍵字，以獲得盲化索引集合；通過排列加密的文件標識符、匹配指示符和盲化索引集合，形成盲化索引表的一行。
9.根據權利要求8所述的方法，其中加密密鑰還用於加密與該行對應的文件，以獲得加密的文件數據。
10.根據權利要求8或9所述的方法，其中每一個關鍵字索引項屬於一個域，並且與一個盲化索引相對應。
11.根據權利要求8或9所述的方法，其中盲化索引表的每一行至少包括一個匹配指示符和一個盲化索引集合。
12.根據權利要求8或9所述的方法，其中索引表是正向索引表，域的名稱反映了屬於該域的索引項的公共屬性。
13.根據權利要求8或9所述的方法，其中索引表是轉換自正向索引表的倒排索引表，在該倒排索引表中，域的名稱被定義為正 向索引表的一個索引項，域的每一項為布爾型。
14.根據權利要求10所述的方法，其中用另一個秘密密鑰來加密每個域的域名。
15.一種在盲化索引表中執行聯合關鍵字搜索的設備，包括關鍵字預處理單元，用於通過使用秘密密鑰，針對所查詢的關鍵字集合中的每個關鍵 字產生私密關鍵字，所產生的私密關鍵字形成了與所查詢的關鍵字集合相對應的私密關鍵 字集合，私密關鍵字和所查詢的關鍵字的數量都是正整數；權限發布單元，用於利用公共密鑰、秘密密鑰和私密關鍵字集合來產生所查詢關鍵字 集合的搜索權限，搜索權限標識了所查詢關鍵字集合所屬的域，以及用於利用搜索權限和 秘密密鑰來產生解密權限；命中項匹配單元，如果盲化索引表中一行的匹配指示符與從屬於該行中的所標識的域 的各個索引項和搜索權限而聯合產生的值相同，則確定該行是命中行；解密單元，用於利用屬於命中行中的所標識的域的各個索引項和解密權限來產生每一 命中行的解密密鑰，以及用於利用解密密鑰來解密每一命中行的已加密文件標識符和已加 密文件數據，以獲得搜索結果。
16.根據權利要求15所述的設備，其中盲化索引表的每一行至少包括一個匹配指示符和一個盲化索引集合。
17.根據權利要求15或16所述的設備，其中索引表是正向索引表，域的名稱反映了屬於該域的索引項的公共屬性。
18.根據權利要求15或16所述的設備，其中索引表是轉換自正向索引表的倒排索引表，在該倒排索引表中，域的名稱被定義為正 向索引表的一個索引項，域的每一項為布爾型。
19.根據權利要求15或16所述的設備，還包括域加密單元，用於用另一個秘密密鑰來加密每個域的域名。
20.一種在盲化索引表中執行聯合關鍵字搜索的方法，包括步驟通過使用秘密密鑰，針對所查詢的關鍵字集合中的每個關鍵字產生私密關鍵字，所產 生的私密關鍵字形成了與所查詢的關鍵字集合相對應的私密關鍵字集合，私密關鍵字和所 查詢的關鍵字的數量都是正整數；利用公共密鑰、秘密密鑰和私密關鍵字集合來產生所查詢關鍵字集合的搜索權限，搜 索權限標識了所查詢關鍵字集合所屬的域；利用搜索權限和秘密密鑰來產生解密權限；如果盲化索引表中一行的匹配指示符與從屬於該行中的所標識的域的各個索引項和 搜索權限而聯合產生的值相同，則確定該行是命中行；利用屬於命中行中的所標識的域的各個索引項和解密權限來產生每一命中行的解密 密鑰；以及利用解密密鑰來解密每一命中行的已加密文件標識符和已加密文件數據，以獲得搜索結果。
21.根據權利要求20所述的方法，其中盲化索引表的每一行至少包括一個匹配指示符和一個盲化索引集合。
22.根據權利要求20或21所述的方法，其中索引表是正向索引表，域的名稱反映了屬於該域的索引項的公共屬性。
23.根據權利要求20或21所述的方法，其中索引表是轉換自正向索引表的倒排索引表，在該倒排索引表中，域的名稱被定義為正 向索引表的一個索引項，域的每一項為布爾型。
24.根據權利要求20或21所述的方法，其中 用另一個秘密密鑰來加密每個域的域名。
全文摘要
本發明提出了一種盲化索引表產生設備，包括初始化單元，用於執行初始化過程以獲得秘密密鑰和公共密鑰；關鍵字預處理單元，用於利用秘密密鑰，根據關鍵字索引項，產生私密關鍵字；盲化單元，用於對於索引表的每一行隨機地選擇種子；利用公共密鑰和種子來產生匹配指示符；利用公共密鑰、秘密密鑰和種子來產生加密密鑰；利用加密密鑰來加密該行中的文件標識符項，以獲得加密的文件標識符；利用秘密密鑰和種子來盲化該行中的私密關鍵字，以獲得盲化索引集合；通過排列加密的文件標識符、匹配指示符和盲化索引集合，形成盲化索引表的一行。本發明還提出了相應的盲化索引表產生方法。此外，本發明還提出了一種聯合關鍵字搜索方法和設備。
文檔編號G06F21/00GK101859306SQ200910132570
公開日2010年10月13日 申請日期2009年4月7日 優先權日2009年4月7日
發明者曾珂, 福島俊一 申請人:日電(中國)有限公司