云環(huán)境下基于字形相似度的密文模糊檢索方案

黃保華 袁鴻 黃丕榮 程琪

摘? ?要：中文關鍵詞的模糊檢索可以基于字形、字音、字義等不同方面，針對目前相關研究主要基于拼音相似度進行的局限性，文章提出了云環(huán)境下基于漢字字形相似度的密文模糊檢索方案。方案基于漢字字形相似性，通過歐幾里得距離來計算漢字的相似度，基于布隆過濾器和p-穩(wěn)定分布的局部敏感哈希函數(shù)構建索引，通過安全陷門和安全索引內(nèi)積的方式，實現(xiàn)了漢字多關鍵字的密文模糊檢索。實驗證明，方案在保證密文模糊檢索安全性的同時，具有較低的時間代價和空間代價。

關鍵詞：字形相似度;云環(huán)境;局部敏感哈希;可搜索加密;模糊檢索

中圖分類號： TP391? ? ? ? ? 文獻標識碼：A

1 引言

隨著云計算的普及，為節(jié)約數(shù)據(jù)存儲成本和增加訪問便捷性，大量數(shù)據(jù)被存儲于云服務器，其中不乏涉密的非結構化文檔，而這些文檔存儲之前需先進行加密。隨時間流逝，數(shù)據(jù)規(guī)模膨脹，對于大量加密數(shù)據(jù)的檢索成為問題，可搜索加密（Searchable Encryption，SE）應運而生[1]。

經(jīng)典SE通過關鍵字精確檢索密文數(shù)據(jù)，但檢索易出現(xiàn)格式錯誤或檢索結果與查詢目標不一致，針對這些問題，Jin Li提出了模糊檢索，基于編輯距離構建模糊詞集合，實現(xiàn)模糊檢索[2]。Wang B提出適用于多個關鍵詞的密文模糊檢索，使用局部敏感哈希（Locality Sensitive Hashing，LSH）函數(shù)和布隆過濾器構造索引，大幅地提高了檢索效率[3]。

漢字構詞為多個單字組成，與英文有明顯界限的構詞方式不同。根據(jù)漢字構詞特性，Ding W利用TF-IDF實現(xiàn)漢字關鍵詞的自動提煉，并基于拼音構建模糊詞集進行匹配[4]。陳何峰根據(jù)英文關鍵詞構建模糊詞集，設計了新的編輯距離衡量方法用于構建模糊集合[5]。方忠進根據(jù)漢字讀音的特點建立音近模糊詞集合，并用英文和中文實現(xiàn)了關鍵詞的同義詞構建，實現(xiàn)中文模糊音和同義關鍵詞的檢索[6]。

漢字除了讀音外還有含義、字形等差異，不能用同樣的方式進行度量。Cao J采用三種不同的編輯距離衡量方式，通過多個精準匹配進行模糊匹配[7]。羅文俊提出以同義詞集合建立擴展索引實現(xiàn)對同義詞的檢索[8]。

上述這些方案對中文關鍵詞的密文模糊檢索，主要是基于漢字拼音相似進行，但在中文漢字的構成中，字形和字音都是漢字的構成基礎。人們在日常生活中遇見生字時，習慣使用字形相近的漢字進行代替，如江新所述，在漢字學習中，相近字形引起的錯誤多于相近字音引起的錯誤[9]。所以，在檢索中基于字形相似度的模糊檢索十分必要，王逍翔[10]提出了一種在明文狀態(tài)下通過點陣對字形進行編碼的關鍵字校檢方案，該方案實現(xiàn)的是明文下的關鍵字校檢，存在編碼方式過于復雜，依賴于圖形圖像處理等缺陷。本文提出了一種云環(huán)境下中文多關鍵詞密文模糊檢索方案。方案基于字形相似度進行搜索，字形編碼簡便，支持多個中文關鍵詞同時進行檢索，且不需要預先構建模糊詞集。

2 相關工作

2.1 布隆過濾器

1970年Howard Bloom提出一種二進制向量數(shù)據(jù)結構—布隆過濾器（Bloom Filter），它擁有優(yōu)秀的時間和空間效率，可用來判定一個元素是否在集合中[11]。

Bloomfilter判定元素是否在集合的思路是采取哈希函數(shù)的方法，先構建一個初始值為0、長度為m的陣列，再將元素映射到布隆過濾器進行判定。該元素在集合內(nèi)，則該點為1，否則為0。布隆過濾器工作原理如圖1所示，有集合S={a1，a2，a3，…，ak}，布隆過濾器使用l個獨立分布的哈希函數(shù){h1（·），h2（·），h3（·），……h(huán)l（·）}，將ai映射到對應的比特位，即把數(shù)組h（ai）位置的值為1。如果對應位置已有映射，即對應位置值為1，則不影響前面映射的效果[11]。

2.2 歐氏距離

歐幾里得度量（Euclidean Metric，也稱歐氏距離）常用來定義距離，指兩個點在n維空間中的真實距離，或向量的自然長度（即該點到原點距離），在二維和三維空間中就表示兩點之間的直觀空間距離[12]。

n維空間中，每個點都有n個坐標，表示為x[1]，x[2]，x[3]，……，x[n]，n維空間中任兩個點x1、x2之間的歐式距離計算方法如公式（1）所示。

（1）

2.3 p-穩(wěn)定分布的歐氏局部敏感哈希

LSH是一類滿足條件的函數(shù)，條件為：在原始數(shù)據(jù)具有很高相似度的情況下，使用此哈希函數(shù)哈希后仍保持高相似度;若它們本來不具相似度，對它們哈希后仍不相似[13]。

歐氏局部敏感哈希（Exact Euclidean Locality Sensitive Hashing，E2LSH）是LSH在歐氏空間的一種隨機化實現(xiàn)方法[13]。E2LSH基本原理：利用基于P-穩(wěn)定的性質(zhì)使用LSH將高維數(shù)據(jù)降維，并保證降維后的高維數(shù)據(jù)依然滿足LSH的特性。

p-穩(wěn)定分布的哈希函數(shù)族可用來對高維特征向量進行處理，在其將高維數(shù)據(jù)降維的同時，能保持數(shù)據(jù)間距離穩(wěn)定[14]。具體方法：隨機構建一個d維向量a，如果a中每個元素的生成都滿足p-穩(wěn)定分布，那么對于d維特征向量v，依據(jù)穩(wěn)定分布特性，隨機變量a·v和（|vi|p）1/p·X分布相同（其中X為隨機變量且滿足p-穩(wěn)定分布），所以可以用a·v來降維向量v，還能用來計算||v||p，易看出這是一個可以線性組合的過程，可以認為，a（v1 -v2） = a.v1–a.v2[14]，于是構造計算公式為：

（2）

其中，是向下取整操作，v為需要降維的數(shù)據(jù)點，向量 a滿足p-穩(wěn)定分布，r為大于0的常數(shù)，b是均勻分布在[0，r]上的實數(shù)。

2.4 五筆字型輸入法

五筆字型輸入法是一種可以將每個漢字表示為不超過四字符的編碼串的中文形碼輸入法。其特點是在輸入時基本不用選字，省了找字的時間。與拼音輸入法類比，其不會受到方言、發(fā)音不規(guī)范等問題的干擾，即使不認識該字也可以打出想要的字。五筆字型輸入法使用A-Y的25個英文字母（Z為“萬能學習鍵”可用于代替未知字根，作為通配符使用）對漢字實行編碼，其字形編碼拆解方式稱為字根，字根表如圖2所示。

3 預備知識

3.1 系統(tǒng)模型

圖3是本方案的系統(tǒng)模型，系統(tǒng)由云服務器，數(shù)據(jù)擁有者和授權用戶三個部分組成。數(shù)據(jù)擁有者使用明文文檔生成安全索引并對明文文檔執(zhí)行加密，再將安全索引與密文文檔一同上傳到云服務器，同時可以下發(fā)密鑰給其他云服務器用戶。獲得數(shù)據(jù)擁有者下發(fā)的密鑰的云服務器用戶稱為授權用戶。授權用戶可在本地構建安全陷門發(fā)送到云服務器。云服務器接收到安全陷門之后對加密索引執(zhí)行檢索，并把檢索到的密文文檔返回給授權用戶。授權用戶使用擁有者下發(fā)的密鑰解密密文文檔，獲得明文文檔。

3.2 符號定義

F：明文文檔集合;

D：加密后的密文文檔集合;

W：從F分詞出的關鍵詞集合;

EIndex：生成的安全索引;

K：密鑰，用于加密、解密、構建安全索引和構建安全陷門;

Q：查詢請求;

T：安全陷門，用于檢索;

R：搜索結果，為文檔集合。

4 云環(huán)境下密文多關鍵字模糊檢索方案

4.1基于字形相似度

漢字分為四類：象形字、形聲字、會意字、指事字。漢字中的85%為形聲字，所以中國人在認識漢字的過程中，遇到生字時會將字的一部分的讀音作為整個字的讀音。然而漢字中又有形近字，部分形近字字形相似，讀音卻有巨大差距，如荀（xun）與茍（gou）、治（zhi）與冶（ye）等。

每個漢字都有其獨特字形，用五筆字型輸入法的思維可將每個漢字拆解成不超過四個英文字符的字形編碼。將漢字轉(zhuǎn)換為字形編碼后可通過字形相似度衡量漢字之間的距離。這具備兩個優(yōu)點：一是細化編輯距離，提高模糊檢索的精確度;二是編碼串可以轉(zhuǎn)換為高維向量，從而通過E2LSH將編輯距離轉(zhuǎn)化為歐式距離用于生成安全索引和安全陷門。

4.2 算法實現(xiàn)

4.2.1 密鑰生成

首先根據(jù)安全參數(shù)m生成密鑰sk，數(shù)據(jù)擁有者進行初始化操作，獲得密鑰K，其過程如算法1所示。

算法1：密鑰生成算法

輸入：安全參數(shù)m;

輸出：密鑰K;

1）生成對稱加密所需的密鑰sk;

2）隨機生成L個E2LSH所需要的密鑰對hk = { （ a1，b1 ） ，（ a2，b2 ） ，…，（an，bn） };

3）隨機構建一個m * m的可逆矩陣M1和M2;

4）Return K =（sk，hk，M1，M2）。

4.2.2 安全索引生成

為保證信息安全，提取中文關鍵詞和構建安全索引過程在本地進行。安全索引構建具體步驟：（1）對文件實行分詞處理，提煉中文關鍵詞，并將中文關鍵詞轉(zhuǎn)換為字形編碼串，構建二維向量vi;（2）構建與文件數(shù)相等的布隆過濾器，使每個文件對應一個Bloomfilter，使用E2LSH將vi映射到對應Bloomfilter，獲得索引向量;（3）使用可逆矩陣M1、M2對索引向量進行加密，獲得安全索引。

算法描述如算法2所示。

算法2：

輸入：明文文檔集合F;

輸出：安全索引EIndex;

1）for ?fi∈F? do;

2）Bi = 0? //構造m位的布隆過濾器;

3）get W ={w1，w2，…，wn} for fi? ? //分詞;

4）forWi W? do;

5）? wi = “c1c2……ck”//將關鍵詞wi轉(zhuǎn)換成五筆字形編碼（大寫）;

6）? wi = {c1c2，c2c3，……，ck-1ck}//以wi中相鄰的兩編碼字符為一組;

7）? vi = 0? //構造一個大小為26x26的向量;

8）? for j = 0 to k-1 do;

9）? ? ?a =（ the ASCII of? cj）-65;

10）? ? b =（ the ASCII of? cj+1）-65;

11）? ? vi [a] [b] = 1;

12）? end;

13）? x1 =ha1，b1（v1），x2=ha2，b2（v2）…xl=hal，hbl（vl）;

14）? Bi[x1] = 1 ，Bi[X2]=1，……，Bi[xl]=1;? ?//x映射至相應布隆過濾器;

15）? Bi= the first half? of B，B=the second half of B//Bi分為前后相等兩部分;

16）? Ii? = M1Bi，Ii = M2Bi，Ii= {Ii，Ii};

17）end;

18）return? EIndex= {I1，I2，……，In}。

構建安全陷門與構建安全索引過程相同，所以安全陷門的安全性與安全索引安全性能相同，在陷門的生成過程中保證了信息安全。

5.2 性能測試

本文方案性能測試的實驗環(huán)境：操作系統(tǒng)Windows8.1（64位），CPU為Intel（R）Core（TM）i5-3230M（2.60GHz），內(nèi)存大小8GB，編程語言為Java。使用500篇中文期刊文獻作為數(shù)據(jù)文件，大小約1GB，從文獻標題提取關鍵詞共6，437個關鍵詞。

5.2.1 檢索效率

本文方案與文獻[6]提出的基于關鍵詞的加密云數(shù)據(jù)模糊搜索時間做對比，結果如圖7所示。

從圖7可看出，在進行關鍵詞的模糊檢索時，本文方案由于不需要與模糊詞集進行對比，相對于文獻[6]的方案在檢索效率上有較大提高。隨著關鍵詞數(shù)量的增加，本文方案檢索時間也呈遞增趨勢，但其趨勢平緩，適用于云存儲中大量關鍵詞的模糊檢索。

5.2.2 空間效率

設密文文檔數(shù)為N，關鍵詞數(shù)量為M，本文方案所需存儲空間僅為密文文檔所需空間以及安全索引所需空間，且安全索引由固定大小的布隆過濾器所構建，可設其所需存儲大小為常數(shù)k，所以本文方案所需存儲空間大小為O（kN），僅與文件數(shù)量呈線性相關。文獻[6]方案中，需要額外構建模糊詞集，模糊詞集大小與編輯距離相關，設編輯距離為d，其模糊詞集的大小與編輯距離以及關鍵詞數(shù)量均相關，所以文獻[6]方案的空間代價為O（dMN），而且其關鍵詞數(shù)量與文檔數(shù)成正比關系，其空間代價可表示為O（N2）。所以在空間效率方面，本文方案優(yōu)于文獻[6]方案。

6 結束語

本文針對云環(huán)境下密文模糊檢索問題，提出了一種基于字形相似度的密文模糊檢索方案，實驗表明該方案具有較理想的效果。本文方案與基于拼音相似度的方案相比，提出了一種新的模糊檢索思路，將漢字轉(zhuǎn)換成字形編碼串，用字形編碼串相似度來衡量字形相似度。同時，使用歐氏局部敏感哈希來實現(xiàn)編輯距離的量化，再利用布隆過濾器構建安全索引和安全陷門，減少空間使用的同時大幅地提高檢索效率，且能很好地保證信息安全。未來將考慮采用分層次的布隆過濾樹對方案進行改進，進一步提高方案的檢索效率。

基金項目：

1.國家自然科學基金項目（項目編號：61962005）;

2.國家重點研發(fā)計劃課題（項目編號：2018YFB1404404）。

參考文獻

[1] Song D. Practical Techniques for Searches on Encrypted Data[C]// IEEE Security and Privacy Symposium， May. IEEE， 2000.

[2] Jin Li， Qian Wang， Cong Wang， et al. Fuzzy Keyword Search over Encrypted Data in Cloud Computing[C]// IEEE Conference on Computer Communications， IEEE， 2010.

[3] Wang B ， Yu S ， Lou W ， et al. Privacy-Preserving Multi-Keyword Fuzzy Search over Encrypted Data in the Cloud[C]// IEEE Conference on Computer Communications. IEEE， 2014.

[4] Ding W ，? Liu Y ，? Zhang J . Chinese-keyword Fuzzy Search and Extraction over Encrypted Patent Documents[C]// International Joint Conference on Knowledge Discovery. IEEE， 2016.

[5] 陳何峰，林柏鋼，楊旸，等.基于密文的中文關鍵詞模糊搜索方案[J].信息網(wǎng)絡安全，2014（07）：75-80.

[6] 方忠進，周舒，夏志華.基于關鍵詞的加密云數(shù)據(jù)模糊搜索策略研究[J].計算機科學，2015， 042（003）：136-139，173.

[7] Cao J ， Wu X ， Xia Y ， et al. Pinyin-indexed method for approximate matching in Chinese[J]. Qinghua Daxue Xuebao/journal of Tsinghua University， 2009， 49：1328-1332.

[8] 羅文俊，孫志蔚.基于simhash的密文同義詞檢索方法[J].武漢大學學報：理學版，2014，60（5）.

[9] 江新，柳燕梅.拼音文字背景的外國學生漢字書寫錯誤研究[J].世界漢語教學，2004（01）：6+62-72.

[10] 王逍翔，邵玉斌，龍華.基于形近字識別的互聯(lián)網(wǎng)搜索關鍵字校驗[C].第六屆云南省科協(xié)學術年會暨紅河流域發(fā)展論壇論， 2016：194-200.

[11] Burton H Bloom. Space/time trade-offs in hash coding with allowable errors[J]. Communications of the ACM， 1970， 12（7）：422-426.

[12] 賈楠，付曉東，黃袁，等.基于樹編輯距離的工作流距離度量方法[J].計算機應用，2012，32（012）：3529-3533.

[13] M Datar， N Immorlica， P Indyk， et al. Locality sensitive hashing scheme based on p-stable distributions[C]. // The twentieth annual symposium on computational geometry， 2004， 34（2）：253--262.

[14] 史世澤.局部敏感哈希算法的研究[D].西安：西安電子科技大學.2013.

作者簡介：

黃保華（1973-），男，漢族，貴州盤縣人，華中科技大學，博士，廣西大學，副教授;主要研究方向和關注領域：數(shù)據(jù)庫安全、車聯(lián)網(wǎng)安全、密文信息處理。

袁鴻（1995-），男，漢族，湖南邵陽人，廣西大學，碩士;主要研究方向和關注領域：密文信息處理。

黃丕榮（1993-），男，壯族，廣西崇左人，廣西大學，碩士;主要研究方向和關注領域：密文信息處理。

程琪（1994-），男，漢族，廣西岑溪人，廣西大學，碩士;主要研究方向和關注領域：密文信息處理。