非加密方法安全計算集合包含關系

陳振華 李順東 王道順 黃 瓊 董立紅

1(西安科技大學計算機科學與技術學院 西安 710054)2(信息安全國家重點實驗室(中國科學院信息工程研究所) 北京 100093)3(陜西師范大學計算機科學學院 西安 710062)4(清華大學計算機科學與技術系 北京 100084)5 (華南農業大學數學與信息學院 廣州 510642)

?

非加密方法安全計算集合包含關系

陳振華1,2李順東3王道順4黃 瓊5董立紅1

1(西安科技大學計算機科學與技術學院 西安 710054)2(信息安全國家重點實驗室(中國科學院信息工程研究所) 北京 100093)3(陜西師范大學計算機科學學院 西安 710062)4(清華大學計算機科學與技術系 北京 100084)5(華南農業大學數學與信息學院 廣州 510642)

(chenzhenhua@snnu.edu.cn)

針對已存在的安全計算集合包含關系的協議大多基于多次公鑰加密算法，計算復雜性較高，并且不能公開計算，應用受限的問題.提出了2種非加密安全計算集合包含關系的協議.協議1首先將集合包含問題轉化為向量內積問題;然后利用數學難解問題解決了此問題;最后針對不可信第三方存在的應用場景，利用雙線性對和數學難解問題給出了可公開判斷集合包含關系的實用性協議2.協議1和協議2都沒有使用任何公鑰加密方法，避免了前人方案中繁瑣的公私鑰產生和加解密過程以及多次匹配查找，因此更加高效而簡潔.此外，協議2開拓了保密判斷集合關系的新應用場景.

集合包含；安全計算；雙線性對；數學難題；公開判斷

安全多方計算最早由Yao[1]提出，是指在不泄漏各方的輸入數據(隱私性)的條件下，能正確完成輸入數據的函數計算(正確性).現實問題中涉及到保護隱私的合作計算都可以歸結到安全多方計算的范圍.因此它在保護隱私的質量評估[2]、定位查找[3]、數據挖掘[4]、數據查詢[5]、外包計算[6]等方面有著廣泛的應用.

安全計算集合關系屬于安全多方計算的一個分支，要求保密地判斷一方的集合和另一個集合的關系，卻不泄露2個集合數據的隱私，它是保護隱私的數據查詢和匹配中的常見問題.針對于此，Freedman等人[7]利用多項式的值研究了集合相交、交集的勢等問題；Kissner等人[8]利用多項式的性質；Clifton等人[9]利用隨機數分別研究了集合交集、并集、交集的勢等問題；夏峰等人[10]基于LWE(learning with errors)困難問題解決了集合相等、相交等問題.這些文獻大多集中在集合交集、并集、交集的勢等問題，對于集合的包含問題研究并不多.

安全計算集合包含關系要求在不泄露2個集合數據隱私的情況下，保密地判斷一方的集合是否包含在另一個集合中.這個問題在現實中有著非常廣泛的應用.例如2014年Guo等人[11]提出了基于集合包含關系的加密，并用于不經意傳輸.在這個加密算法中，只有滿足集合包含關系的成員才能恢復消息.但存在的問題是：一方的集合未加保護是在公開信道上傳遞的，這就導致了集合中部分信息泄露，存在安全漏洞.若能進行全隱私的集合包含關系的判定，就能解決此方案中出現的問題，很好地改進方案.因此，本文對安全計算集合包含關系進行的研究，有著重要的現實意義.若能有效解決安全計算2個集合的包含問題，并以此為基礎模塊，就能建立很多其他密碼學上的方案和應用.

針對安全計算集合包含關系的問題，以往的學者們提出了一些解決方案.李順東等人[12]利用可交換的加密方案通過求交集的勢，從而判斷了集合是否包含，該方案實質上是將集合包含問題轉化成百萬富翁問題，利用可交換加密進行多次逐一匹配查找，若集合很大的話，導致匹配查找的次數也很大，效率較低；Kissner等人[8]將集合表示成多項式，利用門限同態加密算法解決了集合包含問題，但此方案需要門限解密，復雜性很高；李榮花等人[13]也將集合表示成多項式，利用同態加密的方法判斷集合的包含關系.雖然比Kissner等人[8]的效率有所提高，但也利用了多次加解密算法，方案還是不夠簡潔.

由于這些方案都使用了多次公鑰加解密算法，而公鑰加解密算法，一般效率較低.此外，如果集合的規模很大，多次逐一匹配查找會使得方案的效率進一步降低.

針對以上方案中存在的問題，我們充分利用多項式性質，并結合密碼學中的困難問題，重新設計了2個保密判斷集合包含關系的協議，貢獻有3點：

1) 提出了新的轉化方法.本文將集合包含問題轉化成向量內積問題，并利用數學難解問題解決了原問題.

2) 拓展了新的應用場景.本文的協議2將傳統模式下只能兩方保密計算集合關系的場景拓展到任何不可信第三方可參與計算的場景，為可公開保密判斷的應用環境提供了新的技術.

3) 提高了效率.本文方案沒有使用任何公鑰加密算法，避免了前人方案中煩瑣的公私鑰產生和加解密過程以及多次匹配比較，提高了效率.

1 預備知識

1.1 數學難解問題

1)n-Diffie -Hellman inversion(n-DHI)問題[14]：給定gα,ga2,…,gan∈Gn+1，計算g∈G.

2)n-Diffie -Hellman inversion(n-DHI)假設[14]：不存在多項式時間算法可以解決n-DHI問題.

1.2 雙線性對

G,G1為2個同為素數階q的乘法群，e為一個線性映射，e:G×G→G1，g為G的一個生成元，若e滿足3種性質：

1) 雙線性性.對于任意的a,b∈q,e(ga,gb)=e(g,g)ab;

2) 非退化性.e(g,g)≠1;

3) 可計算性.對于任意的P,Q∈G，e(P,Q)可有效計算.

則e為群G,G1上的雙線性對.

1.3 內積協議

定義1. 內積問題. Alice擁有向量X=(x1,x2,…,xn),Bob擁有向量Y=(y1,y2,…,yn).在不揭示雙方向量隱私的條件下，兩者合作計算出內積〈X,Y〉=x1y1+x2y2+…+xnyn的值.

內積問題是安全多方計算中的基本問題，針對該問題構造的內積協議是構建安全多方計算協議的基本模塊.內積協議最早由Atallah等人[15]提出，后來有很多文獻[16-22]分別根據不同程度的復雜性和安全性提出了不同的方法.

1.4 安全多方計算的安全性

1) 半誠實參與者

安全多方計算的協議運行環境分為半誠實參與者模型和惡意攻擊者模型[23]，半誠實參與者指協議方將誠實地執行協議，不會篡改輸入和輸出信息，但可能會保留計算的中間結果，試圖推導出協議之外的信息或者他人的信息.

2) 半誠實模型下的安全性定義

Goldreich[23]利用比特承諾和零知識證明理論設計了一個編譯器，這個編譯器可以將在半誠實參與者條件下保密計算函數f的協議π自動生成在惡意參與者條件下也能保密計算f的協議π′.新的協議π′可以迫使惡意參與者以半誠實方式參與協議的執行，否則就會被發現.因此大多數情況下，我們只設計半誠實模型下的協議.當我們設計出所需要的半誠實模型下的安全多方協議時，只要按照Goldreich[23]的通用轉化方法就可以將原協議轉化為惡意模型下的新協議.基于這一結論，本文也只給出半誠實模型下的協議和相應的安全性模擬范例.

設f(x,y)為概率多項式函數，π是計算f的協議，設Alice擁有x，Bob擁有y，他們要在不暴露x,y的前提下，合作計算函數f(x,y)=(f1(x,y),f2(x,y)).計算的目的是為了讓Alice和Bob分別得到函數f的2個分量f1(x,y),f2(x,y).Alice在執行協議π的過程中所得到的視圖記為view1(x,y),輸出記作output1(x,y)；同理，Bob的視圖記為view2(x,y)，輸出記作output2(x,y).Goldreich在文獻[23]中給出計算不可區分性的半誠實參與者的安全兩方計算的定義，表述如下：

定義2. 我們說協議π保密地計算了f(x,y)，如果存在概率多項式時間模擬器S1與S2，使得式(1)、式(2)同時成立：

{(S1(x,f1(x,y)),f2(x,y))}

(1)

{(f1(x,y),S2(y,f2(x,y)))}

(2)

此定義說明了任何一方參與者視圖中的信息只能從自己輸入和所獲得的輸出中得到，即說明任何一方參與者視圖中不包含額外的信息，這樣就保證了在協議執行過程中,任何一方得不到其他方的私有信息.因此要證明一個兩方計算協議是保密的，就必須構造使得式(1)和式(2)成立的模擬器S1與S2.

2 問題的描述和轉化

2.1 問題的描述

安全計算集合包含關系：已知Alice擁有集合X={x1,x2,…,xn},Bob擁有集合Y={y1,y2,…,ym}，其中m≤n.除了2個集合的勢以外，在不泄露X和Y任何信息的情況下，Alice和Bob都想知道集合X和集合Y是否存在包含關系，即是否Y?X.

2.2 問題的轉化

Alice擁有集合X={x1,x2,…,xn}，則此集合可表示為一個n次的多項式:

定理1. 記以上多項式f(x)系數組成的向量a′=(a0,a1,…,an)，某一個元素y對應的向量記為b′=(1,y,y2,…,yn)，若y∈X?f(y)=0?〈a′,b′〉=0.

推論1. 記以上多項式f(x)系數組成的向量a′=(a0,a1,…,an)，另一個集合Y={y1,y2,…,ym}對應的向量記為

則有：

Y?X?(y1∧y2∧…∧ym)∈X?

f(y1)+f(y2)+…+f(ym)=0?〈a′,y′〉=0.

證明. 1) 充分性

Y?X?f(y1)+f(y2)+…+

f(ym)=0?〈a′,y′〉=0.

若Y?X，則對于Y中每一個點yi∈X，根據定理1，有f(yi)=0，則有：

(f(y1)=0)∧(f(y2)=0)∧…∧(f(yn)=0)，即有f(y1)+f(y2)+…+f(ym)=0，得到〈a′,y′〉=0.

2) 必要性

〈a′,y′〉=0?f(y1)+f(y2)+…+

f(ym)=0?Y?X.

?

根據內積的性質有：

于是得到〈a′,y′〉=0時，有(y1∧y2∧…∧ym)∈X.即若〈a′,y′〉=0，有f(y1)+f(y2)+…+f(ym)=0，得到Y?X.

由分析可以看出，要判斷2個集合是否包含(即是否Y?X)，只要計算2個集合轉化的向量內積是否為0(即是否〈a′,y′〉=0).

證畢.

3 基本協議

協議假設所有的參與者都在半誠實模型下，網絡之間傳輸都是公開信道.基于2.2節的轉化方法，我們給出基本協議1

協議1. 利用內積安全計算集合包含關系.

輸入: Alice保密輸入集合X={x1,x2,…,xn}、Bob保密輸入集合Y={y1,y2,…,ym}(m≤n)；

輸出: Alice和Bob都知道Y?X或者Y?X.

1) 利用2.2節的轉化方法，Alice將集合X表示成n次多項式f(x)，f(x)的系數對應的向量記為a′=(a0,a1,…,an).Bob將集合Y表示為向量：

2) Alice選取一個隨機數r(r≠0,1)，并計算f(x)系數的承諾gra0,gra1,…,gran發送給Bob.

gr[f(y1)+f(y2)+…+f(ym)].

若gr[f(y1)+f(y2)+…+f(ym)]=1，則說明：

r[f(y1)+f(y2)+…+f(ym)]=0，

即:

f(y1)+f(y2)+…+f(ym)=0?〈a′,y′〉=0，

因此，Y?X；否則Y?X.

4) Bob把結果告訴Alice.

分析：在協議1中，類似于Feldman[24]的VSS(verifiable secret sharing)方案中的承諾方法，利用離散對數保護Bob所持有的多項式f(x)的系數a0,a1,…,an的隱私性，但是兩者并不相同.Feldman的原VSS方案中的多項式系數是隨機選取，而且破解離散對數困難.而我們這里的多項式系數是定值，因此為了保護Alice多項式系數的隱私性，加入隨機數r.并且為了無法破解離散對數，隨機數r要在一個較大數域中選擇.這樣選擇的r保護了Alice的多項式系數a0,a1,…,an的隱私性，但并不影響最后的計算結果f(y1)+f(y2)+…+f(ym).

4 應用實例：公開保密判斷集合包含關系

協議1雖然保護了雙方的隱私，但仍然只適用于傳統模式：即只能由參與雙方交互完成，第三方并不能參與，否則有一方隱私就會泄露.但在一些場景中，比如云計算下的數據訪問、加密數據搜索、可公開仲裁的抗抵賴等環境，第三方必須參與運算.但由于第三方(服務器)是不可信的，用戶并不想暴露自己的隱私，那么如何在不可信第三方存在的情況下設計安全計算集合關系的協議呢？針對此問題，我們將協議1拓展，并結合雙線性對重新設計了適合此場景的協議2.

協議假設兩方和任何第三方驗證者都是半誠實模型，網絡之間都是公開信道，允許第三方和任何一方合謀.

協議2. 不可信第三方存在場景下公開判斷集合包含關系

輸入: Alice保密輸入集合X={x1,x2,…,xn}、Bob保密輸入集合Y={y1,y2,…,ym}(m≤n)；

輸出: 任何第三方(包括Alice和Bob)都知道Y?X或者Y?X.

y′=(m,(y1+y2+…+ym),…,

e(gra0,gm)=e(g,g)rma0，

e(gra1,g(y1+y2+…+ym))=e(g,g)ra1(y1+y2+…+ym)，

?

再計算乘積：

e(g,g)r[f(y1)+f(y2)+…+f(ym)].

若gr[f(y1)+f(y2)+…+f(ym)]=1，則說明 ：

r[f(y1)+f(y2)+…+f(ym)]=0，

即

f(y1)+f(y2)+…+f(ym)=0?〈a′,y′〉=0，

因此Y?X；否則Y?X.

4) 公布結果.

備注：以上的協議1、協議2，唯一泄露的就是2個集合的勢，但這并不是協議本身的缺陷.即使泄露了集合的勢，但這并不影響集合包含的保密判定，只要2個集合不是特殊的空集，這唯一的信息對于判定集合是否包含關系，并不起任何作用.關于這一點，Du等人在文獻[25]專門有論證：在設計協議時，如果在降低完美安全性的程度上，允許泄露的信息并不影響方案的有效性，那么這就是可接受性安全.而可接受性安全要根據具體問題，具體設定.

5 安全性分析

本節我們應用1.4節的安全性模擬范例給出本文2個協議的安全性證明.由于協議2和協議1證明過程相似，為了節省篇幅，我們證明了協議1、協議2只給出結論即可.

定理2. 協議1保密地判定了集合成員關系.

證明. 通過構造滿足式(1)和式(2)的模擬器S1,S2來證明本定理.在本協議中

f1(X,Y)=f2(X,Y)=(Y?X)

或者

f1(X,Y)=f2(X,Y)=(Y?X).

假設f1(X,Y)=f2(X,Y)=(Y?X)，構造模擬器S1.S1接受(X,f1(X,Y))作為輸入，工作步驟如下：

步驟1.S1接受輸入(X,Y?X)后，首先隨機選

步驟3.S1計算：

再計算乘積：

{(view1(x,y),output2(x,y))}.

同理，用類似的方法可構造模擬器S2,使得：

{(output1(x,y),view2(x,y))}.

證畢.

定理3. 在不可信第三方存在的情況下，協議2保密地判定了集合成員關系.

用定理2類似的方法可以證明定理3，這里不再一一贅述.

6 效率分析與比較

本節給出本文協議和引言中相關文獻[8,12-13]在計算復雜性、通信復雜性以及性能方面的比較.

1) 計算復雜度.為了便于比較，統一本文和文獻[8,12-13]中一方集合的勢為n，另一方集合的勢為m(n≥m).已存方案使用的多是公鑰加密算法和匹配查找的方法，由于公鑰加密算法的計算復雜性較高，而匹配查找的次數也制約著效率，因此以公鑰加密算法的加解密次數和匹配查找次數作為衡量計算復雜性的指標.文獻[8]中的協議需要n次加密和1次門限解密，由于1次門限解密的復雜性遠遠大于1次單獨解密的復雜性，為了有所區分，記1次門限解密為“1”次解密.文獻[12]中兩方各需要nm次加密.文獻[13]中的協議需要n次加密和1次單獨解密.本文的2個協議均沒有使用加解密算法.

2) 通信復雜度.衡量通信復雜度的指標用協議交換信息的位數，或者用通信輪數(round)，在多方保密計算研究中通常用輪數作為衡量通信復雜性的指標.

3) 性能.在本文中以各個協議是否可公開計算、是否適合不可信第三方存在的場景作為衡量性能的指標.

綜合以上分析，得到各個協議的效率比較如表1所示，性能比較如表2所示.

從表1可以看出，已存的所有方案都使用了公鑰加密算法，而我們的2個協議并沒有使用任何加解密算法，避免了煩瑣的公私鑰產生和加解密過程.此外，我們的2個協議也沒有使用任何匹配查找的方法，而文獻[12]在集合很大時，最壞情況下需要查找比較m次，明顯制約了效率.因此從表1可以看出我們設計的協議計算復雜性和通信復雜性都較低，效率憂于其他方案.

Table 1 Efficiency Comparison Between Ours and the existing Schemes表1 本文協議與現有方案的效率比較

Table 2 Performance Comparison Between Ours and the existing Schemes表2 本文協議與現有方案的性能比較

從表2可以看出，已存所有文獻都只適用于傳統模式：即只能參與者兩方完成保密計算，并不適合不可信第三方存在的情況，也不能公開保密計算.而我們在沒有提高計算復雜性和通信復雜性的同時，首次針不可信第三方存在的應用場景，設計了實用型協議2.這使得我們開拓了安全計算集合包關系的新應用場景，比如云計算下的數據訪問、加密數據搜索、可公開仲裁的抗抵賴等，也解決了引言中Mu等人[11]設計的加密方案中如何全隱私判斷集合包含關系的問題.

7 總結和開放問題

集合包含關系的安全計算是安全多方計算中很重要的組成部分，但是這方面的研究并不多.而已存在的方案大多利用了多次匹配查找和多次加解密算法，這在集合很大的情況下比較低效，并不實用.本文將原問題轉化為向量內積問題，然后基于數學難題和密碼學知識解決了此問題.我們設計的2個協議，并沒有使用任何加解密算法，避免了煩瑣的公私鑰產生和加解密過程，也沒有使用匹配查找的方法，因此效率較高.此外，我們設計的協議2開拓了安全計算集合包含關系的新應用場景，具有較強的現實意義.

在本文的協議中，最重要的一個思想，就是將原問題轉化.這種思想是安全多方計算的一個關鍵，因具體問題轉化方法不同，直接制約著利用的密碼學工具和方案的效率.本文將集合包含判斷問題利用代數性質轉化為內積的思想，進一步推廣可以解決多種集合關系的保密判斷，比如集合成員關系、集合的交集、并集等一類集合問題.反之，將這些安全多方計算中的集合關系嵌入到加密算法中，可以設計出不同以往的帶有集合屬性關系的加密方案.這些工作，我們都已經在陸續研究中.

我們的2個協議，為了提高效率，以接受性安全作為犧牲代價，有一定的信息泄露，雖然不影響協議的執行和有效性，但并未取得完美性安全.因此，可以進一步考慮如何設計關于此問題的完美安全性下的高效協議.以上這些問題都將是未來進一步研究的課題.

[1]Yao A C. Protocols for secure computations[C]Proc of the 23rd IEEE Symp on Foundations of Computer Science. Piscataway, NJ: IEEE, 1982: 160-164

[2]Freudiger J, Rane S, Brito A E, et al. Privacy preserving data quality assessment for high-fidelity data sharing[C]Proc of the ACM Workshop on Information Sharing & Collaborative Security. New York: ACM, 2014: 21-29

[3]Li Xiangyang, Jung T. Search me if you can privacy-preserving location query service[C]Proc of IEEE INFOCOM’13. Piscataway, NJ: IEEE, 2013: 2760-2768

[4]Yang Jing, Zhao Jiashi, Zhang Jianpei. A privacy preservation method for high dimension data mining[J]. Acta Electronica Sinica, 2013, 41(11): 2187-2192 (in Chinese)(楊靜, 趙家石, 張健沛. 一種面向高維數據挖掘的隱私保護方法[J]. 電子學報, 2013, 41(11): 2187-2192)

[5]Samanthula B K, Elmehdwi Y, Howser G, et al. A secure data sharing and query processing framework via federation of cloud computing[J]. Information Systems, 2015, 48(c): 196-212

[6]Kerschbaum F. Privacy-preserving computation[G]LNCS 8319: Proc of the Annual Privacy Forum. Berlin: Springer, 2014: 41-54

[7]Freedman M J, Nissim K, Pinkas B. Efficient private matching and set intersection[G]LNCS 3027: Proc of Advances in Cryptology (EuroCrypt’04). Berlin: Springer, 2004: 1-19

[8]Kissner L, Song D. Privacy-preserving set operations[G]LNCS 3621: Proc of Advances in Cryptology (Crypt’05). Berlin: Springer, 2005: 241-257

[9]Clifton C, Kantarcioglu M, Lin X D, et al. Tools for privacy-preserving distributed data mining[J]. ACM SIGKDD Explorations Newsletter, 2002, 4(2): 28-34

[10]Xia Feng, Yang Bo, Zhang Mingwu, et al. Secure two-party computation for set intersection and set equality problems based on LWE[J]. Journal of Electronics and Information Technology, 2012, 34(2): 462-467 (in Chinese)(夏峰, 楊波, 張明武, 等. 基于 LWE 的集合相交和相等的兩方保密計算[J]. 電子與信息學報, 2012, 34(2): 462-467)

[11]Guo Fuchun, Mu Yi, Willy S. Subset membership encryption and its applications to oblivious transfer[J]. IEEE Trans on Information Forensics & Security, 2014, 9(7): 1098-1107

[12]Li Shundong, Si Tiange, Dai Yiqi. Secure multi-party computation about set-inclusion graph-inclusion[J]. Journal of Computation Research and Development, 2005, 42(10): 1647-165 (in Chinese)(李順東, 司天歌, 戴一奇. 集合包含與幾何包含的多方保密計算[J]. 計算機研究與發展, 2005, 42(10): 1647-165)

[13]Li Ronghua, Wu Chuankun, Zhang Yuqin. Secure computation protocols for testing the inclusion relation of sets[J]. Chinese Journal of Computers, 2009, 32(7): 1337-1346 (in Chinese)(李榮花, 武傳坤, 張玉清. 判斷集合包含關系的安全計算協議[J]. 計算機學報, 2009, 32(7): 1337-1346)

[14]Mitsunari S, Sakai R, Kasahara M. A new traitor tracing[J]. IEICE Trans on Fundamentals of Electronics, Communications and Computer Sciences, 2002, 85(2): 481-484

[15]Atallah M J, Du W L. Secure multi-party computational geometry[G]LNCS 2125: Proc of the Workshop on Algorithms and Data Structures. Berlin: Springer, 2001: 1165-1179

[16]Liu Fang, Ng W K, Zhang Wei. Secure scalar product for big-data in MapReduce[C]Proc of 2015 1st IEEE Int Conf on Big Data Computing Service and Applications. Piscataway, NJ: IEEE, 2015: 120-129

[17]Calvino A, Ricci S, Domingo-Ferrer J. Privacy-preserving distributed statistical computation to a semi-honest multi-cloud[C]Proc of IEEE Conf on Communications and Network Security. Piscataway, NJ: IEEE, 2015: 506-514

[18]Zhu Youwen, Takagi T. Efficient scalar product protocol and its privacy-preserving application[J]. International Journal of Electronic Security and Digital Forensics, 2015, 7(1): 1-19

[19]Mohammed N, Alhadidi D, Fung B, et al. Secure two-party differentially private data release for vertically partitioned data[J]. IEEE Trans on Dependable and Secure Computing, 2014, 11(1): 59-71

[20]De I, Tripathy A. A secure two party hierarchical clustering approach for vertically partitioned data set with accuracy measure[G]Proc of the Advances in Intelligent Systems and Computing. Berlin: Springer, 2014: 153-162

[21]Sheng Gang, Wen Tao, Guo Quan, et al. Privacy preserving inner product of vectors in cloud computing[J]. International Journal of Distributed Sensor Networks, 2014, 6: 1-6

[22]Dong Changyu, Chen Liqun. A fast secure dot product protocol with application to privacy preserving association rule mining[G]LNCS 8443: Proc of the Advances in Knowledge Discovery and Data Mining. Berlin: Springer, 2014: 606-617

[23]Goldreich O. Foundations of Cryptography: Basic Applications[M]. London: Cambridge University Press, 2004: 599-729

[24]Feldman P. A practical scheme for non-interactive verifiable secret sharing[C]Proc of the 28th IEEE Annual Symp on Foundations of Computer Science. Piscataway, NJ: IEEE, 1987: 427-438

[25]Du Wenliang, Zhan Zhijun. A practical approach to solve secure multi-party computation problems[C]Proc of the 2002 Workshop on New Security Paradigms. New York: ACM, 2002: 127-135

Chen Zhenhua, born in 1976. PhD. Associate professor. Her main research interests include secret sharing and secure multi-party computation, etc.

Li Shundong, born in 1963. PhD, professor. His main research interests include information hiding and secure multi-party computation, etc.

Wang Daoshun, born in 1964. PhD, associate professor. His main research interests include key management, digital watermarking and multimedia security, etc.

Huang Qiong, born in 1981. PhD, professor. Member of CCF and Chinese Association for Cryptologic Research. His main research interests include cryptography and information security.

Dong Lihong, born in 1968. PhD, professor. Her main research interests include scientific computation and system engineer, etc.

Protocols for Secure Computation of Set-Inclusion with the Unencrypted Method

Chen Zhenhua1,2, Li Shundong3, Wang Daoshun4, Huang Qiong5, and Dong Lihong1

1(SchoolofComputerScienceandTechnology,Xi’anUniversityofScienceandTechnology,Xi’an710054)2(StateKeyLaboratoryofInformationSecurity(InstituteofInformationEngineering,ChineseAcademyofSciences),Beijing100093)3(SchoolofComputerScience,ShaanxiNormalUniversity,Xi’an710062)4(DepartmentofComputerScienceandTechnology,TsinghuaUniversity,Beijing100084)5(CollegeofMathematicsandInformatics,SouthChinaAgriculturalUniversity,Guangzhou510642)

The most existing protocols for secure computation of set-inclusion are based on multiple public-key encryption algorithms and cannot either be computed publicly, which makes the computation complexity high and the application range limited as well. To cope with these problems, we design two protocols for secure computation of set-inclusion with the unencrypted method. Protocol 1 first transforms the original problem into the scalar-product problem, and then solves it with the hard problem in cryptography. Next, we present the practical protocol 2 under a certain scenario with a third untrusted party, in which we solve the set-inclusion problem combing the bilinear pairing with the hard problem in cryptography. Lastly, we give the security proof of two protocols, the performance analysis and comparison with others. Both of our protocols employ neither any public-key encryption algorithm nor multiple matching searches so as to avoid the intricate procedures of key-generation, encryption and decryption. This makes our protocols more efficient and concise than the previously known. In addition, we extend the secure computation of set-inclusion to a new application scenario, in which we can determine the set-inclusion relation publicly without revealing the privacy of both sets even if the untrusted third party exists.

set-inclusion; secure computation; bilinear pairing; hard mathematics problem; public determination

2016-01-19；

2016-10-10

國家自然科學基金項目(61272435)；西安科技大學博士啟動金項目(2015QDJ008)；信息安全國家重點實驗室開放課題基金項目(2016-MS-19) This work was supported by the National Natural Science Foundation of China (61272435), the Research Fund for the Doctoral Program of Xi’an University of Science and Technology (2015QDJ008), and the Open Fund for State Key Laboratory of Information Security (2016-MS-19).

TP309.7