买专利卖专利找龙图腾，真高效！ 查专利查商标用IPTOP,全免费！专利年费监控用IP管家,真方便！

龙图腾网获悉齐鲁工业大学(山东省科学院);山东省计算中心(国家超级计算济南中心)申请的专利一种满足K跳约束的加密图最短路径查询方法获国家发明授权专利权，本发明授权专利权由国家知识产权局授予，授权公告号为：CN119696907B 。

龙图腾网通过国家知识产权局官网在2025-09-02发布的发明授权授权公告中获悉：该发明授权的专利申请号/专利号为：202411890563.2，技术领域涉及：H04L9/40；该发明授权一种满足K跳约束的加密图最短路径查询方法是由杨明;高雅;吴晓明;唐勇伟;穆超;王鑫;陈振娅;刘臣胜;贺云鹏设计研发完成，并于2024-12-20向国家知识产权局提交的专利申请。

本一种满足K跳约束的加密图最短路径查询方法在说明书摘要公布了：本发明属于保密通信的技术领域，更具体地，涉及一种满足K跳约束的加密图最短路径查询方法。所述方法包括：图数据拥有者生成授权令牌并通过安全信道发送给图数据查询者；图数据查询者加密查询请求并发送给图数据拥有者；图数据拥有者解密查询请求对原始图数据进行处理并加密图数据信息发送给云服务器；云服务器接收到加密的数据处理查询最短路径发送给数据查询用户；图数据查询者接收到查询的结果，利用授权令牌的sk进行解密，得到明文结果。本发明解决了现有技术数据容易泄露，查询效率低下的问题。

本发明授权一种满足K跳约束的加密图最短路径查询方法在权利要求书中公布了：1.一种满足k跳约束的加密图最短路径查询方法，其特征在于，所述方法包括： S1、图数据拥有者生成一个授权令牌，并通过安全信道发送给图数据查询者； （1） 式（1）中，sk是非对称加密算法RSA生成的密钥对sk,pk中的私钥，sk必须保密，只有密钥对的持有者才能知道，用来解密数据；pk是非对称加密算法RSA生成的密钥对sk,pk中的公钥，用于加密查询请求；k1和k2是使用伪随机函数生成两个密钥k1和k2，k1用于加密后续加密路径邻接表，k2用于同态加密过程中加密权值，为填充边的虚拟节点，用来混淆加密； S2、图数据查询者接收到授权令牌之后，将自身的查询请求使用授权令牌中公钥pk进行加密并发送给图数据拥有者； S3、图数据拥有者接收到图数据查询者加密后的查询请求，使用私钥sk进行解密，得到原始的查询请求；然后，图数据拥有者根据解密后的查询请求，在图中构建满足k跳限制的s-t的简单路径，并确定需要发送给云服务器LP与RP邻接表，最后将LP与RP邻接表进行加密并发送给云服务器，具体的步骤包括： S31、图数据拥有者使用sk进行解密查询请求，获取跳跃约束k，起点s以及终点t； S32、根据解密之后的跳跃约束k、起点s和终点t,对原图G进行修剪，生成简化图； S33、对新生成的简化图进行中间点分割，在简化图中，扫描所有节点，确定哪些节点作为中间点vc，每个中间点vc将路径分为两部分，包括从起点s到中间点vc的路径lp和从终点t到中间点vc的路径rp： （2） 对应的将路径索引分为LP和RP邻接表，LP用于存储从起点s到中间点vc的路径，RP用于存储从终点t到中间点vc的路径； LP存储的路径需要满足以下条件： （3） 式（3）中，lenlp表示从起点s到中间点vc的路径lp的长度，Distt[vc]表示从vc到终点t的距离，k表示跳跃约束； RP存储的路径需要满足以下条件： （4） 式（4）中，表示从中间点vc到终点t的路径rp的长度，表示从起点s到中间点vc的距离； 对于每个中间点vc，存储从起点s出发，长度从1到的所有路径，存储从终点t出发，长度从1到的所有路径，LP和RP的邻接表结构表示如下： （5） （6） 式（5）和式（6）中，表示用来存储从s到vc的长度为i的路径的路径集合；表示用来存储从中间点vc到终点t的长度为j的路径的路径集合；此时LP与RP邻接表中，存储着中间点vc以及对应的路径集合； S34、图数据拥有者将加密的邻接表LP和RP发送给云服务器； 所述将LP与RP邻接表进行加密是指，使用哈希函数H对每个遍历到的中间点vc进行加密，将中间点的唯一标识符转换为固定长度的哈希值，得到加密后的中间点标识Hvc；对于路径加密，使用密钥k1对路径中的每个中间点标识进行加密；对于图中边的权值，使用同态加密算法和密钥k2对图中边的权值进行加密，加密后的权值表示为[n]pkp，其中pkp表示使用同态加密算法和密钥k2进行加密后的结果，n表示未加密的权值； S4、云服务器接收到图数据拥有者发送的加密的邻接表；然后，云服务器对收到的邻接表数据对路径信息中的权值进行比较，并将路径信息中权值最小的路径发送给图数据查询者，具体步骤如下： S41、云服务器接收图数据拥有者发送的两个加密邻接表和，云服务器对中的每个中间点vc进行遍历，寻找与中相匹配的中间点，所述相匹配是指哈希函数Hvc的值相同，一旦找到匹配的中间节点，云服务器将中的边信息与中的边信息进行连接形成简单路径；连接操作包括将左右两边的路径合并，并且使用同态加密技术对边信息中的权值进行相加； S42、云服务器将连接后的简单路径以及计算出的权值存储到一个新的邻接表path中，邻接表path包含了从起点s到终点t的简单路径，以及每条路径的总权值； S43、云服务器需要对所有连接后的简单路径进行比较，只保留满足k跳跃约束的路径，并对满足条件的路径中权值的大小进行比较，挑选出权值最小的路径； S44、云服务器将挑选出的权值最小的所有路径信息发送给图数据查询者； S5、图数据查询者接收到查询的结果，利用授权令牌的sk进行解密，得到明文结果。

如需购买、转让、实施、许可或投资类似专利技术，可联系本专利的申请人或专利权人齐鲁工业大学(山东省科学院);山东省计算中心(国家超级计算济南中心)，其通讯地址为：250000 山东省济南市长清区西部新城大学科技园；或者联系龙图腾网官方客服，联系龙图腾网可拨打电话0551-65771310或微信搜索“龙图腾网”。