1.本发明实施例涉及隐私计算技术领域，尤其涉及到一种基数估计方法、系统、计算设备及计算机存储介质。
背景技术：2.分布式基数计算，即计算多个数据集合的并集的不同元素的数量，一直以来都是一个非常基础也非常重要的问题，而随着互联网的飞速发展，隐私保护的重要性越来越得到重视。
3.相关技术中，通常基于布隆过滤器计算基数，但该方案不能保护差分隐私，攻击者可以通过结果反推某一个用户是否在集合里，造成隐私数据泄露。
4.因此，如何实现基数估计中的差分隐私保护是现有技术亟待解决的技术问题。
技术实现要素：5.鉴于上述问题，提出了本发明实施例以便提供一种克服上述问题或者至少部分地解决上述问题的一种基数估计方法、系统、计算设备及计算机存储介质。
6.根据本发明实施例的一个方面，提供了一种基数估计方法，包括：
7.多个数据提供方将各自建立的本地概率数据结构、以及各自生成的随机噪声发送至多个计算方；
8.每个所述计算方基于接收到的所有所述本地概率数据结构，确定目标概率数据结构，并基于所述目标概率数据结构、以及接收到的所有所述随机噪声，确定初始估计结果；
9.任意一个所述计算方基于所述初始估计结果，确定目标基数估计结果。
10.在一种可选的方式中，对于每个所述数据提供方，所述本地概率数据结构通过以下方式确定：
11.所述数据提供方采集用于基数估计的统计数据，对所述统计数据进行哈希映射，得到随机比特串；
12.所述数据提供方基于所述随机比特串，确定建立的零比特值概率数据结构对应的数据位置；
13.所述数据提供方将所述零比特值概率数据结构对应的数据位置的数据设置为1，得到所述本地概率数据结构。
14.在一种可选的方式中，对于每个所述数据提供方，所述对所述统计数据进行哈希映射，得到随机比特串，包括：
15.所述数据提供方获取哈希密钥，对所述统计数据和所述哈希密钥进行哈希映射，得到所述随机比特串。
16.在一种可选的方式中，所述本地概率数据结构包含设定数量的比特串，每个所述比特串包含设定长度的一维比特向量。
17.在一种可选的方式中，对于每个所述数据提供方，所述数据提供方将本地概率数
据结构和随机噪声发送至多个所述计算方的过程，包括：
18.所述数据提供方获取待发送数据和有限域，其中，所述待发送数据为随机噪声或所述本地概率数据结构中的单个比特位；
19.所述数据提供方基于所述有限域，确定所述待发送数据对应的多个秘密分享值，其中，所述待发送数据对应的秘密分享值的数量与所述计算方的数量相同；
20.所述数据提供方将各个所述秘密分享值发送至各个所述计算方，其中，不同的所述计算方接收的秘密分享值不同。
21.在一种可选的方式中，所述数据提供方基于所述有限域，确定所述待发送数据对应的多个秘密分享值，包括：
22.多个所述计算方各自生成所述待发送数据对应的随机数份额值；
23.所述数据提供方接收每个所述随机数份额值，基于各个所述随机数份额值，确定所述待发送数据对应的随机数，并确定所述待发送数据与所述待发送数据对应的随机数之间的差值，基于所述有限域，确定所述差值对应的多个秘密分享值。
24.在一种可选的方式中，所述任意一个所述计算方基于所述初始估计结果，确定目标基数估计结果，包括：
25.每个所述计算方获取各自对应的全局密钥份额，基于所述初始估计结果和所述全局密钥份额，确定所述初始估计结果对应的第一验证结果，并广播所述第一验证结果；
26.任意一个所述计算方接收其它所述计算方的第一验证结果，并将所有所述第一验证结果相加，得到第二验证结果；
27.若所述第二验证结果不等于0，则所有所述数据提供方和所有所述计算方停止基数估计；
28.若所述第二验证结果等于0，则任意一个所述计算方基于所述初始估计结果，确定目标基数估计结果。
29.根据本发明实施例的另一方面，提供了一种基数估计系统，包括多个数据提供方和多个计算方；
30.多个所述数据提供方，用于将各自建立的本地概率数据结构、以及各自生成的随机噪声发送至多个所述计算方；
31.每个所述计算方，用于基于接收到的所有所述本地概率数据结构，确定目标概率数据结构，并基于所述目标概率数据结构、以及接收到的所有所述随机噪声，确定初始估计结果；
32.任意一个所述计算方，还用于基于所述初始估计结果，确定目标基数估计结果。
33.根据本发明实施例的又一方面，提供了一种计算设备，包括：处理器、存储器、通信接口和通信总线，所述处理器、所述存储器和所述通信接口通过所述通信总线完成相互间的通信；
34.所述存储器用于存放至少一可执行指令，所述可执行指令使所述处理器执行上述基数估计方法对应的操作。
35.根据本发明实施例的再一方面，提供了一种计算机存储介质，所述存储介质中存储有至少一可执行指令，所述可执行指令使处理器执行如上述基数估计方法对应的操作。
36.根据本发明实施例的提供的基数估计方法、系统、计算设备及计算机存储介质，多
个数据提供方提供随机噪声，各个计算方基于概率数据结构和接收到的所有随机噪声，计算基数估计结果，从而使得任何攻击者都没有办法通过该基数估计结果推断出某一个个体是否在集合当中，从而实现基数估计中的差分隐私保护。
37.上述说明仅是本发明实施例技术方案的概述，为了能够更清楚了解本发明实施例的技术手段，而可依照说明书的内容予以实施，并且为了让本发明实施例的上述和其它目的、特征和优点能够更明显易懂，以下特举本发明实施例的具体实施方式。
附图说明
38.通过阅读下文优选实施方式的详细描述，各种其他的优点和益处对于本领域普通技术人员将变得清楚明了。附图仅用于示出优选实施方式的目的，而并不认为是对本发明实施例的限制。而且在整个附图中，用相同的参考符号表示相同的部件。在附图中：
39.图1示出了根据本发明一个实施例的基数估计方法的流程图；
40.图2示出了根据本发明一个实施例的概率数据结构和随机比特串的结构图；
41.图3示出了根据本发明实施例的一种计算设备的结构示意图。
具体实施方式
42.下面将参照附图更详细地描述本发明的示例性实施例。虽然附图中显示了本发明的示例性实施例，然而应当理解，可以以各种形式实现本发明而不应被这里阐述的实施例所限制。相反，提供这些实施例是为了能够更透彻地理解本发明，并且能够将本发明的范围完整的传达给本领域的技术人员。
43.在本发明实施例提供的解决方案中，各个数据提供方用于收集计算方所要统计的数据，如访问某些网站的ip地址、点击广告的用户id及射频识别系统采集到的车流信息等，并以概率数据结构的方式存储或发送上述数据，从而减少资源的占用空间消耗。在本发明实施例中，计算方可以是云计算服务器等具有较大计算资源的设备，数据提供方可以是数据仓库设备等具有较大数据容量的设备，本发明对此不作限制。
44.图1示出了根据本发明一个实施例的基数估计方法的流程图，该方法包括如下步骤：
45.步骤101，多个数据提供方将各自建立的本地概率数据结构、以及各自生成的随机噪声发送至多个计算方。
46.在该实施例中，每个数据提供方收集本地的统计数据集，以构建本地fms sketch(本地概率数据结构)，并且把自己的本地fms sketch秘密共享给所有的计算方。同时，每个数据提供方也生成一个离散高斯随机变量(即随机噪声)，用于实现差分隐私保护。
47.示例性地，本实施例采用分布式离散高斯噪声机制，具体来讲，每一个数据提供方j生成一个满足离散高斯分布nz(0,σ2)的随机数(即随机噪声))的随机数(即随机噪声)为整数域，σ2为方差。且每一个数据提供方都秘密共享他的随机噪声给所有的计算方，计算方基于c个数据提供方的噪声总和实现差分隐私保护。经实验，上述分布式离散高斯噪声机制可以实现参数为0.5∈2的浓缩差分隐私，其中，∈2用于表示隐私保密度。
48.可选的，在一个实施例中，对于每个所述数据提供方，所述本地概率数据结构通过
以下方式确定：
49.所述数据提供方采集用于基数估计的统计数据，对所述统计数据进行哈希映射，得到随机比特串；
50.所述数据提供方基于所述随机比特串，确定建立的零比特值概率数据结构对应的数据位置；
51.所述数据提供方将所述零比特值概率数据结构对应的数据位置的数据设置为1，得到所述本地概率数据结构。
52.需要说明的是，fms sketch是由本发明实施例首次提出的一种概率数据结构，这种概率数据结构可以用于统计极大规模数据集的基数，且内存需求只需几kb，更新每一条数据的时间复杂度只有o(1)，相比于fmsketch的o(m)(m通常取几千)降低了3个数量级。
53.可选的，所述本地概率数据结构包含设定数量的比特串，每个所述比特串包含设定长度的一维比特向量。
54.示例性地，fms sketch{bi,h}
i＝1,
…
,m
包含m个比特串b1,
…
,bm，h为用于更新fms sketch的哈希函数，其中，m＝2r，r是一个正整数。每一个比特串都是一个长度为w的一维的比特向量，m和w的取值可由各个数据提供方和计算方协商决定。每个数据提供方的本地fms sketch刚开始都初始化为0。除此以外，每个数据提供方的的fms sketch统一使用一个哈希函数h()，该哈希函数h()用于将一个元素映射为一个长度为(r+w-1)位的随机比特串。
55.上述随机比特串用于更新fms sketch，如图2所示的fms sketch，其对应的参数r和w分别等于3和8，图2中的变量z1至zm表示序号为0至7的8个比特串各自对应的0比特位的数量，h(x)表示对数据x的哈希映射操作，01011100111为生成的随机比特串。将随机比特串最右边的r(即3)位的二进制111转换为十进制，以确定要更新的fms sketch中的比特串的序号(即7)，并以随机比特串最右边出现的第一个0所具有的连续0的数量，确定要更新的比特串中的具体下标(即2)，从而确定建立的零比特值概率数据结构对应的数据位置。若fms sketch中该数据位置的比特值为0，则设置为1，若fms sketch中该数据位置的比特值为1，则不作更改，从而完成对fms sketch的更新。
56.可选的，对于每个所述数据提供方，所述对所述统计数据进行哈希映射，得到随机比特串，包括：
57.所述数据提供方获取哈希密钥，对所述统计数据和所述哈希密钥进行哈希映射，得到所述随机比特串。
58.示例性地，所有的数据提供方选择一种键控哈希，并且执行可验证组秘钥协议获取哈希秘钥k。这样一来，更新概率数据结构所用到的哈希映射操作就可以通过哈希函数h(e)＝h(k||e)来实现。其中，||是字符串串联操作符，e可以表示统计数据中的单个元素。
59.可选的，在一个实施例中，对于每个所述数据提供方，所述数据提供方将本地概率数据结构和随机噪声发送至多个所述计算方的过程，包括：
60.所述数据提供方获取待发送数据和有限域，其中，所述待发送数据为随机噪声或所述本地概率数据结构中的单个比特位；
61.所述数据提供方基于所述有限域，确定所述待发送数据对应的多个秘密分享值，其中，所述待发送数据对应的秘密分享值的数量与所述计算方的数量相同；
62.所述数据提供方将各个所述秘密分享值发送至各个所述计算方，其中，不同的所
述计算方接收的秘密分享值不同。
63.示例性地，数据提供方和计算方共同协商一个有限域其中，模数p是一个(λ+τ)位的质数，λ(比如取40)是一个统计安全参数，τ(比如取32)是由明文域的长度决定的。
64.对于待发送数据对应的多个秘密分享值的设置，以本地概率数据结构中的单个比特位为例进行说明。该单个比特位对应的每个秘密分享值均属于有效域即秘密分享值的取值为0至(p-1)中的一项，且利用模数p对所有秘密分享值的总和进行取模计算，得到的计算结果应等于所有秘密分享值对应的该单个比特位的值。
65.进一步的，数据提供方在生成了本地fms sketch和随机噪声以后，将这些待发送数据以秘密分享值的形式秘密共享给所有的计算方。该秘密共享的流程如下：
66.首先，在spdz框架下，一个整数被表示为有限域(例如，基于模数p构建的有限域，其中，p是一个非常大的质数)内分享的形式，具体如下：
[0067][0068]
共c个计算方，每一个计算方j都只持有一个三元组
[0069]
其中，三元组的三个部分分别代表待发送数据x、mac和mac秘钥的加法共享。mac和mac秘钥是用来验证待发送数据x的可信程度的，有如果有敌手篡改了待发送数据x，那么我们可以通过mac和mac秘钥来发现。
[0070]
可选的，对于每个所述数据提供方，所述数据提供方基于所述有限域，确定所述待发送数据对应的多个秘密分享值，包括：
[0071]
多个所述计算方各自生成所述待发送数据对应的随机数份额值；
[0072]
所述数据提供方接收每个所述随机数份额值，基于各个所述随机数份额值，确定所述待发送数据对应的随机数，并确定所述待发送数据与所述待发送数据对应的随机数之间的差值，基于所述有限域，确定所述差值对应的多个秘密分享值。
[0073]
可以理解的是，各个数据提供方和计算方可以根据自己对于安全系数、隐私预算以及估计精度的要求预先协商秘钥长度、比特串数量以及有限域大小。
[0074]
示例性地，所有的计算方执行离线协议，预先生成足量的随机数，以便后续使用。在一次秘密分享中，选择一个未被使用的随机数，以防止有敌手破解加密，并使每一个计算方都只拿到这个随机数的一个秘密份额，即随机数份额值。所以当且仅当所有的计算方都被控制了，敌手才有可能获取到随机数的真实值。
[0075]
为了将数据提供方的一个待发送数据x分享给计算方，本实施例采取了一个秘密分享子协议。具体来讲，所有的计算方(共c个)共同向该数据提供方揭露一个随机数其中，和δ1,
…
,δc分别表示随机数a对应的mac和mac密钥。揭露的方法就是每一个计算方将自己的aj发送给该数据提供方。随后该数据提供方就可以计算出随机数a的实际值。获取到a以后，该数据提供方计算差值(x-a)，并将该差值字广播给所有的计算方。
[0076]
其中，所用到的离线阶段生成随机数的协议的可以包括triple()、rand()、rand2
()和randexp()，这些都可以通过spdz协议实现。
[0077]
具体的，rand()用于生成随机整数的秘密表示在秘密数加法和秘密数和明文加法里用到。rand2()用于生成0或1的秘密表示，其中，0或1各自都有不止一种加密结果。triple()用于生成三个秘密数其中，c＝a
×
b，triple()可以用于秘密数乘法。randexp()生成一系列秘密数在判零协议里用到。
[0078]
作为一种可能的实施方式，向计算方j分享待发送数据x的规则如下：
[0079]
如果满足j＝1，则否则，
[0080]
可以理解的是，由于随机数a的真实值对于至多只控制了c-1个计算方的敌手是不知情的，所以上述分享过程的安全的。为了避免可能的攻击，随机数a一旦用过以后就被抛弃。所以，每一次秘密分享都要用到一个不同的随机数，从而基于多个计算方共同确定的随机数，每一个数据提供方都能够将自己的本地fms sketch的每一位都秘密共享给所有的计算方。
[0081]
步骤102，每个所述计算方基于接收到的所有所述本地概率数据结构，确定目标概率数据结构，并基于所述目标概率数据结构、以及接收到的所有所述随机噪声，确定初始估计结果。
[0082]
作为一种可能的实施方式，每个计算方计算所有统计数据的并集的fms sketch的过程如下：
[0083]
假设每个fms sketch由m个比特串组成：{bi}
i＝1,
…
,m
，共有d个数据提供方的本地fms sketch，表示第k个本地fms sketch中第i个比特串的第l个比特位的值，则定义b
i*
[l]为：
[0084][0085]
显而易见，当b
i*
[l]＞0时，bi[l]＝1，当b
i*
[l]＝0时，bi[l]＝0，其中，bi[l]为并集的fms sketch中的第i个比特串的第l个比特位的值。
[0086]
而在spdz协议里，对于秘密分享至计算方j的数据x和y(计算方j的全局密钥份额为δj，和为数据x和y对应的mac)，秘密数相加定义如下：
[0087][0088]
因此，结合上述b
i*
[l]与bi[l]的取值关系以及秘密数相加的定义，对于每个计算方，若要基于接收到的所有fms sketch对应的秘密分享值，计算得到(bi[l]的秘密表达)，首先需要基于的秘密表达，计算b
i*
[l]的秘密表达然后再基于计算结果是否为0，推知的取值。
[0089]
在该实施例中，每个计算方计算所有统计数据的并集的fms sketch，以得到目标概率数据结构，并计算该目标概率数据结构的z变量，最后对该z变量安全地添加随机噪声以得到初始估计结果，从而实现差分隐私保护。
[0090]
其中，z变量用于表示目标概率数据结构中仍然为0的比特位的数量，即：
[0091][0092]
其中，bi[x]表示目标概率数据结构中第i个比特串的第x个比特位的值，fms sketch由m个比特串组成，每个比特串长度为w。
[0093]
示例性地，每一个计算方j都持有噪声变量d为数据提供方的数量，计算方j将噪声变量加起来：其中，就是最终所需要添加的噪声。
[0094]
在已有了和的基础上，每个计算方j计算初始估计结果其中，fms sketch由m个比特串组成，c为数据提供方的数量，每个比特串长度为w。
[0095]
步骤103，任意一个所述计算方基于所述初始估计结果，确定目标基数估计结果。
[0096]
作为一种可能的实施方式，假设fms sketch由m个比特串组成，每个比特串长度为w，z的期望是：
[0097][0098]
其中：
[0099][0100]
因此，在估计基数时，将计算得到的z和各个随机噪声之间的和(即初始估计结果)作为e(z)，通过牛顿迭代法或二分法得到目标基数估计结果n。
[0101]
可选的，在一个实施例中，所述任意一个所述计算方基于所述初始估计结果，确定目标基数估计结果，包括：
[0102]
每个所述计算方获取各自对应的全局密钥份额，基于所述初始估计结果和所述全局密钥份额，确定所述初始估计结果对应的第一验证结果，并广播所述第一验证结果；
[0103]
任意一个所述计算方接收其它所述计算方的第一验证结果，并将所有所述第一验证结果相加，得到第二验证结果；
[0104]
若所述第二验证结果不等于0，则所有所述数据提供方和所有所述计算方停止基数估计；
[0105]
若所述第二验证结果等于0，则任意一个所述计算方基于所述初始估计结果，确定目标基数估计结果。
[0106]
作为一种可能的实施方式，所有的计算方执行spdz协议的初始化阶段，以确定一个全局密钥，并各自获取该全局密钥的一个秘密份额，从而得到全局密钥份额。
[0107]
示例性地，假设共c个数据提供方，nk为噪声变量，z为并集的概率数据结构中0比
特位的个数，在spdz框架公开揭露之前，首先检查x的真实性。检查方法如下：
[0108]
每一个计算方都计算第一验证结果然后公开广播计算方检查是否第二验证结果如果结果不是0，那么说明计算结果被篡改了，程序停止。如果结果是0，说明计算正确，计算方公开x，以计算并输出目标基数估计结果。
[0109]
其中，每个计算方可以在计算得到初始估计结果x的同时，根据该初始估计结果x和全局密钥份额δj，确定并在公开初始估计结果x之前，基于当前存储的初始估计结果x计算xδj，进而基于验证计算结果是否被篡改。
[0110]
基于上述实施例提供的基数估计方法，以医疗系统的患病种类统计的使用场景为例进行说明。此时，多家医院作为数据提供方以统计本地医疗系统中记录的患者信息(包含患者的身份信息和患病种类)。对于每个医院，其本地医疗系统中记录的患者信息将用于构造医院本地的fms sketch，以减少统计患者信息所产生的资源消耗，从而降低对数据提供方的计算资源需求；同时，每家医院将为所有计算方提供一个随机噪声，并将构建完成的本地fms sketch和随机噪声发给所有的计算方。各个计算方基于接收到的所有医院的本地fms sketch，确定能够表征所有患者信息的并集的目标fms sketch，并根据该目标fms sketch，得到能够用于求解患病种类数量的估计量，将该估计量与接收的各个随机噪声进行叠加后再对患病种类数量进行估计，以使攻击方不能基于估计结果推知任一病患的患者信息，从而实现在患病种类估计(即基数估计)中对患者信息的差分隐私保护。
[0111]
可以理解的是，上述实施例提供的基数估计方法，使用一种原创的fms sketch，仅需要几kb的空间就可以统计数十亿的数据量，同时，对于数据流当中的每一个元素，只需要一次哈希运算来更新sketch，而传统的方案需要几千次的哈希运算来更新sketch，使得本发明实施例提供的基数估计方法对于数据提供方要求的计算资源非常低，且数据收集速度快。且本发明实施例采用了一种由多个数据提供方提供高斯噪声的方法来实现差分隐私，解决了以往算法难以保证差分隐私的问题。同时，本发明实施例中用到的fms sketch，由于其独特的构造，使得计算得到的变量z对噪声的敏感度也非常低，因而实现差分隐私只需要添加非常小的噪声。
[0112]
具体来讲，算法f(x)的敏感度定义为：δf＝max|f(x)-f(y)|。
[0113]
其中，x和y是只有一个数据不同的任意数据集合。例如，x＝{a，b，c，d，e}，y＝{a，b，c，d}。
[0114]
基于上述敏感度定义可知，fms sketch用于估计基数的变量z的敏感度是1。
[0115]
对于需要添加的噪声大小，如果采用高斯机制来实现差分隐私，需要添加的噪声是满足该分布的高斯噪声：
[0116][0117]
其中，μ和σ2为噪声的均值和方差，δ为隐私参数，ε2用于表示隐私保密度。
[0118]
在其他参数确定的情况下，fms sketch为实现差分隐私需要添加的噪声的方差仅为相比于fm sketch(敏感度为w
·
m)和hll sketch(敏感度为w+1)，其所需添加的噪声非常小。
[0119]
本发明实施例还提供了一种基数估计系统，包括多个数据提供方和多个计算方；
[0120]
多个所述数据提供方，用于将各自建立的本地概率数据结构、以及各自生成的随机噪声发送至多个所述计算方；
[0121]
每个所述计算方，用于基于接收到的所有所述本地概率数据结构，确定目标概率数据结构，并基于所述目标概率数据结构、以及接收到的所有所述随机噪声，确定初始估计结果；
[0122]
任意一个所述计算方，还用于基于所述初始估计结果，确定目标基数估计结果。
[0123]
在一种可选的方式中，所述数据提供方，还用于采集用于基数估计的统计数据，对所述统计数据进行哈希映射，得到随机比特串；基于所述随机比特串，确定建立的零比特值概率数据结构对应的数据位置；将所述零比特值概率数据结构对应的数据位置的数据设置为1，得到所述本地概率数据结构。
[0124]
在一种可选的方式中，所述数据提供方，还用于获取哈希密钥，对所述统计数据和所述哈希密钥进行哈希映射，得到所述随机比特串。
[0125]
在一种可选的方式中，所述本地概率数据结构包含设定数量的比特串，每个所述比特串包含设定长度的一维比特向量。
[0126]
在一种可选的方式中，所述数据提供方，还用于获取待发送数据和有限域，其中，所述待发送数据为随机噪声或所述本地概率数据结构中的单个比特位；基于所述有限域，确定所述待发送数据对应的多个秘密分享值，其中，所述待发送数据对应的秘密分享值的数量与所述计算方的数量相同；将各个所述秘密分享值发送至各个所述计算方，其中，不同的所述计算方接收的秘密分享值不同。
[0127]
在一种可选的方式中，多个所述计算方，还用于各自生成所述待发送数据对应的随机数份额值；
[0128]
所述数据提供方，还用于接收每个所述随机数份额值，基于各个所述随机数份额值，确定所述待发送数据对应的随机数，并确定所述待发送数据与所述待发送数据对应的随机数之间的差值，基于所述有限域，确定所述差值对应的多个秘密分享值。
[0129]
在一种可选的方式中，每个所述计算方，还用于获取各自对应的全局密钥份额，基于所述初始估计结果和所述全局密钥份额，确定所述初始估计结果对应的第一验证结果，并广播所述第一验证结果；
[0130]
任意一个所述计算方，还用于接收其它所述计算方的第一验证结果，并将所有所述第一验证结果相加，得到第二验证结果；
[0131]
若所述第二验证结果不等于0，则所有所述数据提供方和所有所述计算方停止基数估计；
[0132]
若所述第二验证结果等于0，则任意一个所述计算方，还用于基于所述初始估计结果，确定目标基数估计结果。
[0133]
以上各模块的描述参照方法实施例中对应的描述，在此不再赘述。
[0134]
本发明实施例还提供了一种非易失性计算机存储介质，计算机存储介质存储有至少一可执行指令，可执行指令可执行上述任意方法实施例中的基数估计方法。
[0135]
图3示出了根据本发明实施例的一种计算设备的结构示意图，本发明实施例的具体实施例并不对计算设备的具体实现做限定。如图3所示，该计算设备可以包括：处理器(processor)1002、通信接口(communications interface)1004、存储器(memory)1006、以及通信总线1008。其中：
[0136]
处理器1002、通信接口1004、以及存储器1006通过通信总线1008完成相互间的通信。
[0137]
通信接口1004，用于与其它设备比如客户端或其它服务器等的网元通信。处理器1002，用于执行程序1010，具体可以执行上述基数估计方法实施例中的相关步骤。
[0138]
具体地，程序1010可以包括程序代码，该程序代码包括计算机操作指令。处理器1002可能是中央处理器cpu，或者是特定集成电路asic(applicationspecific integrated circuit)，或者是被配置成实施本发明实施例的一个或多个集成电路。计算设备包括的一个或多个处理器，可以是同一类型的处理器，如一个或多个cpu；也可以是不同类型的处理器，如一个或多个cpu以及一个或多个asic。
[0139]
存储器1006，用于存放程序1010。存储器1006可能包含高速ram存储器，也可能还包括非易失性存储器(non-volatile memory)，例如至少一个磁盘存储器。
[0140]
程序1010具体可以用于使得处理器1002执行上述任意方法实施例中的基数估计方法。程序1010中各步骤的具体实现可以参见上述基数估计方法实施例中的相应步骤和单元中对应的描述，在此不赘述。所属领域的技术人员可以清楚地了解到，为描述的方便和简洁，上述描述的设备和模块的具体工作过程，可以参考前述方法实施例中的对应过程描述，在此不再赘述。
[0141]
在此提供的算法或显示不与任何特定计算机、虚拟系统或者其它设备固有相关。各种通用系统也可以与基于在此的示教一起使用。根据上面的描述，构造这类系统所要求的结构是显而易见的。此外，本发明实施例也不针对任何特定编程语言。应当明白，可以利用各种编程语言实现在此描述的本发明实施例的内容，并且上面对特定语言所做的描述是为了披露本发明实施例的较佳实施方式。
[0142]
在此处所提供的说明书中，说明了大量具体细节。然而，能够理解，本发明的实施例可以在没有这些具体细节的情况下实践。在一些实例中，并未详细示出公知的方法、结构和技术，以便不模糊对本说明书的理解。
[0143]
类似地，应当理解，为了精简本发明实施例并帮助理解各个发明方面中的一个或多个，在上面对本发明的示例性实施例的描述中，本发明实施例的各个特征有时被一起分组到单个实施例、图、或者对其的描述中。然而，并不应将该公开的方法解释成反映如下意图：即所要求保护的本发明实施例要求比在每个权利要求中所明确记载的特征更多的特征。更确切地说，如下面的权利要求书所反映的那样，发明方面在于少于前面公开的单个实施例的所有特征。因此，遵循具体实施方式的权利要求书由此明确地并入该具体实施方式，其中每个权利要求本身都作为本发明的单独实施例。
[0144]
本领域那些技术人员可以理解，可以对实施例中的设备中的模块进行自适应性地
改变并且把它们设置在与该实施例不同的一个或多个设备中。可以把实施例中的模块或单元或组件组合成一个模块或单元或组件，以及此外可以把它们分成多个子模块或子单元或子组件。除了这样的特征和/或过程或者单元中的至少一些是相互排斥之外，可以采用任何组合对本说明书(包括伴随的权利要求、摘要和附图)中公开的所有特征以及如此公开的任何方法或者设备的所有过程或单元进行组合。除非另外明确陈述，本说明书(包括伴随的权利要求、摘要和附图)中公开的每个特征可以由提供相同、等同或相似目的的替代特征来代替。
技术特征：1.一种基数估计方法，其特征在于，包括：多个数据提供方将各自建立的本地概率数据结构、以及各自生成的随机噪声发送至多个计算方；每个所述计算方基于接收到的所有所述本地概率数据结构，确定目标概率数据结构，并基于所述目标概率数据结构、以及接收到的所有所述随机噪声，确定初始估计结果；任意一个所述计算方基于所述初始估计结果，确定目标基数估计结果。2.根据权利要求1所述的方法，其特征在于，对于每个所述数据提供方，所述本地概率数据结构通过以下方式确定：所述数据提供方采集用于基数估计的统计数据，对所述统计数据进行哈希映射，得到随机比特串；所述数据提供方基于所述随机比特串，确定建立的零比特值概率数据结构对应的数据位置；所述数据提供方将所述零比特值概率数据结构对应的数据位置的数据设置为1，得到所述本地概率数据结构。3.根据权利要求2所述的方法，其特征在于，对于每个所述数据提供方，所述对所述统计数据进行哈希映射，得到随机比特串，包括：所述数据提供方获取哈希密钥，对所述统计数据和所述哈希密钥进行哈希映射，得到所述随机比特串。4.根据权利要求2所述的方法，其特征在于，所述本地概率数据结构包含设定数量的比特串，每个所述比特串包含设定长度的一维比特向量。5.根据权利要求1所述的方法，其特征在于，对于每个所述数据提供方，所述数据提供方将本地概率数据结构和随机噪声发送至多个所述计算方的过程，包括：所述数据提供方获取待发送数据和有限域，其中，所述待发送数据为随机噪声或所述本地概率数据结构中的单个比特位；所述数据提供方基于所述有限域，确定所述待发送数据对应的多个秘密分享值，其中，所述待发送数据对应的秘密分享值的数量与所述计算方的数量相同；所述数据提供方将各个所述秘密分享值发送至各个所述计算方，其中，不同的所述计算方接收的秘密分享值不同。6.根据权利要求5所述的方法，其特征在于，对于每个所述数据提供方，所述数据提供方基于所述有限域，确定所述待发送数据对应的多个秘密分享值，包括：多个所述计算方各自生成所述待发送数据对应的随机数份额值；所述数据提供方接收每个所述随机数份额值，基于各个所述随机数份额值，确定所述待发送数据对应的随机数，并确定所述待发送数据与所述待发送数据对应的随机数之间的差值，基于所述有限域，确定所述差值对应的多个秘密分享值。7.根据权利要求1至6中任一项所述的方法，其特征在于，所述任意一个所述计算方基于所述初始估计结果，确定目标基数估计结果，包括：每个所述计算方获取各自对应的全局密钥份额，基于所述初始估计结果和所述全局密钥份额，确定所述初始估计结果对应的第一验证结果，并广播所述第一验证结果；任意一个所述计算方接收其它所述计算方的第一验证结果，并将所有所述第一验证结
果相加，得到第二验证结果；若所述第二验证结果不等于0，则所有所述数据提供方和所有所述计算方停止基数估计；若所述第二验证结果等于0，则任意一个所述计算方基于所述初始估计结果，确定目标基数估计结果。8.一种基数估计系统，其特征在于，包括多个数据提供方和多个计算方；多个所述数据提供方，用于将各自建立的本地概率数据结构、以及各自生成的随机噪声发送至多个所述计算方；每个所述计算方，用于基于接收到的所有所述本地概率数据结构，确定目标概率数据结构，并基于所述目标概率数据结构、以及接收到的所有所述随机噪声，确定初始估计结果；任意一个所述计算方，还用于基于所述初始估计结果，确定目标基数估计结果。9.一种计算设备，其特征在于，包括：处理器、存储器、通信接口和通信总线，所述处理器、所述存储器和所述通信接口通过所述通信总线完成相互间的通信；所述存储器用于存放至少一可执行指令，所述可执行指令使所述处理器执行如权利要求1-7中任一项所述的基数估计方法对应的操作。10.一种计算机存储介质，其特征在于，所述存储介质中存储有至少一可执行指令，所述可执行指令使处理器执行如权利要求1-7中任一项所述的基数估计方法对应的操作。
技术总结本发明实施例公开了一种基数估计方法、系统、计算设备及计算机存储介质。方法包括：多个数据提供方将各自建立的本地概率数据结构、以及各自生成的随机噪声发送至多个计算方；每个所述计算方基于接收到的所有所述本地概率数据结构，确定目标概率数据结构，并基于所述目标概率数据结构、以及接收到的所有所述随机噪声，确定初始估计结果；任意一个所述计算方基于所述初始估计结果，确定目标基数估计结果。本发明实施例中，多个数据提供方提供随机噪声，计算方基于概率数据结构和所有随机噪声，计算基数估计结果，从而使得任何攻击者都没有办法通过该基数估计结果推断出某一个个体是否在集合当中，从而实现基数估计中的差分隐私保护。保护。保护。
技术研发人员：王平辉 谢东东 杨承锦
受保护的技术使用者：西安交通大学
技术研发日：2022.07.22
技术公布日：2022/11/1
