生活中我们希望利用智能手机通过合作计算发现志趣相投的朋友，而不泄露个人兴趣信息。这些合作计算都可以抽象化为安全多方计算 (Secure multi-party computation, SMPC)，它考虑的问题为：n个互不信任的参与方共同合作计算某函数f(x1,x2,…,xn)=(y1,y2,…,yn)，每个参与方Pi拥有秘密输入xi，通过合作计算得到yi但不能获知任何其他信息。SMPC对于隐私保护提供了一种天然的解决方案。
本作品利用安全多方计算技术，设计并实现了一种基于用户兴趣隐私保护的朋友发现系统。系统针对用户通过在移动社交网络中随时分享心情、照片、活动、兴趣爱好等来不断地发现新的朋友，从而进一步扩大自己的社交范围类网络应用，且能很好保护用户兴趣爱好隐私信息不会被泄漏。通过此系统，用户可以安全寻找志趣相投的朋友而不泄漏个人兴趣爱好信息。
背景介绍
1）问题描述
生活中我们经常通过社交软件来发现志趣相投的朋友。Soul通过用户【心理测试题结果】或【声音】的结果来发现相匹配的好友，网易云音乐通过【歌单】来发现有相同品味的好友。这些场景属于个人信誉保密问题，转化成数学模型就是判断元素与集合关系的问题。
2）应用场景
这类朋友发现系统的一般场景如图所示：
参与计算的用户将自己的属性信息（可以是上述例子中的【测试结果】【声音】【歌单】等）提交给一个“可信”的第三方，由这个第三方计算得到结果，并把结果发送给计算发起者。
但，这个第三方真的可信吗？
3）安全风险
目前针对移动社交网络朋友发现系统的隐私保护，主要依靠可信服务第三方（Trusted Third Party, TTP）参与 。在有TTP参与的方案中，用户需要将他们的特征属性配置文件提交给TTP，由TTP作为匹配中心来计算用户之间的相似度，这种方案虽然在一定程度上解放了客户端的计算能力，在一定程度上提高了用户的匹配效率。但是依然存在以下安全风险：
针对以上安全风险，我们利用安全多方计算技术设计了一种高效的集合交集安全两方计算协议，并将协议成功地应用到了朋友发现系统的核心功能模块当中。
主要的工作内容如下：
设计了一种基于位向量的集合表示方法，能天然保护集合势的大小。 本系统中，用户兴趣集合的所有元素选自一个固定大小的数据域，则每个用户的兴趣集合可以表示为一个位向量，如果数据域中某个元素属于兴趣集合，则位向量对应位置的值为1，否则为0。由于不同的集合的位向量表示后的向量长度等于域的大小，因此这种表示方法天然隐藏了集合的势。
设计了一种高效实用的集合交集安全两方计算协议。 基于新的集合表示方法及加法同态加密算法，我们设计了一种高效实用的集合交集安全两方计算协议。在协议的实际应用中，用户采用图2-2中的模式，在最初就选择自己的兴趣集合并加密保存到用户数据中心，好友兴趣匹配响应者也同样可以先用发起者的公钥加密许多零值密文以便在协议执行时使用。这种预处理的方式，将协议中比较耗时的加密步骤提前进行了处理，能够提高实际应用过程中的运行效率。同时，在实际的测试结果中也验证了这种预处理的高效性，当兴趣集合大小为212时，局域网环境中好友匹配时间仅为147ms。
将所设计的协议成功应用到朋友发现系统的核心功能模块。 我们在现有密码算法库的基础上，对协议进行了实现并将其成功应用到朋友发现系统的核心功能模块：好友匹配。用户在系统初始化时选择自己的兴趣集合并加密后保存到用户数据中心，在使用好友匹配功能的时，执行我们所设计的集合交集安全两方计算协议，求得共同兴趣。同时，在整个应用过程中，用户双方的会话信息是通过SSL协议提供安全可信的通信服务，确保双方之间数据发送的正确性和安全性，没有发生任何隐私信息的泄漏。
理论基础
支持本作品的主要理论基础是我们设计的一种高效的集合交集安全两方计算协议。协议只涉及两方参与计算，便能得到需要的结果，具有很好的隐私保护效果。
1）用户兴趣集合表示
服务器拥有一组固定顺序的兴趣属性，每位用户通过一个位向量来表示自己的兴趣结合，即，对应位置的元素是用户的兴趣时，用户位向量对应位置的值为1，否则，为0。
基于位向量的集合表示方法，集合交集的计算问题便可以转化为两向量的阵列乘法，具体操作为两位向量对应位置的值相乘，最后得到的向量即集合交集的位向量表示。
2）加法同态加密系统
我们提出的集合的安全两方计算主要基于加法同态加密，同态性质是某些公钥加密系统所具有的重要性质，在安全多方计算中有重要应用。具有加法同态性质的加密系统除了具有普通公钥密码系统的性质以外，还具有以下性质：
3）协议流程
整个协议共分为三步，最后Bob解密得到的结果即交集的位向量表示。协议时序图如下：
4）正确性证明
协议主要是要得到【陈列乘法】的计算形式，利用加法同态加密系统的主要性质，对Alice计算后的结果e向量，有：
5）安全性证明
设计与实现
1）系统架构
2）主要功能
效率分析
1）测试环境
测试手段：对本系统测试手段主要是手工测试，模拟实际用户进行相关测试。
测试环境：测试环境为装有Android 7.0系统的华为Mate Pad BTV-W09。
硬件条件：处理器为海思 Kirin 950，处理器主频2.3GHz，4GB内存。
编程环境：客户端编程环境为Android Studio，利用Java语言进行开发。服务器编程环境为MyEclipse，利用Java语言及Servlet技术开发
服 务 器：服务器搭建在阿里云上，服务器系统版本为Cent OS 7
开 发 库：JPBC(The Java Pairing Based Cryptography Library)，java.math.BigInteger，java.security以及javax.crypto库；其中java.math.BigInteger库主要用于对大数的操作，java.security主要用于安全随机数的生成，javax.crypto主要用于密钥管理。
2）测试结果
我们首先用Java语言对协议进行了实现，并自己实现了两种加法同态加密算法——Paillier和ElGamal，我们详细的测试了两种方案，数据如下，协议的加密步骤均可提前处理，使用这种预处理的方式可以大大提高协议的执行效率。
a）Running time (in milliseconds) of the protocol in Paillier Scheme
b）Running time (in milliseconds) of the protocol in ElGamal Scheme
实际情况中的使用效果：
References
[1] O. Ruan, Z. Wang, J. Mi and M. Zhang, “New Approach to Set Representation and Practical Private Set-Intersection Protocols,” in IEEE Access, vol. 7, pp. 64897-64906, 2019.
[2] E. De Cristofaro, G. Tsudik, “Practical private set intersection protocols with linear complexity”, Proc. Int. Conf. Financial Cryptogr. Data Secur., pp. 143-159, 2010.
[3] A. Abadi, S. Terzis, C. Dong, “VD-PSI: Verifiable delegated private set intersection on outsourced private datasets”, Proc. Int. Conf. Financial Cryptogr. Data Secur., pp. 149-168, 2016.
[4] Y. Huang, D. Evans, J. Katz, “Private set intersection: Are garbled circuits better than custom protocols?”, Proc. 19th Netw. Distrib. Syst. Secur. Symp., pp. 1-15, 2012.
[5] B. Pinkas, T. Schneider, M. Zohner, “Scalable private set intersection based on OT extension”, ACM Trans. Privacy Secur., vol. 21, no. 2, pp. 1-35, Feb. 2018.
[6] B. Pinkas, T. Schneider, M. Zohner, “Faster private set intersection based on OT extension”, Proc. 23rd USENIX Secur. Symp., pp. 797-812, 2014.