第三方應用數據收集過程中隱私保護問題研究進展

孫偉　張永

摘 要：不同于傳統網絡，在移動互聯網與云計算環境下，眾多的第三方服務依賴于用戶數據的收集與分析。如何在保證用戶數據安全與隱私的情況下，得到合理的分析與統計結果，一直是網絡安全領域研究的熱點問題。本文對用戶數據隱私保護需求進行了總結，分析了目前在數據收集過程中常用的交集計算相關算法的優缺點，對未來的研究方向做出了總結。

關鍵詞：隱私保護；安全多方計算；數據安全

中圖分類號：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）

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

set intersection protocol）

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

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

根據線性代數理論，當該多項式的階數高于5時，不存在線性復雜度的算法求解該多項式。

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

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

設共有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），并分別發送給：X1，…，Xn-1，這些用戶解密后，將結果返回給Xn，Xn通過計算返回數據的和，即可知道交集元素。

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

5 結論（Conclusion）

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

參考文獻（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，FairplayMP：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，FOCS 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-），男，博士，副教授.研究領域：網絡安全，互聯網流媒體傳輸技術，無線網絡.

張 永（1980-），男，博士，副教授.研究領域：無線傳感器網絡，網絡安全.endprint

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

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

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

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

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

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

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

set intersection protocol）

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

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

根據線性代數理論，當該多項式的階數高于5時，不存在線性復雜度的算法求解該多項式。

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

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

設共有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），并分別發送給：X1，…，Xn-1，這些用戶解密后，將結果返回給Xn，Xn通過計算返回數據的和，即可知道交集元素。

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

5 結論（Conclusion）

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

參考文獻（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，FairplayMP：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，FOCS 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-），男，博士，副教授.研究領域：網絡安全，互聯網流媒體傳輸技術，無線網絡.

張 永（1980-），男，博士，副教授.研究領域：無線傳感器網絡，網絡安全.endprint

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

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

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

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

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

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

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

set intersection protocol）

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

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

根據線性代數理論，當該多項式的階數高于5時，不存在線性復雜度的算法求解該多項式。

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

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

設共有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），并分別發送給：X1，…，Xn-1，這些用戶解密后，將結果返回給Xn，Xn通過計算返回數據的和，即可知道交集元素。

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

5 結論（Conclusion）

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

參考文獻（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，FairplayMP：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，FOCS 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-），男，博士，副教授.研究領域：網絡安全，互聯網流媒體傳輸技術，無線網絡.

張 永（1980-），男，博士，副教授.研究領域：無線傳感器網絡，網絡安全.endprint