基于符號OBDD的保護隱私集合運算協(xié)議

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

(桂林電子科技大學廣西可信軟件重點實驗室,廣西桂林 541004)

基于符號OBDD的保護隱私集合運算協(xié)議

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

(桂林電子科技大學廣西可信軟件重點實驗室,廣西桂林 541004)

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

集合成員判定;集合相等;連分數(shù);Cantor編碼

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

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

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

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

1 預備知識

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

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

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

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

定義3 不經(jīng)意傳輸協(xié)議。1-out-of-n不經(jīng)意傳輸協(xié)議(OTn1)是一個2方交互協(xié)議。協(xié)議包括發(fā)送者和接收者,其中發(fā)送者有n個秘密消息mi(i=0, 1,2,…,n),接收者擁有一個選擇數(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é)議,可實例化為文獻[14]中的高效解決方案。

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

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

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

在OBDD的圖形表示中,一般非終節(jié)點用圓圈表示,終節(jié)點用方框表示。每個非終節(jié)點均具有2個輸出分支弧,將非終節(jié)點和2個分支節(jié)點連接起來,當非終節(jié)點變量取1時輸出弧記為1-邊,用實線表示;當非終節(jié)點變量取0時輸出弧記為0-邊,用虛線表示。

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

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

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

2 解決方案

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

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

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

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

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

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

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

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

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

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

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

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

協(xié)議步驟:

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

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

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

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

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

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

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

1)將集合S中的成員按遞增順序排序為一個遞增序列,該序列可看成分量互異的連分數(shù)的部分商,求出部分商對應(yīng)的分數(shù)。

2)分數(shù)的分子和分母看成自然數(shù)對,經(jīng)過Cantor編碼得到一個自然數(shù)。

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

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

保護隱私的集合相等關(guān)系判定問題:假定Alice和Bob各自擁有一個成員為非零自然數(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個有序集合經(jīng)過連分數(shù)和Cantor編碼轉(zhuǎn)換成自然數(shù)NA和NB。

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

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

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

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

3 分析

3.1 正確性分析

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

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

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

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

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

3.2 安全性分析

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

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

3.3 效率分析

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

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

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

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

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

4 結(jié)束語

協(xié)議1、2構(gòu)建集合的特征函數(shù)和集合通過連分數(shù)以及Cantor編碼轉(zhuǎn)換成自然數(shù)的比較相等函數(shù),基于OBDD的安全函數(shù)評估協(xié)議對集合的特征函數(shù)和比較相等函數(shù)進行安全評估,分別用于解決保護隱私的集合成員判定和集合相等關(guān)系判定問題。避免了多項式表示集合的解決方案和對集合成員進行加密的解決方案泄露集合成員個數(shù)和集合成員比較情況等信息安全問題。給出將協(xié)議1、2由2方拓展到多方的方法。由于其他保護隱私的集合運算也存在類似安全問題,今后工作針對其他集合運算構(gòu)造安全性能更高的安全計算協(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].計算機研究與發(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)系的安全計算協(xié)議[J].計算機學報,2009,32(7):1337-1345.

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

[11] 夏峰,楊波,張明武,等.基于LWE的集合相交和相等的兩方保密計算[J].電子與信息學報,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] 張立昂.可計算性與計算復雜度導引[M].北京:北京大學出版社,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].北京:科學出版社,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.

編輯:翁史振 見習編輯:陳汝偉

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

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

古天龍(1964―),男,山西芮城人,教授,博士,研究方向為形式化方法、符號計算、知識工程。E-mail:cctlgu@guet.edu.cn

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