王 萊 周騰達(dá) 王正飛 洪佳明

(廣州中醫(yī)藥大學(xué)醫(yī)學(xué)信息工程學(xué)院 廣東 廣州 510006)

0 引 言

電子病歷中包含了許多隱私信息，包括病人的個人信息、性別、年齡、身份證號等，身體情況中單是病史就包括了既往史、現(xiàn)病史、月經(jīng)史、婚育史等多項內(nèi)容。如何保護(hù)這些隱私信息在云服務(wù)(或者外包)環(huán)境中不被泄露變得非常重要[1]，進(jìn)一步地，我們還常常需要進(jìn)行信息檢索。

當(dāng)前大數(shù)據(jù)發(fā)展如火如荼，電子病歷數(shù)據(jù)越來越冗雜，醫(yī)療機(jī)構(gòu)信息化建設(shè)必須加快。2019年1月，國務(wù)院辦公廳下發(fā)《關(guān)于加強(qiáng)三級公立醫(yī)院績效考核工作的意見》(國辦發(fā)〔2019〕4號)，要求三級公立醫(yī)院要加強(qiáng)以電子病歷為核心的醫(yī)院信息化建設(shè)，將“電子病歷應(yīng)用功能水平分級”指標(biāo)列為國家監(jiān)測指標(biāo)。按照相關(guān)規(guī)定，2019年8月底前，各地衛(wèi)健委須組織三級公立醫(yī)院完成電子病歷的編碼和術(shù)語轉(zhuǎn)換工作，將全面啟用統(tǒng)一的疾病分類編碼、手術(shù)操作編碼、醫(yī)學(xué)名詞術(shù)語。

加密是電子病歷數(shù)據(jù)的基本要求，有效搜索則是利用與處理電子病歷數(shù)據(jù)的基礎(chǔ)技術(shù)。但由于隱私信息加密后失去了原有語義，如何對密文進(jìn)行準(zhǔn)確和快速查詢成為關(guān)鍵問題。許多研究人員都對密文查詢進(jìn)了研究，Song等[2]首次提出了對密文進(jìn)行搜索，用戶采用對稱加密算法完成加密后發(fā)送給服務(wù)器，查詢時，用戶采用哈希函數(shù)建立陷門(trapdoor)并發(fā)送給服務(wù)器，服務(wù)器根據(jù)陷門完成搜索后，返回密文給用戶。與Song等類似，Boneh利用哈希函數(shù)和雙線性對映射生成密文，用戶關(guān)鍵詞映射為搜索憑證發(fā)送給服務(wù)器完成對密文的搜索，該方法為非確定性加密，服務(wù)器端無法根據(jù)密文判斷其中包含的關(guān)鍵詞。但這些方法都需要對所有文檔進(jìn)行搜索，搜索效率低下。Wang等[3]根據(jù)關(guān)鍵詞的出現(xiàn)頻率先進(jìn)行排序，實現(xiàn)密文的搜索，但排序會在一定程度上影響安全性[4]。

針對密文搜索效率低下的問題，Goh[5]提出一種基于布隆過濾的z-index方法，該方法建立在布隆過濾器的基礎(chǔ)上，為每個文檔增加對應(yīng)的BF數(shù)據(jù)結(jié)構(gòu)。該文定義和實施了四個函數(shù)：Keygen(s)，Trapdoor(Kpriv,w)，BuildIndex(D,Kpriv)，SearchIndex(Tw,ID)。其中：Keygen()用來生成包含多個子密鑰的主密鑰；Trapdoor()用來生成關(guān)鍵詞對應(yīng)的陷門；BuildIndex()用來為每個文檔構(gòu)建索引；SearchIndex()用來根據(jù)用戶提交的陷門完成對加密文檔查詢。該方法的主要優(yōu)點是能夠利用哈希函數(shù)快速計算的特點，迅速從密文中直接查詢到匹配的文檔。但是該方法需要對文檔中所有布隆過濾器進(jìn)行遍歷，才能搜索到匹配的文檔，極大地影響了系統(tǒng)的性能，特別是在大規(guī)模數(shù)據(jù)處理場景中不適用。

Demertzis等[6]對于SE(Searchable Encryption)領(lǐng)域十分關(guān)注，提出了兩種在保證安全性的前提下提升工作效率的方案，其具有可調(diào)整局域性和線性空間，提升了讀取效率和減少了端到端的搜索時間，并可以調(diào)優(yōu)以實現(xiàn)空間、讀取效率、位置、并行性和通信開銷之間的權(quán)衡。Demertzis等[7]試圖在效率和安全性之間進(jìn)行權(quán)衡的另一個方案則基于可搜索對稱加密(SSE)技術(shù)，主要用于關(guān)鍵字搜索，使用了樹狀索引的范圍覆蓋技術(shù)將范圍搜索簡化為多關(guān)鍵詞搜索。

本文在z-index的基礎(chǔ)上對布隆過濾器BF進(jìn)行改進(jìn)，把布隆過濾器組織成倒排文件，并建立B+樹，充分利用了布隆過濾器的過濾效率高[8]和倒排索引的全文快速查詢特點，從而提高電子病歷密文查詢性能。

1 電子病歷密文搜索模型

為了支持對加密電子病歷的密文查詢，設(shè)計了電子病歷密文搜索模型，如圖1所示。數(shù)據(jù)擁有者根據(jù)電子病歷文檔中所包含的關(guān)鍵詞，為其建立索引，然后把加密后的電子病歷和其對應(yīng)索引提交給云服務(wù)器；用戶查詢電子病歷時，提交陷門(加密后的關(guān)鍵詞)給云服務(wù)器，云服務(wù)器根據(jù)陷門在索引中進(jìn)行查詢，在不解密情況下找到匹配的電子病歷密文，并把密文返回給用戶，用戶收到密文后再解密。

圖1 電子病歷密文搜索模型

這種模型很好地保護(hù)了用戶隱私信息安全。一方面，由于用戶只是提交了陷門，用戶的查詢關(guān)鍵詞不會暴露給云服務(wù)器，所以云服務(wù)器無法直接獲得用戶的查詢請求。另一方面，云服務(wù)器在查詢過程中，使用密文索引直接進(jìn)行查詢，無須對密文電子病歷進(jìn)行解密，更好地保護(hù)了密文電子病歷隱私信息的安全。在該模型中，為進(jìn)一步提高對索引檢索的效率，本文把布隆過濾器組織為B+樹，檢索效率從原來的O(n)提高到O(logmn)。

2 方法設(shè)計

2.1 布隆過濾器創(chuàng)建

布隆過濾器(Bloom Filter，BF)起源于1970年，由Burton Bloom首次提出，是一種高時空效率的數(shù)據(jù)結(jié)構(gòu)，由一個一定長度(比如128 bit位)的二進(jìn)制向量和一組相互獨立的哈希函數(shù)組成[9]。布隆過濾器可以用來檢查一個元素是否出現(xiàn)在一個數(shù)據(jù)集合中，具有很好的過濾效果。

對于特定關(guān)鍵詞W，建立布隆過濾器過程如下：

(1) 使用密鑰生成算法Keygen(s)：給定一個安全參數(shù)s，生成主密鑰Kpriv=(k1,k2,…,kr)←R{0,1}sr，其中主密鑰包含r個子密鑰，每個子密鑰的長度為Sbit位。

(2) 使用陷門生成算法Trapdoor(Kpriv,w)：給定主密鑰Kpriv和查詢關(guān)鍵詞w，生成陷門Tw=(f(w,k1),f(w,k2)，…,f(w,kr))∈{0,1}sr，其中f是偽隨機(jī)函數(shù)，本文使用哈希函數(shù)HMAC-SHA1作為偽隨機(jī)函數(shù)：{0,1}*×{0,1}160→{0,1}160，允許處理任意長度關(guān)鍵詞。對于每個關(guān)鍵詞w，進(jìn)行r次哈希處理，每次使用一個子密鑰kr，每次會產(chǎn)生一個陷門值。產(chǎn)生的陷門要保存好，因為在后續(xù)的索引構(gòu)建和用戶查詢過程中將會繼續(xù)使用。

例：電子病歷中的主訴文檔包含關(guān)鍵詞“糖尿病”，假定布隆過濾器長度為128 bit。(1) 生成主密鑰Kpriv=(k1,k2，k3,k4)；(2) 計算“糖尿病”的陷門和編碼詞，x1=f(“糖尿病”,k1),x2=f(“糖尿病”,k2),x3=f(“糖尿病”,k3),x4=f(“糖尿病”,k4)),c1=f(Did‖x1),c2=f(Did‖x1),c3=f(Did‖x1),c4=f(Did‖x4)；(3) 對編碼詞c1,c2,…,c4進(jìn)行哈希計算pr=Hr(cr)，得到p1=79,p2=25,p3=48,p4=103,則布隆過濾器相應(yīng)的位置“1”，如圖2所示，在布隆過濾器的第25、48、79和103位置為1，其余為0。

圖2 布隆過濾器

2.2 基于布隆過濾器的倒排索引創(chuàng)建(BF_II)

為電子病歷中所有的關(guān)鍵詞建立好布隆過濾器后，需要構(gòu)建基于布隆過濾器的倒排索引，如圖3虛線部分所示。倒排文件中包含倒排列表和詞典兩部分。倒排列表包含某一關(guān)鍵詞的所有文檔的地址集合，與傳統(tǒng)倒排文件相同；詞典包含BFi和指針pi，詞典中用BFi代替了傳統(tǒng)的關(guān)鍵詞。

圖3 基于B+樹的倒排索引構(gòu)建

需要注意的是，本文中BF與z-index創(chuàng)建BF有所區(qū)別，z-index為每份電子病歷建立布隆過濾器，而本文通過分詞器從電子病歷提取關(guān)鍵詞，然后為每個關(guān)鍵詞構(gòu)建布隆過濾器，并代替倒排索引中的詞典。在建立布隆過濾器的過程中，把包含同一個關(guān)鍵詞的電子病歷放到同一個集合中。如果多份電子病歷中都包含了關(guān)鍵詞“高血糖”，那么就將這些電子病歷的地址放到同一個集合中，其他的關(guān)鍵詞重復(fù)上述步驟，最后得到本文的倒排索引。此外，可將BF按照頻次高低進(jìn)行排序，進(jìn)一步提高查詢效率。

將布隆過濾器與倒排索引結(jié)合起來，一方面充分利用了布隆過濾器的高空間過濾性和倒排索引的高效文本搜索性能；另一方面將明文的關(guān)鍵詞轉(zhuǎn)換為布隆過濾器，還能保護(hù)用戶查詢請求的安全和云服務(wù)器中數(shù)據(jù)的安全。

2.3 基于B+樹和布隆過濾器的倒排索引(B_BF_II)

利用布隆過濾器查詢時，由于詞典中的詞表BF是有序的，可以采用二分查詢算法，查詢代價為O(log2n)，但是在大數(shù)據(jù)環(huán)境中，倒排索引空間開銷大，內(nèi)存難以存放，將極大降低系統(tǒng)查詢性能[10]。因此，在BF_II的基礎(chǔ)上，提出一種改進(jìn)的基于B+樹的倒排文件(B_BF_II),利用B+樹快速查詢的特點，為倒排文件中的詞典建立B+樹索引，如圖3左部所示。在B+創(chuàng)建時，把詞典中的BF作為葉節(jié)點，然后逐步建立中間節(jié)點，直至根節(jié)點。

2.4 電子病歷密文查詢算法

把加密的電子病歷和倒排索引以及B+索引發(fā)送給云服務(wù)器存儲。查詢時，用戶提交陷門，首先對B+檢索，快速定位到倒排索引中詞表，然后找到布隆過濾器對密文直接篩選。

對加密數(shù)據(jù)的查詢，分兩步進(jìn)行：(1) 客戶端生成陷門Tw，對B+樹進(jìn)行查詢，找到滿足查詢條件的葉節(jié)點，獲得相應(yīng)電子病歷的id，根據(jù)id讀取對應(yīng)的加密電子病歷文檔并傳輸至客戶端；(2) 客戶端解密獲得明文電子病歷。

算法1基于BF和B+樹加密電子病歷查詢

輸入：搜索的關(guān)鍵詞Wi,Did(電子病歷編號)。

輸出：密文電子病歷。

1. 用戶計算陷門Tw=Trapdoor(Kpriv,wi)=(x1,x2,…xr)，并發(fā)送給服務(wù)器。

2. 服務(wù)器接收到陷門Tw。

(1) (c1=f(Did‖x1),(c2=f(Did‖x2),…,cr=f(Did‖xr))∈{0,1}sr。

(2) 計算編碼詞的位置，選取r個哈希函數(shù)H1,H2,…,Hr，計算p1=H1(c1),p2=H2(c2),…,pr=Hr(cr)。

(3) 把布隆過濾器BF中p1,p2,…,pt的位置上修改為1，沒有修改過的仍為0，得到該關(guān)鍵詞的布隆過濾器。

(4) 查詢B+樹，從根節(jié)點開始，直至葉節(jié)點。如果找到滿足條件的葉節(jié)點(倒排索引中的詞條)，繼續(xù)步驟3，否則停止搜索，返回未找到密文電子病歷信息。

3. 服務(wù)器根據(jù)倒排索引中的詞條所對應(yīng)的指針Pi,搜索到倒排文檔的地址集合，然后返回用戶密文電子病歷。

4. 用戶解密，獲得明文電子病歷。

3 系統(tǒng)分析

3.1 安全性分析

(1) 服務(wù)器安全性。服務(wù)器存儲了電子病歷密文和索引兩部分，前者采用了加密算法(如AES、DES)進(jìn)行加密以保證其安全性，能夠抵抗選擇明文攻擊，本文不作討論。后者是根據(jù)前者的關(guān)鍵詞經(jīng)過一系列轉(zhuǎn)換得到，轉(zhuǎn)換過程主要使用了哈希函數(shù)保證其安全性。如圖3所示，索引結(jié)構(gòu)中包含了BF、倒排文件和B+樹，由于倒排索引和B+都是建立在BF的基礎(chǔ)上，安全的關(guān)鍵在于BF上。在BF的構(gòu)建過程中，首先通過用戶的安全參數(shù)s動態(tài)生成r個密鑰ki，只要用戶安全參數(shù)s不泄露，即使攻擊服務(wù)器端獲得用戶的身份信息，也無法獲得密鑰。其次在產(chǎn)生陷門時，采用了偽隨機(jī)函數(shù)(HMAC-SHA1),對于布隆過濾器中的每個詞條進(jìn)行了r次哈希處理，能夠抵抗選擇明文攻擊(Adaptive Chosen Keyword Attack,IND-CKA)[11]。在倒排文件中，BF與地址p連接成為詞典，BF是有序的，但并不會給攻擊者帶來任何機(jī)會，因為從BF的構(gòu)建過程中可以發(fā)現(xiàn)，BF有序，但關(guān)鍵詞的順序被打亂，攻擊者無法從BF的有序信息得到關(guān)鍵詞的順序關(guān)系。類似地，B+樹也是根據(jù)BF的順序來構(gòu)建，攻擊者也無法進(jìn)行選擇明文攻擊[12]。

(2) 用戶端安全性。首先，用戶查詢電子病歷時，向服務(wù)器發(fā)送陷門，而不是關(guān)鍵詞，保證了用戶查詢使用的關(guān)鍵詞不被服務(wù)器知道。其次，服務(wù)器返回電子病歷密文，很好地保護(hù)了用戶查詢結(jié)果的安全。

3.2 正確性分析

把加密的電子病歷和倒排索引以及B+索引發(fā)送給云服務(wù)器存儲。查詢時，用戶提交陷門，首先對B+檢索，快速定位到倒排索引中詞表，然后找到布隆過濾器對密文直接篩選。利用布隆過濾器查詢電子病歷密文時，不會遺漏任何包含該關(guān)鍵詞的電子病歷。根據(jù)BuildIndex(D,Kpriv)，每個關(guān)鍵詞都會在布隆過濾對應(yīng)的r個位上置1。查詢時，根據(jù)用戶提交陷門再重復(fù)相同計算，必定也是在相同的r個位上置1，所以只要電子病歷包含該關(guān)鍵詞，絕對不會遺漏。

但是，布隆過濾器置1時，由于為不同關(guān)鍵詞建立索引時，同一個位置可能會重復(fù)置1，這樣可能產(chǎn)生假陽性(False Positives)。假陽性概率為：

(1)

式中：m是過濾器大小(bit)；n是關(guān)鍵詞個數(shù)；k是哈希函數(shù)個數(shù)?？梢杂^察到，隨著過濾器位數(shù)m增加，假陽性概率下降；隨著關(guān)鍵詞個數(shù)n的增加，假陽性概率上升。

3.3 性能分析

在電子病歷文檔中，常用醫(yī)學(xué)專業(yè)詞匯關(guān)鍵詞個數(shù)1 000個左右，假設(shè)使用8個哈希函數(shù)，那么布隆數(shù)組大小為213=8 192 bit，假陽率能夠控制在0.01即1/100之內(nèi)，這樣的空間過濾效果能夠滿足密文電子病歷搜索需求。

對于未能過濾掉的偽文檔，常見的處理方法是發(fā)送給用戶，用戶解密后發(fā)現(xiàn)文檔不符合要求再舍棄。當(dāng)然，發(fā)送給用戶的密文都需要與訪問控制措施結(jié)合起來，用戶有權(quán)限才能獲得相關(guān)的密文。

作為樹形的數(shù)據(jù)結(jié)構(gòu)的B+樹能夠多路查找，具有能夠保持?jǐn)?shù)據(jù)的穩(wěn)定有序的特點，有良好的查詢效率[13]，因此B+樹被廣泛應(yīng)用于數(shù)據(jù)庫和操作系統(tǒng)的文件系統(tǒng)中，如此廣泛的應(yīng)用足以體現(xiàn)出B+樹查詢等方面的優(yōu)勢。本文使用B+樹將倒排文件組織成BIF，充分挖掘B+樹的查詢優(yōu)勢。

4 實 驗

在實驗中，比較了倒排索引(II)、基于布隆過濾器的倒排索引(BF_II)、基于B+樹和BF的倒排索引(B_BF_II)方法在創(chuàng)建時的空間代價和查詢的時間代價。實驗中使用的關(guān)鍵詞是從常用臨床醫(yī)學(xué)術(shù)語中獲取，分成1 630和5 295兩組。每次實驗做10次，取其平均值作為最后實驗分析數(shù)據(jù)。實驗中使用的哈希算法為HMAC-SHA1，實驗環(huán)境為Windows 10操作系統(tǒng)，P4 2.8 GHz的CPU，8 GB的內(nèi)存。

4.1 構(gòu)建索引的空間代價

在實驗中，對三種不同索引的空間大小進(jìn)行比較。如圖4所示，(a)和(b)比較了關(guān)鍵詞個數(shù)分別為1 630和5 295時三種索引的空間大小。從實驗結(jié)果可以得出：布隆過濾器大小由8 bit逐漸增加至128 bit時，BF_II比II的空間稍微減少，這是由于BF過濾器采用位圖表示，比關(guān)鍵詞所占存儲空間相應(yīng)少一些。而B_BF_II相對另外兩種索引空間稍微增加，這主要是因為B_BF_II在BF_II基礎(chǔ)上增加了二級索引B+，空間相應(yīng)地增加了一些。

(a) 關(guān)鍵詞個數(shù)為1 630

4.2 查詢的時間代價

用戶查詢代價是衡量系統(tǒng)性能的最重要指標(biāo)，盡量減少查詢和驗證時間是本文研究的一個重要目的。在這個實驗中，用戶查數(shù)據(jù)時，采用了單關(guān)鍵詞查詢和多關(guān)鍵詞查詢兩種方式，例如：單關(guān)鍵詞查詢疾病為“糖尿病”，多關(guān)鍵詞查詢疾病為“糖尿病”和“血脂高”。如圖5所示，通過單關(guān)鍵詞查詢的實驗結(jié)果對比可以得出，BF_II比II的性能稍優(yōu)，而在BF的位數(shù)增加時性能優(yōu)勢稍微有所減少，這是因為在BF位數(shù)小時進(jìn)行比較的位數(shù)少，比關(guān)鍵詞的直接比較要稍微快一點，所以隨著BF位數(shù)增加，BF_II的優(yōu)勢就會有所減弱。而B_BF_II在布隆過濾器位數(shù)較少時查詢代價比BF_II的要高出許多，但是隨著BF位數(shù)的增加B_BF_II的查詢性能體現(xiàn)出很大的優(yōu)勢。所以當(dāng)BF位數(shù)比較大時，B_BF_II的查詢代價有明顯優(yōu)勢。

(a) 關(guān)鍵詞個數(shù)為1 630

多關(guān)鍵詞查詢的實驗結(jié)果對比如圖6所示，實驗結(jié)果與單關(guān)鍵詞查詢結(jié)果相似，在BF位數(shù)較少時，II與BF_II的性能相近，但BF_II的略優(yōu)，此時兩者都比B_BF_II的性能好。但當(dāng)BF位數(shù)較大時，B_BF_II的查詢性能體現(xiàn)出明顯優(yōu)勢。

(a) 關(guān)鍵詞個數(shù)為1 630

4.3 與z-index查詢時間代價對比

本文基于z-index對可搜索密文技術(shù)進(jìn)行相應(yīng)改進(jìn)。上述實驗結(jié)果還沒有對比本文技術(shù)與z-index查詢方面的性能。如圖7所示，就是本文所說的四種索引之間的查詢代價對比圖。該實驗中BF的大小為128 bit，從實驗結(jié)果對比可知前三者的查詢性能都比z-index有著明顯的優(yōu)勢。根據(jù)上文的敘述前三者都是倒排索引，而z-index是正排索引，所以從實驗結(jié)果可以看出，倒排索引在查詢性能上擁有良好的優(yōu)勢。

圖7 與z-index查詢代價的對比

5 結(jié) 語

本文中主要討論如何設(shè)計索引，用戶通過對索引的查詢就能獲得密文，而不需要解密，針對現(xiàn)有可搜索密文技術(shù)的一些缺陷進(jìn)行改進(jìn)，主要采用了基于BF的倒排索引與B+樹結(jié)合的方法，提高了電子病歷的密文查詢效率，還能支持布爾查詢進(jìn)行“與”“或”“非”查詢，提高檢索效率。在醫(yī)院電子病歷的大數(shù)據(jù)環(huán)境如火如荼的今天，本文的研究能夠為各大醫(yī)療機(jī)構(gòu)提高自己的醫(yī)療信息系統(tǒng)的性能或為其他領(lǐng)域的技術(shù)研究提供一些幫助，促進(jìn)醫(yī)院電子病歷系統(tǒng)的革新與改進(jìn)。