俞強(qiáng)生，古天龍，徐周波，寧黎華

(桂林電子科技大學(xué) 廣西可信軟件重點(diǎn)實(shí)驗(yàn)室，廣西 桂林541004)

計(jì)算機(jī)和網(wǎng)絡(luò)技術(shù)的迅猛發(fā)展為多方聯(lián)合計(jì)算提供了大量應(yīng)用場(chǎng)景。然而，信息化發(fā)展帶來便利的同時(shí)，數(shù)據(jù)安全與隱私保護(hù)問題不斷凸顯，成為制約多方聯(lián)合計(jì)算發(fā)展的最大障礙。安全多方計(jì)算(secure multi-part computation，簡(jiǎn)稱SMC)概念最早由圖靈獎(jiǎng)獲得者Yao提出［1］，其核心思想是在保護(hù)隱私的前提下，互不信任的參與方進(jìn)行聯(lián)合計(jì)算，并得到預(yù)期執(zhí)行結(jié)果。安全多方計(jì)算在隱私保護(hù)基因計(jì)算［2］、保密計(jì)算［3］等許多領(lǐng)域有廣泛應(yīng)用。

決策函數(shù)有效表示問題是安全多方計(jì)算研究的熱點(diǎn)問題，決策函數(shù)表示是否高效決定了協(xié)議效率的高低。Yao［4］最早提出用混淆布爾電路的方法解決決策函數(shù)表示問題，但布爾電路不能描述偽布爾函數(shù)。同時(shí)，隨著決策函數(shù)復(fù)雜性增加，布爾電路中的電路門規(guī)模急劇增大，造成編碼規(guī)模大、計(jì)算復(fù)雜度高等問題。

符號(hào)描述技術(shù)是一種求解決策函數(shù)表示問題的新方法，其中有序二叉決策圖(ordered binary decision diagram，簡(jiǎn)稱OBDD)是布爾電路的一種緊湊表示方式。Kruger于2006年提出基于OBDD技術(shù)描述決策函數(shù)［5］，一定程度上降低了編碼復(fù)雜度，提高了協(xié)議效率。但是，OBDD是布爾電路方法基礎(chǔ)上的一種形式化表示，也不能描述偽布爾函數(shù)。在文獻(xiàn)［5］基礎(chǔ)上，古天龍等［6］提出基于代數(shù)決策圖(algebraic decision diagram，簡(jiǎn)稱ADD)技術(shù)取代符號(hào)OBDD刻畫決策函數(shù)，決策函數(shù)的表示形式由此得到極大擴(kuò)展。然而，符號(hào)ADD隨著決策函數(shù)復(fù)雜性增加，葉子節(jié)點(diǎn)規(guī)模會(huì)急劇膨脹，協(xié)議面臨狀態(tài)空間爆炸問題。

安全計(jì)算借助可編程通用電路，將函數(shù)描述及隱私數(shù)據(jù)作為輸入，進(jìn)行聯(lián)合計(jì)算并輸出結(jié)果［7］，但是，由于布爾電路本身固有的局限性，描述效率不夠理想。因此，Brickell等［8］使用分支程序(branching program，簡(jiǎn)稱BP)表示安全計(jì)算問題。為減少交互次數(shù)，降低協(xié)議復(fù)雜度，Mohassel［9］結(jié)合不經(jīng)意傳輸技術(shù)，提出基于不經(jīng)意傳輸BP的安全計(jì)算協(xié)議。

邊值二叉決策圖(edge-valued binary decision diagram，簡(jiǎn)稱EVBDD)作為表示偽布爾函數(shù)的一種新型數(shù)據(jù)結(jié)構(gòu)，極大改善了偽布爾函數(shù)和有限域取值函數(shù)的描述能力，在一定程度上解決了因決策函數(shù)規(guī)模增大而導(dǎo)致的狀態(tài)空間爆炸問題。為此，引入EVBDD的符號(hào)描述技術(shù)，利用其易操作和高緊湊性的優(yōu)點(diǎn)，給出一種基于EVBDD的決策函數(shù)表示方法，并設(shè)計(jì)一個(gè)效率高、評(píng)估計(jì)算簡(jiǎn)單且適用大多數(shù)決策函數(shù)的基于符號(hào)EVBDD的安全2方計(jì)算協(xié)議。同時(shí)，在分支程序的基礎(chǔ)上，提出一種分支程序的逆向評(píng)估方法，借助基于邊值二叉決策圖的安全2方計(jì)算協(xié)議為基礎(chǔ)協(xié)議，設(shè)計(jì)一個(gè)基于分支程序逆向評(píng)估的安全多方計(jì)算協(xié)議，此協(xié)議將傳統(tǒng)的2方計(jì)算擴(kuò)展到多方，其效率也有所提高。

1 預(yù)備知識(shí)

1.1 不經(jīng)意傳輸協(xié)議

定義1［10］2選1不經(jīng)意傳輸協(xié)議(O):參與者按行為劃分為發(fā)送方和選擇方。發(fā)送方輸入一串長(zhǎng)為t的字符串對(duì)∈{0，1}t，其中i=1，2，…，n，選擇方輸入選擇位b∈{0，1}。協(xié)議執(zhí)行完畢，選擇方獲得字符串，但無法知曉另一字符串，而發(fā)送方也無法獲知選擇方的選擇b。

1.2 同態(tài)加密(HE)

使用一種語義安全的加同態(tài)公鑰加密機(jī)制，加密機(jī)制的語義安全是指無法從特定密文中提取任何明文信息。

加同態(tài)加密算法具有如下性質(zhì):存在有效算法⊕，E(x+y)=E(x)⊕E(y)或x+y=D(E(x)⊕E(y))成立，并且不泄漏x和y。因此，加同態(tài)算法也可直接用于與常數(shù)k的乘法操作:kE(x)=E(kx)。對(duì)同態(tài)加密的實(shí)例化采用文獻(xiàn)［11］中的加密機(jī)制。

2 基于符號(hào)EVBDD的安全2方計(jì)算協(xié)議(協(xié)議1)

2.1 邊值二叉決策圖(EVBDD)

EVBDD［12］是在ADD的基礎(chǔ)上，在邊中引入權(quán)值提高子圖的共享度，進(jìn)而為函數(shù)值是整數(shù)的偽布爾函數(shù)提供一種更為規(guī)范、緊湊的表示形式。EVBDD不僅能像OBDD一樣實(shí)現(xiàn)布爾函數(shù)操作，還能像ADD一樣實(shí)現(xiàn)對(duì)偽布爾函數(shù)的布爾操作和算術(shù)操作。這里，決策函數(shù)的EVBDD表示建立在有序的基礎(chǔ)上。圖1和圖2是偽布爾函數(shù)f=3+5x1+6x2+x3分別在ADD和EVBDD符號(hào)表示下的圖形結(jié)構(gòu)，變量序?yàn)閤1＜x2＜x3。在輸入模式(0，1，0)下，函數(shù)f對(duì)應(yīng)的函數(shù)值為3+0+6+0=9。

圖1 偽布爾函數(shù)f=3+5x1+6x2+x3 ADD表示Fig.1 ADD for pseudo-Boolean functionf=3+5x1+6x2+x3

圖2 偽布爾函數(shù)f=3+5x1+6x2+x3 EVBDD表示Fig.2 EVBDD for pseudo-Boolean functionf=3+5x1+6x2+x3

2.2 協(xié)議流程

在符號(hào)EVBDD表示的基礎(chǔ)上，提出基于符號(hào)EVBDD的安全2方計(jì)算協(xié)議。假設(shè)參與計(jì)算雙方為Alice和Bob，輸入為:表示(偽)布爾函數(shù)f(x1，x2，…，xn)的EVBDD(f)，其中變量序?yàn)閤1＜x2＜…＜xn。Alice的輸入Xa=(x1，x2，…，xk)對(duì)應(yīng)EVBDD(f)中前k個(gè)變量，Bob的輸入Xb對(duì)應(yīng)后n-k個(gè)變量。預(yù)期輸出為:C=f(Xa，Xb)。

參與方Alice執(zhí)行協(xié)議的流程為:

1)用變量(x1，x2，…，xk)遍歷EVBDD(f)的前k個(gè)節(jié)點(diǎn)，約束后的初始節(jié)點(diǎn)記為v。

2)約束后的EVBDD(ffull|Xa)隨機(jī)產(chǎn)生n-k對(duì)節(jié)點(diǎn)的取值密鑰:，并為每個(gè)節(jié)點(diǎn)v分配節(jié)點(diǎn)密鑰sv。

3)為k+1層到n層的每個(gè)節(jié)點(diǎn)隨機(jī)分配一個(gè)標(biāo)簽，用l(v)表示節(jié)點(diǎn)v所處的層數(shù)。

4)為約束后的EVBDD(ffull|Xa)填充虛節(jié)點(diǎn)。

5)加密EVBDD(ffull|Xa)，每個(gè)節(jié)點(diǎn)密文都包含代表該節(jié)點(diǎn)位置的節(jié)點(diǎn)標(biāo)簽、該節(jié)點(diǎn)不同取值下的2條子密文。每條子密文又包含路徑中下一節(jié)點(diǎn)的標(biāo)簽、下一節(jié)點(diǎn)的節(jié)點(diǎn)密鑰、該節(jié)點(diǎn)取值時(shí)的邊值(也稱權(quán)值)。

6)Alice將k+1層到n層的節(jié)點(diǎn)密文和初始節(jié)點(diǎn)的節(jié)點(diǎn)密鑰sv發(fā)送給Bob。

參與方Bob執(zhí)行協(xié)議的流程為:

1)Bob獲取初始節(jié)點(diǎn)的節(jié)點(diǎn)密鑰sv，并通過nk次1-out-of-2不經(jīng)意傳輸獲得對(duì)應(yīng)其輸入的密鑰

2)Bob用獲得的密鑰解密，從Alice步驟5)獲取的密文得到C，即f(Xa，Xb)。

3 基于分支程序逆向評(píng)估的安全多方計(jì)算

3.1 分支程序

定義2［9］分支程序:分支程序是3元組〈{P1，P2，…，Pz}，L，R〉的有向無環(huán)圖，其中Pi(i=1，2，…，z)為節(jié)點(diǎn)集，且滿足以下條件。

1)P1，P2，…，Pd為決策節(jié)點(diǎn)(又稱內(nèi)部節(jié)點(diǎn)、非終節(jié)點(diǎn))，Pd+1，Pd+2，…，Pz為分類節(jié)點(diǎn)(終節(jié)點(diǎn))。

2)每個(gè)決策節(jié)點(diǎn)Pi(1≤i≤d)對(duì)應(yīng)一個(gè)2元組〈ti，αi〉，對(duì)應(yīng)輸入值V=v1，v2，…，vn。其中，ti為閥值，αi為輸入索引，vai為索引αi下的輸入值。

3)分類節(jié)點(diǎn)(又稱診斷節(jié)點(diǎn)、終節(jié)點(diǎn))即為葉子節(jié)點(diǎn)，每一個(gè)葉子節(jié)點(diǎn)都持有唯一的標(biāo)簽〈di〉。

4)L和R分別表示決策點(diǎn)Pi的左右分支索引函數(shù)的有向無環(huán)圖，若vai≤ti，索引為L(zhǎng)(i)，反之，則為R(i)。

分支程序的評(píng)估始于節(jié)點(diǎn)P1，若va1≤t1，h=L(1)，否則，h=R(1)。重復(fù)此過程計(jì)算Ph，直到獲取葉子節(jié)點(diǎn)。從分支程序的評(píng)估過程可知，評(píng)估順序從初始節(jié)點(diǎn)依次到葉子節(jié)點(diǎn)，稱為順序評(píng)估，順序評(píng)估的優(yōu)點(diǎn)在于評(píng)估層次明顯，過程簡(jiǎn)單。

3.2 分支程序的逆向評(píng)估

由分支程序的評(píng)估過程可知，評(píng)估信息需要交互。若考慮隱私因素，參與對(duì)象只能局限于2方，即所有決策節(jié)點(diǎn)為1方所有。鑒于此，引入分支程序的逆向評(píng)估方法，評(píng)估順序從葉子節(jié)點(diǎn)依次逆向直到初始節(jié)點(diǎn)，如此節(jié)點(diǎn)之間無需信息交互，各個(gè)評(píng)估節(jié)點(diǎn)可分屬不同參與方所有。其逆向評(píng)估過程如下:假設(shè)分支程序?yàn)椤磠P1，P2，…，P15}，L，R〉，其中P1，P2，…，P10為決策節(jié)點(diǎn)，P11，P12，…，P15為葉子節(jié)點(diǎn)，評(píng)估輸入V=v1，v2，v3，v4。如圖3、4所示，參與者4開始評(píng)估第4層節(jié)點(diǎn)，得到相應(yīng)葉子節(jié)點(diǎn)信息1、2、3、4，用此信息替代第4層節(jié)點(diǎn)內(nèi)容。依次逆向評(píng)估第3層節(jié)點(diǎn)，參與者3將評(píng)估得到的第4層節(jié)點(diǎn)的葉子節(jié)點(diǎn)信息替代第3層節(jié)點(diǎn)內(nèi)容，如此直到唯一一個(gè)葉子節(jié)點(diǎn)信息替代初始節(jié)點(diǎn)內(nèi)容，評(píng)估結(jié)束。

圖3 分支程序葉子節(jié)點(diǎn)評(píng)估Fig.3 The leaf nodes evaluation of branch program

圖4 分支程序第4層節(jié)點(diǎn)評(píng)估Fig.4 The fourth layer nodes evaluation of branch program

3.3 基于分支程序逆向評(píng)估的安全多方計(jì)算協(xié)議(協(xié)議2)

良好的隱私保護(hù)和對(duì)決策函數(shù)的有效表示是降低安全多方計(jì)算協(xié)議復(fù)雜度、提高協(xié)議效率的關(guān)鍵所在。為此，將安全多方計(jì)算任務(wù)分割成若干個(gè)子任務(wù)，在分支程序中不同決策節(jié)點(diǎn)處理不同子任務(wù)。其中，借助基于EVBDD的安全2方計(jì)算協(xié)議為基礎(chǔ)協(xié)議，分別處理各個(gè)子任務(wù)。

基于分支程序逆向評(píng)估的安全多方計(jì)算協(xié)議需要分3步:分支程序的混淆處理、不經(jīng)意傳輸選擇和安全計(jì)算的逆向評(píng)估。為保證隱私得到保護(hù)，需要將分支程序T轉(zhuǎn)換成混淆的分支程序T′。假設(shè)輸入V=v1，v2，…，vn，其長(zhǎng)度為l，具體算法如下。

算法1分支程序的混淆處理。輸入:分支程序T=〈{P1，P2，…，Pk}，L，R〉，pi=〈ti，αi〉為決策節(jié)點(diǎn)，其中i=1，2，…，d，pi=〈di〉為葉子節(jié)點(diǎn)，i=d+1，d+2，…，k。輸出:1)混淆后的安全分支程序T′。2)k對(duì)隨機(jī)l+l′值b1，b2，…，bk。3)2kl對(duì)隨機(jī)邊值密鑰，其中1≤i≤k，1≤j≤l。

算法步驟為:

1)令Q為集合{1，2，…，k}的隨機(jī)置換函數(shù)，且Q［1］=1。

2)為所有k個(gè)決策節(jié)點(diǎn)分配節(jié)點(diǎn)密鑰λ1，λ2，…，λk。

3)對(duì)i=1，2，…，k進(jìn)行遍歷。

4)為節(jié)點(diǎn)i分配邊值密鑰，，其中，j=1，2，…，l。

6)對(duì)所有節(jié)點(diǎn)編號(hào)進(jìn)行混淆，令ι=Q［i］。

7)若Pi是葉子節(jié)點(diǎn)，即Pi=〈di〉，則令Si={“l(fā)abel”，di}λι。

8)若Pi是決策節(jié)點(diǎn)，即Pi=〈ti，αi〉，則借助基于符號(hào)EVBDD的安全2方計(jì)算協(xié)議來刻畫評(píng)估該節(jié)點(diǎn)，并根據(jù)該EVBDD的最終計(jì)算結(jié)果x，計(jì)算x-(b′imod 2l)。

9)若步驟8)的計(jì)算結(jié)果小于閥值ti，則轉(zhuǎn)向左分支L，否則轉(zhuǎn)向右分支R。其中，L=(Q［L(i)］，KQ［L(i)］)，R=(Q［R(i)，KQ［R(i)］)，所有被評(píng)估計(jì)算的決策節(jié)點(diǎn)標(biāo)記為C。

10)對(duì)決策節(jié)點(diǎn)內(nèi)容進(jìn)行加密:Si={Ci}λι。

11)協(xié)議輸出:T′=〈{S1，S2，…，Sk}，k1〉，協(xié)議結(jié)束。

算法2不經(jīng)意傳輸選擇。輸入:長(zhǎng)為l的值V=v1，v2，…，vn，混淆后分支程序T′中的閥值ti，索引αi和混淆值bi。輸出:1)s1，s2，…，sk，其中對(duì)于任意i有si=vai+(bimod 2l)。2)對(duì)于任意i，用邊密鑰wi1，wi2，…，wil加密si，其中si又等價(jià)于vai+(b′imod 2l)。

算法步驟為:

1)各參與方構(gòu)造相應(yīng)的同態(tài)加密方案，并將公鑰發(fā)送給服務(wù)器。

全省礦業(yè)綠色發(fā)展現(xiàn)場(chǎng)會(huì)在湖州召開（省廳新聞宣傳中心） ............................................................................9-6

2)對(duì)i=1，2，…，k進(jìn)行遍歷。

3)參與方對(duì)各自的隱私輸入進(jìn)行加密，并將加密結(jié)果E［vi］發(fā)送給服務(wù)器。

4)服務(wù)器接收公鑰以及密文E［vi］，同態(tài)計(jì)算E［vai+bi］=E［vai］+E［bi］，將結(jié)果返回參與方。

5)參與方用私鑰對(duì)E［vai+bi］進(jìn)行解密，得到vai+bi。令si=vai+(bimod 2l)=vai+(b′imod 2l)。

6)對(duì)j從1到l進(jìn)行遍歷。

在算法2獲取邊密鑰的基礎(chǔ)上，參與者利用服務(wù)器提供的節(jié)點(diǎn)密鑰對(duì)混淆后的安全分支程序進(jìn)行逆向計(jì)算評(píng)估，具體算法如下。

算法3安全計(jì)算逆向評(píng)估。輸入:混淆后的安全分支程序T′、索引向量h、節(jié)點(diǎn)密鑰λh以及邊密鑰wi1，wi2，…，wil。輸出:葉子節(jié)點(diǎn)信息m=T(V)。

算法步驟為:

1)參與方根據(jù)節(jié)點(diǎn)密鑰kh對(duì)混淆后的分支程序T′的倒數(shù)第2層決策節(jié)點(diǎn)(已加密)進(jìn)行解密，得到?jīng)Q策節(jié)點(diǎn)Ch。

2)若決策節(jié)點(diǎn)Ch不是初始節(jié)點(diǎn)，則利用基于符號(hào)EVBDD的安全2方計(jì)算協(xié)議以及輸入wh1，wh2，…，whl對(duì)該決策節(jié)點(diǎn)進(jìn)行評(píng)估計(jì)算，否則轉(zhuǎn)向步驟6)。

3)將上述計(jì)算結(jié)果(即葉子節(jié)點(diǎn)信息)標(biāo)記為M。

4)將M替代已經(jīng)解密的決策節(jié)點(diǎn)Ch，并令h=h-1。

5)轉(zhuǎn)向步驟2)。

6)評(píng)估計(jì)算初始節(jié)點(diǎn)，獲取最終結(jié)果m=T(V)，協(xié)議結(jié)束。

本協(xié)議引入分支程序逆向評(píng)估技術(shù)，并在內(nèi)部決策節(jié)點(diǎn)分配不同子任務(wù)，使協(xié)議的評(píng)估參與者由2方擴(kuò)展到多方。同時(shí)，借助基于EVBDD的安全2方計(jì)算協(xié)議處理各個(gè)不同子任務(wù)，提高了決策函數(shù)的描述效率，保障了協(xié)議的隱私安全。

4 協(xié)議的正確性、安全性和效率分析

4.1 正確性分析

1)協(xié)議1的正確性。假設(shè)Alice成功構(gòu)造決策函數(shù)的EVBDD結(jié)構(gòu)，在約束Xa=(x1，x2，…，xk)下，添加相應(yīng)虛節(jié)點(diǎn)得:f|Xa。Bob無法得知約束前Alice輸入的Xa及約束后的EVBDD結(jié)構(gòu)。Alice為約束后EVBDD結(jié)構(gòu)中的各個(gè)節(jié)點(diǎn)分配1個(gè)節(jié)點(diǎn)密鑰sv，并連同解密后的節(jié)點(diǎn)密文一起發(fā)送給Bob。同時(shí)，Alice根據(jù)Bob的可能取值為所有非葉子節(jié)點(diǎn)分配1對(duì)取值密鑰)，假設(shè)此時(shí)π=0。設(shè)Bob得到加密后的節(jié)點(diǎn)為pv，其密文中的2條子密文為c1、c2，Bob根據(jù)此節(jié)點(diǎn)取值π，經(jīng)過不經(jīng)意傳輸協(xié)議在Alice對(duì)應(yīng)該節(jié)點(diǎn)的取值密鑰對(duì)中，獲得其中1個(gè)取值密鑰。Bob根據(jù)sv和即可解出2條子密文中的1條，得到計(jì)算路徑中節(jié)點(diǎn)pv的下一個(gè)節(jié)點(diǎn)的位置以及加密后新的2條子密文。重復(fù)上述步驟即可到達(dá)葉子節(jié)點(diǎn)，得到正確計(jì)算結(jié)果。由此，可知協(xié)議的正確性。

2)協(xié)議2的正確性。參與方通過算法2不經(jīng)意傳輸選擇協(xié)議得到邊密鑰wi1，wi2，…，wil，通過算法3獲取節(jié)點(diǎn)密鑰λh、安全分支程序T′和索引向量h。令葉子節(jié)點(diǎn)信息為M={m1，m2，…，mn}，參與方1根據(jù)輸入逆向評(píng)估計(jì)算出信息M1={m1，m2，…，mk}(1≤k≤n)，用此信息替換參與方1所在決策節(jié)點(diǎn)信息。然后，參與方2根據(jù)其輸入逆向計(jì)算出信息M2={m1，m2，…，mt}(1≤t≤k)，用此信息替換參與方2所在決策節(jié)點(diǎn)信息。由于分支程序決策節(jié)點(diǎn)內(nèi)部的計(jì)算以協(xié)議1為基礎(chǔ)協(xié)議，決策節(jié)點(diǎn)內(nèi)部結(jié)構(gòu)圖的計(jì)算正確。以此類推，依次逆向評(píng)估計(jì)算，最終正確計(jì)算出唯一的一個(gè)葉子信息m。因此，協(xié)議2是正確的。

4.2 安全性分析

1)協(xié)議1的安全性。假設(shè)Alice提供節(jié)點(diǎn)密鑰為sv(v=1，2，…，n-k)，節(jié)點(diǎn)的取值密鑰為，。Bob首先獲取相應(yīng)節(jié)點(diǎn)密鑰，然后通過1-out-of-2不經(jīng)意傳輸協(xié)議獲取唯一的取值密鑰，即和兩者中只能獲取其中一個(gè)，同時(shí)Alice無法得知Bob的選擇信息，這就確保了計(jì)算雙方的隱私都能得到保護(hù)。Bob用獲取的節(jié)點(diǎn)密鑰和該節(jié)點(diǎn)的取值密鑰可解密出該節(jié)點(diǎn)在相應(yīng)取值后的下一節(jié)點(diǎn)，而且是唯一的。以此類推，能得到唯一的一條路徑安全地到達(dá)葉子節(jié)點(diǎn)。由此可見，在這條唯一計(jì)算路徑的求解過程中，參與者的信息都得到了保護(hù)。

2)協(xié)議2的安全性。服務(wù)器通過算法1混淆后的分支程序是安全的。算法2通過同態(tài)加密E［vai］對(duì)輸入數(shù)據(jù)進(jìn)行加密，并通過混淆值si=vai+(bimod 2l)=vai+(b′imod 2l)對(duì)輸入數(shù)據(jù)進(jìn)行混淆，保證了參與各方輸入隱私的安全性。參與方在算法2中通過不經(jīng)意傳輸選擇協(xié)議得到不同分支中的唯一一個(gè)分支邊密鑰，這里的唯一性是由OT12所決定的。結(jié)合節(jié)點(diǎn)密鑰計(jì)算出唯一的葉子節(jié)點(diǎn)信息。由于邊密鑰的唯一性，確保評(píng)估計(jì)算過程中信息安全。由于決策節(jié)點(diǎn)的內(nèi)部評(píng)估以協(xié)議1為基礎(chǔ)協(xié)議，其安全性分析同協(xié)議1。此外，逆向評(píng)估計(jì)算避免了參與各方之間的信息交互，提高了協(xié)議的安全性。因此，協(xié)議2是安全的。

4.3 效率分析

5 結(jié)束語

針對(duì)傳統(tǒng)決策函數(shù)表示計(jì)算復(fù)雜度高、編碼規(guī)模大以及參與者局限于2方問題，提出一種基于邊值二叉決策圖和分支程序逆向評(píng)估的解決方案。與文獻(xiàn)［9］相比，不僅將協(xié)議擴(kuò)展到多方，而且降低了決策函數(shù)的復(fù)雜度，提高了協(xié)議效率。

由于分支程序逆向評(píng)估計(jì)算僅考慮了2分支的情況，在下一步工作中，可對(duì)多分支程序逆向評(píng)估計(jì)算進(jìn)行研究。此外，基于EVBDD的決策函數(shù)描述方式，由于邊權(quán)重因子的出現(xiàn)，協(xié)議中節(jié)點(diǎn)的存儲(chǔ)變得更加復(fù)雜。因此，基于EVBDD決策函數(shù)描述的優(yōu)化將是今后研究的方向。

［1］Yao A.Protocols for secure computations［C］//Proceedings of the 23th Annual Aymposium on Foundations of Computer Science，IEEE，1982:160-164.

［2］Katz J，Malka L.Secure text processing with applications to private DNA matching［C］//Proceedings of the 17th ACM Conference on Computer and Communications Security，2010:485-492.

［3］李順東，王道順.基于同態(tài)加密的高效多方保密計(jì)算［J］.電子學(xué)報(bào)，2013，41(4):798-803.

［4］Yao A.How to generate and exchange secrets［C］//Proceedings of the 27th Annual Symposium on Foundations of Computer Science，IEEE，1986:162-167.

［5］Kruger L，Jha S，Goh E，et al.Secure function evaluation with ordered binary decision diagrams［C］//Proceedings of the 13th ACM Conference on Computer and Communications Security，2006:410-420.

［6］古天龍，何仲春，常亮等.基于符號(hào)ADD和線性多分支程序的分類算法安全評(píng)估［J］.電子學(xué)報(bào)，2014，42(5):940-947.

［7］Kolesnikov V，Schneider T.A Practical Universal Circuit Construction and Secure Evaluation of Private Functions［M］//Financial Cryptography and Data Security.［S.l.］:Springer Berlin Heidelberg，2008:83-97.

［8］Brickell J，Porter D，Shmatikov V，et al.Privacy-preserving remote diagnostics［C］//Proceedings of the 14th ACM Conference on Computer and Communications Security，2007:498-507.

［9］Mohassel P，Niksefat S.Oblivious Decision Programs from Oblivious Transfer:Efficient Reductions［M］//Angelos D.Financial Cryptography and Data Security.［S.l.］:Springer Berlin Heidelberg，2012:269-284.

［10］Rabin M.How toExchange Secrets by Oblivious Transfer［R］.Harvard University，1981.

［11］Paillier P.Public-key cryptosystems based on composite degree residuosity classes［C］//Advances in Cryptology-EUROCRYPT’99.［S.l.］:Springer Berlin Heidelberg，1999:223-238.

［12］古天龍，徐周波.有序二叉樹決策圖及應(yīng)用［M］.北京:科學(xué)出版社，2009:17-57.