姚友罡,肖 錚,2

(1.成都東軟學(xué)院 保衛(wèi)部，成都 611844;2.四川工商職業(yè)技術(shù)學(xué)院 信息工程系， 成都 611830)

0 引言

大數(shù)據(jù)分析是企業(yè)對外決策的關(guān)鍵環(huán)節(jié)之一，決策的數(shù)據(jù)往往來自不同的數(shù)據(jù)源。例如，從企業(yè)自身數(shù)據(jù)到城市數(shù)據(jù)、從基因數(shù)據(jù)到網(wǎng)絡(luò)數(shù)據(jù)等，跨數(shù)據(jù)實體(數(shù)據(jù)源)分析是數(shù)據(jù)分析的迫切需求。然而，隱私數(shù)據(jù)或機密數(shù)據(jù)泄露已成為跨數(shù)據(jù)源分析的主要障礙，工業(yè)界、學(xué)術(shù)界致力于尋找跨數(shù)據(jù)源分析的實用技術(shù)。安全多方計算(MPC)作為一種密碼技術(shù)，允許獨立的參與方在不泄露自身私有輸入的情況下聯(lián)合執(zhí)行所需的計算，是跨數(shù)據(jù)源分析的常用技術(shù)之一。自20世紀(jì)70年代末提出MPC概念[1-3],到如今的30多年歷史里，一直是密碼學(xué)研究的活躍領(lǐng)域。近年來，MPC的研究取得了重大進展[4-6]，然而，由于以下四方面的原因，使得MPC的研究仍局限于概念驗證階段[7]：

1)因涉及密碼學(xué)相關(guān)技術(shù)，MPC應(yīng)用、部署較難。

2)MPC無法利用現(xiàn)有的成熟算法，需要從頭開始部署。

3)現(xiàn)有的MPC引擎是孤立設(shè)計的，不適應(yīng)如MapReduce之類的云編程范式。

4)MPC開發(fā)所需的編程/工程專業(yè)知識異于在敏感數(shù)據(jù)集上評估隱私泄露所需的專業(yè)知識。

與專注于MPC協(xié)議原語的實現(xiàn)不同，從MPC技術(shù)在云計算環(huán)境中的實際應(yīng)用與企業(yè)項目開發(fā)角度考慮如何處理這些問題，即將MPC集成到云計算的編程范式中。更具體地說，同時擴展了MPC的MapReduce實現(xiàn)技術(shù)，允許多方利用自己的計算資源，支持多方計算(MPC)和MapReduce的混合編程。本文的創(chuàng)新點和主要貢獻如下：

首先構(gòu)建了MPC最小化的基本思想及實現(xiàn)步驟；其次，以線性聚類為例，提出了一種在確保安全性的同時最小化MPC實用計算的方法。該方法允許將計算劃分為MPC計算部分和非MPC計算部分，其中非MPC計算部分在本地簇完成，無需多方通信，可并發(fā)執(zhí)行，從而提高計算效率。最后，本文構(gòu)建了一個實驗原型系統(tǒng)，并以UCI數(shù)據(jù)集為例，驗證了提出技術(shù)的可行性與正確性。

基于以上目標(biāo)，全文的結(jié)構(gòu)安排為。第1節(jié)討論了大數(shù)據(jù)相關(guān)技術(shù)，特別是MapReduce編程基礎(chǔ)，常用的MPC實現(xiàn)技術(shù)以及MPC與非MPC相關(guān)的劃分技術(shù)。本文的技術(shù)創(chuàng)新性工作在第2節(jié)中展示，以線性聚類為例，分析MPC與非MPC劃分方法及與MapReduce混合編程技術(shù)。第3節(jié)展示了以UCI機器學(xué)習(xí)數(shù)據(jù)集為基礎(chǔ)的實驗及實驗結(jié)果數(shù)據(jù)。最后，第5節(jié)為結(jié)論以及對下一步工作的展望。

1 相關(guān)工作

文中主要討論提高MPC計算效率的技術(shù)與方法，即如何有效地將MPC技術(shù)融入大數(shù)據(jù)處理流程，不涉及MPC協(xié)議原語的實現(xiàn)或大數(shù)據(jù)處理等技術(shù)問題。與本文相關(guān)的工作包括Pyspark數(shù)據(jù)分析技術(shù)、MPC技術(shù)以及提高MPC運行效率的現(xiàn)有方法與實踐等。

1.1 Pyspark數(shù)據(jù)分析技術(shù)

Pyspark源自Apache的Spark項目，是為實現(xiàn)用Python語言編寫Spark應(yīng)用程序而對Spark的封裝。作為Hadoop中MapReduce的改進與替代方案，Spark引入了彈性分布式數(shù)據(jù)集(RDD, Resilient Distributed Datasets)這一基于內(nèi)存的數(shù)據(jù)結(jié)構(gòu)，以適應(yīng)交互式、實時、分布式與容錯的低延時應(yīng)用。Spark使應(yīng)用開發(fā)人員專心于業(yè)務(wù)邏輯的開發(fā)而無需擔(dān)心基礎(chǔ)架構(gòu)、環(huán)境等問題。文中利用Spark的并行處理能力，提高非MPC類計算的效率(完成的主要計算任務(wù)是矩陣乘法，該部分的內(nèi)容在2.3節(jié))。

1.2 MPC技術(shù)

安全多方計算作為一種通用的加密原語，在保護個人或組織數(shù)據(jù)隱私的同時實現(xiàn)多方私有數(shù)據(jù)的分析與挖掘。常借助電路 (布爾電路或算術(shù)電路)的概念以建立MPC的形式化定義。通用的安全多方計算的定義如定義1所示。

定義1：安全多方計算

在n個互不信任的參與方之間的安全多方計算(函數(shù))F，常用是一個三元組來表示：

F=(C,Ti,To}

(1)

其中:C表示電路，是用戶需求、功能、算法的抽象；Ti表示輸入方及其輸入數(shù)據(jù)的集合；To表示輸出方及其輸出數(shù)據(jù)的集合。在F的計算過程中，要求任意參與方pi除獲得自身的輸出信息外，均不能獲得其他參與方的任何輸入或輸出信息。MPC的這一定義是較為嚴格的，實際應(yīng)用中往往放寬某些限制，以提高效率。

已有一些基本子協(xié)議(技術(shù))用于構(gòu)建MPC協(xié)議：這些子協(xié)議(技術(shù))主要包括：1)不經(jīng)意傳輸(OT,oblivious transfer)協(xié)議；2)加密電路(GC,garbled circuit)技術(shù);3)同態(tài)加密(HE,homomorphic encryption)技術(shù)以及秘密共(SS,secret sharing)協(xié)議。從這些基礎(chǔ)協(xié)議構(gòu)建MPC實用程序不是易事，需要了解密碼學(xué)的相關(guān)知識。目前業(yè)界已提出MPC的實可編程式現(xiàn)框架，這些框架主要包括Obliv-C、ObliVM、SPDZ、Sharemind等。在實際應(yīng)用中，借助于技術(shù)實現(xiàn)框架，即便是不具備密碼學(xué)專業(yè)知識的應(yīng)用程序開發(fā)人員也能編寫實現(xiàn)數(shù)據(jù)安全分析的任務(wù)。另一方面，雖然這些框架都是基于MPC技術(shù)獨立實現(xiàn)的，但各自擁有不同的特性及優(yōu)缺點。因ObliVM及SPDZ不再維護或更新，本文的實驗部分，采用了Obliv-c及Sharemind的作為MPC的評估版。為此，表1列出了這兩種框架的特點差異。

表1 常用MPC實現(xiàn)框架特點對比

1.3 現(xiàn)有方法

在本小節(jié)中，先后簡要描述了加速MPC計算的方法，以提高多方計算高效可行。目前，有兩種互補的提高MPC計算效率的方法。其一是直接提高MPC計算協(xié)議并發(fā)度；其二采用混合MPC計算。前者從MPC協(xié)議角度出發(fā)，通過并發(fā)實現(xiàn)茫然計算。這種對MPC效率的改進有限，特別是不適應(yīng)大數(shù)據(jù)處理需求。后者將安全計算按照一定的規(guī)則劃分為不安全的非MPC類計算及少量的安全MPC類計算，通過提高非MPC類計算的效率間接提高計算的整體效率。兩種方式都基于到MapReduce編程范式的基本思想，文中著眼于第二種實現(xiàn)方式。

文獻[9-10]先后提出并證明“并行有助于不經(jīng)意”以及流式MapReduce的概念以及任何在流式MapReduce抽象中編寫的程序都可以被轉(zhuǎn)換為高效的不經(jīng)意的算法，并利用這一想法涉及了網(wǎng)絡(luò)ORAM方案。Liu等人[11]等人則基于MapReduce編程抽象構(gòu)建MPC實現(xiàn)框架，即ObliVM 同年，Kartik等[4]設(shè)計并實現(xiàn)的GraphSC框架都屬于提高MPC計算協(xié)議并發(fā)度的范疇。

Rastogi[12]等首先提出了混合MPC計算方法，其中非MPC的計算，各參與方在本地獨立完成作業(yè)，類似普通的應(yīng)用程序。MPC計算部分由各參與方協(xié)同，共同完成。然而，在Rastogi等人的設(shè)計中，需要程序設(shè)計人員手動標(biāo)注非MPC類及MPC類計算。雖然這些標(biāo)注是精細化的，但程序設(shè)計人員需要具備專業(yè)的MPC知識，使其應(yīng)用受到限制。在此基礎(chǔ)上，文獻[12]進一步將MapReduce編程范式融入到本地非MPC計算中。在他們的設(shè)計中，參與計算的節(jié)點可以分為兩種類型：控制節(jié)點和工作節(jié)點。其中，控制器節(jié)點作為任務(wù)分配器、作業(yè)監(jiān)督器以及任務(wù)同步器并作為節(jié)點間共享公共數(shù)據(jù)的存儲介質(zhì)；工作節(jié)點跨參與方完成MPC任務(wù)，如訪問參與方自身的私有數(shù)據(jù)，充當(dāng)本地MapReduce任務(wù)的執(zhí)行器。文獻[14-15]借助有向無環(huán)圖(DAG)研究與查詢相關(guān)的MPC計算及其可擴展性問題。與上述工作不同，文中以線性回歸問題及其擴展為主要研究目標(biāo)。

2 實現(xiàn)方法

本節(jié)首先介紹了最小化安全多方計算的基本思想及步驟，然后以線性回歸模型為例具體討論相關(guān)技術(shù)及方法。

2.1 基本思想及步驟

本文提出的最小化安全多方計算(下文常稱為計算)的基本思想是使MPC類的計算盡可能少，只實現(xiàn)必要的MPC，即能不用MPC實現(xiàn)的盡可能不采用。如何能最小化MPC類的計算，本文提出將計算分解、轉(zhuǎn)換為有向圖，進而簡化MPC，重構(gòu)MPC算法。步驟總結(jié)如下：

1)確定數(shù)據(jù)的屬主。根據(jù)算法所屬數(shù)據(jù)屬主的差異，確定數(shù)據(jù)的“主人”。

2)確定信任標(biāo)注(可選)。根據(jù)數(shù)據(jù)屬主，確定參與者之間的信任關(guān)系。這種信任關(guān)系可能繁殖，或者終止，這些工作采用自動以及交互的方式來實現(xiàn)。

3)算法重寫。即獲得與當(dāng)前算法等效的算法，但其需要的MPC類計算更少。區(qū)分本地計算以及多方計算等；采用的技術(shù)包括信任繁衍、組合、分割。

4)MPC優(yōu)化。MPC優(yōu)化技術(shù)包括：MPC前端(MPC操作與本地明文操作之間的邊界)下移、MPC前端上移以及混合操作(如混合聯(lián)接、公共聯(lián)接和混合聚合)等。

5)算法優(yōu)化。除了對單個計算節(jié)點的優(yōu)化，算法的整體性能也應(yīng)優(yōu)化。常用的方法是減少對MPC底層算法的依賴。

本節(jié)的余下部分以線性回歸預(yù)測模型為例，討論最小化MPC計算的實現(xiàn)方法。

2.2 線性回歸模型

線性回歸預(yù)測模型是一種有監(jiān)督的學(xué)習(xí)算法，是許多機器學(xué)習(xí)算法的基本組成部分。它通過擬合訓(xùn)練數(shù)據(jù)集的線性曲線來獲得目標(biāo)模型并實現(xiàn)預(yù)測，該模型的通用公式如式(2)所示。

Y=Xθ+ε

(2)

式中，Y∈Rn，是由n個元素的列向量組成的目標(biāo)變量，也稱為標(biāo)簽或因變量；X∈Rn×d，是n行d維的輸入向量，即因變量；θ∈Rn，稱為擬合參數(shù)或模型參數(shù)，ε是為了平衡模型兩邊的值而添加的部分，稱為誤差項。

求解方程(1)中的模型參數(shù)的過程稱為模型的學(xué)習(xí)，常通過最小化均方誤差來求解，如式(3)所示。

(3)

式(3)稱為線性回歸的目標(biāo)函數(shù)。更一般地，線性回歸模型的目標(biāo)函數(shù)可寫為如式(4)所示。

(4)

首先展開平方項得等待如下的式子：

(5)

式(5)對θ的一階偏導(dǎo)數(shù)為：

(6)

在式(6)中，令導(dǎo)數(shù)等于0，可知回歸系數(shù)滿足式(7):

(7)

如第1節(jié)所述，提高大數(shù)據(jù)分析的安全計算效率的基本思路是，盡量降低MPC類計算的需求，為此文中采用如下兩階段的優(yōu)化措施。

2.3 數(shù)據(jù)計算優(yōu)化

該階段從計算的內(nèi)在需求出發(fā)，找出MPC類計算與非MPC類計算部分。為計算式(7)需考慮兩種不同的數(shù)據(jù)分布情況：1)數(shù)據(jù)在參與方間水平分割，即一個參與者有一條完美的；2)數(shù)據(jù)在參與方間垂直分割。

2.3.1 數(shù)據(jù)水平分割

該階段從計算的內(nèi)在需求出發(fā)，找出MPC類計算與非MPC類計算部分。為計算式(7)需考慮兩種不同的數(shù)據(jù)分布情況：1)數(shù)據(jù)在參與方之間水平分割；2)數(shù)據(jù)在參與方之間垂直分割。

2.3.2 數(shù)據(jù)垂直分割

在垂直分割下，數(shù)據(jù)X按屬性劃分，并由各參與方持有。即X=[x1,x2,...,xi]，xi∈Rn×β(β?d)由參與方i持有。特別地，考慮兩方參與的情況，即數(shù)據(jù)X被劃分成X1，X2兩個子集，并分別由參與方p1和p2方持有。變量Y由其中一方持有，這里假設(shè)Y由p2持有。則式(7)中的因子XTX可以用式(8)表示：

(8)

XTY的結(jié)果如式(9)所示：

(9)

2.4 計算流程優(yōu)化

該階段從計算需求出發(fā)，使用DAG (Directed Acyclic Graph)圖來表示計算流程，并利用DAG圖的內(nèi)在聯(lián)系，進一步降低MPC類的計算需求。在利用共軛梯度下降法求解式(7)的解時，參考文獻[8]可得如算法1所示求解思路。

使用DAG圖表示程序流程及模板的通用性，如圖1(a)所示。圖中圓形內(nèi)的阿拉伯?dāng)?shù)字對應(yīng)算法1中的序號，圓形旁的字符是參與方的縮寫。

圖1 安全計算流程及其改進措施

算法1：優(yōu)化的安全多方(以兩方為例)計算求解算法

參與方：數(shù)據(jù)提供者p1、p2，可信初始值設(shè)定者TI/加密服務(wù)提供商CSP、電路評估者evaluator

輸出：數(shù)據(jù)提供者共同學(xué)習(xí)到的模型參數(shù)θ

6)CSP生成重構(gòu)及求解式(6)的混淆電路C ，并將其發(fā)送給評估者evaluator。

7)數(shù)據(jù)提供者與加密服務(wù)提供商CSP之間利用茫然傳輸協(xié)議獲取其在混淆電路C中的共享輸入，并將該共享值轉(zhuǎn)發(fā)給電路評估者evaluator。

對于處理的數(shù)據(jù)，為提高安全計算的效率，增加三方面的額外信息：1) 增加計算數(shù)據(jù)所有者域及數(shù)據(jù)所有者傳遞規(guī)則(某計算節(jié)點的數(shù)據(jù)所有者域由該節(jié)點的數(shù)據(jù)提供者及其輸入弧傳遞進來的數(shù)據(jù)所有者共同確定，數(shù)據(jù)所有者沿圖結(jié)構(gòu)向下傳遞，受信任標(biāo)識集的影響而可能終止)。2) 增加計算結(jié)果數(shù)據(jù)的接收者域(由弧的終點確定)。3) 增加數(shù)據(jù)安全處理需求，用于表示該數(shù)據(jù)是否需要在MPC下完成計算。例如，圖1(a)中，計算節(jié)點①的沒有輸入弧(入度為0)，即該節(jié)點沒有輸入數(shù)據(jù)，其數(shù)據(jù)所有者域僅包含該節(jié)點自身，即可信初始值設(shè)定者TI。該節(jié)點有兩條輸出弧(出度為2)，表示該節(jié)點有兩條輸出信息，其接收者分別是兩條弧指向的節(jié)點，即數(shù)據(jù)提供方p1和p2。同時該節(jié)點數(shù)據(jù)不包含隱私信息，僅需通過安全通道傳遞給接收方即可，可見針對該節(jié)點的計算無需在MPC下執(zhí)行。

增加數(shù)據(jù)信任標(biāo)識集，即由數(shù)據(jù)提供者授權(quán)的可在明文狀態(tài)下(非MPC計算類)使用其數(shù)據(jù)的使用方構(gòu)成的集合。例如公共數(shù)據(jù)或多方共享數(shù)據(jù)的所有者構(gòu)成了這些數(shù)據(jù)的信任標(biāo)識集，同時信任標(biāo)識集也可以是權(quán)威數(shù)據(jù)管理機構(gòu)，他們擁有參與方的原始數(shù)據(jù)。信任標(biāo)識集里的各參與方在明文狀態(tài)下使用數(shù)據(jù)，降低了計算成本。

節(jié)點分裂與繁殖，即將復(fù)雜的MPC類計算節(jié)點細分成MPC類計算節(jié)點與非MPC類計算節(jié)點。目前，存在3種方式實現(xiàn)節(jié)點分裂與繁殖。其一是利用上述兩項措施，即當(dāng)節(jié)點計算執(zhí)行參與方是節(jié)點計算數(shù)據(jù)的所有者或者執(zhí)行方屬于節(jié)點數(shù)據(jù)的信任標(biāo)識集，該類計算可以劃分為非MPC類計算。其二是通過添加混合協(xié)議，即將部分高負載的MPC類計算在可信方完成，從而分離出非MPC計算類與輕負載的MPC計算類，其三是利用數(shù)據(jù)已有計算結(jié)果及數(shù)據(jù)混淆技術(shù)減少計算茫然性的需求。節(jié)點分裂與繁殖進一步減輕了MPC計算負載。

圖1(a)的DAG圖，在經(jīng)過上述處理后步驟后的DAG圖如圖1(b)所示。其中帶方框的節(jié)點屬于非MPC計算類。從中可以看出MPC安全計算結(jié)點的數(shù)量有所降低。

3 實驗與評估

3.1 實驗設(shè)置

本節(jié)建立了以Python編程語言為基礎(chǔ)的實驗開發(fā)環(huán)境。為突出實驗效果，實驗共設(shè)置了4個參與節(jié)點，各節(jié)點都配置有4核CPU(2.4G)以及8G的內(nèi)存。其中2個作為數(shù)據(jù)提供者；一個作為可信初始值設(shè)定者TI及加密服務(wù)提供商；另一個作為數(shù)據(jù)評估者。各參與節(jié)點都配備有本地Pyspark組件、MPC組件、私有數(shù)據(jù)訪問與存儲接口以及用于與控制器節(jié)點通信的網(wǎng)絡(luò)接口。其中，評估節(jié)點以及兩個數(shù)據(jù)提供者節(jié)點組成了含3節(jié)點的Spark獨立集群。評估節(jié)點作為Spark的主節(jié)點，數(shù)據(jù)提供者節(jié)點是Spark的工作者節(jié)點。MPC組件的實現(xiàn)采用的是Obliv-c，通過Python的模板替換工具Pystache，以及算法流程的DAG圖自動生成MPC與非MPC代碼。評估用的數(shù)據(jù)集來自UCI機器學(xué)習(xí)數(shù)據(jù)集，數(shù)據(jù)集及其主要特性如表2所示。各數(shù)據(jù)集按7∶3的比例隨機選取作為訓(xùn)練數(shù)據(jù)集與測試數(shù)據(jù)集，并將數(shù)據(jù)按1∶1的比例隨機分配給數(shù)據(jù)提供者p1和p2。

表2 實驗數(shù)據(jù)集及其主要特性

基于以上的實驗設(shè)置，主要完成了以下兩方面的評估指標(biāo)。

運行時間：針對不同數(shù)據(jù)集，在不同MPC優(yōu)化層次下(包括在Pyspark下的全明文技術(shù))運行時間不同的優(yōu)化參數(shù)對MPC運行時間的影響。

預(yù)測精度：即在各種設(shè)置下所獲得的預(yù)測值與真實值之間的根均方誤差(RMSE)。

3.2 實驗評估

本節(jié)從運行時間及精度兩方面討論算法的性能。

3.2.1 運行時間

針對不同的數(shù)據(jù)集，在相同的設(shè)置(如3.1節(jié)所述)不同的安全配置(全明文Pyspark、現(xiàn)有安全多方計算Obliv-c以及文中的優(yōu)化設(shè)置)下，各重復(fù)實驗10次，記錄其平均值，實驗結(jié)果如表3所示。

表3 不同設(shè)置下各數(shù)據(jù)集所需運行時間

實驗結(jié)果表明，所有不同的安全配置下運行時間都隨記錄數(shù)的增加而增加，同時運行時間也受數(shù)據(jù)維度的影響。總體而言，全明文分析所需的時間最少，現(xiàn)有安全多方計算(Obliv-c)所需時間最多，本文提出的方法與全明文分析所需時間十分接近。另外，可以注意到當(dāng)記錄數(shù)達到萬級以上時，Obliv-c的運行耗時迅速增加，如本例中的CT slices數(shù)據(jù)集，其運行時間在25分鐘。當(dāng)記錄數(shù)繼續(xù)增加時，該方案甚至不可接受，如本例的Gas sensor數(shù)據(jù)集?？梢娢闹刑岢龅姆椒@著降提高了運行效率，提高了應(yīng)用在時間的可行性。接下來分析該方案在精度上能否滿足要求。

3.2.2 精度

與3.2.1節(jié)運行時間設(shè)置相同，同時記錄了現(xiàn)有安全多方計算Obliv-c以及文中的優(yōu)化設(shè)置兩種情況下的根均方誤差，如表4所示。

表4 不同設(shè)置下各數(shù)據(jù)集的根均方誤差

可見，各種方法在精度上的差異并不顯著，3種安全配置下的根均方誤差大致相同，即文中設(shè)計的方法(在現(xiàn)有技術(shù)條件下)滿足精度需要。

4 結(jié)束語

本文以數(shù)據(jù)分析中的常用方法——線性回歸為例討論在安全多方計算中如何提高數(shù)據(jù)分析的效率。提出的優(yōu)化措施包括：計算優(yōu)化以及執(zhí)行流程優(yōu)化。在實驗部分，針對UCI真實數(shù)據(jù)集完成的實驗驗證。實驗結(jié)果表明，文中提出的方案在精度、時間上都是可行的。下一步準(zhǔn)備將混合MPC以及MPC并行化相結(jié)合，進一步驗證文中提出的方法的可行性。另一方面，如何將混合MPC技術(shù)推廣，以適應(yīng)更多的真實應(yīng)用場景也是未來工作方向之一。同時如何減少對可信初始值設(shè)定者、加密服務(wù)提供商、電路評估者的信任和依賴，從而提高系統(tǒng)可信性，也是未來應(yīng)考慮的主要工作之一。以去信任為中心的區(qū)塊鏈技術(shù)提供了相應(yīng)的解決思路。