(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202210678574.9 (22)申请日 2022.06.15 (71)申请人 华中科技大 学 地址 430074 湖北省武汉市洪山区珞喻路 1037号 (72)发明人 何媛媛　王法尧　谭新宇　 (74)专利代理 机构 华中科技大 学专利中心 42201 专利代理师 夏倩　李智 (51)Int.Cl. H04L 9/00(2022.01) H04L 9/32(2006.01) H04L 9/40(2022.01) (54)发明名称 差分隐私保护的集合交集及其基数计算方 法、 装置及系统 (57)摘要 本发明公开了一种差分隐私保护的集合交 集及其基数计算方法、 装置及系统， 属于数据安 全和隐私保护领域， 包括： 使用异或同态加密算 法结合布隆过滤器高效判断元素的相等性， 保护 交集以外的集合元素； 利用随机响应机制独立扰 动每个元素的判断结果， 输出扰动后的交集及交 集基数， 对交集基数、 交集内元素的敏感信息实 现差分隐私保护； 在计算交集基数时， 使用校正 公式修正随机化运算对真实交集基数的影 响， 提 供无偏估计； 在计算交集时， 产生不同扰动程度 的交集结果， 保护弱势方用户的利益。 本发明能 够在计算隐私保护集合的交集及交集基数的过 程中， 有效保护交集内部元素和交集基数， 并提 高计算效率。 权利要求书4页 说明书13页 附图4页 CN 115242371 A 2022.10.25 CN 115242371 A 1.一种隐私保护集合的交集基数计算方法， 其特征在于， 包括： 在大数据方执行的加密 步骤和基数计算步骤， 以及在小数据方执行 的扰动步骤； 大数据方持有的样本数量不小于 小数据方持有的样本数量； 所述加密步骤包括： 构造布隆过滤器， 并将所述大数据 方的样本集合A中的各元素插入 所述布隆过滤器， 利用公钥对所述布隆过滤器加密后， 将加密后的布隆过滤器连同所述公 钥发送给小 数据方； 所述样 本集合A由所述大数据方所持有的样 本的ID组成； 所述样 本集合 A中每个元素在所述布隆过滤器中对应多个插入位置， 所述多个插入位置由预设的散列函 数集合中的各散列函数对该 元素计算得到； 所述扰动步骤包括： 遍历所述小数据 方的样本集合B中的元素， 对于每一个遍历到的元 素， 基于随机响应机制将该元素与所述布隆过滤器中的密文进行匹配， 以生成用于标识元 素匹配结果的元素， 并加入到扰动集合； 遍历结束后， 将所述扰动集合发送给所述大数据 方； 所述样本集 合B由所述小数据方 所持有的样本的ID组成； 所述基数计算步骤包括： 利用与所述公钥配对的私钥对所述扰动集合进行解密， 统计 解密后的扰动集合中表示匹配成功的元素的个数， 作为隐私保护集合的交集的基数并发送 给所述小数据方。 2.如权利要求1所述的隐私保护集合的交集基数计算方法， 其特征在于， 在所述扰动步 骤中， 对于遍历到的元素， 基于随机响应机制将该元素与所述布隆过滤器中的密文进行匹 配， 以生成用于标识匹配结果的元 素， 并加入到扰动集 合， 包括： 按照概率p从加密后的布隆过滤器中抽取密文， 并利用所述公钥对抽取出的密文进行 加密， 得到用于标识元素匹配结果的元素， 加入所述扰动集合； 抽取密文的方式为： 利用所 述散列函数集合中的每一个散列函数对所遍历 到的元素计算散列值， 按照所计算的散列值 从布隆过 滤器中对应的位置抽取密文； p∈[0,1]； 若不抽取密文， 则直接生成用于表示元素匹配成功 的元素， 或者用于表示元素匹配失 败的元素， 并加入所述扰动集 合； 生成用于表示元 素匹配成功的元 素的概率为q； q∈[0,1]。 3.如权利要求2所述的隐私保护集合的交集基数计算方法， 其特征在于， 利用所述公钥 对抽取出的密文 进行加密， 所使用的加密算法为具有同态性质的加密算法。 4.如权利要求3所述的隐私保护集合的交集基数计算方法， 其特征在于， 所述具有同态 性质的加密算法为具有异或同态性质的加密算法。 5.如权利要求2～4任一项所述的隐私保护集合的交集基数计算方法， 其特征在于， 所 述基数计算 步骤还包括： 利用校正公式对统计得到的基数进行 校正； 所述校正公式为： 其中， card ′和card分别表示校正前、 后的基数， nw表示所述样本集合B中的元素个数； p ≠0。 6.一种隐私保护集 合的交集计算方法， 其特 征在于， 包括： 在大数据方， 利用防碰撞的散列函数对 其样本集合DA中的各元素进行编码， 得到编码集 合CA， 并利用公钥pbA对所述编码集合CA中的各元素加密， 得到密文集合MA； 在小数据方， 利 用所述防碰撞的散列函数对其样本集合DB中的各元素进行编码， 得到编码集合CB； 所述样本 集合DA由所述大数据方所持有的样本的ID组成， 所述样本集合DB由所述小数据方所持有的权　利　要　求　书 1/4 页 2 CN 115242371 A 2样本的ID组成； 在所述小数据方， 构造布隆过滤器， 并将其抽样集合SB中的各元素插入所述布隆过滤 器， 利用公钥pbB对所述布隆过滤器加密后， 将加密后的布隆过滤器连同所述公钥pbB发送给 大数据方； 所述抽样集合SB由所述样本集合DB中的全部元素或随机抽样得到的部分元素构 成； 所述抽样集合SB中每个元素在所述布隆过滤器中对应多个插入位置， 所述多个插入位 置由预设的散列函数集 合中的各散列函数对该 元素计算得到； 在所述大数据方， 遍历所述编码集合CA， 对于每一个遍历到的元素编码， 利用所述公钥 pbB加密该元素编码的每一位后， 基于随机响应机制将加密所得的编码密文与所述布隆过 滤器中的密文进行匹配， 以生成用于标识元素匹配结果的元素， 并加入到扰动集合A； 遍历 结束后， 将所述扰动集 合A、 所述密文集 合MA连同所述公钥pbA发送给所述小数据方； 在所述小数据方， 利用与所述公钥pbB相配对的私钥pvB对所述扰动集合A进行解密， 获 得解密后的扰动集合A与所述编码集合CB相同的元素编码后， 利用所述样本集合DB中与这些 元素编码相对应的元素构成小数据方的隐私保护集合的交集， 记为第二交集； 在所述小数 据方， 从所述密文集合MA中随机抽取部分密文， 并利用公钥pbA对所抽取的密文及第二交集 中各元素 的密文添加随机数以进行密文盲化， 将盲化密文加入一个集合， 随机扰乱集合中 密文排序并记此集 合为扰动集 合B， 之后将所述扰动集 合B发送给 所述大数据方； 在所述大数据方， 利用与所述公钥pbA相配对的私钥pvA对所述扰动集合B进行解密， 获 得解密后的扰动集合B与所述编码集合CA相同的元素编码后， 利用所述样本集合DA中与这些 编码元素相对应的元 素构成大 数据方的隐私保护集 合的交集， 记为第一交集； 其中， 大数据方持有的样本数量 不小于小数据方持有的样本数量。 7.如权利要求6所述的隐私保护集合的交集计算方法， 其特征在于， 在所述大数据方， 遍历所述编码集合CA时， 对于遍历到的元素编码， 利用所述公钥pbB加密该元素编码的每一 位后， 基于随机响应机制将加密所得的编码密文与所述布隆过滤器中的密文进行匹配， 以 生成用于标识元 素匹配结果的元 素， 并加入到扰动集 合A， 包括： 在大数据方， 利用所述公钥pbB加密遍历到的元素编码的每一位后， 按照概率p从加密后 的布隆过滤器中抽取密文， 并将加密得到的编码密文与抽取出的密文进行逐位求积， 得到 用于标识元素匹配结果的元素， 并加入到扰动集合A； 抽取密文的方式为： 利用所述散列函 数集合中的每一个散列函数对所遍历 到的元素计算散列值， 按照所计算的散列值从布隆过 滤器中对应的位置抽取密文； p∈[0,1]。 8.如权利要求6或7 所述的隐私保护集 合的交集计算方法， 其特 征在于， 还 包括： 在所述小数据方， 对所述第二交集的大小和元素位置进行重新设置， 使所述第二交集 的大小与所述第一交集相同， 且所述二交集中与所述第一交集相对应的元素在两个集合中 的位置一 致， 从而实现样本对齐。 9.一种隐私保护集合的交集基数计算系统， 其特征在于， 包括： 大数据端和小数据端； 所述大数据端包括加密模块和基数计算模块； 所述小数据端包括扰动模块； 所述加密模块， 用于在大数据 方构造布隆过滤器， 并将所述大数据 方的样本集合A中的 各元素插入所述布隆过滤器， 利用公钥对所述布隆过滤器加密后， 将加密后的布隆过滤器 连同所述 公钥发送给小 数据方； 所述样 本集合A由所述大数据方所持有的样 本的ID组成； 所 述样本集合A中每个元素在所述布隆过滤器中对应多个插入位置， 所述多个插入位置由预权　利　要　求　书 2/4 页 3 CN 115242371 A 3