第三方应用数据收集过程中隐私保护问题研究进展

孙伟　张永

摘 要：不同于传统网络，在移动互联网与云计算环境下，众多的第三方服务依赖于用户数据的收集与分析。如何在保证用户数据安全与隐私的情况下，得到合理的分析与统计结果，一直是网络安全领域研究的热点问题。本文对用户数据隐私保护需求进行了总结，分析了目前在数据收集过程中常用的交集计算相关算法的优缺点，对未来的研究方向做出了总结。

关键词：隐私保护；安全多方计算；数据安全

中图分类号：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