第三方應(yīng)用數(shù)據(jù)收集過程中隱私保護問題研究進展

孫偉　張永

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

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

中圖分類號：TP393.08 文獻標識碼：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）

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

set intersection protocol）

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

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

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

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

為避免hash表中的小值域問題，用戶X可以將加密的多項式發(fā)送給Y。即發(fā)送加密的多項式系數(shù)：E（ai），Y通過加密的多項式計算E（f（yi） ）+E（yi），并返回給X，因為加密過程滿足加法與乘法同態(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通過解密，即可得到交集中的元素。

該模式可以擴展到n個用戶模式。

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

Xn為集合中的每一個元素準備（n-1）個隨機值，滿足：

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

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

5 結(jié)論（Conclusion）

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

參考文獻（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.

作者簡介：

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

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

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

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

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

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

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

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

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

set intersection protocol）

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

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

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

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

為避免hash表中的小值域問題，用戶X可以將加密的多項式發(fā)送給Y。即發(fā)送加密的多項式系數(shù)：E（ai），Y通過加密的多項式計算E（f（yi） ）+E（yi），并返回給X，因為加密過程滿足加法與乘法同態(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通過解密，即可得到交集中的元素。

該模式可以擴展到n個用戶模式。

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

Xn為集合中的每一個元素準備（n-1）個隨機值，滿足：

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

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

5 結(jié)論（Conclusion）

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

參考文獻（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.

作者簡介：

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

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

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

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

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

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

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

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

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

set intersection protocol）

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

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

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

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

為避免hash表中的小值域問題，用戶X可以將加密的多項式發(fā)送給Y。即發(fā)送加密的多項式系數(shù)：E（ai），Y通過加密的多項式計算E（f（yi） ）+E（yi），并返回給X，因為加密過程滿足加法與乘法同態(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通過解密，即可得到交集中的元素。

該模式可以擴展到n個用戶模式。

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

Xn為集合中的每一個元素準備（n-1）個隨機值，滿足：

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

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

5 結(jié)論（Conclusion）

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

參考文獻（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.

作者簡介：

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

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