(19)中华 人民共和国 国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202111559832.3 (22)申请日 2021.12.20 (71)申请人 武汉天喻信息产业股份有限公司 地址 430223 湖北省武汉市东湖新 技术开 发区华工大 学科技园天喻信息 (72)发明人 崔昌　孟庆树　王丽　李云青　 董逢华　 (74)专利代理 机构 北京汇泽知识产权代理有限 公司 11228 代理人 吴静 (51)Int.Cl. H04L 9/06(2006.01) H04L 9/32(2006.01) H04L 9/40(2022.01) (54)发明名称 一种隐私集 合求交的方法和系统 (57)摘要 一种隐私集合求交的方法， 包括： 当离线阶 段时， 服务器对自身数据集R使用布谷鸟哈希算 法进行编号存储， 得到新的数据集R1； 服务器生 成伪随机矩阵T， 并利用一个伪随机函数C， 结合 新的数据集R1得到矩阵U； 服务器与客户端 合作， 基于客户端的选择预设比特长的字符串p以及服 务器矩阵T、 U， 通过不经意传输扩展得到矩阵Q； 当在线阶段时， 服务器对矩阵T的每一行通过哈 希算法计算H(ti)， 并形成一张真值表， 将该真值 表发送给客户端； 客户端对自身每一个数据y通 过哈希算法计算H(qj+C(y)*p),并与真值表H (tj)进行比对。 本发明解决了现有技术在隐私集 合求交中， 在线阶段服务器发送的信息量过大， 在中慢速网络环境中会拖累整体效率的问题。 权利要求书1页 说明书5页 附图1页 CN 114401080 A 2022.04.26 CN 114401080 A 1.一种隐私集 合求交的方法， 其特 征在于， 包括： S100.当离线阶段时， 服务器对自身数据集R使用布谷鸟哈希算法进行编号存储， 得到 新的数据集R 1； S200.服务器生成伪随机矩阵T， 并利用一个伪随机函数C， 结合新的数据 集R1得到矩阵 U； S300.服务器与客户端合作， 基于客户端的选择预设比特长的字符串p以及服务器矩阵 T、 U， 通过不经意传输扩展得到矩阵Q； S400.当在线阶段时， 服务器对矩阵T的每一行通过哈希算法计算H(ti)， 并形成一张真 值表， 将该真值表发送给客户端； S500.客户端对自身每一个数据y通过哈希算法计算H(qj+C(y)*p)， 其中， H是一个h ash 函数， 输出定长， qj是矩阵Q的第j行， C是一个伪随机函数， y是客户端数据， p是客户端的选 择预设比特长 的字符串； 并将H(qj+C(y)*p)与真值表H(tj)进行比对， 若H(qj+C(y)*p)与H (tj)相等， 则认为数据y在客户端与服 务器的交集当中。 2.如权利 要求1所述的一种隐私集合求交的方法， 其特征在于， S100中， 当自身数据集R 为有n个数据时， 通过布谷鸟哈希算法， 新的数据集R1数据扩大为1.2n+s个， 即R＝{r1， r2， ...， rn， ...， r1.2n+s}， 其中， s为布谷鸟哈希算法的特定参数。 3.如权利要求1所述的一种隐私集合求交的方法， 其特征在于， S200中， 随机矩阵T为 1.2n+s行、 k列矩阵， 并且矩阵内元 素为0或1随机分布。 4.如权利 要求1所述的一种隐私集合求交的方法， 其特征在于， S200中， 矩阵U的每一行 ui＝ti+C(ri)， 其中ti表示矩阵T的第i行， ri服务器数据。 5.如权利 要求1所述的一种隐私集合求交的方法， 其特征在于， S200中， 伪随机函数C支 持任意输入， 输出一个满足安全性要求的k比特的字符串。 6.如权利 要求1所述的一种隐私集合求交的方法， 其特征在于， S300中， 矩阵Q的每一行 qi具体为： qi＝ti+C(ri)*p， 其中ti表示矩阵T的第i行， ri服务器数据。 7.如权利要求1所述的一种隐私集合求交的方法， 其特征在于， S400中， 通过哈希算法 计算H(ti),通过计算的H(ti)输出一个定 长的比特串。 8.权利要求1所述的一种隐私集合求交的方法， 其特征在于， S500中， j等于H1(y)， H2 (y)， H3(y)， 1.2n+1， 1.2n+2， ...， 1.2n+s公有3+s个取值， 其中H1， H2， H3是布谷鸟哈希的哈 希函数， 其输出为闭区间[1,1.2n]中的一个整数。 9.一种隐私集合求交的系统， 其特征在于， 包括： 服务器和客户端， 其中： 服务器， 用于 在离线阶段时， 对自身数据集R使用布谷鸟哈希算法进行编号存储， 得到新的数据集R1； 用 于生成伪随机矩阵T， 并利用一个伪随机函数C， 结合新的数据集R1得到矩阵U； 用于与客户 端合作， 基于客户端的选择预设比特长的字符串p以及服务器矩阵T、 U， 通过不经意传输扩 展得到矩阵Q； 还用于在在线阶段时， 对矩阵T的每一行通过 哈希算法计算H(ti)， 并形成一 张真值表， 将该真值表发送给客户端； 客户端， 用于在在线阶段时， 对自身每一个数据y通过哈希算法计算H(qj+C(y)*p)， 其 中， H是一个hash函数， 输出定长， qj是矩阵Q的第j行， C是一个伪随机函数， y是客户端数据， 客户端的选择预设比特长的字符串； 并将H(qj+C(y)*p)与真值表H(tj)进行比对， 若H(qj+C (y)*p)与H(tj)相等， 则认为数据y在客户端与服 务器的交集当中。权　利　要　求　书 1/1 页 2 CN 114401080 A 2一种隐私集合求交的方 法和系统 技术领域 [0001]本发明涉及的是通信领域， 特别涉及一种隐私集 合求交的方法和系统。 背景技术 [0002]目前， 现有技术中提供一种高效批处理不经意伪随机函数在隐私集合求交中的应 用(Effificient  Batched Oblivious  PRF with Applications  to Private Set  Intersection)的方法， 该方法会在离线阶段客户端将自身集合进行布谷鸟哈希编号存储 的基础上， 并与服务器利用不经意传输扩展构造了批量的不经意伪随机函数(batch ‑ OPRF)。 在 线阶段服务器将自身集合经过batch ‑OPRF处理后发送给客户端， 客户端接收信息 并与自身内容比对， 进 而得出双方交集。 [0003]但是现有技术提供的该方法存在明显的问题， 即在线阶段服务器发送的信息量过 大了， 这在中慢速网络环境中会拖累 该方案的整体效率， 目前还未有此类方法来降低该方 案中传输的信息量。 发明内容 [0004]鉴于上述问题， 提出了本发明以便提供一种克服上述问题或者至少部分地解决上 述问题的一种隐私集 合求交的方法。 [0005]为了解决上述 技术问题， 本申请实施例公开了如下技 术方案： [0006]一种隐私集 合求交的方法， 包括： [0007]S100.当离线阶段时， 服务器对 自身数据集R使用布谷鸟哈希算法进行编号存储， 得到新的数据集R 1； [0008]S200.服务器生成伪随机矩阵T， 并利用一个伪随机函数C， 结合新的数据集R1得到 矩阵U； [0009]S300.服务器与客户端合作， 基于客户端的选择预设比特长的字符串p以及服务器 矩阵T、 U， 通过不经意传输扩展得到矩阵Q； [0010]S400.当在线阶段 时， 服务器对矩阵T的每一行通过哈希算法计算H(ti)， 并形成一 张真值表， 将该真值表发送给客户端； [0011]S500.客户端对自身每一个数据y通过哈希算法计算H(qj+C(y)*p)， 其中， H是一个 hash函数， 输出定长， qj是矩阵Q的第j行， C是一个伪随机函数， y是客户端数据， p是客户端 的选择预设比特长的字符串； 并将H(qj+C(y)*p)与真值表H(tj)进行比对， 若H(qj+C(y)*p) 与H(tj)相等， 则认为数据y在客户端与服 务器的交集当中。 [0012]进一步地， S100中， 当自身数据集R为有n个数据时， 通过布谷鸟哈希算法， 新的数 据集R1数据扩大为1.2n+s个， 即R＝{r1， r2， ...， rn， ...， r1.2n+s}， 其中， s布谷鸟哈希算法为 的特定参数。 [0013]进一步地， S200中， 随机矩阵T为1.2n+s行、 k列矩阵， 并且矩阵内元素为0或1随机 分布。说　明　书 1/5 页 3 CN 114401080 A 3