(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202210341719.6 (22)申请日 2022.04.02 (71)申请人 哈尔滨工业大 学 （深圳） 地址 518055 广东省深圳市南 山区桃源街 道深圳大 学城哈尔滨工业大 学校区 (72)发明人 郑宜峰　王松磊　 (74)专利代理 机构 深圳市君胜知识产权代理事 务所(普通 合伙) 44268 专利代理师 陈专 (51)Int.Cl. G06F 21/62(2013.01) G06F 21/60(2013.01) G06F 17/16(2006.01) (54)发明名称 一种隐私保护的分布式图数据特征分解方 法及系统 (57)摘要 本发明公开了一种隐私保护的分布式图数 据特征分解方法及系统， 本发明提供的方法中， 被随机采样的持有局部图数据的图节 点， 加密自 身的度信息， 并发送给第一计算终端和第二计算 终端， 第一计算终端和第二计算终端协同地在密 文域计算生成第一加密度分布信息和第二加密 度分布信息， 可以使 得图节点确定自身的度所属 的目标区间， 进而选择合适的采样敏感度采样噪 声， 在真实的图邻接矩阵中添加权值为0虚假的 边， 矩阵三元组的形式实现了矩阵的稀疏表示， 对添加了虚假的边的三元组集合进行加密并将 密文分别发送给第一计算终端和第二计算终端 以进行加密的特征分解， 实现了在保护节点隐私 的前提下， 保留图数据的稀 疏性并且保证了特征 分解的有效性。 权利要求书4页 说明书19页 附图6页 CN 114692200 A 2022.07.01 CN 114692200 A 1.一种隐私保护的分布式图数据特 征分解方法， 其特 征在于， 所述方法包括： 全局图中的目标图节点根据本地局部图数据生成初始集合， 所述初始集合中包括多组 三元组， 每组三元组中包括所述 目标图节点的节点标记、 所述 目标图节点的一个相邻图节 点的节点标记、 以及所述目标图节点和所述相邻图节点的连接边的权 重； 所述目标图节点基于函数秘密共享对所述目标图节点的度进行加密， 得到第 一加密度 信息和第二加密度信息， 将所述第一加密度信息发送给第一计算终端， 将所述第二加密度 信息发送给 所述第二计算终端； 所述第一计算终端和所述第二计算终端根据多个所述目标图节点发送的所述第一加 密度信息和所述第二加密度信息生成全局图数据的第一加密度分布信息和第二加密度分 布信息； 所述目标图节点根据接收到的所述第一加密度分布信息和所述第二加密度分布信息 确定所述目标图节点的度所属的目标区间， 根据所述目标区间的边界信息确定目标采样敏 感度， 根据所述目标采样敏感度从拉普拉斯分布中采样噪声， 根据所述噪声在所述 目标结 合中添加虚假 三元组， 生成目标集 合， 所述虚假 三元组中的权 重值为0； 所述目标图节点基于加性秘密共享对所述目标集合进行加密， 得到第 一加密集合和第 二加密集合， 将所述第一加密集合发送给第一计算终端， 将所述第二加密集合发送给第二 计算终端； 所述第一计算终端和所述第二计算终端根据所述全局图中的各个节点对应的所述第 一加密集 合和所述第二加密集 合， 对所述全局图数据进行 特征分解。 2.根据权利要求1所述的隐私保护的分布式 图数据特征分解方法， 其特征在于， 所述目 标图节点基于函数秘密共享对所述目标图节点的度进行加密之前， 包括： 所述第一计算终端和/或所述第 二计算终端在所述全局图的所有节点中随机选择部分 节点发送度加密请求； 当所述目标图节点接收到所述度加密请求后， 所述目标图节点基于函数秘密共享对所 述目标图节点的度进行加密。 3.根据权利要求1所述的隐私保护的分布式 图数据特征分解方法， 其特征在于， 所述目 标图节点基于函数秘密 共享对所述目标图节点的度进 行加密， 得到第一加密度信息和 第二 加密度信息， 包括： 所述目标图节点获取函数秘密共享中的第一预设算法输出的所述第一加密度信息和 所述第二加密度信息， 其中， 所述第一预设算法的输入中包括所述目标图节点的度。 4.根据权利要求3所述的隐私保护的分布式 图数据特征分解方法， 其特征在于， 所述第 一计算终端和所述第二计算终端根据多个所述目标图节点发送的所述第一加密度信息和 所述第二加密度信息生成全局图数据的第一加密度分布信息和第二加密度分布信息， 包 括： 所述第一计算终端将所述目标图节点的所述第一加密度信息和一个目标度输入至函 数秘密共享中的第二预设算法， 得到所述目标图节点的度与所述目标度之 间的第一加密度 比较信息， 所述第二计算 终端将所述目标图节点的所述第二加密度信息和所述目标度输入 至所述第二预设算法， 得到所述目标图节点的度与所述目标度之间的第二加密度比较信 息；权　利　要　求　书 1/4 页 2 CN 114692200 A 2其中， 当所述目标图节点的度与所述目标度相等时， 所述目标图节点的度与所述目标 度的所述第一加密度比较信息和所述第二加密度比较信息的和为1， 否则为0； 所述第一计算终端获取第 一加密直方图信 息， 所述第 二计算终端获取第 二加密直方图 信息， 所述第一加密直方图信息中包括每个所述 目标度对应的第一加密图节点数量信息， 每个所述第一加密图节点数量信息为一个所述目标度对应的所有所述第一加密度比较信 息的和， 所述第二加密直方图信息中包括每个所述 目标度对应的第二加密图节点数量， 每 个所述第二加密图节点数量信息为一个所述目标度对应的所有所述第二加密度比较信息 的和； 获取多个所述目标图节点的度分别与各个所述目标度之间的所述第一加密度信息作 为第一加密度直方图信息， 所述第二计算终端获取多个所述目标图节点的度分别与各个所 述目标度之间的所述第二加密度信息作为第二加密度直方图信息； 所述第一计算终端和所述第二计算终端根据所述第一加密度直方图信息和所述第二 加密度直方图信息确定所述第一加密度分布信息和所述第二加密度分布信息 。 5.根据权利要求4所述的隐私保护的分布式 图数据特征分解方法， 其特征在于， 所述第 一加密度分布信息和所述第二加密度分布信息中的每一位数值为0或1； 所述第一计算 终端 和所述第二计算终端根据所述第一加密度直方图信息和所述第二加密度直方图信息确定 所述第一加密度分布信息和所述第二加密度分布信息， 包括： 所述第一计算终端和所述第二计算终端根据发送加密度信息的所述目标图节点的数 量和预设的区间数量， 确定每 个区间内的目标节点数量； 所述第一计算终端将所述第一加密度直方图信息中的各个所述第一加密图节点数量 信息按照对应的所述目标度的大小顺序依次加入至第一累加器中， 所述第二计算 终端将所 述第二加密度直方图信息中的各个所述第二加密图节点数量信息按照对应的所述目标度 的大小顺序依次加入至第二累加器中； 每次所述第一加密图节点数量信息和所述第二加密图节点数量信息分别加入至所述 第一累加器和所述第二累加器中后， 所述第一计算终端根据所述第一累加器获取第一加密 比较结果， 根据所述第一加密比较结果生成所述第一加密度分布信息中的新一位数值， 所 述第二计算 终端根据所述第二累加器获取第二加密比较结果， 根据所述第二加密比较结果 生成所述第二加密度分布信息中的新一位数值， 其中， 当所述第一累加器和所述第二累加 器的和不小于所述目标节点数量时， 所述第一加密比较结果和所述第二加密比较结果的异 或门运算结果为 1， 当所述第一累加器和所述第二累加器的和小于所述目标节 点数量时， 所 述第一加密比较结果和所述第二加密比较结果的异或门运 算结果为0； 所述第一计算终端将所述第 一加密度分布信 息中的最新一位数值翻转得到翻转位， 所 述第一计算 终端基于加性秘密 共享计算得到第一秘密 共享份额， 所述第二计算终端基于加 性秘密共享计算得到第二秘密共享份额， 其中， 所述第一秘密共享份额与所述第二秘密共 享份额的和为第一值与第二值的乘积， 所述第一值为所述翻转位和所述第二加密度分布信 息中的最新一位的异或门运算结果， 所述第二值为所述第一累加器和所述第二累加器的 和； 所述第一计算终端将所述第 一累加器的值更新为所述第 一秘密共享份额， 将下一个所 述第一加密图节点数量信息加入至所述第一累加器， 所述第二计算 终端将所述第二累加器权　利　要　求　书 2/4 页 3 CN 114692200 A 3