加密文檔排序中保序加密算法的最優(yōu)化選取

張久嶺，黃道超，沈時(shí)軍

（國(guó)家計(jì)算機(jī)網(wǎng)絡(luò)應(yīng)急技術(shù)處理協(xié)調(diào)中心，北京 100029）

傳統(tǒng)的電子郵箱服務(wù)、遠(yuǎn)程數(shù)據(jù)庫(kù)服務(wù)等需要把包含用戶個(gè)人隱私的數(shù)據(jù)存儲(chǔ)在服務(wù)提供商的服務(wù)器上。云計(jì)算和云存儲(chǔ)的快速發(fā)展降低了用戶數(shù)據(jù)信息管理成本及存儲(chǔ)資源與計(jì)算資源的消耗，而手持移動(dòng)終端的愈加頻繁使用使得更多用戶數(shù)據(jù)存儲(chǔ)在云端，這樣在客觀上造成了數(shù)據(jù)存儲(chǔ)和計(jì)算資源的集中化。然而，隨著越來越多的用戶數(shù)據(jù)存儲(chǔ)在遠(yuǎn)程服務(wù)器，對(duì)于服務(wù)提供商來說用戶的數(shù)據(jù)是完全可見的。此外，服務(wù)提供商還可以對(duì)用戶數(shù)據(jù)進(jìn)行統(tǒng)計(jì)分析等操作，如果數(shù)據(jù)在不同的服務(wù)提供商間存在交互流動(dòng)，則服務(wù)商可合并獲取用戶信息，會(huì)進(jìn)一步侵犯用戶隱私。因此，對(duì)用戶隱私數(shù)據(jù)的保護(hù)越來越受到人們的關(guān)注，用戶的數(shù)據(jù)隱私保護(hù)是一個(gè)迫切需要解決的問題。雖然可以通過簽訂服務(wù)協(xié)議或通過多方計(jì)算等方式避免服務(wù)提供商濫用用戶數(shù)據(jù)，但是無(wú)法從根本上保護(hù)用戶隱私。為有效地保護(hù)用戶的隱私，對(duì)用戶信息進(jìn)行加密處理是一種解決方案。用戶數(shù)據(jù)多以文檔形式存儲(chǔ)在服務(wù)提供商側(cè)，因此對(duì)用戶以文檔形式進(jìn)行信息加密并存儲(chǔ)在遠(yuǎn)程服務(wù)器是一種可行且有效的數(shù)據(jù)保護(hù)方案。

然而，當(dāng)存儲(chǔ)在遠(yuǎn)程服務(wù)器的用戶加密數(shù)據(jù)形成規(guī)模之后，用戶在進(jìn)行查詢以滿足其信息需求時(shí)，需把加密文檔全部下載回用戶終端，這將帶來巨大的通信開銷，因此難以實(shí)現(xiàn)。如何對(duì)密文形式的數(shù)據(jù)進(jìn)行檢索成為亟待解決的問題。Song等［1］在2000年開創(chuàng)性地提出了一種實(shí)用的且可以搜索的對(duì)稱加密算法，在進(jìn)行加密關(guān)鍵詞搜索時(shí)，需進(jìn)行線性遍歷，由于加密過程中一次一密，具有較強(qiáng)的抗統(tǒng)計(jì)分析能力。Boneh等［2］在2004年提出了一種可搜索公鑰加密算法。Park等［3］提出了基于布隆過濾的多關(guān)鍵詞安全搜索算法，布隆過濾在小規(guī)模數(shù)據(jù)集情況下可以進(jìn)行有效檢索，但在大規(guī)模數(shù)據(jù)集下，該算法檢索時(shí)所需的布隆過濾器長(zhǎng)度非常大。以上算法可以有效地從加密數(shù)據(jù)中檢索到用戶所需的文檔。然而，隨著數(shù)據(jù)集規(guī)模的增大，檢索到可能相關(guān)的文檔集合的規(guī)模也逐漸增大。例如，很多私人信息郵件被存儲(chǔ)在某不可靠的郵件提供商服務(wù)器上，當(dāng)進(jìn)行檢索時(shí)，即有對(duì)較多返回結(jié)果進(jìn)行排序的需求。如果將檢索到的文檔信息無(wú)差別返回給用戶，一方面將帶來巨大的通信、計(jì)算及存儲(chǔ)開銷，另一方面用戶也無(wú)力消費(fèi)大量的原始明文數(shù)據(jù)。因此，在不泄露用戶信息的情況下，對(duì)檢索到的加密文檔進(jìn)行相關(guān)性排序并給出最符合用戶信息需求的文檔是需要進(jìn)一步研究和解決的問題。

在一般明文信息檢索中，為對(duì)結(jié)果根據(jù)查詢的相關(guān)性進(jìn)行排序，一般利用到詞頻、關(guān)鍵詞權(quán)重等關(guān)鍵信息。在加密信息檢索情況下，為有效依據(jù)文檔中的詞頻、關(guān)鍵詞權(quán)重等加密信息對(duì)加密文檔進(jìn)行相關(guān)性排序，Swaminathan等［4］提出了基于保序加密算法的加密文檔排序算法，該算法中文檔的詞頻被保序加密算法加密，在需要進(jìn)行排序時(shí)，把加密形式的詞頻相加給出相關(guān)度并以此進(jìn)行排序。Wang等［5］提出了用保序加密算法對(duì)關(guān)鍵詞權(quán)重進(jìn)行加密，并對(duì)加密的權(quán)重進(jìn)行加法運(yùn)算得到查詢與加密文檔相似度的算法進(jìn)行排序。Lu等［6］提出了將其類似的算法推廣應(yīng)用于多媒體檢索中并對(duì)多媒體信息檢索結(jié)果進(jìn)行排序。Phong等［7］提出了基于保序加密算法的隱私保護(hù)深度學(xué)習(xí)系統(tǒng)，可以在不把個(gè)人數(shù)據(jù)透露給遠(yuǎn)程服務(wù)器的基礎(chǔ)上，實(shí)現(xiàn)基于神經(jīng)網(wǎng)絡(luò)的深度學(xué)習(xí)。因此，有必要研究加密算法在加密文檔排序中的應(yīng)用。

在典型加密信息檢索中，當(dāng)查詢中只有1個(gè)關(guān)鍵詞時(shí)，通過基于保序加密算法的加密文檔排序算法可以很好地對(duì)檢索到的加密文檔進(jìn)行排序，這是因?yàn)橛帽Ｐ蚣用芩惴用艿拿魑臄?shù)據(jù)加密后其密文順序保持不變。然而，當(dāng)查詢中有2個(gè)及2個(gè)以上的關(guān)鍵詞時(shí)，基于保序加密算法加密得到密文和并不一定保持與其明文和對(duì)應(yīng)的順序。在這種情況下，并非所有保序加密算法在多關(guān)鍵詞查詢時(shí)，其密文和均能較好保持順序并取得較好排序結(jié)果。因此，可以通過適當(dāng)?shù)剡x擇加密算法來保證密文和能最大限度保持其明文和的順序，而研究探索最優(yōu)化選取滿足上述需求的加密算法也至少具有理論上的指導(dǎo)意義。

本文介紹了保序加密算法，擬合了TREC的標(biāo)準(zhǔn)數(shù)據(jù)集中關(guān)鍵詞權(quán)重概率分布，比較了2種保序加密算法密文隨明文的變化，提出了基于鑒別信息的保序加密算法選取標(biāo)準(zhǔn)。對(duì)選擇不同保序加密算法的加密文檔檢索排序結(jié)果進(jìn)行了比較，并在標(biāo)準(zhǔn)數(shù)據(jù)集上進(jìn)行了實(shí)驗(yàn)，驗(yàn)證了采用開放式保序加密算法進(jìn)行加密排序取得的結(jié)果優(yōu)于采用封閉式保序加密算法的情況。

1 保序加密算法及其加密文檔排序

1.1 保序加密算法

2003年，Ozsoyoglu等［8］開創(chuàng)性提出了保序加密算法，以解決關(guān)系型數(shù)據(jù)庫(kù)數(shù)值數(shù)據(jù)隱私保護(hù)的問題。2004年，Agrawal等［9］提出了一種可以直接加密新數(shù)據(jù)且無(wú)需對(duì)已加密密文進(jìn)行更新的保序加密算法。Boldyreva等［10］提出了基于超幾何分布的保序?qū)ΨQ加密算法及基于模的保序加密算法［11］。文獻(xiàn)［12］中的算法應(yīng)用于無(wú)線傳感網(wǎng)，通過加密信號(hào)數(shù)據(jù)并傳輸?shù)絺鞲泄?jié)點(diǎn)，傳感節(jié)點(diǎn)無(wú)需解密即可進(jìn)行大小比較操作，降低了節(jié)點(diǎn)的功耗開銷。在保序加密算法應(yīng)用于遠(yuǎn)程數(shù)據(jù)庫(kù)數(shù)據(jù)保護(hù)的相關(guān)研究中，有工作針對(duì)數(shù)據(jù)順序本身也是敏感信息提出了隱藏密文順序但支持有效比較運(yùn)算的算法，提高了數(shù)據(jù)安全性［13］；也有工作提出了一種在數(shù)據(jù)庫(kù)中插入假元組并保證數(shù)據(jù)完整性的算法，在該算法中真元組和假元組都經(jīng)過保序加密，以允許用戶驗(yàn)證保序加密數(shù)據(jù)庫(kù)的查詢完整性［14］；還有工作提出了具有有序選擇重復(fù)明文分布攻擊下的不可區(qū)分性的算法［15］。其他算法包括基于一般近似公約數(shù)問題的保序加密算法［16］及使用保序概率編碼對(duì)明文的變換進(jìn)行編碼并通過2輪交互協(xié)議生成密文的公開保序密文生成算法［17］。

由于上述提到的其他算法與開放式及封閉式保序加密算法具有本質(zhì)上的相似性，為不失一般性，主要針對(duì)Ozsoyoglu等［8］提出的2種典型保序加密算法進(jìn)行分析，其第1種開放形式的保序加密算法實(shí)現(xiàn)過程的描述如下：

步驟1 生成一個(gè)序列的隨機(jī)數(shù)yi∈［1，M］。

步驟2 定義zi：S1：＝z1：＝y(tǒng)1。

步驟3 對(duì)于k≥1，令A(yù)k＝M－Sk。

步驟4 zk＋1＝Int（yk＋1×Ak／M）。

步驟5 Sk＋1＝Sk＋zk＋1。

其中，對(duì)于明文k，保序加密算法加密的結(jié)果為

第2種為封閉式的保序加密算法，其可以描述為

式中：x為待加密變量；Ci（0≤i≤n）為常量。

在其他算法中，Agrawal等［9］提出的算法把服從某一分布明文映射到服從另一分布的密文空間。而Boldyreva等［10］提出的加密算法的實(shí)質(zhì)是利用超幾何分布產(chǎn)生保序的密文數(shù)據(jù)，與Ozsoyoglu等［8］提出的第1種開放形式保序加密算法本質(zhì)上類似。

1.2 明文文檔檢索及排序

典型的信息檢索模型包括布爾模型、向量空間模型及概率模型等［18］。布爾模型是基于布爾代數(shù)的檢索模型，該模型中1個(gè)查詢即構(gòu)成了1個(gè)布爾表達(dá)式。盡管布爾模型在數(shù)據(jù)庫(kù)檢索中仍有使用價(jià)值，但在文檔檢索中無(wú)法對(duì)檢索到的文檔進(jìn)行排序，在實(shí)踐中使用較少。在向量空間模型中，文檔及查詢分別被標(biāo)記為向量空間中的向量，通過向量之間的相似度來對(duì)文檔進(jìn)行相關(guān)性排序。概率模型通過計(jì)算文檔與查詢之間相關(guān)的概率對(duì)文檔進(jìn)行排序。為不失一般性，以概率模型的一種變形，即以O(shè)kapi BM25模型為例，實(shí)現(xiàn)對(duì)文檔及查詢相關(guān)度的計(jì)算。

Okapi BM25模型自從20世紀(jì)90年代被提出后，由于檢索的準(zhǔn)確率相對(duì)其他模型較高，在文檔排序中的應(yīng)用非常普遍，并被推廣應(yīng)用到文本分類聚類等眾多領(lǐng)域［18-19］。

Okapi BM25模型中，文檔和查詢之間的相似度定義為

式中：wqi為關(guān)鍵詞qi在文檔D中所占的權(quán)重，定義為文檔中詞頻和逆文檔頻率的函數(shù)，有很多個(gè)變種。本文中，為不失一般性，采用其中比較常用的一種：

1.3 基于保序加密的文檔排序

在加密文檔檢索中，當(dāng)檢索到所需的文檔之后，需要對(duì)已經(jīng)加密的文檔進(jìn)行基于詞頻或關(guān)鍵詞權(quán)重對(duì)應(yīng)密文的排序操作。Swaminathan等［4］提出了用保序加密算法對(duì)文檔中的詞頻進(jìn)行加密的方法，在查詢單個(gè)關(guān)鍵詞的情況下，通過保序加密的詞頻可以得到相關(guān)度的排序。盡管詞頻在一定程度上可以描述文檔和查詢的相關(guān)度，然而權(quán)重更為有效地描述了關(guān)鍵詞在文檔中的出現(xiàn)對(duì)文檔與查詢相關(guān)度的影響。

因此，通過對(duì)關(guān)鍵詞的權(quán)重進(jìn)行加密，可以更為有效地描述一個(gè)關(guān)鍵詞在文檔中出現(xiàn)的作用。這里對(duì)文檔排序的對(duì)象是關(guān)鍵詞權(quán)重對(duì)應(yīng)的密文。

理論上，當(dāng)查詢中關(guān)鍵詞個(gè)數(shù)｜Q｜為1時(shí)，用保序加密算法排序所得到的結(jié)果具有很好的性能。而當(dāng)查詢中關(guān)鍵詞個(gè)數(shù)｜Q｜多于1個(gè)時(shí)，由于涉及到對(duì)加密密文的加法操作，而加法后的密文排序并非明文和的順序。因此，當(dāng)查詢中有多個(gè)關(guān)鍵詞時(shí)，排序的結(jié)果與保序加密算法有關(guān)。

2 保序加密算法選取

2.1 明文分布

式中：各參數(shù)的擬合值如表1所示。

表1 參數(shù)擬合值Table 1 Parameter fitting values

由圖1可以看出，該分布并非是嚴(yán)格的對(duì)數(shù)正態(tài)分布，這是因?yàn)樵~頻和逆文檔頻率并非是完全獨(dú)立的，而詞頻本身是對(duì)關(guān)鍵詞出現(xiàn)頻率進(jìn)行運(yùn)算的結(jié)果，且權(quán)重的分布是選擇保序加密算法的決定性因素。

圖1 Okapi BM25模型權(quán)重出現(xiàn)頻率的分布函數(shù)Fig.1 Probability distribution function of term weights in Okapi BM25 model

2.2 保序加密算法選取方法

對(duì)2種保序加密算法下的密文進(jìn)行了比較，結(jié)果如圖2所示。由于加密后的值較大不便于直接展示，為便于比較，對(duì)密文取對(duì)數(shù)。圖2的曲線表明，當(dāng)采用開放形式保序加密算法的密文值增大到一定程度后便保持穩(wěn)定，而封閉形式保序加密算法的密文值一直明顯地增加。

圖2 開放式保序加密算法與封閉式保序加密算法密文隨明文變化情況Fig.2 Change of cipher text with plaintext for open order preserving encryption scheme and closed order preserving encryption scheme

2種保序加密算法都可以很好地對(duì)加密數(shù)值保持順序。然而，本文有以下啟發(fā)性結(jié)論：針對(duì)密文的加法運(yùn)算，采用開放形式保序加密算法加密的密文能更好地保持其順序。這是因?yàn)椋河瞄_放式保序算法加密得到的密文值比較接近，然而，用封閉式加密算法加密得到的密文值在數(shù)值空間上分布越來越稀疏。因此，封閉式保序加密算法加密得到的密文值加法運(yùn)算結(jié)果的保序效果劣于開放式保序加密算法。反映在加密文檔排序效果上，采用開放形式保序加密算法的檢索結(jié)果在性能上優(yōu)于封閉形式保序加密算法得到的檢索結(jié)果。

3 保序加密算法選取標(biāo)準(zhǔn)

理想情況下，設(shè)保序加密由連續(xù)函數(shù)h（x）表示，那么，給定明文X，則其對(duì)應(yīng)密文Y＝h（X）的分布為為使在保序加密的情況下其加法在統(tǒng)計(jì)意義上仍然是保序的，通過保序加密算法加密的密文如果服從明文分布f（x）或接近明文的分布，則在理論上同樣可以達(dá)到明文檢索下相差較小的檢索結(jié)果。經(jīng)過加密變換Y＝h（X）之后，Y值的變化區(qū)間為［h（0），h（3）），為便于進(jìn)行分布比較，可以將Y通過某線性變換Z＝3（Y－h(huán)（0））／（h（3）－h(huán)（0））將其值重新映射到區(qū)間［0，3）。線性變換不影響2個(gè)數(shù)加法的結(jié)果，因此，可以對(duì)Z與X的分布進(jìn)行比較。Z的分布由Y的分布表示為

衡量2種分布之間差異性的一種比較好的方法是鑒別信息。通過鑒別信息可以對(duì)明文與密文概率分布的差異性進(jìn)行描述。為使二者分布距離最近，需要使鑒別信息最小。為使保序加密后的密文仍然保持原有的分布，需要滿足：

然而，對(duì)保序加密算法的選擇是有其他約束性的。例如，為保證算法的安全性，封閉式保序加密算法系數(shù)的選取范圍應(yīng)該足夠大；而在開放性的保序加密算法中，為保證明文對(duì)應(yīng)的密文各不相同，需要增加密文值域等。因此，保序加密算法h（x）的優(yōu)化選擇可為

4 實(shí)驗(yàn)結(jié)果

有工作分析研究了云數(shù)據(jù)搜索中一到多保序加密算法的安全性，并提出了通過保序密文的差異可以進(jìn)行差分攻擊的問題［20］。本文從另一個(gè)角度，即在算法具有同等安全性的前提下對(duì)如何最優(yōu)化選取保序加密算法進(jìn)行了研究。在TREC的標(biāo)準(zhǔn)數(shù)據(jù)集ClueWeb09 Cat.B上進(jìn)行了實(shí)驗(yàn)，由于數(shù)據(jù)集合規(guī)模較大，其結(jié)果相比Cranfield等小規(guī)模數(shù)據(jù)集更接近真實(shí)環(huán)境。在該數(shù)據(jù)集中，有50 000 000個(gè)文檔、50個(gè)標(biāo)準(zhǔn)查詢。針對(duì)該數(shù)據(jù)集的任1個(gè)文檔進(jìn)行分詞、記干化等預(yù)處理，可以得到其對(duì)應(yīng)的詞頻f（ti，D）及文檔長(zhǎng)度｜D｜。然而，通過對(duì)整個(gè)文檔進(jìn)行統(tǒng)計(jì)，可以得到式（4）中參數(shù)的avgdl、C及n（ti）的值。

通過以上參數(shù)，可以計(jì)算得到關(guān)鍵詞ti所對(duì)應(yīng)的Okapi BM25模型下的權(quán)重。用戶對(duì)其通過保序加密算法進(jìn)行加密，把得到的密文存儲(chǔ)在服務(wù)器端，而在服務(wù)器端，對(duì)對(duì)應(yīng)關(guān)鍵詞的保序加密形式的權(quán)重進(jìn)行加法運(yùn)算，通過所得到的結(jié)果對(duì)文檔進(jìn)行排序。

在實(shí)驗(yàn)中所采用的保序加密算法分別為1.1節(jié)中文獻(xiàn)［8］所提到的開放式保序加密算法與封閉式保序加密算法。

評(píng)價(jià)檢索結(jié)果效果的指標(biāo)為準(zhǔn)確率及返回率。準(zhǔn)確率定義為返回的且相關(guān)的文檔占所返回文檔的比例，返回率定義為返回的且相關(guān)的文檔占所有相關(guān)文檔的比例。

采用不同保序加密算法對(duì)加密文檔進(jìn)行排序及明文檢索情況下的準(zhǔn)確率-返回率曲線的對(duì)比結(jié)果如圖3所示。可以看出，在ClueWeb09 Cat.B數(shù)據(jù)集上，采用保序加密算法排序的準(zhǔn)確率-返回率曲線比明文檢索的情況低；采用開放式保序加密的準(zhǔn)確率-返回率曲線比封閉式保序加密對(duì)應(yīng)的曲線高。

圖3 不同檢索排序方式下的準(zhǔn)確率-返回率曲線Fig.3 Curves of precision versus recall rate with different retrieval and ranking methods

前N個(gè)文檔的準(zhǔn)確率（P@N）如表2所示，此處N的取值分別為5、10、20、30、50、100。表2中不同返回文檔個(gè)數(shù)下的準(zhǔn)確率表明，開放式的保序加密算法可以達(dá)到較封閉式保序加密算法更好的檢索結(jié)果，比較重要的指標(biāo)，如前10個(gè)及前20個(gè)的準(zhǔn)確率明顯高于后者，其中P@10高出3.4%。然而，2種保序加密算法的準(zhǔn)確率都低于作為比較基準(zhǔn)的明文檢索情況下的檢索排序準(zhǔn)確率。這說明單純依靠保序加密算法可以開展對(duì)加密文檔的排序，但距離明文檢索下的結(jié)果還有差距，后續(xù)將研究通過結(jié)合使用同態(tài)加密算法來進(jìn)一步提高檢索的準(zhǔn)確率。通過結(jié)合使用保序加密及同態(tài)加密算法，可在減少在本地運(yùn)算量的基礎(chǔ)上，為密文空間提供更加精細(xì)的相關(guān)度計(jì)算結(jié)果。

表2 前N個(gè)返回文檔的準(zhǔn)確率Table 2 Precision of top N recalled documents

5 結(jié) 論

1）通過在ClueWeb09 Cat.B數(shù)據(jù)集上對(duì)權(quán)重進(jìn)行統(tǒng)計(jì)分析，擬合了其權(quán)重的分布。

2）P@10的加密文檔排序中，基于開放式保序加密算法的準(zhǔn)確率比封閉式保序加密算法高出3.4%，驗(yàn)證了在加法運(yùn)算下的開放形式保序加密算法的密文能更好地保持原有順序的結(jié)論。

3）給出了對(duì)保序加密算法最優(yōu)化選取的準(zhǔn)則，該準(zhǔn)則具有理論上的指導(dǎo)意義。

探索保序加密算法的共性特征及在此基礎(chǔ)上提出最優(yōu)化選取方案有待進(jìn)一步的深入研究。