基于MapReduce框架下的數(shù)據(jù)隱私保護(hù)

姚庚梅，張永棠,2

(1. 廣東東軟學(xué)院 計(jì)算機(jī)學(xué)院，廣東 佛山 528225；2. 南昌工程學(xué)院 江西省協(xié)同感知與先進(jìn)計(jì)算技術(shù)研究所，江西 南昌 330003)

0 引言

云計(jì)算框架外包數(shù)據(jù)處理和存儲(chǔ)的快速發(fā)展，向現(xiàn)代社會(huì)發(fā)展提供了大量有用的數(shù)據(jù)。但是，數(shù)據(jù)隱私保險(xiǎn)是云環(huán)境下海量數(shù)據(jù)集管理中的一個(gè)主要問題，因?yàn)閿?shù)據(jù)集所有者沒有按照云安全聯(lián)盟[1]（CSA）的規(guī)定對(duì)其數(shù)據(jù)集進(jìn)行任何物理控制。因此，MapReduce作為一個(gè)處理和創(chuàng)建大量分布式信息的計(jì)算框架，必須具有很強(qiáng)的安全性，才能在云中保護(hù)數(shù)據(jù)隱私。通過MapReduce和Cloud發(fā)現(xiàn)的安全保證問題已經(jīng)開始引起認(rèn)真的考慮。文獻(xiàn)[2]提供了一組名為 Silverline的工具，可以將所有實(shí)際上可加密的信息與其他云應(yīng)用程序信息隔離開來，以確保數(shù)據(jù)保護(hù)。同樣，文獻(xiàn)[3]提出了一種基于隱私泄漏上限限制的解決方案，通過對(duì)云上部分可用數(shù)據(jù)進(jìn)行加密來解決數(shù)據(jù)隱私保護(hù)問題。文獻(xiàn)[4]提出了一個(gè)名為Airavat的框架，該框架通過差異隱私技術(shù)限制強(qiáng)制訪問控制。文獻(xiàn)[5]提出了一個(gè)名為Prism的數(shù)據(jù)隱私模型，用于云上的MapReduce結(jié)構(gòu)，對(duì)加密數(shù)據(jù)集進(jìn)行并行字搜索。文獻(xiàn)[6]提出了Hybrex MapReduce模型，該模型通過私有云處理非常敏感和私有的信息，而其他數(shù)據(jù)可以在公共云中安全地處理。文獻(xiàn)[7]提出了一個(gè)名為sedic的系統(tǒng)，該系統(tǒng)根據(jù)數(shù)據(jù)的安全標(biāo)簽對(duì)Map進(jìn)行分區(qū)，從而減少計(jì)算任務(wù)。然而，傳統(tǒng)的數(shù)據(jù)加密被認(rèn)為是解決云安全問題的關(guān)鍵技術(shù)，不能直接在MapReduce框架中實(shí)現(xiàn)。因此，在文獻(xiàn)[8]中首次引入了一種新的可處理加密數(shù)據(jù)的同態(tài)加密體制，以找到解決這一難題的有效方法。這種完全同態(tài)加密（Fully homomorphic encryption，F(xiàn)HE）可以在不使用密鑰的情況下計(jì)算加密數(shù)據(jù)的任意函數(shù)。然而，F(xiàn)HE在實(shí)施和計(jì)算成本方面提出了兩個(gè)主要挑戰(zhàn)。

為此，文獻(xiàn)[9]提出了DGHV方案，使用許多來自Gentry的工具，而不需要理想的格式。此外，Gentry中的某些同態(tài)分量可以被一個(gè)非常簡(jiǎn)單的、使用整數(shù)的、有些同態(tài)的格式所取代。因此，它們的模型在概念上更簡(jiǎn)單，但是私有密鑰應(yīng)該轉(zhuǎn)移到云服務(wù)器，這是非常不安全的。文獻(xiàn)[10]提出了一種同態(tài)加密 Gen 10方案，適用于云環(huán)境，概念簡(jiǎn)單。在該方案中，加密函數(shù)在加、減、乘上是同態(tài)的，使用一個(gè)隨機(jī)的私鑰參數(shù)來代替私有密鑰。然而，私鑰參數(shù)被發(fā)送到服務(wù)器，需要通過公式計(jì)算得出密文，這個(gè)過程可能會(huì)泄漏密文。所以這個(gè)方案也存在安全漏洞。本文的目標(biāo)是構(gòu)建一個(gè)具有更好密鑰大小的有效 FHE方案，提出一種優(yōu)化的完全同態(tài)方案（Op_FHE），該方案首先通過密文的高效操作解決上述數(shù)據(jù)隱私保護(hù)缺點(diǎn)。此外，我們演示了我們提出的解決方案在 Reduce階段以優(yōu)化和安全的方式檢索密文的速度。

1 準(zhǔn)備工作

MapReduce是一種用于處理和生成大型數(shù)據(jù)集的計(jì)算框架。在此編程環(huán)境中，用戶指定一個(gè)映射函數(shù)，該函數(shù)處理一個(gè)鍵/值對(duì)以生成一組中間鍵/值對(duì)，以及一個(gè)reduce函數(shù)，該函數(shù)合并與相同中間鍵相關(guān)的所有中間值。我們有許多可以由 mapreduce表示的問題解決方法，比如計(jì)算大型數(shù)據(jù)集中每個(gè)術(shù)語的出現(xiàn)次數(shù)的問題。

MapReduce框架上的安全保密問題已經(jīng)開始引起越來越多的關(guān)注。安全界從業(yè)人員對(duì)數(shù)據(jù)加密保護(hù)問題進(jìn)行了廣泛研究，并取得了富有成效的進(jìn)展。以下是MapReduce框架上已有的幾個(gè)關(guān)于安全保護(hù)的模型。

文獻(xiàn)[12]中提出了一種利用同態(tài)加密的MapReduce數(shù)據(jù)隱私保險(xiǎn)方案。它是一種改進(jìn)的MapReduce模型，以保證數(shù)據(jù)的保密性，并以加密的形式對(duì)數(shù)據(jù)進(jìn)行處理。他們選擇兩個(gè)主要素?cái)?shù)A，B，并使P=A· B，然后生成一個(gè)隨機(jī)的正整數(shù)A，這是私鑰，而B也應(yīng)該是保密的。

加密：

解密：

但是，為了在該方案中應(yīng)用同態(tài)加密，作者對(duì)密文進(jìn)行了很少的修改，允許約簡(jiǎn)函數(shù)找到相同的密鑰，然后對(duì)它們進(jìn)行分組。即，對(duì)于密文，其中R為隨機(jī)正數(shù)。然后，通過C*來檢索類似的鍵（而不是C）。因此，很明顯，為了得到概率同態(tài)密碼系統(tǒng)，它們?cè)赗educe階段需要額外的計(jì)算C*，這在計(jì)算上是昂貴的。這種同態(tài)密碼體制的代價(jià)非常高，因此它們的模型效率很低。

由于文獻(xiàn)[13]需要在Reduce階段進(jìn)行額外的計(jì)算，并且DGHV 和Gen 10方案分別將它們的私鑰和敏感安全參數(shù)發(fā)送到不可靠的公共云服務(wù)器（危及密碼系統(tǒng)）。此外，也沒有解決密文檢索的安全性和效率問題。因此，文獻(xiàn)[14]提出了一種完全同態(tài)加密（Fully homomorphic encryption，F(xiàn)HE）方案。該方案的主要目標(biāo)是在還原階段安全地檢索密文，提高檢索算法的準(zhǔn)確性，而不需要獲取有關(guān)中間可搜索密文內(nèi)容的任何信息，以解決DGHV和Gen 10中的安全缺陷。FHE方案是同態(tài)加密的有效候選方案，通過強(qiáng)大的混合加密來保護(hù)云中的數(shù)據(jù)隱私，在計(jì)算和通信成本方面，這是一種非常昂貴的方案。

因此，我們提出了一種優(yōu)化的 FHE（Optimized Fully homomorphic encryption，Op_FHE）方案。該方案的創(chuàng)新點(diǎn)是通過邏輯 Merkle哈希樹存儲(chǔ)庫(kù)結(jié)構(gòu)，降低時(shí)空成本，解決元數(shù)據(jù)動(dòng)態(tài)和認(rèn)證路徑的輸入文件分解（MAP階段）和密文檢索算法（Reduce階段）的優(yōu)化問題。

2 Op_FHE 方案描述

同態(tài)加密可以有效地在加密數(shù)據(jù)上進(jìn)行一些操作，但在計(jì)算和通信成本方面，這是一種非常昂貴的方案。因此，我們提出了一種優(yōu)化的FHE（即 Op_FHE）。Op_FHE解決方案的體系結(jié)構(gòu)如圖1所示。

圖1 Op_FHE 架構(gòu)

在主程序的控制下，在用戶端引入了一個(gè)新的邏輯代理：匿名者（其三個(gè)組件：分解表、查詢處理和元數(shù)據(jù)倉(cāng)庫(kù)）。這樣，用戶程序就可以在加密數(shù)據(jù)之前，有效地將給定輸入文件的最優(yōu)分解（拆分：鍵/值）發(fā)送給主程序。在邏輯Merkle樹結(jié)構(gòu)中使用優(yōu)化的三值搜索嘗試（TST）[15]，通過元數(shù)據(jù)存儲(chǔ)庫(kù)組件最優(yōu)地解決元數(shù)據(jù)認(rèn)證和動(dòng)態(tài)問題。

為了解決元數(shù)據(jù)身份驗(yàn)證和動(dòng)態(tài)問題，加強(qiáng)數(shù)據(jù)隱私保護(hù)。如圖1所示，我們?cè)谥骺爻绦蛑幸肓艘粋€(gè)邏輯代理：匿名者。匿名者有三個(gè)部分組成，即：分解表、查詢處理和元數(shù)據(jù)存儲(chǔ)庫(kù)。它們的功能描述如下：

分解表：它負(fù)責(zé)為最佳數(shù)量的特定輸入文件定義精確的屬性集A。

查詢處理：它過濾主程序生成的候選Map工作線程查詢請(qǐng)求，以便對(duì)數(shù)據(jù)位置產(chǎn)生基于查詢的匿名請(qǐng)求以進(jìn)行處理。

元數(shù)據(jù)存儲(chǔ)庫(kù)：它保存分解表完成的數(shù)據(jù)分解，并將其轉(zhuǎn)發(fā)給查詢處理單元，以生成新的匿名查詢請(qǐng)求。為了提高該方案的效率，我們使用Merkle哈希樹結(jié)構(gòu)[16]來處理元數(shù)據(jù)認(rèn)證和動(dòng)態(tài)問題。因此，主程序?qū)⑻囟ǖ妮斎胛募纸獗恚ˋ）分配給Map工作線程，以便進(jìn)行邏輯處理，如下所示。

所有輸入文件都被轉(zhuǎn)換成一組符號(hào) a1, a2,… ,an，如圖2所示。數(shù)據(jù)匹配和認(rèn)證以自頂向下的方式從根節(jié)點(diǎn)開始，其動(dòng)態(tài)過程可以描述如下。

圖2 高效的基于符號(hào)的樹檢索

文件上傳：假設(shè)數(shù)據(jù)所有者希望用公共云服務(wù)器處理由ai(葉節(jié)點(diǎn))標(biāo)識(shí)的文件F，該文件的屬性滿足私有云服務(wù)器定義的訪問策略AP=［ap1, a p2,… ,a pn］。假設(shè)文件F由關(guān)鍵字集W組成，那么，所有者從密鑰空間中隨機(jī)選擇對(duì)稱密鑰Ske，并用Ske加密文件F以獲得密文Ctf。隨后，數(shù)據(jù)所有者運(yùn)行算法 E ncrypt（ AP , Ske）以獲得加密文本Cske，即針對(duì)訪問策略AP的對(duì)稱密鑰Ske的加密。所有者將（ai, Ctf, Cske）上載到公共云。此外，為了為W中的關(guān)鍵字生成陷門，所有者還向私有云發(fā)送 （ai, A P,W ） 。當(dāng)接收到 （ai, A P,W ） 時(shí)，私有云將訪問策略AP轉(zhuǎn)換為一組｛Pj｝ AP特權(quán)。然后，對(duì)于每個(gè)wi∈W和 pi∈ ｛ Pj｝AP ，它計(jì)算tpi，，其中kpi是每個(gè)pi的對(duì)稱密鑰。最后，私有云也向公共云發(fā)送

為了提高搜索效率，使用基于符號(hào)的樹來建立存儲(chǔ)在私有云（元數(shù)據(jù)存儲(chǔ)庫(kù)）中的索引。更準(zhǔn)確地說，將單向函數(shù) f的輸出劃分為l個(gè)部分，并預(yù)先定義一個(gè)屬性集 A = ｛a1, a2,… ,ai｝，其中包含每個(gè)部分中的所有可能值，圖3顯示了這種樹的一個(gè)示例。最初，基于符號(hào)樹的索引只有一個(gè)根節(jié)點(diǎn)（表示為node 0），它由?（一個(gè)空集）組成。基于符號(hào)的樹中的搜索過程是深度優(yōu)先搜索。可以按以下方式更新和搜索樹。

Update：假設(shè)數(shù)據(jù)所有者希望外包一個(gè)文件F，該文件由帶有關(guān)鍵字集W的ai標(biāo)識(shí)，則公共云將從數(shù)據(jù)所有者和私有云接收（ai, Ctf, Cske）和（ai, ｛ tpi, wi｝ ） ，其中pi是相應(yīng)的特權(quán)，wi是W中的關(guān)鍵字。然后，對(duì)于每個(gè)（tpi, wi） ，公有云將按照以下步驟將其添加到trie索引中。

Step.1公有云將 （tpi, wi） 解析為符號(hào) ai1,ai2,… ,ail的序列。

Step.2公有云從樹的根節(jié)點(diǎn)開始，它掃描根節(jié)點(diǎn)的所有子節(jié)點(diǎn)，并檢查是否存在子節(jié)點(diǎn)l，這樣節(jié)點(diǎn)l中包含的符號(hào)等于ail。此操作以自頂向下的方式執(zhí)行。通常，假設(shè)符號(hào) ai1,ai2,… ,ail的子序列已經(jīng)匹配，當(dāng)前節(jié)點(diǎn)是 n odej-1，公共云將檢查nodej-1的所有子節(jié)點(diǎn)，并試圖找出某個(gè)節(jié)點(diǎn)，例如nodej中包含的符號(hào)等于aij。如果存在這樣的節(jié)點(diǎn)，則當(dāng)前節(jié)點(diǎn)設(shè)置為nodej，并且匹配下一個(gè)aij+1對(duì)象，否則跳到步驟3。

Step.3假設(shè)當(dāng)前節(jié)點(diǎn)nodej沒有與符號(hào)aij+1匹配的子節(jié)點(diǎn)，則公共云將分別為所有其余的符號(hào)（i.e. aij+1, aij+2,… ,ail） 構(gòu)建節(jié)點(diǎn) n odej+1,… ,n odejl，并將它們鏈接為附加于nodej的節(jié)點(diǎn)列表。最后，添加由ai標(biāo)識(shí)為附加 n odejl的葉節(jié)點(diǎn)的另一個(gè)節(jié)點(diǎn)。

Search：假定合法用戶希望使用關(guān)鍵字w和權(quán)限｛pi｝ 搜索外包文件，則公共云將從私有云接收 （tpi, wi） 。對(duì)于每個(gè) （tpi, wi） ，公共云將執(zhí)行類似于上述三個(gè)步驟的操作。一個(gè)例外是，如果匹配失敗（即當(dāng)前節(jié)點(diǎn)沒有可以匹配符號(hào)的子節(jié)點(diǎn)），則中止對(duì)（tpi, wi） 的搜索。否則，通過葉節(jié)點(diǎn)中的標(biāo)識(shí)符ai獲取相應(yīng)的（Ctf, Cske）。

因此，為了解決Merkle樹遍歷問題，我們使用了文獻(xiàn)[17]中的高效算法中的一些工具來解決時(shí)空問題。此外，為了優(yōu)化Merkle哈希樹遍歷過程中的時(shí)間空間約束，我們?cè)O(shè)計(jì)了一個(gè)優(yōu)化的三值搜索嘗試（ternary search tries，TST），這是一種將快速排序和基排序相結(jié)合的排序算法。因此，它與最著名的C-排序碼競(jìng)爭(zhēng)。它比傳統(tǒng)的散列和其他常用的搜索方法更快，如表1所示。

表1 不同搜索方法的執(zhí)行消耗

TST節(jié)省空間，但會(huì)隨著字符串?dāng)?shù)N的增加而增加。因此，遍歷問題是如何有效地計(jì)算從第一個(gè)葉子到最后一個(gè)葉子依次開始的所有葉的身份驗(yàn)證路徑，以最小的時(shí)空開銷。因此，它意味著要分析單件屬性ai的最佳分布，以提高所提出的解決方案的效率，即找到填充樹的字符串或?qū)傩訬的最佳數(shù)量。在這里，我們使用文獻(xiàn)[18]的庫(kù)恩塔克條件（karush kuhn-tucker，KKT）來解決約束優(yōu)化問題，以找到最小單件類標(biāo)識(shí)符數(shù)目，從而為所提出的遍歷算法效率提供最佳的安全級(jí)別。

因此，在通用分解表中，任意選擇N個(gè)選項(xiàng)（條目）中的一個(gè)元素，第i個(gè)元素成為單個(gè)元素的概率為

將變量xi用來表示第i個(gè)元素是否為單例的指標(biāo)，其期望值可計(jì)算為：

最后，對(duì)于具有最大不同值總數(shù)N的分解表，單例擬標(biāo)識(shí)符的最優(yōu)數(shù)目為。利用該最優(yōu)數(shù)填充三值搜索樹，通過解決時(shí)空代價(jià)問題，提高了Merkle樹遍歷算法的性能。

3 Op_FHE 效率和安全分析

為了優(yōu)化 Map階段的外包數(shù)據(jù)處理，防止Reduce階段的中間數(shù)據(jù)泄露，以加強(qiáng)Mapreduce框架上的數(shù)據(jù)隱私。本文的主要目標(biāo)是對(duì)Map階段（輸入文件分解）和Reduce階段（密文檢索）過程進(jìn)行安全優(yōu)化。因此,我們實(shí)現(xiàn)一個(gè)標(biāo)量?jī)?yōu)化基于同態(tài)的MapReduce方案（Op_FHE）,它包含注 冊(cè)KeyGen（ke） 、 加 密KeyGen（ke） 、 解 密Decrypt（c）和檢索 R etrieval（c）等四個(gè)部分。修改后的輸入文件分割算法如算法1所示。

該算法用FS表示的所選特征子集，其初始化為空集，將輸入文件分割為子集。通過在選定的特征子集中添加一個(gè)特征fd（其中d∈ ［1 ,D］），生成一個(gè)候選特征子集FC，并用算法2計(jì)算哈希索引IWIFC。然后，該算法刪除該特征并添加另一個(gè)特征以生成新的候選項(xiàng)。也就是說，所選候選子集中的新特性將被添加到所選的特征子集中。因此，該算法通過迭代添加一個(gè)特征（如果使用了浮動(dòng)策略，則添加固定的特征數(shù)）來增加所選的特征子集，直到達(dá)到閾值為止。需要指出的是，本文提出的算法與文獻(xiàn)[19]中現(xiàn)有算法的主要區(qū)別在于：我們的算法基于哈希索引值生成高度相關(guān)的數(shù)據(jù)子集。因此，在壓縮階段的密文檢索過程在速度上會(huì)更有效。

為了驗(yàn)證Op_FHE的效率，我們使用HElibmaster-2018.3庫(kù)對(duì)Op_FHE系統(tǒng)進(jìn)行了驗(yàn)證。并將結(jié)果與現(xiàn)有的盲全同態(tài)Fhe_DFI_LM算法、原Fhe_Schr算法進(jìn)行了比較，證明了對(duì)候選解的有效分析。表2和圖3顯示了我們提出的解決方案（Op_FHE）與相關(guān)工作（FHE_DFI_LM和FHE）的平均性能。

表2 不同算法的平均耗時(shí)對(duì)比

圖3 不同算法的性能比較

可以看出，我們的Op_FHE在Map階段的數(shù)據(jù)處理耗時(shí)，比 FHE_DFI_LM （13078 ms）少2.5倍（5932 ms），比FHE（11684 ms）少2倍。這個(gè)結(jié)果是在文件分解過程中，通過使用最優(yōu)數(shù)，對(duì)給定的N項(xiàng)分解表進(jìn)行優(yōu)化選擇得到的。因此，對(duì)于給定的數(shù)據(jù)集，我們的算法預(yù)先計(jì)算出精確的最優(yōu)子集數(shù)（特征選擇）和Map工作進(jìn)程，以加快Map階段的分割和數(shù)據(jù)分配過程。并且子集的每個(gè)元素（特征）都由一個(gè)有效的特征選擇算法（參見算法1）來選擇。

基于上述有效的實(shí)驗(yàn)結(jié)果，提出的優(yōu)化方案Op_FHE在不影響密碼體制的情況下，無疑加快了系統(tǒng)的設(shè)置（輸入文件分解）和密文檢索時(shí)間。因此，圖3表明，在密文檢索和計(jì)算成本降低方面，所提出的方案更為有效。由于同態(tài)密碼系統(tǒng)非常昂貴，因此，我們的解決方案是一個(gè)可靠的替代方案，可以最大限度地降低總體計(jì)算和通信成本。

我們的安全方案是采用基于屬性的加密（Attribute-Based Encryption，ABE），將屬性和策略分別嵌入到密鑰Ctf和密文Cske中，加密為。因此攻擊者應(yīng)首先解密Cske，但是，由于這種會(huì)話密鑰受ABE方案的保護(hù)。因此，數(shù)據(jù)的保密性可以歸結(jié)為ABE的保密安全性。由于策略嵌入密文中，優(yōu)化方案Op_FHE做到了一個(gè)粒度可以細(xì)化到屬性級(jí)別的加密訪問控制，實(shí)現(xiàn)數(shù)據(jù)機(jī)密性。

為了在數(shù)據(jù)認(rèn)證路徑和動(dòng)態(tài)方面提高所提解決方案的安全性，我們采用Merkle的哈希樹來存儲(chǔ)元數(shù)據(jù)分解 ai∈A= ｛ a1, a2,… ,an｝ ，它完全不受任何數(shù)論猜想的限制，從而實(shí)現(xiàn)自由安全保護(hù)。因此，提出的解決方案（優(yōu)化的fhe_SHCR）可以加強(qiáng)數(shù)據(jù)隱私保密性。

4 結(jié)論

針對(duì)MapReduce框架下的數(shù)據(jù)隱私問題，提出了在Map階段優(yōu)化外包數(shù)據(jù)處理、防止中間數(shù)據(jù)泄露。實(shí)現(xiàn)了一個(gè)安全的前端數(shù)據(jù)庫(kù)管理代理：匿名者及其三個(gè)組件（分解表、查詢處理和元數(shù)據(jù)倉(cāng)庫(kù)），以增強(qiáng)我們提出的解決方案的數(shù)據(jù)安全機(jī)制。密碼系統(tǒng)工具是一個(gè)標(biāo)量同態(tài)加密，在更安全和優(yōu)化的設(shè)計(jì)中對(duì)加密的數(shù)據(jù)執(zhí)行一些計(jì)算。實(shí)驗(yàn)結(jié)果表明，優(yōu)化后的密碼體制 Op_FHE是降低通信和計(jì)算成本的有效選擇。在實(shí)際應(yīng)用中，它采用了一個(gè)優(yōu)化的分解表作為輸入文件，提高了MapReduce環(huán)境下密文檢索過程的速度和準(zhǔn)確性。在此基礎(chǔ)上，應(yīng)用優(yōu)化的三值搜索嘗試（TST）算法，解決了元數(shù)據(jù)存儲(chǔ)庫(kù)中Merkle樹結(jié)構(gòu)遍歷的元數(shù)據(jù)動(dòng)態(tài)和時(shí)空代價(jià)約束問題。