(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202210361247.0 (22)申请日 2022.04.07 (71)申请人 中南民族大 学 地址 430074 湖北省武汉市洪山区民族大 道182号 申请人 武汉空天软件技 术有限公司 (72)发明人 孟博　张国兴　王德军　李子茂　 (74)专利代理 机构 武汉科皓知识产权代理事务 所(特殊普通 合伙) 42222 专利代理师 肖明洲 (51)Int.Cl. G06F 21/60(2013.01) G06F 21/62(2013.01) (54)发明名称 基于二分裂变的差分隐私直方图发布方法、 系统及设备 (57)摘要 本发明公开了一种基于二分裂变的差分隐 私直方图发布方法、 系统及设备， 方法包括隐私 预算划分， 中间直方图生成， 直方图排序， 二 分裂 变划分直方图， 分组求均值， 生成差分隐私直方 图和直方图发布等步骤； 本发明针对现有直方图 发布技术可用性不高的问题， 提升了分组划分阶 段的准确性， 进而提高了发布数据的可用性并提 升了发布效率， 可保证在对数据去隐私化的同 时， 降低发布数据误差； 使得整个直方图发布过 程更加安全、 高效。 权利要求书2页 说明书6页 附图4页 CN 114780974 A 2022.07.22 CN 114780974 A 1.一种基于二分裂 变的差分隐私直方图发布方法， 其特 征在于， 包括以下步骤： 步骤1： 针对原始直方图数据H{h1,h2,...,hn}， 确定隐私预算ε， 并将ε分为两部分ε1和 ε2， 且 ε1＞ ε2， 其中， n表示 直方图的数量； 步骤2： 对原始直方图数据H{h1,h2,...,hn}添加大小为 ε1的laplace噪声， 生成中间直方 图 步骤3： 将步骤2中生成的中间直方图进行升序排序， 获得排序后的直方图 步骤4： 设置分组数 K并二分裂 变划分直方图； 将步骤3中排序后的直方图视 为一个分组， 遍历出该分组 中所有可能 的二分裂 变划分方案， 选择误差最小的二分裂 变划分方案作为划分结果； 选择该划分结果中误差最大的子分组循环执行步骤4中的遍历及二分裂变划分过程， 直至划分出 K个分组并得到最终划分方案G(G1,G2,...,Gk)； 步骤5： 对划分方案G(G1,G2,...,Gk)求取均值得到 步骤6： 生成差分隐私直方图； 对均值分组 添加大小为 ε2的Laplace噪声 得到分组噪音直方图 对 恢复原有直方 图顺序得到 差分隐私直方图 步骤7： 将经 过去隐私化的差分隐私直方图 进行发布。 2.根据权利要求1所述的基于二分裂变的差分隐私直方图发布方法， 其特征在于， 步骤 4的具体实现包括以下子步骤： 步骤4.1： 设置分组数 K； 步骤4.2： 记二分裂变分组为g{h1,h2,...,hn}， 且g中桶的数量为n， 并将其视为一个分 组； 从分组内的第1个桶后开始分裂， 计算出分裂后的分裂方案的误差error之和， 然后计算 第2个桶后分裂的分裂方案的误差error之和， 直到计算出第n ‑1个桶后的分裂方案的误差 error之和； 其中， 分组的误差 hi表示该分组中的单个序列， 表示该分组的平均 值， 步骤4.3： 挑选最小er ror值对应的分裂方案保存； 步骤4.4： 判断分组数是否达到K； 如果是， 则结束分裂， 并执行下述步骤4.6； 如果否， 则 执行下述步骤4.5； 步骤4.5： 选择 该分裂方案中er ror最大的子分组继续执 行步骤4.2 ‑步骤4.4； 步骤4.6： 保存最终分组方案， 形成直方图分组。 3.一种基于二分裂 变的差分隐私直方图发布系统， 其特 征在于， 包括以下模块： 模块1， 用于针对原始直方图数据H{h1,h2,...,hn}， 确定隐私预算 ε， 并将 ε分为两部分ε1权　利　要　求　书 1/2 页 2 CN 114780974 A 2和 ε2， 且 ε1＞ ε2， 其中， n表示 直方图的数量； 模块2， 用于对原始直方图数据H{h1,h2,...,hn}添加大小为 ε1的laplace噪声， 生成中间 直方图 模块3， 用于将模块2中生成的中间直方图进行升序排序， 获得排序后的直方图 模块4， 用于设置分组数 K并二分裂 变划分直方图； 将模块3中排序后的直方图视 为一个分组， 遍历出该分组 中所有可能 的二分裂 变划分方案， 选择误差最小的二分裂 变划分方案作为划分结果； 选择该划分结果中误差最大的子分组循环执行模块4中的遍历及二分裂变划分过程， 直至划分出 K个分组并得到最终划分方案G(G1,G2,...,Gk)； 模块5， 用于对划分方案G(G1,G2,...,Gk)求取均值得到 模块6， 用于生成差分隐私直方图； 对均值分组 添加大小为ε2的Laplace噪声得到分组 噪音直方图 对 恢复原有直方 图顺序得到 差分隐私直方图 模块7， 用于将经 过去隐私化的差分隐私直方图 进行发布。 4.根据权利要求3所述的基于二分裂变的差分隐私直方图发布系统， 其特征在于， 模块 4包括以下子模块： 模块4.1， 用于设置分组数 K； 模块4.2， 用于记二分裂变分组为g{h1,h2,...,hn}， 且g中桶的数量为n， 并将其视为一 个分组； 从分组内的第1个桶后开始分裂， 计算出分裂后的分裂方案的误差err or之和， 然后 计算第2个桶后分裂的分裂方案的误差error之和， 直到计算出第n ‑1个桶后的分裂方案的 误差error之和； 其中， 分组的误差 hi表示该分组中的单个序列， 表示该分组的平均 值， 模块4.3， 用于挑选最小er ror值对应的分裂方案保存； 模块4.4， 用于判断分组数是否达到K； 如果是， 则结束分裂， 并执行下述模块4.6； 如果 否， 则执行下述模块 4.5； 模块4.5， 用于 选择该分裂方案中er ror最大的子分组继续执 行模块4.2‑模块4.4； 模块4.6， 用于保存最终分组方案， 形成直方图分组。 5.一种基于二分裂 变的差分隐私直方图发布设备， 其特 征在于， 包括： 一个或多个处 理器； 存储装置， 用于存储一个或多个程序， 当所述一个或多个程序被所述一个或多个处理 器执行时， 使得所述一个或多个处理器实现如权利要求 1至2中任一项 所述的基于二分裂变 的差分隐私直方图发布方法。权　利　要　求　书 2/2 页 3 CN 114780974 A 3