亢 佳，楊曉藝，劉 新

(陜西師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院，陜西 西安 710119)

集合間基本操作的多方保密計(jì)算

亢 佳，楊曉藝，劉 新

(陜西師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院，陜西 西安 710119)

多方保密計(jì)算是近年來國際密碼學(xué)界研究的熱點(diǎn)問題。集合是科學(xué)研究中一個(gè)非常重要的概念，其在數(shù)學(xué)領(lǐng)域具有無可比擬的特殊重要性?，F(xiàn)實(shí)生活中的許多問題可以轉(zhuǎn)化成集合之間的基本操作問題來解決。對(duì)集合間的保密操作，如保密地計(jì)算集合交集、并集是多方保密計(jì)算中的一個(gè)重要方面，在保密的數(shù)據(jù)挖掘，保密的數(shù)據(jù)庫查詢等方面有重要的意義，在現(xiàn)實(shí)生活中也有廣泛的應(yīng)用前景和實(shí)用價(jià)值。為了解決集合之間基本操作的保密問題，提出了基于Paillier加法同態(tài)加密算法的安全兩數(shù)差平方計(jì)算協(xié)議和求解集合交集的保密協(xié)議，并設(shè)計(jì)了基于百萬富翁協(xié)議的求解集合并集的保密協(xié)議。理論分析表明，基于Paillier加法同態(tài)加密算法的安全兩數(shù)差平方計(jì)算協(xié)議以及求解集合交集與并集的保密協(xié)議具有較好的正確性和安全性。

多方保密計(jì)算；集合交集；集合并集；加法同態(tài)

0 引 言

多方保密計(jì)算是近年來國際密碼學(xué)界的一個(gè)研究熱點(diǎn)[1-5]，在計(jì)算科學(xué)中占有重要地位。多方保密計(jì)算問題由Yao[6]最先提出，Goldreich等[7]對(duì)其進(jìn)行了深入研究，推動(dòng)多方保密計(jì)算理論的發(fā)展。

許多學(xué)者致力于研究具有實(shí)際應(yīng)用背景的多方保密計(jì)算問題以及它們的解決方案，所研究的問題包括比較兩個(gè)數(shù)的大小[8-11]、保密的數(shù)據(jù)挖掘[12]、比較兩條信息是否相同[13]、保密的數(shù)據(jù)庫查詢、保密拍賣[14]、保密的統(tǒng)計(jì)分析、保密的計(jì)算幾何[15-18]等。

集合是科學(xué)研究中一個(gè)非常重要的概念，其在數(shù)學(xué)領(lǐng)域具有無可比擬的特殊重要性。現(xiàn)實(shí)生活中的許多問題可以利用集合間的基本操作問題來解決。保密的對(duì)集合間的操作是多方保密計(jì)算中的一個(gè)重要方面，在保密的數(shù)據(jù)挖掘、保密的數(shù)據(jù)庫查詢等方面有重要意義，同時(shí)在現(xiàn)實(shí)生活中也有很高的實(shí)用價(jià)值。目前已有的關(guān)于集合間基本操作的研究有保密地求兩個(gè)集合的交集、并集，集合成員的保密判定問題等。

保密地求集合間的幾種基本操作等問題在現(xiàn)實(shí)生活中具有重要意義。例如：2個(gè)護(hù)膚品旗艦店想掌握他們顧客的消費(fèi)趨勢(shì)，也就是他們想得到顧客在旗艦店1買高端護(hù)膚品S1同時(shí)在旗艦店2買中端護(hù)膚品S2的可能性。但是兩個(gè)旗艦店為了保護(hù)顧客的隱私，同時(shí)又不想泄露自己的銷售情況，都不愿把自己的詳細(xì)信息告訴對(duì)方。在這種情況下，就需要用到保密地求集合交集的協(xié)議[19]。

為此，提出了基于加法同態(tài)性加密方案的安全兩數(shù)差平方計(jì)算協(xié)議，并該協(xié)議的基礎(chǔ)上提出求解集合交集的保密協(xié)議以及基于百萬富翁協(xié)議的求解集合并集保密協(xié)議，同時(shí)進(jìn)行了安全性和正確性分析。

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

1.1 可交換的加密方案

對(duì)于一個(gè)加密方案E，如果EKp(EKq(x))=EKq(EKp(x)),其中EKp(x)表示利用密鑰Kp對(duì)x進(jìn)行加密，則稱方案E為可交換的加密方案[20]。定義二元謂詞如下:

更具體地說，如果一個(gè)加密方案滿足如下性質(zhì)，則稱其為可交換的加密方案[20]。

(1)加密得到的結(jié)果與加密時(shí)所使用密鑰的順序無關(guān)。

(2)不同的明文經(jīng)過加密后所得到的密文也不相同。

(3)某一明文m1和對(duì)應(yīng)的密文Ep(m1)(但不泄露密鑰p)，對(duì)于另外任一明文m2，攻擊者不能在多項(xiàng)式時(shí)間內(nèi)對(duì)m2進(jìn)行加密或?qū)p(m2)進(jìn)行解密。

1.2 比較兩數(shù)相等的協(xié)議

Alice有一個(gè)私有數(shù)據(jù)x，Bob有一個(gè)私有數(shù)據(jù)y，他們都想保密地確定x和y是否相等且不泄露x和y的信息。E是一個(gè)可交換加密方案,Alice有密鑰Kp，Bob有密鑰Kq。比較兩數(shù)相等的解決方案[20]如下：

(1)Alice計(jì)算EKp(x),Bob計(jì)算EKq(y)。

(2)Alice和Bob交換EKp(x)和EKq(y)。

(3)Alice計(jì)算EKp(EKq(y))，Bob計(jì)算

EKq(EKp(x))。

(4)Alice和Bob交換EKp(EKq(y))和EKq(EKp(x))，如果EKp(EKq(y))=EKq(EKp(x))，則輸出1，否則輸出0。

1.3 同態(tài)加密方案

同態(tài)加密方案是一種特殊的公鑰加密方案[21],其概念是文獻(xiàn)[22]提出的。同態(tài)加密的特殊性質(zhì)使得能夠直接對(duì)密文進(jìn)行運(yùn)算來代替對(duì)明文的運(yùn)算，從而取得同樣的效果，這樣不影響明文的保密性。簡(jiǎn)單來說，對(duì)密文的計(jì)算等價(jià)于明文計(jì)算之后再加密。同態(tài)加密方案在云計(jì)算和多方保密計(jì)算中發(fā)揮著重要的作用。

目前存在許多同態(tài)加密方案,如RSA公鑰加密方案、ElGamal加密方案、Paillier加密方案、Goldwasser加密方案等。運(yùn)用Paillier加密方案的加法同態(tài)性[23]，即滿足EK(x)?EK(y)=EK(x+y)，從加法同態(tài)性還可以得到E(x)m=E(mx)。

1.4 安全性定義

半誠實(shí)參與者[24]：各個(gè)參與者在協(xié)議執(zhí)行過程中不會(huì)泄露信息或欺騙，也不會(huì)中途退出協(xié)議，完全嚴(yán)格按照協(xié)議的規(guī)定執(zhí)行協(xié)議的每一步。但是他們可能會(huì)通過協(xié)議執(zhí)行過程中自己所得到的信息來試圖推斷其他有用的相關(guān)信息。

大部分研究多方保密計(jì)算的文獻(xiàn)均假設(shè)多方保密計(jì)算的參與者為半誠實(shí)參與者，這是因?yàn)橹灰軌蛟O(shè)計(jì)出在半誠實(shí)參與者模型下保密計(jì)算f的協(xié)議π，就可以通過位承諾方法將π轉(zhuǎn)換成惡意攻擊者參與的模型下保密計(jì)算f的協(xié)議。在這個(gè)轉(zhuǎn)換協(xié)議中，一個(gè)惡意的參與者將被迫按照半誠實(shí)的參與者行事，否則會(huì)被發(fā)現(xiàn)。簡(jiǎn)單地說，半誠實(shí)參與者在協(xié)議執(zhí)行過程中將不折不扣地執(zhí)行協(xié)議，但他們可能會(huì)保留計(jì)算的中間結(jié)果試圖推導(dǎo)出其他參與者的輸入。

定義1(半誠實(shí)參與者的保密性[25])：對(duì)于一個(gè)函數(shù)f,如果存在概率多項(xiàng)式時(shí)間算法S1與S2(有時(shí)稱這樣的多項(xiàng)式時(shí)間算法為模擬器),使得

(1)

(2)

2 多方保密計(jì)算方案

2.1 安全兩數(shù)差平方計(jì)算協(xié)議

問題描述：Alice有一個(gè)實(shí)數(shù)x，Bob有一個(gè)實(shí)數(shù)y。Alice希望保密地得到s，Bob希望保密地得到w，且滿足s=w+(x-y)2。具體步驟如下：

(1)Alice與Bob共同協(xié)商一個(gè)具有加法同態(tài)性的加密方案E。Alice選定公私密鑰對(duì)(PK,SK)，并且將公鑰PK告訴Bob，私鑰SK保密。

(2)Alice選定非零隨機(jī)數(shù)r1，用公鑰PK加密r1x并把E(r1x)，r1發(fā)送給Bob。

(3)Bob選擇隨機(jī)數(shù)r2,r3，計(jì)算并把t1,t2發(fā)送給Alice。

t1=E(r1x)y⊕E(r2)=E(r1xy+r2)

(3)

t2=E(r1y2)⊕E(r3)=E(r1y2+r3)

(4)

(4)Alice用私鑰SK解密t1,t2，得到s1,s2,并計(jì)算s。

s1=D(t1)=D(E(r1xy+r2))=r1xy+r2

(5)

s2=D(t2)=D(E(r1y2+r3))=r1y2+r3

(6)

s=s2-2s1+r1x2=r1(x2+y2-2xy)+r3-2r2

(7)

(5)Bob計(jì)算w=r3-2r2。

協(xié)議正確性分析：

根據(jù)加法同態(tài)加密方案的性質(zhì)，可知E(r1x)y⊕E(r2)=E(r1xy+r2)，E(r1y2)⊕E(r3)=E(r1y2+r3)。

在Alice解密后得到s，s=s2-2s1+r1x2=r1(x2+y2-2xy)+r3-2r2，此時(shí)w=r3-2r2=s-r1(x2+y2-2xy)。因此，該安全兩數(shù)差平方計(jì)算協(xié)議是正確的。

協(xié)議安全性分析：

在步驟2中，Alice與Bob雖然出現(xiàn)了信息交換，但是由于Bob不知道解密的私鑰，不會(huì)推測(cè)出x的值，所以不會(huì)有信息泄漏；步驟4中，雖然Alice擁有解密的私鑰，但是隨機(jī)數(shù)r2,r3僅有Bob知道，Alice不會(huì)由s推測(cè)出(x-y)2以及y的值。由此可知，該安全兩數(shù)差平方計(jì)算協(xié)議在半誠實(shí)模型下是安全的。

2.2 求集合交集的多方保密計(jì)算方案

問題描述：Alice擁有一個(gè)集合A={a1,a2,…,am}，Bob擁有一個(gè)集合B={b1,b2,…,bn}，他們想保密地判定集合A和集合B是否相交，并求得交集I。

協(xié)議一設(shè)計(jì)：

輸入：參與方Alice擁有一個(gè)私有集合A={a1,a2,…,am}，Bob擁有一個(gè)私有集合B={b1,b2,…,bn}。

輸出：兩個(gè)集合的交集I。

1)設(shè)置I=?。

2)對(duì)于集合A和集合B中的每個(gè)元素，Alice和Bob分別做以下工作：

(1)Alice和Bob分別調(diào)用安全兩數(shù)差平方協(xié)議，保密地計(jì)算(ai-bj)2。計(jì)算完成后，Alice得到sij，Bob得到wij。

(2)Alice和Bob調(diào)用比較兩數(shù)相等協(xié)議判斷是否sij=wij。如果相等，則記錄相應(yīng)的ai，I∪{ai}。

協(xié)議一正確性分析：如果ai=bj，那么sij=wij，由此可知協(xié)議正確。

協(xié)議一安全性分析：協(xié)議一的安全性基于安全兩數(shù)差平方協(xié)議的安全性，證明過程不再贅述。

協(xié)議二設(shè)計(jì)：

輸入：參與方Alice擁有一個(gè)私有集合A={a1,a2,…,am}，Bob擁有一個(gè)私有集合B={b1,b2,…,bn}。

輸出：兩個(gè)集合的交集I。

步驟：

(1)Alice與Bob協(xié)商一個(gè)可交換的加密方案E。Alice選取密鑰KA，Bob選取密鑰KB。

(2)Alice利用密鑰KA對(duì)A={a1,a2,…,am}進(jìn)行加密，經(jīng)過計(jì)算得到集合EKA(A)={EKA(a1),EKA(a2),…,EKA(am)}，并將集合EKA(A)全部發(fā)送給Bob。

(3)Bob利用密鑰KB加密EKA(A)，經(jīng)過計(jì)算得到集合EKB(EKA(A))={EKB(EKA(a1)),EKB(EKA(a2)),…,EKB(EKA(am))}。

(4)Bob以EKB(EKA(A))集合中的元素構(gòu)造一個(gè)函數(shù)：

f(x)=[x-EKB(EKA(a1))]×[x-EKB(EKA(a2))]× …×[x-EKB(EKA(am))]

(8)

(5)Bob利用密鑰KB對(duì)B={b1,b2,…,bn}進(jìn)行加密，經(jīng)過計(jì)算得到集合EKB(B)={EKB(b1),EKB(b2),…,EKB(bn)}，并將集合EKB(B)發(fā)送給Alice。

(6)Alice利用密鑰KA加密EKB(B)，經(jīng)過計(jì)算得到集合EKA(EKB(B))={EKA(EKB(b1)),EKA(EKB(b2)),…,EKA(EKB(bn))}，并將結(jié)果發(fā)送給Bob。

(7)對(duì)于i∈{1,2,…,n}，Bob判斷是否f(EKA(EKB(bi)))=0，若等于0，則Bob可判定bi∈I。

(8)Bob把得到的I發(fā)送給Alice。

協(xié)議二安全性分析：Alice用自己的密鑰對(duì)A={a1,a2,…,am}和EKB(B)進(jìn)行加密，Bob用自己的密鑰對(duì)B={b1,b2,…,bn}和EKA(A)進(jìn)行加密，此時(shí)在半誠實(shí)模型下忽略信息泄露的問題。雖然整個(gè)協(xié)議中出現(xiàn)雙方信息交互的過程，但是由于不知道私鑰，不存在信息泄露。所以協(xié)議二是安全的。

2.3 求集合并集的多方保密計(jì)算方案

問題描述：Alice擁有一個(gè)集合A={a1,a2,…,am}，Bob擁有一個(gè)集合B={b1,b2,…,bn}，他們想保密地求集合A和B的并集J=A∪B，而不泄露集合A和B的任何私有信息。

協(xié)議三設(shè)計(jì)：

輸出：兩個(gè)集合的并集J=A∪B。

步驟：

在協(xié)議執(zhí)行之前，Alice和Bob共同商定有限域U中元素的一種大小關(guān)系，使得U中的每一個(gè)元素對(duì)應(yīng)一個(gè)特定的整數(shù)編碼。

(3)Alice與Bob調(diào)用百萬富翁協(xié)議[26]比較mA和mB，協(xié)議結(jié)束后，Alice將得到的比較結(jié)果發(fā)送給Bob。

(4)如果mA>mB，那么Alice將mA從集合A中去除，并將mA放入集合J中；如果mA

重復(fù)步驟(2)～(4)，直到集合A或者集合B中沒有元素為止。

協(xié)議三正確性分析：通過調(diào)用百萬富翁協(xié)議可知是否mA>mB，從而Alice和Bob可以從集合A和集合B中找到編碼值最大的元素，通過循環(huán)，即可將集合A和集合B中的元素不重復(fù)地放入到集合J中，所以協(xié)議三是正確的。

協(xié)議三安全性分析：基于所調(diào)用的百萬富翁協(xié)議的安全性[21]，所以協(xié)議三是安全的。

協(xié)議三復(fù)雜性分析：協(xié)議三的計(jì)算復(fù)雜性主要來自于協(xié)議第3步，在協(xié)議執(zhí)行過程中百萬富翁協(xié)議的執(zhí)行次數(shù)為O(n)。所以協(xié)議三與以前的協(xié)議相比，計(jì)算復(fù)雜性有了一定程度的降低。

3 結(jié)束語

保密地求解集合的交集與并集對(duì)現(xiàn)實(shí)生活的實(shí)際意義越來越重要。為此，提出了基于具有加法同態(tài)性加密方案的安全兩數(shù)差平方協(xié)議、保密判斷集合交集的協(xié)議以及基于百萬富翁協(xié)議求解集合并集的保密協(xié)議，并對(duì)協(xié)議的正確性和安全性進(jìn)行了分析。目前，相關(guān)的研究都是基于半誠實(shí)模型的，對(duì)于多方保密計(jì)算的研究與應(yīng)用有重要的理論意義。應(yīng)該看到，惡意模型的安全性更高，更具有實(shí)際應(yīng)用的前景，實(shí)現(xiàn)惡意模型下的集合操作將是今后的研究方向。

[1] Goldwasser S. Multi party computations: past and present[C]//Proceedings of the sixteenth annual ACM symposium on principles of distributed computing.[s.l.]:ACM,1997:1-6.

[2] Goldreich O.Secure multi-party computation(working draft)[EB/OL].2002.http://www.wisdom.weizmann.ac.il home oded public-html foc.html.

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

[4] Lynn B, Prabhakaran M,Sahai A.Positive results and techniques for obfuscation[C]//Advances in cryptology.Berlin:Springer,2004:20-39.

[5] Aggarwal G,Mishra N,Pinkas B.Secure computation of the k th-ranked element[C]//Advances in cryptology.Berlin:Springer,2004:40-55.

[6] Yao A.Protocols for secure computations[C]//23rd annual symposium on foundations of computer science.[s.l.]:IEEE,1982:160-164.

[7] Goldreich O,Micali S,Wigderson A.How to play any mental game[C]//Proceedings of the nineteenth annual ACM symposium on theory of computing.[s.l.]:ACM,1987:218-229.

[8] Lin H Y,Tzeng W G.An efficient solution to the millionaires’ problem based on homomorphic encryption[C]//International conference on applied cryptography and network security.[s.l.]:[s.n.],2005:456-466.

[9] Li Shundong,Wang Daoshun.Efficient secure multiparty computation based on homomorphic encryption[J].Acta Electronica Sinica,2013,41(4):798-803.

[10] Sheikh R,Mishra D K,Kumar B.Secure multiparty computation: from millionaires problem to anonymizer[J].Information Security Journal:A Global Perspective,2011,20(1):25-33.

[11] Grigoriev D,Shpilrain V.Yao's millionaires' problem and decoy-based public key encryption by classical physics[J].International Journal of Foundations of Computer Science,2014,25(4):409-417.

[12] Lindell Y,Pinkas B.Privacy preserving data mining[J].Journal of Cryptology,2002,15(3):177-206.

[13] Fagin R,Naor M,Winkler P.Comparing information without leaking it[J].Communications of the ACM,1996,39(5):77-85.

[14] Cachin C.Efficient private bidding and auctions with an oblivious third party[C]//Proceedings of the 6th ACM conference on computer and communications security.[s.l.]:ACM,1999:120-127.

[15] Atallah M J,Du W.Secure multi-party computational geometry[C]//Workshop on algorithms and data structures.[s.l.]:[s.n.],2001:165-179.

[16] Du W,Atallah M J.Secure multi-party computation problems and their applications:a review and open problems[C]//Proceedings of the 2001 workshop on new security paradigms.[s.l.]:ACM,2001:13-22.

[17] Li Shundong,Wu Chunying,Wang Daoshun,et al.Secure multiparty computation of solid geometric problems and their applications[J].Information Sciences,2014,282:401-413.

[18] Li Shundong,Wu Chunying,Wang Daoshun,et al.A secure multi-party computation solution to intersection problems of sets and rectangles[J].Progress in Natural Science,2006,16(5):538-545.

[19] 鄭 強(qiáng).不同模型下若干安全多方計(jì)算問題的研究[D].北京:北京郵電大學(xué),2010.

[20] 李順東,王道順,戴一奇,等.兩個(gè)集合相等的多方保密計(jì)算[J].中國科學(xué):信息科學(xué),2009,39(3):305-310.

[21] Frederick R.Core concept:homomorphic encryption[J].Proceedings of the National Academy of Sciences,2015,112(28):8515-8516.

[22] Rivest R L,Adleman L,Dertouzos M L.On data banks and privacy homomorphisms[J].Foundations of Secure Computation,1978,4(11):169-180.

[23] Wu J H,Zhang P,Shi X B.Research of MA protection based on addition-multiplication homomorphism and composite function technology[J].Journal of Chinese Computer Systems,2012,33(10):2223-2226.

[24] Li Shundong,Wang Daoshun,Dai Yiqi.Efficient secure multiparty computational geometry[J].Chinese Journal of Electronics,2010,19(2):324-328.

[25] Goldreich O.Foundations of cryptography:volume 2,basic applications[M].[s.l.]:Cambridge University Press,2004.

[26] 李順東,戴一奇,游啟友.姚氏百萬富翁問題的高效解決方案[J].電子學(xué)報(bào),2005,33(5):769-773.

Secure Multi-party Computation of Basic Operation among Sets

KANG Jia，YANG Xiao-yi，LIU Xin

(School of Computer Science,Shaanxi Normal University,Xi’an 710119,China)

Secure multi-party computation is a focus in international cryptographic community study in recent years.The set is a very important concept in scientific research and has an unparalleled special importance in the field of mathematics.Many problems in real life can be solved by using basic operation between sets.The private operation of sets is an important aspect on secure multi-party computation,such as problem of privately determining whether two sets are intersecting and of set union.The secure multi-party computation for basic operation between sets has most important significance on private data mining and confidential database query and also has broad application perspectives and practical value at the same time in real life.In order to solve the problems of set operation,a protocol about two difference square calculation based on the addition homomorphism of Paillier encryption algorithm is presented,which is employed to privately determine whether two sets are intersecting and designed to solve the set union problems depended on Yao's Millionaires' Problem.The theoretical analysis shows that the they have both high accuracy and safety.

secure multi-party computation;set intersection;set union;addition homomorphism

2016-09-20

2016-12-21 網(wǎng)絡(luò)出版時(shí)間：2017-07-05

中央高校基本科研業(yè)務(wù)費(fèi)專項(xiàng)(GK201504017)；包頭市科技計(jì)劃項(xiàng)目(2014S2004-2-1-15)

亢 佳(1992-)，女，碩士研究生，通訊作者，研究方向?yàn)槊艽a學(xué)與信息安全。

http://kns.cnki.net/kcms/detail/61.1450.TP.20170705.1652.066.html

TP31

A

1673-629X(2017)08-0110-05

10.3969/j.issn.1673-629X.2017.08.023