基于云辅助环境下的非平衡隐私集合求交基数方法

1.本发明属于数据安全技术领域，具体涉及基于云辅助环境下的非平衡隐私集合求交基数方法。


背景技术：

2.隐私集合求交基数是一种隐私保护技术，用于计算两个或多个集合的交集大小，而不暴露集合中的具体元素。该技术通常用于保护个人隐私，例如在医疗研究中，研究人员可以使用隐私集合求交基数来计算两个患者群体之间的重叠程度，以便更好地了解疾病的传播和治疗效果，同时保护患者的隐私。该技术的实现通常基于密码学和加密算法，可以确保计算结果的准确性和隐私保护。
3.近年来，两方psi-ca协议由于其在实际计算和通信方面具有线性复杂度的作用，受到了研究者们的广泛研究。其利用了各种各样的思想，如交换加密、决策diffie-hellman问题(ddh)、elgamal加密、二次剩余性(qr)问题和加性同态加密(ahe)。然而，隐私很难得到保证。针对这一问题，tajima提出了两种不同的两方协议，分别采用bloom filters和bgv-style全同态加密(fhe)方案。然而，使用fhe大大增加了协议的通信和计算开销。基于此，研究者提出了可委托的隐私集合求交基数，允许多个不受信任的云服务器进行计算，从而提高了客户端设备上的psi-ca协议的效率。catalic中psi-ca协议的客户端计算和通信复杂度与较小集合o(n)的大小成线性关系，与较大集合n的大小无关。然而，catalic系统至少需要两台非共谋的云服务器，odk-prf的底层oprf是基于不经意传输协议的，对于底层结构并不友好。
4.由此可以看到，目前隐私集合求交基数协议中各自存在明显的优势与劣势，并且大多数的隐私集合求交基数协议考虑的是参与方之间数据集大小基本相等的情况，但是在一些场景下参与方数据集合大小相差较大，并且参与方的计算和存储能力有限。因此通信量与计算量较大。


技术实现要素：

5.本发明的目的在于提供基于云辅助环境下的非平衡隐私集合求交基数方法，在保证参与方隐私安全的情况下，解决了参与方数据集相差较大的问题，并且减少了发送方的比较次数。
6.本发明所采用的技术方案是，基于云辅助环境下的非平衡隐私集合求交基数方法，具体按照以下步骤实施：
7.步骤1，设置阶段：发送方发送随机密钥k给接收方；接收方选择一个随机种子s，生成m个随机值，并将重排后的值发送给发送方；
8.步骤2，数据外包阶段：发送方和接收方分别将数据集哈希到m个桶中，根据密钥计算桶中的prf值并发送给云服务器；
9.步骤3，计算阶段：云服务器利用发给云服务器的值与接收方调用permute+share
技术；接收方对数据进行编码，并发送给云服务器进行解码，并且将解码后的值按照顺序发送给发送方；
10.步骤4，求交集基数阶段：最终得到交集基数。
11.本发明的特点还在于，
12.步骤1中，具体为：
13.步骤1.1，发送方随机选择一个prf密钥k，发送给接收方；
14.步骤1.2，接收方确定一个随机种子s，对s进行取模计算，生成一个新的数字；将生成的数字作为新的种子值，对新的种子值进行取模计算，重复该步骤，直到生成m个值，形成数据集r＝{r1，
…
，rm}
←
prg(s)；
15.步骤1.3，接收方将数据集r＝{r1，
…
，rm}从中间分为两部分数据集，分别为{r1，r2…
,r
m/2
}和{r m/2
+1，r m/2
+2，
…
,rm}；之后将两部分数据集中的第一个元素对换，即交换r1和r
m/2
+1；再将两部分数据集中的第二个元素对换，即交换r2和r
m/2
+2；依次类推直到交换完最后一个元素，即交换r
m/2
和rm，最终将交换之后的两部分数据集进行合并，得到一组值v＝{v1,....,vm}；并且将这一组值发送给接收方。
16.步骤2中，具体为：
17.步骤2.1，使用cuckoo hashing插值方法，发送方将自己的数据集x＝{x1,x2,....,xn}中的每一个数据通过g个哈希函数哈希到m个桶中，桶中的数据用xb表示；根据步骤1.1中发送方选择的随机密钥k，求得每一个数据的prf值xb’←
f(k,xb)，其中b∈m，b
s[b]
表示发送方第b个桶中的值，由于哈希表的长度为m，即可记为x'＝{x'1,......,x'm}，并且将x'＝{x'1,......,x'm}依次发送给云服务器；
[0018]
步骤2.2，通过simple hashing插值方法，接收方将自己的数据集y＝{y1,y2,....,yn}使用g个哈希函数散列到m个桶中，桶中的数据用yb表示，其中b∈m，根据步骤1.1中发送方发送给接收方的随机密钥k，接收方对于桶中的每一个数据求prf值yb’←
f(k,yb),),b
r[b]
表示接收方第b个桶中的数据，之后将y
b’进行交错置换得到一组值y'
π(b)
。
[0019]
步骤3中，具体为：
[0020]
步骤3.1，云服务器输入步骤2.1中发送方发来的一组值x'＝{x'1,......,x'm}经过置换顺序π后所得到x’[π(b)]，其中x’[π(b)]＝ab⊕
a'b，之后云服务器得到一组输出{a1,a2,...,am}，接收方得到一组输出{a'1,a'2,...,a'm}；
[0021]
步骤3.2，令u'b为不经意键值存储结构的键，接收方计算u'b＝y'
π(b)
⊕
a'b，根据u'b创造一组键值对pa＝(u'b,h(u'b)
⊕
vb)，用pa表示这一组键值对，h(u'b)
⊕
vb作为键值对存储结构中的值；h(u'b)指的是对于u'b求取哈希值；对于这一组键值对进行okvs编码，得到不经意键值对数据结构d＝(d1,d2,
…
,dm)
t
；其中d向量是编码后的okvs数据结构；并且将键值对数据结构d发送给云服务器；
[0022]
步骤3.3，云服务器根据步骤3.2中接收方发送过来的结果值使用步骤3.1中的ab进行解码，令wb表示其解码结果，因此wb＝decode(d,ab)
⊕
h(ab)，h(ab)是对ab求哈希值；令w＝{w1,....wm}并且将w发送给发送方。
[0023]
步骤4中，具体为：由于发送方对于步骤3.3中云服务器发送的集合w和步骤1.3中接收方发送的集合v所对应的数据是一无所知的，因此对其进行比较，如果集合w和集合v的
值相等那么则判定他们有相同的数据，则最终输出交集元素大小|w∩v|。
[0024]
本发明的有益效果是，本发明的方法，能够将隐私集合外包给云服务器，且不会产生隐私泄露问题；另外该方法客户端的计算量更小，通信代价低，适用于发送方设备受限的场景，在保证参与方隐私安全的情况下，解决了参与方数据集相差较大的问题，并且减少了比较次数。
附图说明
[0025]
图1是本发明基于云辅助环境下的非平衡隐私集合求交基数方法的流程图；
[0026]
图2是本发明基于云辅助环境下的隐私集合求交基数与基于布隆过滤器的隐私集合求交基数发送方与接收方的实验时间对比图(一)；
[0027]
图3是本发明基于云辅助环境下的隐私集合求交基数与基于布隆过滤器的隐私集合求交基数发送方与接收方的实验时间对比图(二)。
具体实施方式
[0028]
下面结合附图和具体实施方式对本发明进行详细说明。
[0029]
实施例1
[0030]
本发明基于云辅助环境下的非平衡隐私集合求交基数方法，具体为：
[0031]
步骤1，设置阶段：发送方发送随机密钥k给接收方；接收方选择一个随机种子s，生成m个随机值，并将重排后的值发送给发送方；
[0032]
步骤2，数据外包阶段：发送方和接收方分别将数据集哈希到m个桶中，根据密钥计算桶中的prf值并发送给云服务器；
[0033]
步骤3，计算阶段：云服务器利用发给云服务器的值与接收方调用permute+share技术；接收方对数据进行编码，并发送给云服务器进行解码，并且将解码后的值按照顺序发送给发送方；
[0034]
步骤4，求交集基数阶段：最终得到交集基数。
[0035]
实施例2
[0036]
本发明基于云辅助环境下的非平衡隐私集合求交基数方法，如图1所示，具体按照以下步骤实施：
[0037]
云服务器：作为存储数据的平台，进行求交集操作；
[0038]
发送方：拥有一组值x＝{x1,x2,....,xn；发送方的数据集大小小于接收方；
[0039]
接收方：拥有一组值y＝{y1,y2,....,yn}；
[0040]
步骤1，设置阶段：发送方发送随机密钥k给接收方；接收方选择一个随机种子s，通过prg函数生成m个随机值；使用重排技术将重排过后的值发送给发送方；具体为：
[0041]
步骤1.1，发送方随机选择一个prf密钥k，发送给接收方；
[0042]
步骤1.2，接收方选择一个随机种子s，生成m个随机值，形成数据集r＝{r1，
…
，rm}
←
prg(s)；
[0043]
具体为：接收方确定一个随机种子s，对s进行取模计算，生成一个新的数字；将生成的数字作为新的种子值，对新的种子值进行取模计算，重复该步骤，直到生成m个值，形成数据集r＝{r1，
…
，rm}
←
prg(s)；
[0044]
步骤1.3，由于使用permute+share技术，接收方拥有重排序列π，使用重排方法中的交错置换，得到一组值vb，其中b∈m。并且将这一组值v＝{v1,....,vm}发送给接收方；
[0045]
具体为：接收方将数据集r＝{r1，
…
，rm}从中间分为两部分数据集，分别为{r1，r2…
,r
m/2
}和{r
m/2
+1，r
m/2
+2，
…
,rm}；之后将两部分数据集中的第一个元素对换，即交换r1和r
m/2
+1；再将两部分数据集中的第二个元素对换，即交换r2和r
m/2
+2；依次类推直到交换完最后一个元素，即交换r
m/2
和rm，最终将交换之后的两部分数据集进行合并，得到一组值v＝{v1,....,vm}；并且将这一组值发送给接收方；
[0046]
步骤2，数据外包阶段：发送方通过使用cuckoo hashing将自己的数据集x＝{x1,x2,....,xn}哈希到m个桶中，根据步骤1中选择的密钥k计算每一个桶中的prf值x
b’并且发送给云服务器；接收方使用simple hashing将自己的数据集y＝{y1,y2,....,yn}哈希到m个桶中；具体为：
[0047]
步骤2.1，使用cuckoo hashing插值方法，发送方将自己的数据集x＝{x1,x2,....,xn}中的每一个数据通过g个哈希函数哈希到m个桶中，桶中的数据用xb表示。根据步骤1.1中发送方选择的随机密钥k，求得每一个数据的prf值xb’←
f(k,xb)，其中b∈m，b
s[b]
表示发送方第b个桶中的值，由于哈希表的长度为m，即可记为x'＝{x'1,......,x'm}，并且将x'＝{x'1,......,x'm}依次发送给云服务器；
[0048]
cuckoo hashing插值方法的步骤具体为：
[0049]
初始化一个空的哈希表，表的长度为m，每个桶只能容纳一个数据，b
s[b]
表示发送方第b个桶中的值；选择g个哈希函数h1,
…
hg；g个哈希函数任意位置为空，则随机选择一个位置插入，当g个哈希函数有位置为空时，则插入到空位置；当g个哈希位置均不为空时，随机选择g个之一的位置上的值踢出，计算踢出的值其他哈希值对应的位置进行插入(即当再次插入位置为空时插入，仍旧不为空时，再踢出这个值)
[0050]
步骤2.2，通过simple hashing插值方法，接收方将自己的数据集y＝{y1,y2,....,yn}使用g个哈希函数散列到m个桶中，桶中的数据用yb表示，其中b∈m，根据步骤1.1中发送方发送给接收方的随机密钥k，接收方对于桶中的每一个数据求prf值yb’←
f(k,yb),),b
r[b]
表示接收方第b个桶中的数据，之后将y
b’进行交错置换得到一组值y'
π(b)
；
[0051]
交错置换方法与步骤3.1相同；
[0052]
simple hashing的插入步骤具体如下：
[0053]
初始化一个空的哈希表，表的长度为m，每个桶可以容纳多个数据,b
r[b]
表示接收方第b个桶中的值；选择与发送方相同的g个哈希函数h1,
…
hg；每一个数据使用g次哈希函数，插入到哈希表的每一个桶中；
[0054]
步骤3，计算阶段：云服务器通过利用步骤2中发送方发给云服务器的值x'＝{x'1,......,x'm}与接收方调用permute+share技术；接收方对于置换与共享技术得到的数据进行okvs编码，并且将编码结果d发送给云服务器，云服务器进行解码，并且将解码后的值按照顺序发送给发送方；具体为：
[0055]
步骤3.1，接收方与云服务器调用permute+share，接收方输入置换顺序π(与步骤1.3中的交错置换相同)，云服务器输入步骤2.1中发送方发来的一组值x'＝{x'1,......,x'm}经过置换顺序π后所得到x’[π(b)]，其中x’[π(b)]＝ab⊕
a'b，之后云服务器得到一组输
出{a1,a2,...,am}，接收方得到一组输出{a'1,a'2,...,a'm}，其中b∈m；
[0056]
步骤3.2，令u'b为不经意键值存储结构的键，接收方计算u'b＝y'
π(b)
⊕
a'b，根据u'b创造一组键值对pa＝(u'b,h(u'b)
⊕
vb)，用pa表示这一组键值对，h(u'b)
⊕
vb作为键值对存储结构中的值。h(u'b)指的是对于u'b求取哈希值。对于这一组键值对进行okvs编码，得到不经意键值对数据结构d＝(d1,d2,
…
,dm)
t
。其中d向量是编码后的okvs数据结构，其编码目标就是找到这个d向量；并且将键值对数据结构d发送给云服务器；
[0057]
okvs编码过程具体如下：
[0058]
encode(u'b,h(u'b)
⊕
vb)：将键值对列表编码成okvs的数据结构，其中ub'是不定长bit串，h(u'b)
⊕
vb是长度为l的bit串，具体编码方式如下所示：
[0059][0060]
v(u'b)是预设好的将不定长的x映射到长度为m的bit串的函数,d＝(d1,d2,
…
,dm)
t
，其中元素di是和h(u'b)
⊕
vb长度一致的bit串，d向量就是编码后的okvs数据结构，其编码目标就是找到这个d向量，使得上述矩阵乘法成立，即将v(u'b)产生的bit串中为1对应序号的d向量中的元素求异或的结果是等于h(u'b)
⊕
vb的。
[0061]
步骤3.3，云服务器根据步骤3.2中接收方发送过来的结果值使用步骤3.1中的ab进行解码，令wb表示其解码结果，因此wb＝decode(d,ab)
⊕
h(ab)，其中b∈m，h(ab)指的是对ab求哈希值；令w＝{w1,....wm}并且将w发送给发送方。
[0062]
okvs解码过程具体如下：
[0063]
decode(d,ab)：给定一个okvs的数据结构(d向量)和一个ab，获取这个ab解码所产生对应的值(如果ab在之前编码的列表中，则解出的value值就是对应的h(u'b)
⊕
vb，如果不在，则解出的value就是一个随机项)；
[0064]
步骤4，求交集基数阶段：最终只能得到交集基数，对于交集内容一无所知。
[0065]
具体为：由于发送方对于步骤3.3中云服务器发送的集合w和步骤1.3中接收方发送的集合v所对应的数据是一无所知的，因此对他们进行比较，如果集合w和集合v的值相等那么则判定他们有相同的数据。最终输出交集元素大小|w∩v|。
[0066]
实施例3
[0067]
本发明使用的非平衡隐私集合求交基数方法是基于云服务器的，表1给出了本实验中使用的各个数据大小，哈希函数个数g，哈希表大小m，统计安全参数λ，计算安全参数k。将该方法进行仿真实验，本实验在两台机器上进行。云服务器运行centos 6.7操作系统，配置2.3ghz intel xeon e7-8880 v3 cpu，1tb内存。两台机器通过10gbps的以太网连接。
[0068]
表1各个数据大小
[0069]
数据大小λ40
g3m1.5nk128
[0070]
采用云服务器并且将数据外包给云服务器求交集，有效的提高了求交集的速度。从图2中可以看到，随着数据的增长，发送方的时间以较低的速率和较低的速度在增长。从图3中可以看出，随着数据的增长，接收方的时间以较低的速率和较低的速度在增长。然而在实际应用中，一般接收方的数据集比较大，因此将接收方的数据集大小设置为10000-50000。

技术特征：
1.基于云辅助环境下的非平衡隐私集合求交基数方法，其特征在于，具体按照以下步骤实施：步骤1，设置阶段：发送方发送随机密钥k给接收方；接收方选择一个随机种子s，生成m个随机值，并将重排后的值发送给发送方；步骤2，数据外包阶段：发送方和接收方分别将数据集哈希到m个桶中，根据密钥计算桶中的prf值并发送给云服务器；步骤3，计算阶段：云服务器利用发给云服务器的值与接收方调用permute+share技术；接收方对数据进行编码，并发送给云服务器进行解码，并且将解码后的值按照顺序发送给发送方；步骤4，求交集基数阶段：最终得到交集基数。2.根据权利要求1所述的基于云辅助环境下的非平衡隐私集合求交基数方法，其特征在于，所述步骤1中，具体为：步骤1.1，发送方随机选择一个prf密钥k，发送给接收方；步骤1.2，接收方确定一个随机种子s，对s进行取模计算，生成一个新的数字；将生成的数字作为新的种子值，对新的种子值进行取模计算，重复该步骤，直到生成m个值，形成数据集r＝{r1，
…
，r
m
}
←
prg(s)；步骤1.3，接收方将数据集r＝{r1，
…
，r
m
}从中间分为两部分数据集，分别为{r1，r2…
,r
m/2
}和{r m/2
+1，r m/2
+2，
…
,r
m
}；之后将两部分数据集中的第一个元素对换，即交换r1和r
m/2
+1；再将两部分数据集中的第二个元素对换，即交换r2和r
m/2
+2；依次类推直到交换完最后一个元素，即交换r
m/2
和r
m
，最终将交换之后的两部分数据集进行合并，得到一组值v＝{v1,
…
,v
m
}；并且将这一组值发送给接收方。3.根据权利要求2所述的基于云辅助环境下的非平衡隐私集合求交基数方法，其特征在于，所述步骤2中，具体为：步骤2.1，使用cuckoo hashing插值方法，发送方将自己的数据集x＝{x1,x2,
…
,x
n
}中的每一个数据通过g个哈希函数哈希到m个桶中，桶中的数据用x
b
表示；根据步骤1.1中发送方选择的随机密钥k，求得每一个数据的prf值x
b
’←
f(k,x
b
)，其中b∈m，b
s[b]
表示发送方第b个桶中的值，由于哈希表的长度为m，即可记为x'＝{x'1,......,x'
m
}，并且将x'＝{x'1,......,x'
m
}依次发送给云服务器；步骤2.2，通过simple hashing插值方法，接收方将自己的数据集y＝{y1,y2,
…
,y
n
}使用g个哈希函数散列到m个桶中，桶中的数据用y
b
表示，其中b∈m，根据步骤1.1中发送方发送给接收方的随机密钥k，接收方对于桶中的每一个数据求prf值y
b
’←
f(k,y
b
),),b
r[b]
表示接收方第b个桶中的数据，之后将y
b’进行交错置换得到一组值y
′
π(b)
。4.根据权利要求3所述的基于云辅助环境下的非平衡隐私集合求交基数方法，其特征在于，所述步骤3中，具体为：步骤3.1，云服务器输入步骤2.1中发送方发来的一组值x'＝{x'1,......,x'
m
}经过置换顺序π后所得到x’[π(b)]，其中[π(b)]，其中之后云服务器得到一组输出{a1,a2,...,a
m
}，接收方得到一组输出{a'1,a'2,...,a'
m
}；
步骤3.2，令u
′
b
为不经意键值存储结构的键，接收方计算根据u'
b
创造一组键值对用pa表示这一组键值对，作为键值对存储结构中的值；h(u'
b
)指的是对于u
′
b
求取哈希值；对于这一组键值对进行okvs编码，得到不经意键值对数据结构d＝(d1,d2,
…
,d
m
)
t
；其中d向量是编码后的okvs数据结构；并且将键值对数据结构d发送给云服务器；步骤3.3，云服务器根据步骤3.2中接收方发送过来的结果值使用步骤3.1中的a
b
进行解码，令w
b
表示其解码结果，因此h(a
b
)是对a
b
求哈希值；令w＝{w1,
…
w
m
}并且将w发送给发送方。5.根据权利要求4所述的基于云辅助环境下的非平衡隐私集合求交基数方法，其特征在于，所述步骤4中，具体为：由于发送方对于步骤3.3中云服务器发送的集合w和步骤1.3中接收方发送的集合v所对应的数据是一无所知的，因此对其进行比较，如果集合w和集合v的值相等那么则判定他们有相同的数据，则最终输出交集元素大小|w∩v|。

技术总结
本发明公开了基于云辅助环境下的非平衡隐私集合求交基数方法，具体为：设置阶段：发送方发送随机密钥k给接收方；接收方选择一个随机种子s，生成m个随机值，并将重排后的值发给发送方；数据外包阶段：发送方和接收方分别将数据集哈希到m个桶中，根据密钥计算桶中的PRF值并发给云服务器；计算阶段：云服务器利用发给云服务器的值与接收方调用permute+share技术；接收方对数据进行编码并发给云服务器进行解码，并且将解码后的值发给发送方；最终得到交集基数。本发明的方法，能够将隐私集合外包给云服务器，且不会产生隐私泄露问题；另外该方法客户端的计算量更小，通信代价低，并且减少了求交集过程中的比较次数。少了求交集过程中的比较次数。少了求交集过程中的比较次数。


技术研发人员：刘沫萌 李云云 张英博
受保护的技术使用者：西安工程大学
技术研发日：2023.06.20
技术公布日：2023/9/20