陳益師,古天龍,徐周波,寧黎華

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

基于符號(hào)OBDD的保護(hù)隱私集合運(yùn)算協(xié)議

陳益師,古天龍,徐周波,寧黎華

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

針對(duì)保護(hù)隱私的集合成員判定協(xié)議和集合相等判定協(xié)議泄露信息的缺陷,提出基于符號(hào)OBDD的解決方案。將集合成員編碼成二進(jìn)制碼,提取集合的特征函數(shù);以連分?jǐn)?shù)和Cantor編碼為橋梁,將集合編碼為自然數(shù),構(gòu)造該自然數(shù)的比較相等函數(shù);利用OBDD表示這2類(lèi)函數(shù),結(jié)合基于OBDD的安全函數(shù)評(píng)估協(xié)議,提出解決保護(hù)私有信息的集合相等判定問(wèn)題和集合成員判定問(wèn)題的2個(gè)協(xié)議。所提出的協(xié)議克服了已有解決方案存在的安全問(wèn)題,且有較好的執(zhí)行效率。

集合成員判定;集合相等;連分?jǐn)?shù);Cantor編碼

安全多方計(jì)算[1]是指在一個(gè)分布式網(wǎng)絡(luò)中,互不信任的參與者能夠在不泄露各自私有輸入信息情況下合作執(zhí)行某項(xiàng)可靠計(jì)算任務(wù)。這一概念由Yao[2]首次提出,被人們廣泛研究。由于計(jì)算效率原因,采用通用理論方案[3-5]解決安全多方計(jì)算問(wèn)題中一些特殊問(wèn)題不切實(shí)際,需用特殊方案才能達(dá)到高效性[1]。

在安全多方計(jì)算中,保護(hù)隱私的集合運(yùn)算是研究熱點(diǎn)。保護(hù)隱私的集合運(yùn)算研究的主要問(wèn)題:n個(gè)參與者提供各自秘密輸入,如何在不透露參與者秘密輸入的前提下,通過(guò)相應(yīng)集合運(yùn)算,得到輸出結(jié)果。這些集合運(yùn)算包括:求并集,求并集的勢(shì),求交集,求交集的勢(shì),求集合的包含關(guān)系,集合成員判定,判斷集合是否相等或相交等。在此研究其中的集合成員判定問(wèn)題和集合相等關(guān)系判斷問(wèn)題。解決這2個(gè)問(wèn)題的協(xié)議有很強(qiáng)的應(yīng)用背景,例如:在保護(hù)客戶(hù)信息前提下,銀行C想要判斷某客戶(hù)是否在銀行D的不良信用客戶(hù)名單中;互不信任的通信者,想要在不泄露自己口令的前提下判斷雙方口令是否一致。2個(gè)問(wèn)題的安全計(jì)算協(xié)議輸出為1 bit,如0表示b不屬于集合A或集合A與集合B不相等,而1則相反。

李順東等[6]利用可交換加密提出一個(gè)集合成員判定安全計(jì)算協(xié)議,通過(guò)該協(xié)議構(gòu)造解決集合交集勢(shì)的方案。Freedman等[7]利用多項(xiàng)式表示集合,通過(guò)哈希組分配降低多項(xiàng)式階數(shù)以提高計(jì)算效率,利用同態(tài)加密機(jī)制安全計(jì)算多項(xiàng)式的值,解決集合成員判定問(wèn)題,進(jìn)而提出參與雙方的集合是否有交集和交集勢(shì)的解決方案。Kissner等[8]改進(jìn)文獻(xiàn)[7]中集合的多項(xiàng)式表示方法,使集合的多項(xiàng)式表示不僅可用于解決集合交集問(wèn)題,而且適用于集合求并集問(wèn)題和求差集問(wèn)題。但是,該協(xié)議需要門(mén)限同態(tài)加密機(jī)制,解密過(guò)程比較復(fù)雜,需要分享解密密鑰的各個(gè)成員共享一個(gè)解密值。李榮花等[9]用多項(xiàng)式表示待比較的集合,利用不同多項(xiàng)式判斷集合包含關(guān)系的方法,結(jié)合疊加密和加法同態(tài)加密機(jī)制分別提出3種協(xié)議,用于判斷集合包含關(guān)系,但是,這3種協(xié)議都會(huì)泄露一方參與者的信息。豆永麗等[10]采用混沌加密機(jī)制和同態(tài)加密機(jī)制,借助第3方判斷提出2個(gè)協(xié)議,用于解決保護(hù)隱私的集合成員判定問(wèn)題,但是,這2個(gè)解決方案會(huì)泄露集合的成員個(gè)數(shù),第3方會(huì)得到比較結(jié)果,造成信息泄露。夏峰等[11]等利用格上LWE(learning with error)困難性假設(shè),提出能夠抵抗量子攻擊的安全判斷2數(shù)是否相等的解決方案,并以該方案為基本模塊,解決集合成員判定,求集合交集和集合相等的判定,該方案同樣會(huì)泄露集合的成員個(gè)數(shù)。

當(dāng)前,大部分保護(hù)隱私的集合運(yùn)算協(xié)議利用多項(xiàng)式表示集合。但是,由于多項(xiàng)式系數(shù)個(gè)數(shù)決定了集合大小,協(xié)議不可避免會(huì)泄露某個(gè)參與者集合成員個(gè)數(shù),且加密方式為復(fù)雜度較高的同態(tài)加密。其他對(duì)集合成員加密的解決方案雖然不暴露集合成員的值,但會(huì)泄露集合成員個(gè)數(shù)以及集合成員比較情況。鑒于此,利用有序二叉決策圖(OBDD)表示集合特征函數(shù)和比較相等函數(shù),提出基于OBDD安全評(píng)估協(xié)議的集合成員判定協(xié)議和判斷集合相等協(xié)議,避免了泄露參與者集合成員個(gè)數(shù)以及成員比較情況。

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

定義1 連分?jǐn)?shù)。連分?jǐn)?shù)是一種重要的實(shí)數(shù)表示方法,其一般形式為:當(dāng)r1為整數(shù),r2,r3,…均為正整數(shù)時(shí),稱(chēng)式(1)為連分?jǐn)?shù),記為[r1,r2,r3,…],并稱(chēng)r1,r2,r3,…為該連分?jǐn)?shù)的部分商。當(dāng)部分商的個(gè)數(shù)有限時(shí),稱(chēng)為有限連分?jǐn)?shù)。

Hardy等[12]證明了當(dāng)限制連分?jǐn)?shù)最后一位分量不為1時(shí),實(shí)數(shù)與連分?jǐn)?shù)一一對(duì)應(yīng)。

定義2 Cantor編碼[13]。稱(chēng)如下函數(shù)h(x,y)對(duì)自然數(shù)對(duì)(x,y)的編碼方式為Cantor編碼:

Cantor編碼建立了自然數(shù)對(duì)與自然數(shù)的一一對(duì)應(yīng)關(guān)系。

定義3 不經(jīng)意傳輸協(xié)議。1-out-of-n不經(jīng)意傳輸協(xié)議(OTn1)是一個(gè)2方交互協(xié)議。協(xié)議包括發(fā)送者和接收者,其中發(fā)送者有n個(gè)秘密消息mi(i=0, 1,2,…,n),接收者擁有一個(gè)選擇數(shù)字b(1≤b≤n),執(zhí)行協(xié)議后接收者獲得選擇的mb,但是不知道發(fā)送者中的其他mi的內(nèi)容,發(fā)送者不知道接收者的選擇數(shù)字b。

這里應(yīng)用1-out-of-2(OT12)不經(jīng)意傳輸協(xié)議,可實(shí)例化為文獻(xiàn)[14]中的高效解決方案。

定義4 半誠(chéng)實(shí)參與者。在執(zhí)行協(xié)議的過(guò)程中會(huì)忠實(shí)地履行協(xié)議,但會(huì)保留所有中間結(jié)果,試圖從中間結(jié)果推導(dǎo)出協(xié)議之外信息,這樣的參與者稱(chēng)為半誠(chéng)實(shí)參與者。

一個(gè)惡意參與者在執(zhí)行協(xié)議過(guò)程中可能任意地偏離協(xié)議、拒絕參與協(xié)議、更換自己的本地輸入、甚至可能終止協(xié)議。Goldreich指出:在半誠(chéng)實(shí)參與者條件下的安全計(jì)算協(xié)議中,利用比特承諾和零知識(shí)證明可以迫使惡意參與者以半誠(chéng)實(shí)方式參與執(zhí)行,否則就會(huì)被發(fā)現(xiàn)[1]。因此,很多時(shí)候只需要研究半誠(chéng)實(shí)參與者條件下的安全多方計(jì)算解決方案即可。在此,假設(shè)協(xié)議參與者都是半誠(chéng)實(shí)的。

定義5 OBDD(ordered binary decision diagrams)[15]。對(duì)于從{0,1}n到{0,1}的布爾函數(shù)f(x1, x2,…,xn),一個(gè)OBDD就是在給定變量序π下用于表示布爾函數(shù)的f(x1,x2,…,xn)的有向無(wú)環(huán)圖。

在OBDD的圖形表示中,一般非終節(jié)點(diǎn)用圓圈表示,終節(jié)點(diǎn)用方框表示。每個(gè)非終節(jié)點(diǎn)均具有2個(gè)輸出分支弧,將非終節(jié)點(diǎn)和2個(gè)分支節(jié)點(diǎn)連接起來(lái),當(dāng)非終節(jié)點(diǎn)變量取1時(shí)輸出弧記為1-邊,用實(shí)線(xiàn)表示;當(dāng)非終節(jié)點(diǎn)變量取0時(shí)輸出弧記為0-邊,用虛線(xiàn)表示。

例如布爾函數(shù)f=x1x2+x3,在給定變量序π: x1＜x2＜x3下對(duì)應(yīng)的OBDD如圖1所示。

圖1 函數(shù)f=x1x2+x3的OBDD表示Fig 1 OBDD for the function f=x1x2+x3

定義6 對(duì)稱(chēng)加密。對(duì)稱(chēng)加密是指采用單鑰密碼系統(tǒng)的加密方法,同一個(gè)密鑰可以同時(shí)用作信息的加密和解密,也稱(chēng)為單密鑰加密。在對(duì)OBDD中的節(jié)點(diǎn)進(jìn)行加密時(shí),使用的對(duì)稱(chēng)加密機(jī)制要求語(yǔ)義安全。所謂語(yǔ)義安全類(lèi)似于Shannon給出的完善保密理論,要求從密文中不能得到有關(guān)明文的任何消息。相對(duì)非對(duì)稱(chēng)加密機(jī)制,對(duì)稱(chēng)加密機(jī)制具有加解密算法開(kāi)銷(xiāo)小以及密鑰生成算法簡(jiǎn)單等優(yōu)點(diǎn)。

2 解決方案

2.1 基于OBDD的安全函數(shù)評(píng)估協(xié)議

基于OBDD的安全函數(shù)評(píng)估由Louis Kruger等[16]提出,具有良好的協(xié)議效率,可應(yīng)用于保護(hù)隱私的集合成員判定和集合相等關(guān)系判定。假設(shè)協(xié)議的參與者為服務(wù)端Alice和客戶(hù)端Bob,協(xié)議的主要步驟為:

1)Alice利用變量序?yàn)閤1＜x2＜…＜xn的OBDD表示函數(shù)f(x1,x2,…,xn)。函數(shù)f的自變量x1,x2,…,xk對(duì)應(yīng)Alice的輸入(i1,i2,…,ik); xk+1,xk+2,…,xn對(duì)應(yīng)Bob的輸入(ik+1,ik+2,…, in)。

2)Alice用其輸入約束OBDD,添加偽節(jié)點(diǎn)和混淆節(jié)點(diǎn)后進(jìn)行混淆加密,將混淆加密后的OBDD密文發(fā)送給Bob。

3)Bob根據(jù)其輸入,與Alice共同執(zhí)行不經(jīng)意傳輸協(xié)議,得到解密OBDD密文的取值密鑰。

4)Bob根據(jù)得到的取值密鑰解密OBDD密文,得到OBDD的葉子節(jié)點(diǎn)信息,即函數(shù)f(x1,x2,…, xn)的計(jì)算結(jié)果。

由于使用語(yǔ)義安全的對(duì)稱(chēng)加密對(duì)OBDD節(jié)點(diǎn)進(jìn)行加密,且Alice與Bob進(jìn)行交互時(shí)執(zhí)行不經(jīng)意傳輸,雙方均不能得到對(duì)方的輸入。

2.2 集合成員判定安全計(jì)算協(xié)議

OBDD表示集合的特征函數(shù):設(shè)一個(gè)集合S= {赤色,橙色,紅色},若將S中的每一個(gè)成員編碼為:赤色-00,橙色-01,紅色-10,則集合S的特征函數(shù)為f(x1,x2)=x1′x2′+x1′x2+x1x2′。規(guī)定變量序π為:x2＜x1,存在唯一的OBDD表示集合S的特征函數(shù),如圖2所示。表示集合特征函數(shù)的OBDD可作為基于OBDD的安全函數(shù)評(píng)估的輸入,解決集合成員判定問(wèn)題。

圖2 集合S的OBDD表示Fig 2 OBDD for the set S

保護(hù)隱私的集合成員判定問(wèn)題:假定Alice擁有一個(gè)成員為自然數(shù)的秘密集合SA={a1,a2,…, an},Bob擁有一個(gè)自然數(shù)b,雙方想判斷b∈SA或者b?SA,但都不想泄露自己的信息。

協(xié)議1 保護(hù)隱私的集合成員判定協(xié)議。輸入: Alice秘密輸入集合SA={a1,a2,…,an},Bob秘密輸入b。輸出:b∈SA或b?SA。

協(xié)議步驟:

1)Alice和Bob共同確定SA成員和b所采用二進(jìn)制編碼位數(shù)k。

2)Alice將SA中的各個(gè)成員編碼為k位的二進(jìn)制碼,并根據(jù)二進(jìn)制碼得到集合的特征函數(shù)。Bob將b編碼為二進(jìn)制碼。

3)Alice利用OBDD表示集合的特征函數(shù),添加偽節(jié)點(diǎn)對(duì)其進(jìn)行混淆加密,將OBDD密文發(fā)送給Bob。

4)Bob根據(jù)b的二進(jìn)制碼與Alice共同執(zhí)行不經(jīng)意傳輸協(xié)議,得到取值密鑰,利用取值密鑰計(jì)算葉子節(jié)點(diǎn)信息,即b∈SA或b?SA。

5)Bob將判斷結(jié)果告訴Alice。

2.3 判斷集合相等的安全計(jì)算協(xié)議

有限集合轉(zhuǎn)換成自然數(shù):假設(shè)有限集合S中的成員為非零自然數(shù),按如下步驟可將集合S轉(zhuǎn)換成自然數(shù)。

1)將集合S中的成員按遞增順序排序?yàn)橐粋€(gè)遞增序列,該序列可看成分量互異的連分?jǐn)?shù)的部分商,求出部分商對(duì)應(yīng)的分?jǐn)?shù)。

2)分?jǐn)?shù)的分子和分母看成自然數(shù)對(duì),經(jīng)過(guò)Cantor編碼得到一個(gè)自然數(shù)。

OBDD表示比較相等函數(shù):設(shè)f(x,c)為比較相等函數(shù),其中x為函數(shù)輸入,c為待比較常數(shù),函數(shù)輸出為0或1。當(dāng)x=c時(shí),函數(shù)輸出為1;當(dāng)x≠c時(shí),函數(shù)輸出為0。將比較相等函數(shù)表示為OBDD的步驟為:假設(shè)函數(shù)輸入x和待比較常數(shù)c的取值范圍為[0,N],則需要log2(N+1)?位變量x1,x2,…, xlog2(N+1)?的OBDD進(jìn)行表示。若c的二進(jìn)制碼為c1,c2,…,clog2(N+1)?,則變量x1,x2,…,xlog2(N+1)?分別取值為c1,c2,…,clog2(N+1)?的分支路徑指向的葉子節(jié)點(diǎn)的值為1;變量的其他取值確定的分支路徑指向的葉子節(jié)點(diǎn)值為0。比如一個(gè)比較相等函數(shù)為f(x,c),其中x和c的取值范圍為[0,15],待比較常數(shù)c=10,則OBDD表示該比較相等函數(shù)如圖3所示。

圖3 比較相等函數(shù)的OBDD表示Fig 3 OBDD for the equal function

保護(hù)隱私的集合相等關(guān)系判定問(wèn)題:假定Alice和Bob各自擁有一個(gè)成員為非零自然數(shù)的秘密集合SA={a1,a2,…,am}和SB={b1,b2,…,bn},雙方想判斷SA和SB是否相等,但都不想泄露自己的信息。

協(xié)議2 集合相等關(guān)系判定協(xié)議。輸入:Alice秘密輸入集合SA={a1,a2,…,am},Bob秘密輸入SB={b1,b2,…,bn}。輸出:SA=SB或SA≠SB。

協(xié)議步驟:

1)Alice和Bob各自將集合成員按遞增順序排序,2個(gè)有序集合經(jīng)過(guò)連分?jǐn)?shù)和Cantor編碼轉(zhuǎn)換成自然數(shù)NA和NB。

2)Alice和Bob各自將NA和NB編碼成k位的二進(jìn)制碼,其中k大于log2(NA+1)?和log2(NB+1)?中的較大值。

3)Alice利用OBDD表示待比較常數(shù)為NA的比較相等函數(shù),添加偽節(jié)點(diǎn)并對(duì)其進(jìn)行混淆加密,將OBDD密文發(fā)送給Bob。

4)Bob根據(jù)NB的二進(jìn)制碼與Alice共同執(zhí)行不經(jīng)意傳輸協(xié)議,得到解密OBDD密文的取值密鑰,利用取值密鑰計(jì)算得到葉子節(jié)點(diǎn)信息,即SA=SB或者SA≠SB。

5)Bob將判斷結(jié)果告訴Alice。

3 分析

3.1 正確性分析

所提出的集合成員判定協(xié)議和判斷集合相等協(xié)議基于OBDD安全函數(shù)評(píng)估協(xié)議,文獻(xiàn)[10]證明了OBDD安全函數(shù)評(píng)估協(xié)議的正確性。因此,只對(duì)OBDD表示集合、將集合表示成自然數(shù)以及OBDD表示比較相等函數(shù)的正確性進(jìn)行分析。

1)集合特征函數(shù)的OBDD表示的正確性:將集合成員編碼成n位二進(jìn)制碼,存在唯一一個(gè)n變量布爾函數(shù)f(x1,x2,…,xn),使得當(dāng)輸入的變量值x1, x2,…,xn為某個(gè)成員的二進(jìn)制碼時(shí),布爾函數(shù)的輸出為1,否則布爾函數(shù)的輸出為0。而OBDD是給定的變量序π用于表示布爾函數(shù)的f(x1,x2,…,xn)的規(guī)范式,因此,可用OBDD表示集合。當(dāng)變量x1,x2,…,xn取集合成員的二進(jìn)制碼時(shí),有一條路徑指向值為1的葉子節(jié)點(diǎn);當(dāng)變量x1,x2,…,xn不是取集合成員的二進(jìn)制碼時(shí),有一條與輸入對(duì)應(yīng)的路徑指向值為0的葉子節(jié)點(diǎn)。因此,利用OBDD可正確表示集合,可用于集合成員判定協(xié)議。

2)有限集合通過(guò)連分?jǐn)?shù)和Cantor編碼轉(zhuǎn)換成自然數(shù)的正確性:非零自然數(shù)有限集合的成員按遞增順序排序?yàn)橐粋€(gè)遞增序列,此序列可看成分量互異的連分?jǐn)?shù)的部分商,而連分?jǐn)?shù)與對(duì)應(yīng)的分?jǐn)?shù)存在一一對(duì)應(yīng)關(guān)系,不同的有限集合經(jīng)過(guò)遞增排序得到的遞增序列通過(guò)連分?jǐn)?shù)為橋梁編碼為不同的分?jǐn)?shù)。如此轉(zhuǎn)換,不同的集合對(duì)應(yīng)不同的分?jǐn)?shù)。另外,分?jǐn)?shù)的分子和分母組成的自然數(shù)對(duì)通過(guò)Cantor編碼與自然數(shù)一一對(duì)應(yīng),即分?jǐn)?shù)與自然數(shù)通過(guò)Cantor編碼建立一一對(duì)應(yīng)關(guān)系。因此,不同的有限集合通過(guò)連分?jǐn)?shù)和Cantor編碼轉(zhuǎn)換成不同的自然數(shù),繼而可由自然數(shù)的比較相等判斷集合相等關(guān)系。

比較相等函數(shù)的OBDD表示與集合特征函數(shù)的OBDD表示類(lèi)似,當(dāng)OBDD變量取待比較常數(shù)的二進(jìn)制碼時(shí),得到唯一一條指向值為1的葉子節(jié)點(diǎn)的路徑。

綜上,由OBDD表示集合的特征函數(shù)、集合通過(guò)連分?jǐn)?shù)和Cantor編碼表示為自然數(shù)以及OBDD表示比較相等函數(shù)的正確性,結(jié)合基于OBDD安全函數(shù)評(píng)估協(xié)議的正確性,可知協(xié)議1、2均可以得到正確的計(jì)算結(jié)果。

3.2 安全性分析

在半誠(chéng)實(shí)參與者模型中,對(duì)稱(chēng)加密機(jī)制具有語(yǔ)義安全性且不經(jīng)意傳輸協(xié)議安全假設(shè)下的安全性分析。

協(xié)議參與者雙方交互基于OBDD安全函數(shù)評(píng)估協(xié)議的執(zhí)行過(guò)程。此過(guò)程中Alice用語(yǔ)義安全性的對(duì)稱(chēng)加密機(jī)制混淆加密OBDD,使Bob得到OBDD密文后,只能通過(guò)執(zhí)行不經(jīng)意傳輸協(xié)議得到與其輸入對(duì)應(yīng)的取值密鑰和上一節(jié)點(diǎn)的節(jié)點(diǎn)密鑰共同解密。在一次不經(jīng)意傳輸協(xié)議中,Alice不會(huì)獲知Bob的輸入。另外,由于執(zhí)行一次不經(jīng)意傳輸協(xié)議只能得到與其輸入對(duì)應(yīng)的取值密鑰,不能得到另外分支的取值密鑰。因此,Bob只能解密得到與其輸入對(duì)應(yīng)的下一節(jié)點(diǎn)標(biāo)簽和節(jié)點(diǎn)密鑰,n次不經(jīng)意傳輸?shù)玫轿ㄒ灰粭l從源節(jié)點(diǎn)指向表示集合運(yùn)算結(jié)果的葉子節(jié)點(diǎn)的路徑。因此,在整個(gè)協(xié)議過(guò)程中,不經(jīng)意傳輸協(xié)議和節(jié)點(diǎn)信息加密的安全性保護(hù)了Alice和Bob的各自隱私。

3.3 效率分析

保護(hù)隱私的集合運(yùn)算協(xié)議是一種分布式安全計(jì)算協(xié)議,其計(jì)算復(fù)雜度用協(xié)議中各種類(lèi)型計(jì)算的執(zhí)行次數(shù)描述;而通信復(fù)雜度通常用通信輪數(shù)描述。協(xié)議參與者交互過(guò)程中只進(jìn)行模指數(shù)運(yùn)算,其他運(yùn)算均可在準(zhǔn)備階段完成。另外,相對(duì)于協(xié)議中的其他運(yùn)算,如異或運(yùn)算和加減乘除運(yùn)算,模指數(shù)運(yùn)算需要較高的運(yùn)算代價(jià)。因此,協(xié)議中只考慮模指數(shù)運(yùn)算的計(jì)算代價(jià)。由于執(zhí)行不經(jīng)意傳輸協(xié)議,協(xié)議引入模指數(shù)運(yùn)算,協(xié)議采用文獻(xiàn)[14]中效率較高的不經(jīng)意傳輸協(xié)議,2個(gè)協(xié)議所需模指數(shù)運(yùn)算次數(shù)為2n,n為在協(xié)議1、2中OBDD中的變量個(gè)數(shù)。另外,2個(gè)協(xié)議的通信輪數(shù)均為4。

3.4 協(xié)議的擴(kuò)展性分析

保護(hù)隱私的多方集合成員判定:假設(shè)有n個(gè)參與者P1,P2,…,Pn;P1擁有一個(gè)秘密集合,希望在不泄露參與者信息的前提下計(jì)算P2,P3,…,Pn中擁有的自然數(shù)屬于P1集合的個(gè)數(shù)。

對(duì)協(xié)議1作如下修改,可由2方協(xié)議拓展到多方協(xié)議,用于解決保護(hù)隱私的多方集合運(yùn)算問(wèn)題。Alice對(duì)OBDD進(jìn)行混淆加密時(shí),引入加法同態(tài)加密機(jī)制對(duì)葉子節(jié)點(diǎn)進(jìn)行加密后,發(fā)送給P2,P3,…,Pn; P2,P3,…,Pn與P1進(jìn)行不經(jīng)意傳輸?shù)玫饺≈得荑€,對(duì)OBDD進(jìn)行遍歷得到各自利用加法同態(tài)加密機(jī)制加密的葉子節(jié)點(diǎn)信息;P2,P3,…,Pn將葉子節(jié)點(diǎn)信息相加后傳遞給P1;最后P1解密得到P2,P3,…,Pn中擁有的自然數(shù)屬于P1集合的個(gè)數(shù)。

協(xié)議2經(jīng)過(guò)類(lèi)似修改,可得到在不泄露參與者信息前提下,計(jì)算P2,P3,…,Pn中擁有秘密集合與P1集合相同的個(gè)數(shù)的協(xié)議。另外,在協(xié)議2中,若集合的成員不經(jīng)過(guò)排序,則可用于解決保護(hù)隱私的向量比較相等問(wèn)題。

4 結(jié)束語(yǔ)

協(xié)議1、2構(gòu)建集合的特征函數(shù)和集合通過(guò)連分?jǐn)?shù)以及Cantor編碼轉(zhuǎn)換成自然數(shù)的比較相等函數(shù),基于OBDD的安全函數(shù)評(píng)估協(xié)議對(duì)集合的特征函數(shù)和比較相等函數(shù)進(jìn)行安全評(píng)估,分別用于解決保護(hù)隱私的集合成員判定和集合相等關(guān)系判定問(wèn)題。避免了多項(xiàng)式表示集合的解決方案和對(duì)集合成員進(jìn)行加密的解決方案泄露集合成員個(gè)數(shù)和集合成員比較情況等信息安全問(wèn)題。給出將協(xié)議1、2由2方拓展到多方的方法。由于其他保護(hù)隱私的集合運(yùn)算也存在類(lèi)似安全問(wèn)題,今后工作針對(duì)其他集合運(yùn)算構(gòu)造安全性能更高的安全計(jì)算協(xié)議。

[1] Goldreich O.Foundations of Cryptography,Volume 2, Basic Applications[M].Cambridge:Cambridge University Press,2009:24-29.

[2] Yao A.Protocols for secure computations[C]//2013 IEEE 54th Annual Symposium on Foundations of Computer Science,1982:160-164.

[3] Henecka W,Sadeghi A R,Schneider T,et al.TASTY: tool for automating secure two-party computations [C]//Proceedings of the 17th ACM Conference on Computer and Communications Security,2010:451-462.

[4] Goldwasser S.Multi-party computations:past and present[C]//Proceedings of the 16th Annual ACM Symposium on Principles of Distributed Computing,1997:1-6.

[5] Yao A.How to generate and exchange secrets[C]//27th Annual Symposium on Foundations of Computer Science.IEEE,1986:162-167.

[6] 李順東,司天歌,戴一奇,集合包含與幾何包含的多方保密計(jì)算[J].計(jì)算機(jī)研究與發(fā)展,2005,42(10):1647-1653.

[7] Freedman M J,Nissim K,Pinkas B.Efficient private matching and set intersection[C]//Advances in Cryptology-EUROCRYPT 2004.Springer Berlin Heidelberg, 2004:1-19.

[8] Kissner L,Song D.Privacy-preserving set operations [C]//Advances in Cryptology-CRYPTO 2005,2005: 241-257.

[9] 李榮花,武傳坤,張玉清.判斷集合包含關(guān)系的安全計(jì)算協(xié)議[J].計(jì)算機(jī)學(xué)報(bào),2009,32(7):1337-1345.

[10] 豆永麗,王海春,康劍.集合成員判定問(wèn)題的安全多方計(jì)算解決方案[J].計(jì)算機(jī)應(yīng)用,2013,33(12):3527-3530.

[11] 夏峰,楊波,張明武,等.基于LWE的集合相交和相等的兩方保密計(jì)算[J].電子與信息學(xué)報(bào),2012,34(2): 462-467.

[12] Hardy G H,Wright E M,Heath-Brown D R,et al.An Introduction to the Theory of Numbers[M].Oxford: Clarendon Press,1979:22-25.

[13] 張立昂.可計(jì)算性與計(jì)算復(fù)雜度導(dǎo)引[M].北京:北京大學(xué)出版社,2003:51-52.

[14] Tzeng W.Efficient 1-out-n oblivious transfer schemes [C]//Public Key Cryptography-5th International Workshop on Practice and Theory in Public Key Cryptosystems,2002:159-171.

[15] 古天龍,徐周波.有序二叉決策圖及應(yīng)用[M].北京:科學(xué)出版社,2009:22-40.

[16] Kruger L,Jha S,Goh E J,et al.Secure function evaluation with ordered binary decision diagrams[C]//Proceedings of the 13th ACM Conference on Computer and Communications Security.New York:ACM Press, 2006:410-420.

編輯:翁史振 見(jiàn)習(xí)編輯:陳汝偉

Privacy-preserving set operations protocols based on symbolic OBDD

Chen Yishi,Gu Tianlong,Xu Zhoubo,Ning Lihua
(Guangxi Key Laboratory of Trusted Software,Guilin University of Electronic Technology,Guilin 541004,China)

Because the existing set member decision protocol and set equality protocol leak the private information of the sets, the protocols based on ordered binary decision diagram are proposed.The characteristic function of a set is extracted by encoding the set members into binary code.In addition,using continued fraction and Cantor coding as a bridge,the set is encoded into a natural number,and then an equal function of the natural number is constructed.OBDD is used to represent the two kinds of functions,combined with security function evaluation protocols based on the OBDD,set member decision problem and set equality problem are solved.Compared with the existing protocols,the two new ones can solve the security issues,and they have good execution efficiency.

set member decision;set equality;continued fraction;Cantor coding

TP309

:A

:1673-808X(2015)04-0315-06

2015-03-16

國(guó)家自然科學(xué)基金(61100025,61262030,61363030);廣西自然科學(xué)基金(2014GXNSFAA118354)

古天龍(1964―),男,山西芮城人,教授,博士,研究方向?yàn)樾问交椒?、符?hào)計(jì)算、知識(shí)工程。E-mail:cctlgu@guet.edu.cn

陳益師,古天龍,徐周波,等.基于符號(hào)OBDD的保護(hù)隱私的集合運(yùn)算協(xié)議[J].桂林電子科技大學(xué)學(xué)報(bào),2015,35(4):315-320.