本发明涉及隐私计算加密算法，尤其是涉及一种适合小集合秘密分享的高效电路隐私集合求交方法。
背景技术：
1、随着大数据时代的到来，互联网中与个人用户相关的数据量快速增长，这些数据只用通过数据挖掘后才能充分利用其价值。但对个人用户数据的挖掘和分析往往会带来一些敏感数据的隐私问题，psi作为一种隐私计算技术被广泛运用到广告效益转化、隐私通讯录匹配、用户爱好匹配中。cpsi更关注对集合交集结果的函数运算，如集合交集基数、交集秘密分享等。
2、早期的cpsi需要o(n2)次电路比较，这直接导致整个电路需要o(σn2)个门，其中σ是元素的比特长度。huang等人，提出一种排序-比较-洗牌(sort compare shuffle，scs)技术将电路阶段元素的比较次数降为o(nlogn)，电路的门数降为o(σnlogn)。pinkas等人，在参与方的一方中使用有o(n)个桶的布谷鸟哈希方案另一方使用o(n)个桶的朴素哈希方案，朴素哈希的每一个桶中最多存放o(logn/loglogn)个元素，因此将电路的比较次数降为o(nlogn/loglogn)次，门数降为o(σnlogn/loglogn)个。falk等人，首先使用哈希函数将元素映射到o(n)个桶中，每个桶中存放多个元素，在使用huang等人的scs方案来计算每个桶中的交集结果，其cpsi的通信开销为o(σnloglogn)。pinkas等人，最近提出使用有3个哈希函数且不带暂存区的布谷鸟哈希方案和不经意可编程伪随机函数(oblivious programmablepseudorandom functions，opprf)来实现能对交集结果标签进行秘密分享的cpsi，他们的协议在电路阶段只需要o(n)次元素比较和o(σn)个门。但他们使用的opprf协议是基于多项式插值构造，因此随着元素集合的增加需要较大的计算开销。rindal等人在pinkas等人的基础上，优化了其opprf协议。他们使用基于向量不经意线性评估(vector obliviouslinear evaluation，vole)的线性编码解码函数来构造opprf，在编码阶段其只需要o(an)的计算开销，而pinkas等人的opprf需要o(n2)的计算开销。为了进一步减少电路阶段元素的比较次数，rindal等人，在执行opprf之前使用布谷鸟哈希将接收方的元素映射到o(n)个桶中，每个桶中只存方一个元素；使用朴素哈希将发送方的元素映射到o(n)个桶中，且每个桶中最多存放o(logn)个元素，因此他们的协议在电路比较阶段需要比较o(nlogn)次和o(σn)个门。rindal等人使用哈希方案的目的是为了降低电路比较阶段电路的深度，而本发明提出的适合小集合的cpsi本身就不需要较深的电路运算，因此完全可以略去造成通信开销较大的哈希方案。另外，rindal等人实现的opprf协议是基于vole-oprf和okvs实现的，vole-oprf的主要步骤如下。
3、vole是个两方协议，执行vole后，s获得标量δ和向量b，r获得向量c和a，其中c＝δ.a+b，即c，a，b之间存在线性关系。首先相互约定生成一个大的随机矩阵假设s拥有集合y，|y|＝ny，r拥有集合x，|x|＝nx，r和s分别从m*中随机抽取矩阵r用线性方程组求解器求解mxp＝0，并将a′＝a+p发送给s。因此s拥有oprf密钥k＝b+δ·(a+p)，并可计算oprf值fk(y)＝h(myk-δ·h(y))，r可以计算oprf值fk(x)＝h(mxc)。vole-大矩阵m的宽度m＝2.4n和vole的开销ρnx随着集合大小增加而增加。可以看出，即使在小集合的情况下，vole-oprf也需要较大的通信开销。
4、综上所述，现有技术中存在着在小集合的情况下，vole-oprf也需要较大的通信开销。因此，本发明提供一种适合小集合秘密分享的高效电路隐私集合求交方法。
技术实现思路
1、本发明的目的就是为了克服上述现有技术存在的缺陷而提供一种适合小集合秘密分享的高效电路隐私集合求交方法，其目的在于使用一轮密钥交换协议和不经意键值对存储技术，降低电路比较阶段元素的比较次数和电路psi的通信开销，并实现对交集结果标签的秘密分享，本发明实现了半诚实安全。
2、本发明的目的可以通过以下技术方案来实现：
3、本发明提供一种适合小集合秘密分享的高效电路隐私集合求交方法，包括以下步骤：
4、包括以下步骤：
5、步骤1、参数设置阶段，分别输入发送方和接收方各自的隐私集合，同时输入发送方与隐私集合相关联的标签集合；
6、步骤2、密钥交换阶段，使用一轮密钥交换协议(ka协议)交换发送方和接收方之间的密钥，得到公共密钥；
7、步骤3、电路gmw协议计算阶段，发送方和接收方分别将步骤2中获得的值发送给gmw协议计算，并将输出以秘密分享给发送方和接收方。
8、所述步骤1具体包括：发送方s拥有隐私集合：与隐私集合相关联的标签集合：接收方r拥有集合且nx＝ny。
9、所述步骤2具体包括以下步骤：
10、步骤21：接收方r选择nx个私钥ai，ai←ka.r，并生成公钥集合msgi＝ka，msg(ai)，用okvs方案的encodeh函数将所述公钥集合生成不经意键值对存储对象dr＝encodeh(h1(xi)，π-(msgi))，并发送给发送方s；
11、步骤22：发送方s解码dr，获得ny个接收方r的公钥ki＝π(decodeh(dr，h1(y1)))，对于所有的i∈[ny]，发送方s选择两个随机值数组和以及一个发送方s的私钥b←ka.r，生成发送方s的公钥msg＝ka.msg(b)、并将发送方s的公钥和ds发送给接收方r；
12、步骤23：对于所有的i∈[nx]，接收方r计算公共密钥k′i＝ka.key(ai，msg)，并利用公共密钥解码ds获得(r′i||ω′i)＝decodeh(ds，k′i)。
13、在所述步骤22中，只有当xi＝yi时，发送方s才能正确获得接收方r的公钥集合msgi＝ka，msg(ai)，否则获得一随机数。
14、所述密钥交换协议包括椭圆曲线密钥交换协议。
15、所述椭圆曲线密钥交换协议能够将椭圆曲线点映射为随机的字符串。
16、所述步骤3具体包括：对于所有i∈[nx]，发送方s和接收方r执行电路gmw协议，s输入r输入(r′i‖ω′i)；经过电路gmw协议计算qi＝(r′i＝＝ri)，并将其分别以秘密分享的方式分享给发送方s和接收方r。
17、对qi和zi进行验证：
18、若r′i＝＝ri，则qi＝1，对qi和zi进行秘密分享给发送方s和接收方r；
19、若r′i≠ri，则qi＝0，zi＝0，对qi和zi进行秘密分享给发送方s和接收方r。
20、第二方面，本发明提供一种电子设备，包括至少一个处理器、至少一个存储器和数据总线；其中：所述处理器与所述存储器通过所述数据总线完成相互间的通信；所述存储器存储有被所述处理器执行的程序指令，所述处理器调用所述程序指令以执行上述任一项所述的方法。
21、第三方面，本发明一种计算机可读存储介质，其上存储有计算机程序，该计算机程序被处理器执行时实现上述任一项所述的方法。
22、与现有技术相比，本发明具有以下有益效果：
23、1、本发明使用的一轮密钥交换协议和okvs的方案，在电路阶段只需要比较集合大小次。本发明进一步降低了协议的通信开销，特别是在小集合下取得了可观的通信开销和运行效率。
24、2、本发明在全尺寸集合大小下，只需要最少的通信开销即可实现交集标签的秘密分享，特别是在带宽条件受限的情况下，本发明具有更大的优势。
25、3、本发明使用一轮密钥交换协议和不经意键值对存储技术，降低电路比较阶段元素的比较次数和电路psi的通信开销，并实现对交集结果标签的秘密分享，实现了半诚实安全。
1.一种适合小集合秘密分享的高效电路隐私集合求交方法，其特征在于，包括以下步骤：
2.根据权利要求1所述的一种适合小集合秘密分享的高效电路隐私集合求交方法，其特征在于，所述步骤1具体包括：发送方s拥有隐私集合：与隐私集合相关联的标签集合：接收方r拥有集合且nx＝ny。
3.根据权利要求1所述的一种适合小集合秘密分享的高效电路隐私集合求交方法，其特征在于，所述步骤2具体包括以下步骤：
4.根据权利要求3所述的一种适合小集合秘密分享的高效电路隐私集合求交方法，其特征在于，在所述步骤22中，当xi＝yi时，发送方s能正确获得接收方r的公钥集合msgi＝ka.msg(ai)，否则获得一随机数。
5.根据权利要求4所述的一种适合小集合秘密分享的高效电路隐私集合求交方法，其特征在于，所述密钥交换协议具体为椭圆曲线密钥交换协议。
6.根据权利要求5所述的一种适合小集合秘密分享的高效电路隐私集合求交方法，其特征在于，所述椭圆曲线密钥交换协议能够将椭圆曲线点映射为随机的字符串。
7.根据权利要求1所述的一种适合小集合秘密分享的高效电路隐私集合求交方法，其特征在于，所述步骤3具体包括：对于所有i∈[nx]，发送方s和接收方r执行电路gmw协议，s输入r输入(r′i||ω′i)；经过电路gmw协议计算qi＝(r′i＝＝ri)，并将其分别以秘密分享的方式分享给发送方s和接收方r。
8.根据权利要求7所述的一种适合小集合秘密分享的高效电路隐私集合求交方法的步骤，其特征在于，对qi和zi进行以下验证：
9.一种电子设备，包括至少一个处理器、至少一个存储器和数据总线；其中：所述处理器与所述存储器通过所述数据总线完成相互间的通信；其特征在于，所述存储器存储有被所述处理器执行的程序指令，所述处理器调用所述程序指令以执行如权利要求1-8任一项所述的方法。
10.一种计算机可读存储介质，其上存储有计算机程序，其特征在于，该计算机程序被处理器执行时实现如权利要求1-8中任一项所述的方法。
