(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202210367744.1 (22)申请日 2022.04.08 (71)申请人 合肥工业大 学 地址 230009 安徽省合肥市包河区屯溪路 193号 (72)发明人 李萌　高剑博　祝烈煌　 (74)专利代理 机构 安徽省合肥新 安专利代理有 限责任公司 34101 专利代理师 陆丽莉　何梅生 (51)Int.Cl. G06F 16/51(2019.01) G06F 16/53(2019.01) G06F 7/58(2006.01) G06F 21/60(2013.01) G06F 21/62(2013.01)H04L 9/00(2022.01) (54)发明名称 支持k个无序节 点的图加密最短路径 查询方 法与系统 (57)摘要 本发明公开了一种支持k个无序节 点的图加 密最短路径 查询方法与系统， 应用于由一个用户 模块与一个云服务模块构成的环 境； 用户模块处 理原始图数据计算图加密的安全索引， 并根据查 询的k个无序节点生成查询令牌， 将安全索引同 查询令牌上传到云服务模块， 等待查询结果发回 后解密获得最短路径， 否则一直等待查询结果； 云服务模块从用户模块接收安全索引和查询令 牌， 使用查询令牌搜索安全索引并返回经过k个 无序节点的最短路径。 本发明能够保护用户的路 径查询隐私不受不可信云服 务的侵害。 权利要求书4页 说明书9页 附图1页 CN 114707012 A 2022.07.05 CN 114707012 A 1.一种支持k个无序节点的图加密最短路径查询系统， 其特征包括： 用户模块与云服务 模块； 所述用户模块包括： 系统初始化单元、 用户设置模块、 索引生成单元、 令牌生成单元、 结 果解密单元； 所述云服 务模块包括： 索引接收单 元、 令牌接收单 元、 路径搜索单 元； 所述用户模块的系统初始化单元产生伪随机排列函数、 伪随机函数、 随机预言机函数、 抗碰撞的哈希函数并向系统内所有单 元公开； 所述用户模块的用户设置模块获取用户输入的起点、 终点和k个无序节点并发送给所 述用户模块的令牌 生成单元； 所述用户模块的索引生成单元处理自身存储的原始图数据， 并产生密钥、 公钥和私钥， 并使用所述 公钥、 所述伪随机排列函数、 所述伪随机函数、 所述随机预言机函数和所述抗碰 撞的哈希函数加密处理后的图数据， 再由加密后的图数据生成安全索引并发送到云服务模 块的索引接 收单元， 再将所述密钥分别发送到用户模块的令牌生成单元和结果解密单元， 再将所述私钥发送到用户模块的结果 解密单元； 所述云服 务模块的索引接收单 元接收所述 安全索引后， 转发至自身的路径搜索单 元； 所述用户模块的令牌生成单元接收所述密钥， 并根据用户选择的起点、 终点、 k个无序 节点以及所述伪随机排列函数、 所述伪随机函数、 所述抗碰撞的哈希函数产生查询令牌后， 转发至云服 务模块的令牌接收单 元； 所述云服 务模块的令牌接收单 元接收所述 查询令牌后， 转发至自身的路径搜索单 元； 所述云服务模块的路径搜索单元使用所述查询令牌搜索所述安全索引， 若搜索成功， 则向所述用户模块的结果解密单元发送对应的结果数据， 若搜索失败， 则向所述用户模块 的结果解密单元的结果 解密单元发送空字符串； 所述用户模块的结果解密单元若接收所述结果数据， 则使用所述私钥对所述结果数据 进行解密获得最短距离， 再使用所述伪随机排列函数和所述密钥恢复出从起点出发并经过 k个无序节点后到 达终点的最短路径。 2.一种支持k个无序节点的图加密最短路径查询方法， 其特征是应用于由一个用户端 与一个云服 务方所构成的网络环境中， 所述图加密最短路径查询方法是按如下步骤进行： 步骤一、 构建索引： 步骤1.1所述用户端采用基于Paillier的密码学方法构建公钥同态加密体系Ω， 并生 成密钥产生函数Gen、 同态加密函数Enc、 同态 解密函数Dec， 再使用所述密钥产生函数Gen生 成私钥sk， 公钥pk； 所述用户端生成一个伪随机排列函数PRP、 一个伪随机函数PRF、 一个随机预言机函数 H、 一个抗碰撞的哈希函数h以及两个密钥K1,K2； 步骤1.2所述用户端使用Floyd ‑Warshall算法对由节点集合V和边集合ε 的原始图数据 G＝{V, ε}进行计算后获得路径距离集合PD， 再对所述路径距离集合PD进行 随机排列， 并初 始化一个数组A rr； 步骤1.3所述用户端对节点集合V中的第i个节点vi随机产生一个密钥 一个密钥 和一个随机数ri；权　利　要　求　书 1/4 页 2 CN 114707012 A 2以所述第i个节点vi为起点， 对于所述路径距离集合PD中从起点vi出发到终点vj的第 numi条最短路径， 所述用户端使用抗碰撞的哈希函数h对终点vj进行处理， 产生哈希结果h (vj)， 使用公钥pk和同态加密函数Enc对起点vi出发到终点vj的最短距离 进行处理， 获 得加密结果 使用密钥 和伪随机排列函数PRP对起点vi出发到终点vj的最短 路径上的途径点vij进行处理， 获得路径伪随机排列结果 对路径距离集合PD中第 numi+1条最短路径做随机排列， 获得随机排列结果 π(numi+1)； 链接所述哈希结果h(vj)、 加密结果 路径伪随机排列结果 和随机排 列结果 π(numi+1)后产生一个链表结点No； 使用随机预言机函数H对所述密钥 和随机数rj进行处理， 获得随机预言机结果 将所述链表结点No和随机预言机结果 进行异或运算 并 产生数组异或结果A rrij； 最后将数组异或结果A rrij和随机数rj存放在数组A rr的第numi个位置上； 步骤1.4用户端使用伪随机排列函数PRP和密钥K2对第i个节点vi进行处理， 获得节点伪 随机排列结果 再使用伪随机函数PRF和密钥K1对第i个节点vi进行处理， 获得伪随机 结果 对路径序号numi及其相应起点的密钥 与伪随机结果 做异或运算 获得字典异或结果DXi， 其中， ||是字符串连接运 算； 创建一个字典DX用于存 储伪随机排列结果 和字典异或结果DXi； 步骤1.5用户端将数组A rr和字典DX组成安全索引i ndex并发送给云服 务方； 步骤二、 标准令牌 生成： 步骤2.1用户端选 取将要查询的起点 s、 终点d； 并使用伪随机排列函数PRP和密钥K2对起 点s进行处理， 获得起点伪随机排列结果 并创建一个集合q1用于存放起点伪随机排 列结果 步骤2.2用户端使用伪随机函数PRF和密钥K1对起点s进行处理， 获得起点伪随机结果 并创建一个集 合q2用于存放 起点伪随机结果 步骤2.3用户端使用抗碰撞的哈希函数h对终点d进行处理， 获得终点哈希结果h(d)， 并 创建一个集 合q3用于存放终点哈希结果h(d)； 步骤2.4用户端将集合q1、 集合q2和集合q3组成标准查询令牌q， 并将标准查询令牌q发 送给云服 务方； 步骤三、 k个无序节点的令牌 生成： 步骤3.1用户端选取将要查询的起点s、 终点 d， 并从节点集合V中选取k个无序节点{V1, V2,…,Vk}； 其中， Vk表示第k个无序节点； 使用伪随机排列函数P RP和密钥K2对起点s进行处理， 获得起点伪随机排列 结果 再使用伪随机排列函数PRP和密钥K2对k个无序节点进行处理， 获得k个无序节点的伪随机 排列结果 其中， 表示第k个无序节点Vk的伪随机排列结果，权　利　要　求　书 2/4 页 3 CN 114707012 A 3