孫偉　張永

摘 要：不同于傳統(tǒng)網(wǎng)絡(luò)，在移動(dòng)互聯(lián)網(wǎng)與云計(jì)算環(huán)境下，眾多的第三方服務(wù)依賴于用戶數(shù)據(jù)的收集與分析。如何在保證用戶數(shù)據(jù)安全與隱私的情況下，得到合理的分析與統(tǒng)計(jì)結(jié)果，一直是網(wǎng)絡(luò)安全領(lǐng)域研究的熱點(diǎn)問(wèn)題。本文對(duì)用戶數(shù)據(jù)隱私保護(hù)需求進(jìn)行了總結(jié)，分析了目前在數(shù)據(jù)收集過(guò)程中常用的交集計(jì)算相關(guān)算法的優(yōu)缺點(diǎn)，對(duì)未來(lái)的研究方向做出了總結(jié)。

關(guān)鍵詞：隱私保護(hù)；安全多方計(jì)算；數(shù)據(jù)安全

中圖分類(lèi)號(hào)：TP393.08 文獻(xiàn)標(biāo)識(shí)碼：A

Abstract：Unlike applications in traditional computer network，most third-party applications in mobile internet and cloud computing are based the aggregation and analysis of users data.How to get the analysis and statistic results without violate users private is always the key problem of network security.In this paper，we overviewed the algorithm of set intersection，which is the most common function of data aggregation.At the same time，we summarize the prospect on the future research.

Keywords：privacy insurance；security multi-party computation；data security

1 引言（Introduction）

隨著移動(dòng)互聯(lián)網(wǎng)與社交網(wǎng)絡(luò)的發(fā)展，越來(lái)越多的第三方應(yīng)用服務(wù)依賴于用戶數(shù)據(jù)的收集與行為分析。諸如，F(xiàn)acebook的好友發(fā)現(xiàn)與推薦服務(wù)，eBay的精準(zhǔn)商品推薦機(jī)制等等。傳統(tǒng)意義上，用戶對(duì)于將個(gè)人屬性、行為、習(xí)慣等數(shù)據(jù)透漏給第三方應(yīng)用，持謹(jǐn)慎的態(tài)度，大多數(shù)用戶并不愿意將個(gè)人行為數(shù)據(jù)公開(kāi)給第三方應(yīng)用。但是，隨著移動(dòng)互聯(lián)網(wǎng)與社交網(wǎng)絡(luò)的發(fā)展，越來(lái)越多的第三方應(yīng)用的服務(wù)提供質(zhì)量，依賴于用戶行為數(shù)據(jù)的分析，用戶為了得到更好，更為精準(zhǔn)的服務(wù)，越來(lái)越多的用戶愿意在保證個(gè)人數(shù)據(jù)安全的前提下，允許第三方應(yīng)用收集個(gè)人行為數(shù)據(jù)。因此，如何在第三方應(yīng)用數(shù)據(jù)收集過(guò)程中，保護(hù)用戶的隱私數(shù)據(jù)不被泄漏，成為數(shù)據(jù)安全研究領(lǐng)域的一個(gè)重要問(wèn)題，同時(shí)也得到學(xué)術(shù)界越來(lái)越多的關(guān)注。簡(jiǎn)而言字，所謂的用戶隱私保證，指的是：第三方應(yīng)用可以得到用戶行為的統(tǒng)計(jì)結(jié)果，但每個(gè)具體用戶的數(shù)據(jù)，對(duì)于第三方應(yīng)用和其他用戶而言，依然是保密的。目前，第三方數(shù)據(jù)收集過(guò)程中的主要功能函數(shù)有：求加權(quán)和、求極值、排序、求交集、求并集等。其中，尋找不用用戶或用戶群之間的共同點(diǎn)，是第三方應(yīng)用在數(shù)據(jù)收集與服務(wù)提供過(guò)程中的核心問(wèn)題。目前，對(duì)于求用戶間交集的主要解決方案有安全多方計(jì)算協(xié)議，單項(xiàng)無(wú)碰撞哈希表方案，和基于多項(xiàng)式的集合表示方法兩種。

2 安全多方計(jì)算協(xié)議（Security multi-party computation protocol）

大多數(shù)目前運(yùn)行的第三方應(yīng)用在計(jì)算用戶加權(quán)和時(shí)，采用了安全多方計(jì)算（Secure Multi-party Computations，SMC）[1-3]， 在SMC方案中，每個(gè)參與者提供函數(shù)的一個(gè)輸入（自己的私有數(shù)據(jù)）， 用于共同計(jì)算某個(gè)預(yù)先設(shè)置的函數(shù)，出于安全考慮，要求參與者提供的輸入對(duì)其他人保密。在該過(guò)程中，用戶不用泄漏自己的私有數(shù)據(jù)給其他用戶。即，設(shè)由n個(gè)用戶戶X1…X（n-1）所參與多方安全計(jì)算，每個(gè)用戶持有私有數(shù)據(jù)xi，共同參與函數(shù)戶f（x1…xn）=（y1…yn）的計(jì)算。并且要求即使發(fā)生存在某些惡意參與者的情況下，仍能通過(guò)協(xié)議保證所有參與者數(shù)據(jù)的保密性，同時(shí)確保運(yùn)算的正確性，是的第i個(gè)參與者能夠正確的取得戶yi，并且除此之外無(wú)法得到其他任何信息。

SMC算法最早由Yao提出[3]（millionaire problem）。由于SMC可以在用戶數(shù)據(jù)保密的情況下計(jì)算多種函數(shù)，因此也被眾多應(yīng)用用來(lái)計(jì)算用戶交集。近年來(lái)，SMC得到了眾多學(xué)者的關(guān)注，其在密碼學(xué)上的地位也日益重要。被廣泛應(yīng)用于多方競(jìng)拍，電子投票等應(yīng)用中。目前安全多方計(jì)算已得到許多學(xué)者的研究，它是電子選舉、電子拍賣(mài)等密碼學(xué)協(xié)議的基礎(chǔ)。

研究證明，雖然SMC可以在保護(hù)用戶隱私的情況下安全計(jì)算預(yù)制函數(shù)，但仍然存在一些問(wèn)題需要解決，主要集中在以下幾個(gè)方面：

（1）SMC方案中，所用用戶處于一種合作的狀態(tài)，因此，用戶愿意也必須彼此間進(jìn)行通信來(lái)共同完成計(jì)算。但是，在第三方應(yīng)用中，大部分用戶只愿意和授權(quán)的第三方服務(wù)提供商進(jìn)行通信，并不愿意直接與其他用戶發(fā)生通信聯(lián)系。

（2）在第三方應(yīng)用的環(huán)境下，參與數(shù)據(jù)收集用戶的數(shù)量可能非常龐大（百萬(wàn)數(shù)量級(jí)），而SMC則是為小用戶數(shù)量應(yīng)用設(shè)計(jì)的方案（幾十到幾百數(shù)量級(jí)）。其計(jì)算量和通信量與用戶數(shù)量成正比[在半誠(chéng)實(shí)模式下為O（n），存在惡意用戶情況下為O（n2）]。因此，當(dāng)用戶數(shù)量變大時(shí)，性能下降十分嚴(yán)重。

（3）在第三用應(yīng)用數(shù)據(jù)收集環(huán)境下，某些用戶可能同時(shí)參與多個(gè)不同的數(shù)據(jù)收集進(jìn)程，在這種情況下的用戶隱私保護(hù)問(wèn)題，SMC并未考慮。

3 單向無(wú)碰撞哈希表方案（One-way hash table algorithm）

設(shè)兩個(gè)用戶X、Y分別持有集合：X={x1，x2，...，xn}，Y={y1，y2，...，yn}，用戶希望在不相互泄漏信息的情況下通過(guò)計(jì)算得到交集。即，計(jì)算結(jié)束后，如果n1、n2存在相同元素，則兩個(gè)用戶分別得到交集，但并不得到另外用戶的其他元素信息。endprint

單項(xiàng)無(wú)碰撞哈希算法：X、Y共同初始化一個(gè)hash函數(shù)，X將他集合中的元素，通過(guò)hash表，隱藏真實(shí)信息，得到：

h（X）={h（x1），h（x2），…，h（xn）}

并將hash后的結(jié)果發(fā)送給Y。Y將自身元素通過(guò)同一個(gè)hash表計(jì)算結(jié)果，得到：

h（Y）={h（y1），h（y2），…，h（yn）}

并與X發(fā)送過(guò)來(lái)的結(jié)果h（X）進(jìn)行比對(duì)，具有同樣hash結(jié)果的元素，即為交集元素。同理，X也可以同樣的到交集元素。

該算法的主要優(yōu)點(diǎn)在于原理簡(jiǎn)單，計(jì)算復(fù)雜度低，通常只需要接近常量的計(jì)算時(shí)間，即O（1）的時(shí)間級(jí)[4]。但是，該算法仍然存在明顯的缺陷：如果X、Y集合的值域過(guò)小，Y可以通過(guò)逐個(gè)檢驗(yàn)值域中的元素的hash值，得到X中的具體元素。這樣，將泄漏X的隱私數(shù)據(jù)。因此，該算法主要適用于用戶值域較大情況。

4 基于集合多項(xiàng)式交集計(jì)算協(xié)議（Polynomial based

set intersection protocol）

為了克服單項(xiàng)hash無(wú)碰撞哈希算法的缺陷，一些學(xué)者提出了基于集合多項(xiàng)式表示方法的用戶交集計(jì)算算法，并采用同態(tài)加密算法增強(qiáng)算法的安全性。其中具有代表性的是Michael J. Freedman等人和E. Stefanov等人提出的算法[5，6]。

該算法的基礎(chǔ)是集合的多項(xiàng)式表示。即如果用戶：X持有集合X={x1，x2，...，xn}， 則，X中的元素可以用以下多項(xiàng)式的根表示：

根據(jù)線性代數(shù)理論，當(dāng)該多項(xiàng)式的階數(shù)高于5時(shí)，不存在線性復(fù)雜度的算法求解該多項(xiàng)式。

兩用戶模式下交集計(jì)算：設(shè)兩用戶X和Y，分別持有集合X={x1，x2，...，xn}，Y={y1，y2，...，yn}，f1與f2分別是兩用戶元素的多項(xiàng)式表示，則X和Y的交集為以下多項(xiàng)式的根

為避免hash表中的小值域問(wèn)題，用戶X可以將加密的多項(xiàng)式發(fā)送給Y。即發(fā)送加密的多項(xiàng)式系數(shù)：E（ai），Y通過(guò)加密的多項(xiàng)式計(jì)算E（f（yi） ）+E（yi），并返回給X，因?yàn)榧用苓^(guò)程滿足加法與乘法同態(tài)性，因此：E（f（yi））+E（yi）=E（f（yi）+yi）， 如果yi在交集中，則E（f（yi））+E（yi）=E（f（yi）+yi）=E（0+yi）=E（yi）， X通過(guò)解密，即可得到交集中的元素。

該模式可以擴(kuò)展到n個(gè)用戶模式。

設(shè)共有n個(gè)用戶X1，…，Xn、f1，…，fn-1分別是用戶X1，…，Xn-1所持有集合的多項(xiàng)式表示。用戶Xn的集合為：{y1，…，yk}。

Xn為集合中的每一個(gè)元素準(zhǔn)備（n-1）個(gè)隨機(jī)值，滿足：

對(duì)于每一個(gè)Xn中的元素，Xn利用前（n-1）個(gè)用戶的加密多項(xiàng)式計(jì)算：E1（f1（y1）+y11），E2（f2（y1）+y12），…，E（n-1）（fn-1（y1）+y1n-1），并分別發(fā)送給：X1，…，Xn-1，這些用戶解密后，將結(jié)果返回給Xn，Xn通過(guò)計(jì)算返回?cái)?shù)據(jù)的和，即可知道交集元素。

相比于哈希表算法，該算法可以很好的克服小值域問(wèn)題。由于在傳輸過(guò)程中，多項(xiàng)式系數(shù)被加密，因此，不可能通過(guò)逐個(gè)檢驗(yàn)值域中數(shù)據(jù)的方式得到用戶信息。但同時(shí)，所用用戶共享解密私鑰，為了得到最終結(jié)果，用戶需要進(jìn)行聯(lián)合解密，通信量與用戶數(shù)量成正比。當(dāng)用戶數(shù)量龐大時(shí)，性能下降嚴(yán)重。因此，尋找不依賴于用戶數(shù)量的密鑰生成與解密方案，是提升該算法性能的主要研究方向。

5 結(jié)論（Conclusion）

本文分析了目前第三方應(yīng)用在用戶數(shù)據(jù)收集過(guò)程中的核心函數(shù)：交集計(jì)算問(wèn)題的研究進(jìn)展。集合交集問(wèn)題在軍事，商業(yè)，社交網(wǎng)絡(luò)等領(lǐng)域具有非常重要的應(yīng)用前景。研究安全的數(shù)據(jù)交集計(jì)算協(xié)議對(duì)于實(shí)現(xiàn)安全，公平的數(shù)據(jù)信息共享具有重要的意義。本文介紹了目前學(xué)術(shù)界的研究進(jìn)展分析了具體算法的性能以及現(xiàn)有協(xié)議的不足，然后提出了下一步的研究方向。

參考文獻(xiàn)（References）

[1] O. Gold， Foundations of cryptography： Basic applications [J].Volume 2， Cambridge University Press，2004.

[2] A.Ben-David，N.Nisan，and B.Pinkas，F(xiàn)airplayMP：A system for secure multi-party computation[C].In proceedings of the ACM Conference on Computer and Communications Security，pp.257-266，New York，NY，USA，2008，ACM.

[3] A.Chi-Chih Yao.Protocols for secure computations（extended abstract）[C].IEEE Symposium on Foundations of Computer Science 1982，F(xiàn)OCS 1982，pp.160-164，1992.

[4] E.Stefanov，E.Shi，and D.Song，Policy-Enhanced Private Set Intersection： Sharing Information While Enforcing Privacy Policies [C]. Proceedings of the PKC 2012 The 15th IACR International Conference on Practice and Theory of Public-Key Cryptography，PKC 2012，Springer，2012，pp.413-430.

[5] J.Vaidya and C.Clifton.Secure set intersection cardinality with application to association rule mining [J].Journal of Computer Security， 13（4），Nov.2005.

[6] Michael J.Freedman，KobbiNissim，and Benny Pinkas. Efficient Private Matching and Set Intersection[J].Lecture Notes in Computer Science Volume 3027，pp.1-19，2004.

作者簡(jiǎn)介：

孫 偉（1978-），男，博士，副教授.研究領(lǐng)域：網(wǎng)絡(luò)安全，互聯(lián)網(wǎng)流媒體傳輸技術(shù)，無(wú)線網(wǎng)絡(luò).

張 永（1980-），男，博士，副教授.研究領(lǐng)域：無(wú)線傳感器網(wǎng)絡(luò)，網(wǎng)絡(luò)安全.endprint

單項(xiàng)無(wú)碰撞哈希算法：X、Y共同初始化一個(gè)hash函數(shù)，X將他集合中的元素，通過(guò)hash表，隱藏真實(shí)信息，得到：

h（X）={h（x1），h（x2），…，h（xn）}

并將hash后的結(jié)果發(fā)送給Y。Y將自身元素通過(guò)同一個(gè)hash表計(jì)算結(jié)果，得到：

h（Y）={h（y1），h（y2），…，h（yn）}

并與X發(fā)送過(guò)來(lái)的結(jié)果h（X）進(jìn)行比對(duì)，具有同樣hash結(jié)果的元素，即為交集元素。同理，X也可以同樣的到交集元素。

該算法的主要優(yōu)點(diǎn)在于原理簡(jiǎn)單，計(jì)算復(fù)雜度低，通常只需要接近常量的計(jì)算時(shí)間，即O（1）的時(shí)間級(jí)[4]。但是，該算法仍然存在明顯的缺陷：如果X、Y集合的值域過(guò)小，Y可以通過(guò)逐個(gè)檢驗(yàn)值域中的元素的hash值，得到X中的具體元素。這樣，將泄漏X的隱私數(shù)據(jù)。因此，該算法主要適用于用戶值域較大情況。

4 基于集合多項(xiàng)式交集計(jì)算協(xié)議（Polynomial based

set intersection protocol）

為了克服單項(xiàng)hash無(wú)碰撞哈希算法的缺陷，一些學(xué)者提出了基于集合多項(xiàng)式表示方法的用戶交集計(jì)算算法，并采用同態(tài)加密算法增強(qiáng)算法的安全性。其中具有代表性的是Michael J. Freedman等人和E. Stefanov等人提出的算法[5，6]。

該算法的基礎(chǔ)是集合的多項(xiàng)式表示。即如果用戶：X持有集合X={x1，x2，...，xn}， 則，X中的元素可以用以下多項(xiàng)式的根表示：

根據(jù)線性代數(shù)理論，當(dāng)該多項(xiàng)式的階數(shù)高于5時(shí)，不存在線性復(fù)雜度的算法求解該多項(xiàng)式。

兩用戶模式下交集計(jì)算：設(shè)兩用戶X和Y，分別持有集合X={x1，x2，...，xn}，Y={y1，y2，...，yn}，f1與f2分別是兩用戶元素的多項(xiàng)式表示，則X和Y的交集為以下多項(xiàng)式的根

為避免hash表中的小值域問(wèn)題，用戶X可以將加密的多項(xiàng)式發(fā)送給Y。即發(fā)送加密的多項(xiàng)式系數(shù)：E（ai），Y通過(guò)加密的多項(xiàng)式計(jì)算E（f（yi） ）+E（yi），并返回給X，因?yàn)榧用苓^(guò)程滿足加法與乘法同態(tài)性，因此：E（f（yi））+E（yi）=E（f（yi）+yi）， 如果yi在交集中，則E（f（yi））+E（yi）=E（f（yi）+yi）=E（0+yi）=E（yi）， X通過(guò)解密，即可得到交集中的元素。

該模式可以擴(kuò)展到n個(gè)用戶模式。

設(shè)共有n個(gè)用戶X1，…，Xn、f1，…，fn-1分別是用戶X1，…，Xn-1所持有集合的多項(xiàng)式表示。用戶Xn的集合為：{y1，…，yk}。

Xn為集合中的每一個(gè)元素準(zhǔn)備（n-1）個(gè)隨機(jī)值，滿足：

對(duì)于每一個(gè)Xn中的元素，Xn利用前（n-1）個(gè)用戶的加密多項(xiàng)式計(jì)算：E1（f1（y1）+y11），E2（f2（y1）+y12），…，E（n-1）（fn-1（y1）+y1n-1），并分別發(fā)送給：X1，…，Xn-1，這些用戶解密后，將結(jié)果返回給Xn，Xn通過(guò)計(jì)算返回?cái)?shù)據(jù)的和，即可知道交集元素。

相比于哈希表算法，該算法可以很好的克服小值域問(wèn)題。由于在傳輸過(guò)程中，多項(xiàng)式系數(shù)被加密，因此，不可能通過(guò)逐個(gè)檢驗(yàn)值域中數(shù)據(jù)的方式得到用戶信息。但同時(shí)，所用用戶共享解密私鑰，為了得到最終結(jié)果，用戶需要進(jìn)行聯(lián)合解密，通信量與用戶數(shù)量成正比。當(dāng)用戶數(shù)量龐大時(shí)，性能下降嚴(yán)重。因此，尋找不依賴于用戶數(shù)量的密鑰生成與解密方案，是提升該算法性能的主要研究方向。

5 結(jié)論（Conclusion）

本文分析了目前第三方應(yīng)用在用戶數(shù)據(jù)收集過(guò)程中的核心函數(shù)：交集計(jì)算問(wèn)題的研究進(jìn)展。集合交集問(wèn)題在軍事，商業(yè)，社交網(wǎng)絡(luò)等領(lǐng)域具有非常重要的應(yīng)用前景。研究安全的數(shù)據(jù)交集計(jì)算協(xié)議對(duì)于實(shí)現(xiàn)安全，公平的數(shù)據(jù)信息共享具有重要的意義。本文介紹了目前學(xué)術(shù)界的研究進(jìn)展分析了具體算法的性能以及現(xiàn)有協(xié)議的不足，然后提出了下一步的研究方向。

參考文獻(xiàn)（References）

[1] O. Gold， Foundations of cryptography： Basic applications [J].Volume 2， Cambridge University Press，2004.

[2] A.Ben-David，N.Nisan，and B.Pinkas，F(xiàn)airplayMP：A system for secure multi-party computation[C].In proceedings of the ACM Conference on Computer and Communications Security，pp.257-266，New York，NY，USA，2008，ACM.

[3] A.Chi-Chih Yao.Protocols for secure computations（extended abstract）[C].IEEE Symposium on Foundations of Computer Science 1982，F(xiàn)OCS 1982，pp.160-164，1992.

[4] E.Stefanov，E.Shi，and D.Song，Policy-Enhanced Private Set Intersection： Sharing Information While Enforcing Privacy Policies [C]. Proceedings of the PKC 2012 The 15th IACR International Conference on Practice and Theory of Public-Key Cryptography，PKC 2012，Springer，2012，pp.413-430.

[5] J.Vaidya and C.Clifton.Secure set intersection cardinality with application to association rule mining [J].Journal of Computer Security， 13（4），Nov.2005.

[6] Michael J.Freedman，KobbiNissim，and Benny Pinkas. Efficient Private Matching and Set Intersection[J].Lecture Notes in Computer Science Volume 3027，pp.1-19，2004.

作者簡(jiǎn)介：

孫 偉（1978-），男，博士，副教授.研究領(lǐng)域：網(wǎng)絡(luò)安全，互聯(lián)網(wǎng)流媒體傳輸技術(shù)，無(wú)線網(wǎng)絡(luò).

張 永（1980-），男，博士，副教授.研究領(lǐng)域：無(wú)線傳感器網(wǎng)絡(luò)，網(wǎng)絡(luò)安全.endprint

單項(xiàng)無(wú)碰撞哈希算法：X、Y共同初始化一個(gè)hash函數(shù)，X將他集合中的元素，通過(guò)hash表，隱藏真實(shí)信息，得到：

h（X）={h（x1），h（x2），…，h（xn）}

并將hash后的結(jié)果發(fā)送給Y。Y將自身元素通過(guò)同一個(gè)hash表計(jì)算結(jié)果，得到：

h（Y）={h（y1），h（y2），…，h（yn）}

并與X發(fā)送過(guò)來(lái)的結(jié)果h（X）進(jìn)行比對(duì)，具有同樣hash結(jié)果的元素，即為交集元素。同理，X也可以同樣的到交集元素。

該算法的主要優(yōu)點(diǎn)在于原理簡(jiǎn)單，計(jì)算復(fù)雜度低，通常只需要接近常量的計(jì)算時(shí)間，即O（1）的時(shí)間級(jí)[4]。但是，該算法仍然存在明顯的缺陷：如果X、Y集合的值域過(guò)小，Y可以通過(guò)逐個(gè)檢驗(yàn)值域中的元素的hash值，得到X中的具體元素。這樣，將泄漏X的隱私數(shù)據(jù)。因此，該算法主要適用于用戶值域較大情況。

4 基于集合多項(xiàng)式交集計(jì)算協(xié)議（Polynomial based

set intersection protocol）

為了克服單項(xiàng)hash無(wú)碰撞哈希算法的缺陷，一些學(xué)者提出了基于集合多項(xiàng)式表示方法的用戶交集計(jì)算算法，并采用同態(tài)加密算法增強(qiáng)算法的安全性。其中具有代表性的是Michael J. Freedman等人和E. Stefanov等人提出的算法[5，6]。

該算法的基礎(chǔ)是集合的多項(xiàng)式表示。即如果用戶：X持有集合X={x1，x2，...，xn}， 則，X中的元素可以用以下多項(xiàng)式的根表示：

根據(jù)線性代數(shù)理論，當(dāng)該多項(xiàng)式的階數(shù)高于5時(shí)，不存在線性復(fù)雜度的算法求解該多項(xiàng)式。

兩用戶模式下交集計(jì)算：設(shè)兩用戶X和Y，分別持有集合X={x1，x2，...，xn}，Y={y1，y2，...，yn}，f1與f2分別是兩用戶元素的多項(xiàng)式表示，則X和Y的交集為以下多項(xiàng)式的根

為避免hash表中的小值域問(wèn)題，用戶X可以將加密的多項(xiàng)式發(fā)送給Y。即發(fā)送加密的多項(xiàng)式系數(shù)：E（ai），Y通過(guò)加密的多項(xiàng)式計(jì)算E（f（yi） ）+E（yi），并返回給X，因?yàn)榧用苓^(guò)程滿足加法與乘法同態(tài)性，因此：E（f（yi））+E（yi）=E（f（yi）+yi）， 如果yi在交集中，則E（f（yi））+E（yi）=E（f（yi）+yi）=E（0+yi）=E（yi）， X通過(guò)解密，即可得到交集中的元素。

該模式可以擴(kuò)展到n個(gè)用戶模式。

設(shè)共有n個(gè)用戶X1，…，Xn、f1，…，fn-1分別是用戶X1，…，Xn-1所持有集合的多項(xiàng)式表示。用戶Xn的集合為：{y1，…，yk}。

Xn為集合中的每一個(gè)元素準(zhǔn)備（n-1）個(gè)隨機(jī)值，滿足：

對(duì)于每一個(gè)Xn中的元素，Xn利用前（n-1）個(gè)用戶的加密多項(xiàng)式計(jì)算：E1（f1（y1）+y11），E2（f2（y1）+y12），…，E（n-1）（fn-1（y1）+y1n-1），并分別發(fā)送給：X1，…，Xn-1，這些用戶解密后，將結(jié)果返回給Xn，Xn通過(guò)計(jì)算返回?cái)?shù)據(jù)的和，即可知道交集元素。

相比于哈希表算法，該算法可以很好的克服小值域問(wèn)題。由于在傳輸過(guò)程中，多項(xiàng)式系數(shù)被加密，因此，不可能通過(guò)逐個(gè)檢驗(yàn)值域中數(shù)據(jù)的方式得到用戶信息。但同時(shí)，所用用戶共享解密私鑰，為了得到最終結(jié)果，用戶需要進(jìn)行聯(lián)合解密，通信量與用戶數(shù)量成正比。當(dāng)用戶數(shù)量龐大時(shí)，性能下降嚴(yán)重。因此，尋找不依賴于用戶數(shù)量的密鑰生成與解密方案，是提升該算法性能的主要研究方向。

5 結(jié)論（Conclusion）

本文分析了目前第三方應(yīng)用在用戶數(shù)據(jù)收集過(guò)程中的核心函數(shù)：交集計(jì)算問(wèn)題的研究進(jìn)展。集合交集問(wèn)題在軍事，商業(yè)，社交網(wǎng)絡(luò)等領(lǐng)域具有非常重要的應(yīng)用前景。研究安全的數(shù)據(jù)交集計(jì)算協(xié)議對(duì)于實(shí)現(xiàn)安全，公平的數(shù)據(jù)信息共享具有重要的意義。本文介紹了目前學(xué)術(shù)界的研究進(jìn)展分析了具體算法的性能以及現(xiàn)有協(xié)議的不足，然后提出了下一步的研究方向。

參考文獻(xiàn)（References）

[1] O. Gold， Foundations of cryptography： Basic applications [J].Volume 2， Cambridge University Press，2004.

[2] A.Ben-David，N.Nisan，and B.Pinkas，F(xiàn)airplayMP：A system for secure multi-party computation[C].In proceedings of the ACM Conference on Computer and Communications Security，pp.257-266，New York，NY，USA，2008，ACM.

[3] A.Chi-Chih Yao.Protocols for secure computations（extended abstract）[C].IEEE Symposium on Foundations of Computer Science 1982，F(xiàn)OCS 1982，pp.160-164，1992.

[4] E.Stefanov，E.Shi，and D.Song，Policy-Enhanced Private Set Intersection： Sharing Information While Enforcing Privacy Policies [C]. Proceedings of the PKC 2012 The 15th IACR International Conference on Practice and Theory of Public-Key Cryptography，PKC 2012，Springer，2012，pp.413-430.

[5] J.Vaidya and C.Clifton.Secure set intersection cardinality with application to association rule mining [J].Journal of Computer Security， 13（4），Nov.2005.

[6] Michael J.Freedman，KobbiNissim，and Benny Pinkas. Efficient Private Matching and Set Intersection[J].Lecture Notes in Computer Science Volume 3027，pp.1-19，2004.

作者簡(jiǎn)介：

孫 偉（1978-），男，博士，副教授.研究領(lǐng)域：網(wǎng)絡(luò)安全，互聯(lián)網(wǎng)流媒體傳輸技術(shù)，無(wú)線網(wǎng)絡(luò).

張 永（1980-），男，博士，副教授.研究領(lǐng)域：無(wú)線傳感器網(wǎng)絡(luò)，網(wǎng)絡(luò)安全.endprint