(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202210784240.X (22)申请日 2022.07.05 (71)申请人 青岛大学 地址 266100 山东省青岛市崂山区香港东 路7号 (72)发明人 于佳　宋芸娇　郝蓉　 (74)专利代理 机构 北京集佳知识产权代理有限 公司 11227 专利代理师 薛娇 (51)Int.Cl. G06F 16/901(2019.01) G06F 16/903(2019.01) G06F 21/60(2013.01) G06F 21/62(2013.01) (54)发明名称 一种K步可到 达查询方法、 装置及其介质 (57)摘要 本申请公开了一种K步可到达查询方法、 装 置及其介质， 涉及计算机技术领域， 用于查询图 中两节点是否满足K步可到达， 针对目前的K步可 到达方法无法兼顾数据隐私性的问题， 提供了一 种K步可到达查询方法， 通过揭 序加密算法对min 值和post值进行加密， 在保证min值和post值的 隐私性的前提下， 仍可实现两点之间min值和 post值的大小比较； 又通过Paillier同态加密算 法对TLE值进行加密， 同样在保证TLE值隐私性的 前提下， 仍可实现加减法计算； 从而通过由图生 成的BFSI索引， 实现对于 图中两节点之间是否K 步可到达的确定。 在实现K步可到达查询的前提 下， 兼顾了数据的隐私性。 权利要求书2页 说明书11页 附图4页 CN 115033749 A 2022.09.09 CN 115033749 A 1.一种K步可到 达查询方法， 其特 征在于， 包括： 接收并解析查询请求， 以获取第一节点、 第二节点以及约束步数； 根据BFSI索引， 确定所述第一节点和所述第二节点之间是否满足在所述约束步数下可 达， 并生成查询结果； 其中， 所述BFSI索引 包括各节点以及与该节点对应的三元数组， 为预先通过广度遍历 将所述图分成若干颗广度有向树后， 根据所述广度优先树得到； 所述三元数组中的min值和 post值预 先由揭序加密算法进行加密、 TLE值预 先由Paillier同态加密算法进行加密； 返回所述 查询结果。 2.根据权利 要求1所述的K步可到达查询方法， 其特征在于， 根据B FSI索引， 确定所述第 一节点和所述第二节点之间是否满足在所述约束步数 下可达， 并生成查询结果包括： 判断所述第一节点和所述第二节点是否在同一所述广度有向树， 若是， 则根据所述第 一节点和所述第二节点的TLE值确定加密步数， 将所述加密步数作为 查询结果返回。 3.根据权利要求2所述的K步可到达查询方法， 其特征在于， 在所述判断所述第一节点 和所述第二节点是否在同一所述广 度有向树之后， 还 包括： 若否， 则判断所述第一节点以及其孩 子节点是否存在非树 边； 若不存在， 则所述第一节点和所述第二节点之间不可到 达， 返回查询结果； 若存在， 则根据邻 接链表判断所述第 一节点和所述第 二节点的可达性， 若满足， 则根据 所述第一节点和所述第二节点的TLE值确定所述加密步数， 将所述加密步数作为查询结果 返回， 若不满足， 则所述第一节点和所述第二节点之间不可到 达， 并作为 查询结果返回； 其中， 所述邻接链 表包括所述图中不在所述广 度优先树中的边。 4.根据权利要求3所述的K步可到达查询方法， 其特征在于， 所述根据邻接链表判断所 述第一节点和所述第二节点的可达性包括： 判断所述邻接链 表中是否包 含以所述第一节点作为头结点的边； 若包含， 则根据所述第一节点和所述第二节点的TLE值确定所述加密步数包括： 根据所述邻 接链表确定所述第 一节点对应的非树节点， 并根据 所述非树节点和所述第 二节点的TLE值确定所述加密步数。 5.根据权利要求4所述的K步可到达查询方法， 其特征在于， 在所述判断所述邻接链表 中是否包 含以所述第一节点作为头结点的边之后， 还 包括： 若不包含， 则根据所述BFSI索引确定所述第一节点的所有孩 子节点； 判断所述邻接链 表中是否存在以所述孩 子节点为头结点的边； 若存在， 则根据所述第一节点和所述第二节点的TLE值确定所述加密步数包括： 根据所述孩子节点确定对应的非树节点， 并根据所述非树节点和所述第二节点的TLE 值确定所述加密步数， 将所述加密步数作为 查询结果返回。 6.根据权利要求1所述的K步可到达查询方法， 其特征在于， 所述图中的各点通过伪随 机置换函数进行加密。 7.根据权利要求1至6任意一项所述的K步可到达查询方法， 其特征在于， 所述查询请求 还包括陷门。 8.一种K步可到 达查询装置， 其特 征在于， 包括： 解析模块， 用于 接收并解析查询请求， 以获取第一节点、 第二节点以及约束步数；权　利　要　求　书 1/2 页 2 CN 115033749 A 2查询模块， 用于根据BFSI索引， 确定所述第一节点和所述第二节点之间是否满足在所 述约束步数下可达， 并生 成查询结果； 其中， 所述BFSI索引包括各点以及与该点对应的三元 数组， 为预先通过广度遍历将所述图分成若干颗广度有向树后， 根据所述广度优 先树得到； 所述三元数 组中的min值和post值预先由揭序加密算法进行加密、 TLE值预先由Paillier同 态加密算法进行加密； 返回模块， 用于返回所述 查询结果。 9.一种K步可到 达查询装置， 其特 征在于， 包括： 存储器， 用于存 储计算机程序； 处理器， 用于执行所述计算机程序时实现如权利要求1至7任意一项所述的K步可到达 查询方法的步骤。 10.一种计算机可读存储介质， 其特征在于， 所述计算机可读存储介质上存储有计算机 程序， 所述计算机程序被处理器执行时实现如权利要求1至7任意一项所述的K步可到达查 询方法的步骤。权　利　要　求　书 2/2 页 3 CN 115033749 A 3