(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202210579666.1 (22)申请日 2022.05.26 (71)申请人 哈尔滨工业大 学 （深圳） 地址 518055 广东省深圳市南 山区桃源街 道深圳大 学城哈尔滨工业大 学校区 (72)发明人 郑宜峰　王松磊　 (74)专利代理 机构 深圳市君胜知识产权代理事 务所(普通 合伙) 44268 专利代理师 陈专　李晓凤 (51)Int.Cl. G06F 16/532(2019.01) G06F 21/62(2013.01) (54)发明名称 一种隐私保护的子图匹配方法及系统 (57)摘要 本发明公开了一种隐私保护的子图匹配方 法及系统， 本发明提供的方法中， 将每个属性图 节点本身的节点ID以及属性值编码为独热向量， 同时对每个属性图节点的邻居节点的ID编码为 独热向量并按照不同的节点类型 组成倒排表， 在 倒排表中加入0向量作为虚假节点ID， 将属性图 数据通过复制秘密共享的方式进行加密后分发 至三个计算终端进行计算， 并且还采用属性查询 谓词对应的目标值的独热向量中非0数值的位 置， 生成三对函数秘密共享秘钥对， 组成三个加 密令牌， 分发至三个计算终端， 三个计算终端基 于自身持有的复制秘密共享份额和加密令牌进 行子图匹配， 使得计算终端在不获得关于属性图 以及子图查询隐私信息的情况下， 在加密的属性 图上进行子图匹配 。 权利要求书5页 说明书21页 附图4页 CN 114969406 A 2022.08.30 CN 114969406 A 1.一种隐私保护的子图匹配方法， 其特 征在于， 所述方法包括： 受信终端对属性图数据进行加密， 基于复制秘密共享生成所述属性图中每个属性图节 点的自身信息和邻居节点信息 分别对应的三份复制秘密共享份额， 分别发送 给第一计算 终 端、 第二计算 终端和第三计算 终端， 其中， 目标属性图节点的所述自身信息包括所述目标属 性图节点的节点类型， 所述目标属性图节点的节 点ID对应的独热向量以及所述目标属性图 节点的每种属性的各个属性值对应的独热向量， 所述目标属性图节点的所述邻居节点信息 包括多个倒排表， 所述多个倒排表中的目标倒排表中包括所述目标属性图节点的邻居节点 中具有目标类型 的各个节点的节点ID对应的独热向量以及所述 目标属性图节点的虚假邻 居节点ID对应的独热向量， 所述目标属性图节点的虚假邻居节点ID对应的独热向量为0向 量； 所述受信终端对子图查询数据进行加密， 基于函数秘密共享生成每个子图节点的每个 属性查询谓词对应的加密令牌， 所述加密令牌包括第一加密令牌、 第二加密令牌和第三加 密令牌， 分别发送给所述第一计算终端、 所述第二计算终端和所述第三计算终端， 其中， 所 述第一加密令牌、 所述第二加密令牌和所述第三加密令牌中均包括所述子图节点的节点类 型， 所述子图节点的一个属性以及秘钥组中的两个秘钥， 所述秘钥组中包括三个秘钥对， 每 个所述秘钥对为基于所述子图节点的一个属性查询谓词对应的目标值的独热向量中非0数 值的位置生成的函数秘密共享秘钥对； 所述第一计算终端、 所述第 二计算终端和所述第 三计算终端基于本地持有的属性图节 点的所述自身信息的复制秘密 共享份额， 依次获取每个子图节点的候选节点的复制秘密 共 享份额， 目标子图节点的候选节点的复制秘密共享份额包括候选节 点的节点ID和目标属性 的属性值的复制秘密 共享份额， 其中， 所述目标属性为所述目标子图节点的查询属性， 当所 述目标子图节点没有 前序子图节点时， 所述目标子图节点的候选节点为节点类型与所述目 标子图节点的节点类型相同的所述属 性图节点， 当所述 目标子图节点有前序子图节点时， 所述目标子图节点的候选节点为所述目标子图节点的匹配节点的邻居节点中与所述目标 子图节点的节点类型相同的所述属性图节点； 所述第一计算终端、 所述第 二计算终端和所述第 三计算终端基于本地持有的所述目标 子图节点的候选节点的复制秘密 共享份额和目标子图节点对应的所述加密令牌， 获取每个 候选节点是否为匹配节点的判断结果的复制秘密 共享份额， 匹配节点为所述目标属性的属 性值满足所述目标子图节点的属性 查询谓词的候选节点； 所述第一计算终端、 所述第 二计算终端和所述第 三计算终端基于本地持有的所述目标 子图节点的每个候选节点是否为匹配节点的判断结果的复制秘密 共享份额， 获取目标数据 的复制秘密共享份额， 所述目标数据包括所述目标子图节点的匹配节点的节点ID和属性值 的复制秘密共享份额； 所述第一计算终端、 所述第 二计算终端和所述第 三计算终端基于本地持有的所述目标 子图节点的每个匹配节点的节 点ID的复制秘密 共享份额、 每个候选节点的倒排表的复制秘 密共享份额以及目标匹配节点的节点ID， 获取下一个子图节点的候选节点的复制秘密共享 份额； 所述第一计算终端、 所述第 二计算终端和所述第 三计算终端根据 所述子图查询的公共 结构将本地持有的每个子图节点的所述目标数据重新组织成候选子图， 在所述候选子图中权　利　要　求　书 1/5 页 2 CN 114969406 A 2删除与所述子图查询数据中的结构不完全相同的子图， 分别输出子图匹配结果的复制秘密 共享份额。 2.根据权利要求1所述的隐私保护的子图匹配方法， 其特征在于， 所述受信终端对属性 图数据进行加密之前， 包括： 所述受信终端在各个所述属性图节点中选择若干个节点类型为目标节点类型的多个 第一节点， 任意两个所述第一节点的目标邻居节点的数量的差值在预设范围内， 所述 目标 邻居节点 为节点类型为第一节点类型的邻居节点； 所述受信终端在所述第一节点的所述目标邻居节点中加入至少一个虚假邻居节点ID， 生成所述第一节点的节点类型为所述第一节点类型的所述倒排表； 每个所述第一节点的节点类型为所述第一节点类型的所述倒排表中包括的节点ID的 数量相等。 3.根据权利要求1所述的隐私保护的子 图匹配方法， 其特征在于， 所述第一计算终端、 所述第二计算终端和所述第三计算终端基于本地持有的所述目标子图节点的候选节点的 复制秘密 共享份额和目标子图节点对应的所述加密令牌， 获取每个候选节点是否为匹配节 点的判断结果的复制秘密共享份额， 包括： 所述第一计算终端、 所述第 二计算终端和所述第 三计算终端均在本地执行以下运算以 获取目标候选节点的所述目标属 性的属性值是否满足所述目标子图节点的目标属 性查询 谓词的判断结果的复制秘密共享份额： 基于本地持有的所述目标子图节点的目标属性查询谓词对应的所述加密令牌中的一 个秘钥， 将本地持有的所述目标候选节点的所述目标属性的属性值的一个复制秘密共享份 额中的目标位置序号分别作为 函数秘密共享的输入， 获取函数秘密共享的第一输出； 将所述第一输出和本地持有的所述目标候选节点的所述目标属性的属性值的复制共 享秘密份额中所述 目标位置序号对应的比特进行与运算， 得到第一与运算结果， 对所有的 所述第一与运 算结果进行异或运 算， 得到第一异或运 算结果； 基于本地持有的所述目标子图节点的目标属性查询谓词对应的所述加密令牌中的另 一个秘钥， 将本地持有的所述目标候选节点的所述目标属性的属性值的另一个复制秘密 共 享份额中的所述目标位置序号分别作为函数秘密 共享的输入， 获取函数秘密 共享的第二输 出； 将所述第二输出和本地持有的所述目标候选节点的所述目标属性的属性值的复制共 享秘密份额中所述 目标位置序号对应的比特进行与运算， 得到第二与运算结果， 对所有的 所述第二与运 算结果进行异或运 算， 得到第二异或运 算结果； 所述第一异或运算结果和所述第二异或运算结果的异或运算结果为所述目标候选节 点是否为匹配节点的判断结果的判断结果的一个加性秘密 共享份额， 基于所述第一异或运 算结果和所述第二异或运算结果得到所述目标候选节点的所述目标属 性的属性值是否满 足所述目标子图节点的目标属性 查询谓词的判断结果的复制秘密共享份额； 所述第一计算终端、 所述第 二计算终端和所述第 三计算终端根据自身持有的所述目标 候选节点的所述目标属 性的属性值是否满足所述目标子图节点的目标属 性查询谓词的判 断结果的复制秘密共享份额获取所述目标候选节点是否为所述目标子图节点的匹配节点 的判断结果的复制秘密共享份额。权　利　要　求　书 2/5 页 3 CN 114969406 A 3