[發明專利]一種面向云計算的多關鍵字可排序密文檢索方法

有效

• 申請號: 201711247475.0
• 申請日: 2017-12-01
• 公開（公告）號: CN108171071B
• 公開（公告）日: 2020-02-07
• 發明（設計）人: 許建;黃新宇;楊庚;陳燕俐;陳蕾;朱玉昊
• 申請（專利權）人: 吉林省外國企業服務有限公司
• 主分類號: G06F21/62
• 分類號: G06F21/62;G06F16/22;G06F16/2455
• 代理公司: 11543 北京八月瓜知識產權代理有限公司
• 代理人: 李斌

1.一種面向云計算的多關鍵字可排序密文檢索方法，其特征在于，包括以下步驟：

步驟1、根據數據集構建分組索引數據；

步驟2、利用B⁺樹對步驟1中的每組數據進行索引構建并加密，并和加密后的文檔集一起上傳到云服務器中；

步驟3、根據用戶輸入的查詢關鍵字，創建對應的查詢向量后，對查詢向量進行加密后形成陷門，將陷門上傳至云服務器；

步驟4、在云服務器中利用步驟3中的陷門在步驟2中的索引進行查詢計算，返回給用戶相關性最高的前k個加密文檔；

所述步驟1具體步驟如下：

步驟1-1：根據數據集構建明文文檔向量集F，并提取關鍵字集W，其中W＝{w₁，w₂，…，w_n}，n為關鍵字集大小，w_j表示第j個關鍵字，j＝1，2，…n；F＝{f₁，f₂，…，f_m}，m為數據集數量，f_i為數據集中第i個文檔對應的文檔向量，f_i的長度和W的長度一致，存儲的為關鍵字集W中的關鍵字在f_i所代表的文檔中的詞頻TF值，如果關鍵字沒有出現在f_i所代表的文檔中，則f_i中與該關鍵字所對應的位置存儲0；其中，i＝1，2，…m；

步驟1-2：根據W創建逆關鍵字文檔向量集O，其中O＝{op(w₁)，op(w₂)，…，op(w_n)}，op(w_j)表示包含w_j的TF值最高的前c×k個文檔向量集，c是正整數；

步驟1-3：對W進行分組得到分組后的關鍵字集WG，其中WG＝{WG₁，WG₂，…，WG_b}，WG_l為第l組的的關鍵字集，WG_l包含d個關鍵字，b為WG的組數且根據步驟1-2所得到的O對O中的向量進行相同的分組，得到分組后的逆關鍵字文檔向量集OG，OG＝{OG₁，OG₂，…，OG_b}，OG_l表示包含WG_l的文檔向量集，OG即為分組索引數據，其中，l＝1，2，…，b；

步驟2中，索引構建和加密的步驟如下：

步驟2-1：構建的索引I由兩部分組成，即I＝{IQ，IF}，IQ為B⁺樹索引集，IF為文檔數據集，通過步驟1-3得到OG后構建IQ＝{IQ₁，IQ₂，…，IQ_b}，IQ_l為WG_l對應的B⁺樹索引，其構建所需要的文檔向量由OG_l提供；用N_l表示IQ_l的一個節點，其存儲的關鍵字結構為<fid，children[t]，inf〉，fid為文檔標識符，children[t]為指向N_l的第t個孩子節點的指針，t為B⁺樹的階數，inf是存儲TF值的d維數據向量；如果N_l為葉節點，則fid和文檔標識一致，inf存儲WG_l在fid對應文檔中的TF值；否則fid為空，用key[v]表示節點N_l存儲的第v個關鍵字信息，則第v個關鍵字的inf的第c維存儲的數據，也就是key[v].inf[c]由如下公式計算：

key[v].inf[c]＝

max{N_l.children[v].key[1].inf[c]，…，N_l.children[v].key[m].inf[c]}+|R|％max{N_l.children[v].key[1].inf[c]，…，N_l.children[v].key[m].inf[c]}；

其中R為隨機產生的數值，N_l.children[v].key[v].inf[c]表示N_l的第v個孩子節點存儲的第v個關鍵字內inf的第c維的數據；其中，v＝1，2，…，m，c＝1，2，…，d；

步驟2-2：根據F構建IF＝{IF₁，IF₂，…，IF_m}，其中IF_i基于f_i構建，是f_i的一種向量表達形式，IF_i＝<fid，inf₁，inf₂，…，inf_b>，其中inf_l是長度為d的向量，代表第l組的關鍵字在f_i中的TF值，第l組的第c個關鍵字在f_i中的TF值用inf_l[c]表示；

步驟2-3：遍歷步驟2-1得到的IQ，將IQ_l每個節點存儲關鍵字的inf的每維增加α+1位，α為隨機正整數，每維的第d+p位隨機存儲0或1，第d+α+1位存儲1，p＝1，2，…α；遍歷步驟2-2得到的IF，將IF_i每維增加β位，β為隨機正整數，再增加一維，其位數為β+α+1，每維的擴展位隨機存儲0或1，前b維的所有d+g位存儲的值相同，第b+1維的β+α+1位值為1，g＝1，2，…β；

步驟2-4：構造秘鑰ek₁和ek₂，ek₁＝{E₁，Z₁，Z₂}，ek₂＝{E₂，Z₃，Z₄}，E₁為b維向量，其中E₁中的第l維數據為d+α+1位，每位隨機存儲0或1；Z₁和Z₂一樣，包含b個(d+α+1)×(d+α+1)階可逆矩陣；E₂為(b+1)維的向量，為E₂中的第l維數據，其中E₂的前b維為d+β位，第b+1維為α+β+1位，每位隨機存儲0或1；Z₃和Z₄一樣，包含b個(d+β)×(d+β)階可逆矩陣和一個(β+α+1)×(β+α+1)階可逆矩陣；

步驟2-5：根據步驟2-4得到的秘鑰ek₁對IQ加密后變換為新的數據IQ′和IQ″，也就是將每個IQ_l分為IQ′_l和IQ″_l兩個新的數據，用E_1，l[s]表示E₁第l維的第s位存儲的數據，s＝1，2，…，d+α+1，IQ_l[s]以及IQ′_l[s]和IQ″_l[s]分別表示原數據的第l維的第s位和加密后得到的兩個新數據的第l維的第s位存儲的數據；如果E_1，l[s]＝0，IQ′_l[s]＝IQ″_l[s]＝IQ_l[s]；如果E_1，l[s]＝1，IQ′_l[s]+IQ″_l[s]＝IQ_l[s]；則加密后的IQ為E_IQ，E_IQ用下式表達：

其中和表示Z₁和Z₂的第l個矩陣的轉置，用ek₂對IF進行加密，得到加密后的IF為E_IF，ek₂對IF進行加密的過程同IQ加密；最后將加密后的IF和IQ，也就是E_IF和E_IQ上傳至云服務器；

步驟3具體步驟如下：

步驟3-1：根據用戶輸入的查詢關鍵字，創建對應的查詢向量，查詢向量Q由兩部分組成，即Q＝{QQ，QF}，其中QQ為b維向量集，用于在IQ上進行檢索，QF同樣為b維向量集，并且用于和IF計算求得文檔向量和查詢向量最終的相關性分數；首先構建QQ＝{QQ₁，QQ₂，…，QQ_b}，QQ_l代表在QQ中第l維存儲的向量數據，QQ_l[c]表示第l維的第c位存儲的數據，QQ_l[c]與WG_l，c相對應，如果WG_l，c在查詢關鍵字集W_q中存在，則QQ_l[c]存儲WG_l，c的逆文檔頻率IDF值，否則存儲0；如果QQ_l的所有位存儲的都為0，則將QQ_l設置為空；QF和QQ相等；

步驟3-2：將QQ每維數據擴展α+1位，前α位存儲隨機數γ_l，p，第α+1位存儲另一個隨機數δ_l；將每維的前d+α位放大ε倍；將QF增加長度為β+α+1位的一維，QF的前b維每維增加β位，限制條件為QF_l[d+g]表示QF的第l維的第d+g位存儲的數據，QF_b+1[g]表示QF的第b+1維的第g位存儲的數據；QF的第b+1維的β+p位的值為隨機數γ_p，第β+α+1的值為隨機正數δ；QF的第b+1維除最后一位每位放大ε倍；

步驟3-3：通過步驟2-4得到的ek₁對Q進行加密，將QQ加密后得到新的數據QQ′和QQ″，用QQ′_l[s]和QQ″_l[s]表示兩個新數據QQ′和QQ″第l維的第s位存儲的數據，QQ_l[s]表示數據QQ第l維的第s位存儲的數據；如果E_1，l[s]＝0，則QQ′_l[s]+QQ″_l[s]＝QQ_l[s]；如果E_1，l[s]＝1，則QQ′_l[s]＝QQ″_l[s]＝QQl[s]；最后，加密后的QQ為E_QQ，E_QQ如下：

其中QQ′_l和QQ″_l表示QQ′和QQ″第l維的數據，和表示Z₁和Z₂的第l個矩陣的逆，QQ_l！＝null表示QQ第l維的數據不為空，對QF的加密和QQ的步驟過程一樣，加密后的QF為E_QF，最后將加密后的QQ和QF，也就是E_QQ和E_QF都上傳至云服務器；

步驟4具體如下：

通過E_IQ和E_QQ之間的運算，獲得每組相關性最高的前h個加密文檔，形成返回結果集；通過E_IF和E_QF運算獲得兩者之間的相關性分數，然后將返回結果集進行二次排序，最終返回相關性最高的前k個加密文檔給用戶。

2.根據權利要求1所述的一種面向云計算的多關鍵字可排序密文檢索方法，其特征在于，步驟4具體如下：

步驟4-1：當云服務器接收到E_QQ后，用E_QQ在E_IQ上進行計算并返回具有b組結果的結果集Rlist，Rlist＝{Rlist₁，Rlist₂，…Rlist_b，}，其中Rlist_l為第l組索引檢索后所返回的結果，每組結果包含h個文檔向量，用和表示QQ和IQ第l維的加密數據，則和節點中第v個關鍵字的相關性分數用如下公式計算：

其中N_l.key[v]表示節點N_l存儲的第v個關鍵字，N_l.key[v].inf′和N_l.key[v].inf″表示對關鍵字的inf加密后形成的兩個新的向量，Score(QQ_l，N_l.key[v])表示QQ_l和N_l.key[v]之間的相關性分數；采用深度遍歷將遍歷到的葉子節點存儲的關鍵字信息放入Rlist_l中，如果Rlist_l的信息數量超過h，則對后面要遍歷的節點進行分數判斷，如果節點關鍵字分數大于Rlist_l中最低分，繼續遍歷，否則這個關鍵字所對應的孩子節點不予遍歷；

步驟4-2：將步驟4-1中得到的Rlist進行去除重復元素操作，利用E_QF和對結果集Rlist中的數據進行相關性分數計算，其中表示為IF_i加密后的形式，計算公式如下：

和表示對IF_i的第l維向量加密后獲得的兩個新向量，和表示對QF的第l維向量加密后獲得的兩個新向量，Score(QF，IF_i)表示QF和IF_i的相關性分數，表示E_QF的第l維不為空，通過上述公式得到分數后，返回給用戶分數最高的前k個文檔。