(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202211051296.0 (22)申请日 2022.08.30 (71)申请人 青岛大学 地址 266000 山东省青岛市崂山区香港东 路7号 (72)发明人 于佳　丛林浩　郝蓉　 (74)专利代理 机构 北京华仁联合知识产权代理 有限公司 1 1588 专利代理师 周明新 (51)Int.Cl. G06F 16/903(2019.01) G06F 16/901(2019.01) G06F 16/23(2019.01) G06F 21/60(2013.01) G06F 21/62(2013.01)G06K 9/62(2022.01) (54)发明名称 一种支持数据库动态更新的隐私保护子图 同构查询方法 (57)摘要 本发明公开了一种支持数据库动态更新的 隐私保护子图同构查询方法， 包括： 获取待查询 图形的第一图形特征与图数据库的第二图形特 征， 基于所述第二图形特征建立树状索引， 利用 安全特征向量匹配方法对所述树状索引进行加 密， 获得密文下的匹配查询。 本发明通过采用树 状索引， 显著提高了过滤阶段的速度； 采用Hash 映射的方式决定特征在特征向量上的位置， 更加 充分的利用了特征向量的每一位， 提高了过滤效 果。 本文所提出的查询方法可以支持数据库频繁 更新， 加密索引可以随着数据库的更新快速更 新。 权利要求书2页 说明书7页 附图2页 CN 115408578 A 2022.11.29 CN 115408578 A 1.一种支持数据库动态更新的隐私保护子图同构查询方法， 其特 征在于， 包括： 获取待查询图形的第 一图形特征与图数据库的第 二图形特征， 基于所述第 二图形特征 建立树状索引， 利用安全特征向量匹配方法对所述树状索引进行加密， 获得密文下 的匹配 查询； 基于所述密文下的匹配查询与所述待查询图形的第 一图形特征进行子图同构查询， 获 得查询结果。 2.根据权利要求1所述的支持数据库动态更新的隐私保护子图同构查询方法， 其特征 在于， 利用安全特征向量匹配方法对所述树状索引进行加密， 获得密文下 的匹配查询的过 程包括， 对所述图数据库进行加密获得加密数据库； 提取所述图数据库的第 二图形特征生成第 二特征向量， 基于所述第 二特征向量建立索 引， 对所述索引进行加密获得加密 索引； 将所述加密数据库 与所述加密 索引上传至云服 务器， 获得密文下的匹配查询。 3.根据权利要求2所述的支持数据库动态更新的隐私保护子图同构查询方法， 其特征 在于， 提取所述图数据库的第二图形特征生成第二特征向量， 基于所述第二特征向量建立 索引， 对所述索引进行加密获得加密 索引的过程包括， 为所述图数据库中的每个数据图生成一个n位的全0的特征向量； 利用枚举算法， 提取 所述数据图中小于预设阈值的子树和循环作为第二图形特征； 对所述第二图形特征进 行编 码并利用hash算法将所述第二图形 特征映射到特 征向量上， 获得第二特 征向量； 根据K‑means聚类算法和所述第二特征向量对所述数据图进行分组后建立查询索引 树； 对所述 查询索引树每 个节点的节点向量和特 征向量分别进行加密获得密文索引树。 4.根据权利要求3所述的支持数据库动态更新的隐私保护子图同构查询方法， 其特征 在于， 对所述查询索引树中节点的特征向量进行加密的过程包括， 将节点的特征向量中的1， 0分别进行替换， 获得第一替换特征向量； 对所述第一替换特征向量进行拆分， 获得第一拆 分向量、 第二拆分向量； 通过可逆矩阵对所述第一拆分向量、 第二拆分向量进行加密， 获得 加密特征向量存 储于密文索引的节点中。 5.根据权利要求2所述的支持数据库动态更新的隐私保护子图同构查询方法， 其特征 在于， 对所述索引进行加密获得加密 索引的过程中还 包括生成加密秘钥； 所述加密秘钥包括第一部分M1、 第二部分M2、 第三部分S、 第四部分ρ； 所述第一部分M1、 第二部分M2为随机的n阶可逆矩阵； 所述第三部分S为 一个随机的n阶0， 1向量； 所述第四部分ρ 为 一个n阶随机向量。 6.根据权利要求1所述的支持数据库动态更新的隐私保护子图同构查询方法， 其特征 在于， 基于所述密文下的匹配查询与所述待查询图形的第 一图形特征进行子图同构查询， 获 得查询结果的过程包括， 基于待查询图形的第 一图形特征生成第 一特征向量， 根据 所述第一特征向量生成查询权　利　要　求　书 1/2 页 2 CN 115408578 A 2陷门并将所述查询陷门发送至云服务器， 云服务器运行查询算法在加密索引中进行查询， 获得初始查询结果； 基于对应的验证算法对所述初始查询结果进行验证， 获得目标查询结果。 7.根据权利要求6所述的支持数据库动态更新的隐私保护子图同构查询方法， 其特征 在于， 根据所述第一特征向量生成查询陷门的过程包括， 将第一特征向量中的1， 0分别进行 随机值替换， 获得第二替换特征向量； 对所述第二替换特征向量进 行拆分， 获得第三拆分向 量、 第四拆分向量； 基于第二特 征向量与第三拆分向量、 第四拆分向量获得第五拆分向量； 根据第三拆分向量、 第四拆分向量、 第五拆分向量 生成所述 查询陷门。 8.根据权利要求6所述的支持数据库动态更新的隐私保护子图同构查询方法， 其特征 在于， 云服务器运行查询算法在加密 索引中进行查询， 获得初始查询结果的过程包括， 云服务器判断节点与查询陷门是否匹配， 若匹配节点是叶子节点 时， 对所述叶子节点下的特征向量表中的特征向量进行逐个匹 配， 将匹配通过的放入候选集； 若匹配失败， 放弃对子节点的搜索直至找到所有匹配的叶子 节点， 获得初始查询结果。 9.根据权利要求1所述的支持数据库动态更新的隐私保护子图同构查询方法， 其特征 在于， 所述查询方法还 包括在获得查询结果后对图数据库和索引的动态更新； 所述图数据库和索引的动态更新过程包括， 将待更新数据包发送给云服务器进行图数 据库更新； 基于待 更新数据包， 云服务器执行定位算法定位需要 更新的索引节 点； 判断所述 需要更新的索引节 点是否需要修改节 点向量， 若 是， 进行修改， 云服务器完成索引与图数据 库的同步更新； 否则， 云服务器将需要修改的节 点发送给数据所有者， 数据所有者将需要修 改的节点解密后对节点向量进行修改， 加密获得新的节点并发送至云服务器， 完成索引与 图数据库的同步更新。 10.根据权利要求9所述的支持数据库动态更新的隐私保护 子图同构查询方法， 其特征 在于， 所述图数据库和索引的动态更新包括向加密索引中添加新的特征向量、 删除加密索引 中的特征向量、 修改索引中的特 征向量； 所述向加密 索引中添加新的特 征向量的过程包括： 为要添加的新的特征向量生成更新数据包 并发送给云服务器， 云服务器通过查询算法 为新的特征向量选取合适添加的位置； 所述新的特征向量如果能成功匹配到叶子节点， 则 直接向所述叶子节点添加 新的特征向量； 如果无法匹配到叶子节点， 则从所有能匹配的节 点中选取一个离叶子节点最近的索引节点， 将所述新的特征向量添加至相应的叶子节点， 并修改索引节点到相应的叶子节点 这一路径上的所有节点； 所述删除加密 索引中的特 征向量的过程包括， 将需要删除的特征向量的编号写入更新数据包， 并发送给云服务器， 云服务器找到对 应的特征向量并删除。权　利　要　求　书 2/2 页 3 CN 115408578 A 3