一种图上最短路径安全查询方法、装置、系统及存储介质

摘要

本发明公开了一种图上最短路径安全查询方法、装置、系统及计算机可读存储介质，该方法包括接收客户端发送的查询口令信息，查询口令信息为客户端采用预设加密方法对用户输入的目标图像信息、起始顶点信息、终止顶点信息和受限边标签集合进行加密后得到的；依据查询口令信息从预先存储的各个加密图像中找到对应的目标加密图像，获取目标加密图像中加密后的各个顶点、与每个顶点分别对应的各个邻接点；依据加密后的起始顶点信息、终止顶点信息及受限边标签集合，从目标加密图像的各个邻接点中确定出满足受限边标签集合的起始顶点至终止顶点的最短路径及最小距离；本发明能够找到满足受限边标签集合的最短路径及最小距离，更能够满足实际需求。

说明书

技术领域

本发明实施例涉及网络与信息安全服务及知识图谱技术领域，特别是涉及一种图上最短路径安全查询方法、装置、系统及存储介质。

背景技术

知识图谱技术在很多领域都有广泛的应用场景，比如社交网络、生物医学、工业互联网等，其中，社交关系图谱分析主要基于对象的互联网、通讯网络等虚拟身份信息和动态关联信息进行分析，并在这些数据之间建立起关联关系图谱，通过知识图谱的关系推断、隐含关系挖掘以及虚实身份映射等，分析出目标对象的社交网络图谱关系，并展示目标对象不同的社会渠道的核心关系圈。知识图谱中的数据都是以顶点和边作为主要元素构成的图数据，而最短路径查询是针对图数据计算的一个很重要的基本问题。

传统的支持最短路径(距离)查询的图加密算法考虑的是边上带有权重的情况下的最短路径(距离)查询，通过利用不同的算法可以获得精确的或者近似的最短路径(距离)。但是，现有的方法没有考虑边上带有标签等属性信息的情况，而在现实中产生的图数据里的边往往是与属性相关联的、具有某种意义，因此现有技术中的最短路径查询方法难以满足实际需求。

鉴于此，如何提供一种解决上述技术问题的图上最短路径安全查询方法、装置、系统及计算机存储介质成为本领域技术人员需要解决的技术问题。

发明内容

本发明实施例的目的是提供一种图上最短路径安全查询方法、装置、系统及计算机存储介质，在使用过程能够通过对边的标签进行限制，找到满足受限边标签集合的最短路径及最小距离，得到的最短路径更能够满足实际需求。

为解决上述技术问题，本发明实施例提供了一种图上最短路径安全查询方法，包括：

接收客户端发送的查询口令信息；其中，所述查询口令信息为所述客户端采用预设加密方法对用户输入的目标图像信息、起始顶点信息、终止顶点信息和受限边标签集合进行加密后得到的；

依据所述查询口令信息从预先存储的各个加密图像中找到对应的目标加密图像；

获取所述目标加密图像中加密后的各个顶点、与每个所述顶点分别对应的各个邻接点；

依据加密后的起始顶点信息、终止顶点信息及受限边标签集合，从所述目标加密图像的各个所述邻接点中确定出满足所述受限边标签集合的起始顶点至终止顶点的最短路径及最小距离。

可选的，所述依据加密后的起始顶点信息、终止顶点信息及受限边标签集合，从所述目标加密图像的各个邻接点中确定出满足的起始顶点至终止顶点的最短路径及最小距离的过程为：

将起始顶点作为中心点；

从所述目标加密图像中找出与所述中心点对应的各个邻接点；

对所述中心点的各个邻接点进行遍历，筛选出边的标签满足所述受限边标签集合的各个目标邻接点；

将各个所述目标邻接点中当前没有在最小堆H中的目标邻接点添加至所述最小堆H中；其中，所述最小堆H为预先建立的；

计算出所述最小堆H中各个所述目标邻接点分别至所述起始顶点的最小距离，从各个所述最小距离中选择出最小值距离作为最新距离以更新距离字典中的当前最小距离，其中，所述距离字典为预先建立的；

将所述中心点的信息作为前驱信息存储至预先建立的前驱信息字典中；

将与所述当前最小距离对应的目标邻接点作为所述中心点，并返回从所述目标加密图像中找出与所述中心点对应的各个邻接点的步骤，直至确定出与所述当前最小距离对应的邻接点为终止顶点后得到最小距离，并根据所述前驱信息字典中的各个前驱信息得到最短路径。

可选的，所述将各个所述目标邻接点中当前没有在最小堆H中的目标邻接点添加至所述最小堆H中的过程为：

将各个所述目标邻接点中当前没有在最小堆H中的目标邻接点的伪随机置换值及所述伪随机置换值的关键字添加至预先建立的最小堆H中。

可选的，所述计算出所述最小堆H中的各个所述目标邻接点分别至所述起始顶点的最小距离的过程为：

针对每个所述目标邻接点，计算出所述目标邻接点直接至所述起始顶点的第一距离；

计算出所述目标邻接点通过所述中心点至所述起始顶点的第二距离；

将所述第一距离和所述第二距离中的较小距离作为所述目标邻接点至所述起始顶点的最小距离。

可选的，所述加密图像的存储过程为：

接收所述客户端发送的加密图像，并对所述加密图像进行存储；其中，所述加密图像为所述客户端采用所述预设加密方法对用户输入的待加密图像进行加密后得到的。

可选的，所述客户端采用所述预设加密方法对用户输入的待加密图像进行加密的过程为：

所述客户端接收用户输入的待加密图像，并得到与所述待加密图像中的每个顶点分别对应的邻接表；所述邻接表中存储有多个三元组，所述三元组包括邻接点、边的权重和边的标签，其中，所述边为顶点与邻接点之间的边，每个所述顶点分别对应一个私钥；

针对每个所述邻接表中的每个所述三元组，采用paillier加密算法对边的权值进行加密，采用伪随机置换对所述边的标签进行加密，采用与所述邻接表对应的私钥对所述邻接点进行加密，得到与所述三元组对应的加密数据；

将所述加密数据添加至预先建立的第一数组中；

对所述邻接表中第一个邻接点的地址及所述邻接表的私钥进行盲化后得到盲化结果，并将所述盲化结果添加至预先建立的第一字典中，直至每个所述邻接表中的所有三元组均加密完成，得到基于所述第一数组和所述第一字典的加密图像。

可选的，所述对所述邻接表中第一个邻接点的地址及所述邻接表的私钥进行盲化后得到盲化结果的过程为：

将所述邻接表中第一个邻接点的地址和所述邻接表的私钥作为整体与对应顶点的伪随机函数值进行异或，得到异或结果；

将所述异或结果作为盲化结果。

本发明实施例还相应的提供了一种图上最短路径安全查询装置，包括：

接收模块，用于接收客户端发送的查询口令信息；其中，所述查询口令信息为所述客户端采用预设加密方法对用户输入的目标图像信息、起始顶点信息、终止顶点信息和受限边标签集合进行加密后得到的；

查找模块，用于依据所述查询口令信息从预先存储的各个加密图像中找到对应的目标加密图像；

获取模块，用于获取所述目标加密图像中加密后的各个顶点、与每个所述顶点分别对应的各个邻接点；

筛选模块，用于依据加密后的起始顶点信息、终止顶点信息及受限边标签集合，从所述目标加密图像的各个所述邻接点中确定出满足所述受限边标签集合的起始顶点至终止顶点的最短路径及最小距离。

本发明实施例还提供了一种图上最短路径安全查询系统，包括：

存储器，用于存储计算机程序；

处理器，用于执行所述计算机程序时实现如上述所述图上最短路径安全查询方法的步骤。

本发明实施例还提供了一种计算机可读存储介质，所述计算机可读存储介质上存储有计算机程序，所述计算机程序被处理器执行时实现如上述所述图上最短路径安全查询方法的步骤。

本发明实施例提供了一种图上最短路径安全查询方法、装置、系统及计算机可读存储介质，该方法包括：接收客户端发送的查询口令信息，其中，查询口令信息为客户端采用预设加密方法对用户输入的目标图像信息、起始顶点信息、终止顶点信息和受限边标签集合进行加密后得到的；然后依据查询口令信息从预先存储的各个加密图像中找到对应的目标加密图像，并获取目标加密图像中加密后的各个顶点、与每个顶点分别对应的各个邻接点；依据加密后的起始顶点信息、终止顶点信息及受限边标签集合，然后从目标加密图像的各个邻接点中确定出满足受限边标签集合的起始顶点至终止顶点的最短路径及最小距离；本发明能够通过对边的标签进行限制，找到满足受限边标签集合的最短路径及最小距离，得到的最短路径更能够满足实际需求。

附图说明

为了更清楚地说明本发明实施例中的技术方案，下面将对现有技术和实施例中所需要使用的附图作简单地介绍，显而易见地，下面描述中的附图仅仅是本发明的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据这些附图获得其他的附图。

图1为本发明实施例提供的一种图上最短路径安全查询方法的流程示意图；

图2为本发明实施例提供的一种图上最短路径安全查询装置的结构示意图。

具体实施方式

本发明实施例提供了一种图上最短路径安全查询方法、装置、系统及计算机存储介质，在使用过程能够通过对边的标签进行限制，找到满足受限边标签集合的最短路径及最小距离，得到的最短路径更能够满足实际需求。

为使本发明实施例的目的、技术方案和优点更加清楚，下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。

请参照图1，图1为本发明实施例提供的一种图上最短路径安全查询方法的流程示意图。该方法包括：

S110：接收客户端发送的查询口令信息；其中，查询口令信息为客户端采用预设加密方法对用户输入的目标图像信息、起始顶点信息、终止顶点信息和受限边标签集合进行加密后得到的；

具体的，本发明实施例可以应用在云服务器，其中，用户在需要对加密图像查询两个顶点之间的最短路径时，可以通过客户端输入目标图像信息、起始顶点信息、终止顶点信息和受限边标签集合，然后客户端采用预设加密方法对目标图像信息、起始顶点信息、终止顶点信息和受限边标签集合进行加密，得到查询口令信息，并将该查询口令信息发送至云服务器，具体的查询口令信息可以包括加密后的起始顶点信息、终止顶点信息及受限边标签集合，还可以包括目标图像信息，其中目标图像信息可以为目标图像的标识码或名称等信息。例如，用户需要查询目标图像中的顶点s至顶点t之间的最短路径和距离，受限边标签集合C＝{a

S120：依据查询口令信息从预先存储的各个加密图像中找到对应的目标加密图像；

具体的，可以根据查询口令中加密后的目标图像信息从预先存储的各个加密图像中找到对应的目标加密图像，也即用户需要查询该目标加密图像中的顶点s至顶点t之间的最短路径及距离。

其中，预先对加密图像进行的存储过程具体可以为：

接收客户端发送的加密图像，并对加密图像进行存储；其中，加密图像为客户端采用预设加密方法对用户输入的待加密图像进行加密后得到的。

也即，客户端接收到用户输入的待加密图像后，采用预设加密方法对所述待加密图像进行加密，然后将加密图像发送至云服务器，云服务器接收到加密图像后将其存储。

进一步的，客户端采用预设加密方法对用户输入的待加密图像进行加密的过程为：

客户端接收用户输入的待加密图像，并得到与待加密图像中的每个顶点分别对应的邻接表；邻接表中存储有多个三元组，三元组包括邻接点、边的权重和边的标签，其中，边为顶点与邻接点之间的边，每个顶点分别对应一个私钥；

针对每个邻接表中的每个三元组，采用paillier加密算法对边的权值进行加密，采用伪随机置换对边的标签进行加密，采用与邻接表对应的私钥对邻接点进行加密，得到与三元组对应的加密数据；

将加密数据添加至预先建立的第一数组中；

对邻接表中第一个邻接点的地址及邻接表的私钥进行盲化后得到盲化结果，并将盲化结果添加至预先建立的第一字典中，直至每个邻接表中的所有三元组均加密完成，得到基于第一数组和第一字典的加密图像。

其中，对邻接表中第一个邻接点的地址及邻接表的私钥进行盲化后得到盲化结果的过程可以为：

将邻接表中第一个邻接点的地址和邻接表的私钥作为整体与对应顶点的伪随机函数值进行异或，得到异或结果，并将异或结果作为盲化结果。

需要说明的是，输入为G＝(V,E,Δ)和sk＝(k

具体的，可以假设待加密图像的顶点数为n，也即|V|＝n，边数为m，也即|E|＝m，可以预先初始化一个大小为m第一数组A

对待加密图像上的每个顶点u∈V，执行下列操作：

计算一个用于加密顶点u对应的邻接表中每个节点信息的私钥K

c

S130：获取目标加密图像中加密后的各个顶点、与每个顶点分别对应的各个邻接点；

S140：依据加密后的起始顶点信息、终止顶点信息及受限边标签集合，从目标加密图像的各个邻接点中确定出满足受限边标签集合的起始顶点至终止顶点的最短路径及最小距离。

也即，本发明中可以根据加密后的起始顶点信息和终止顶点信息从加密图像的各个顶点和与每个顶点对应的各个邻接点中找出满足受限边标签集合的最短路径以及相应的最小距离，其中，该最短路径上的各个邻接点的边的标签均满足该受限边标签集合，使得到的最短路径及距离更加满足实际需求。

进一步的，上述S140中依据加密后的起始顶点信息、终止顶点信息及受限边标签集合，从目标加密图像的各个邻接点中确定出满足的起始顶点至终止顶点的最短路径及最小距离的过程，具体可以为：

将起始顶点作为中心点；

从目标加密图像中找出与中心点对应的各个邻接点；

对中心点的各个邻接点进行遍历，筛选出边的标签满足受限边标签集合的各个目标邻接点；

将各个目标邻接点中当前没有在最小堆H中的目标邻接点添加至最小堆H中；其中，最小堆H为预先建立的；也即，从最小堆H中当前已有的各个邻接点中确定出各个所述目标邻接点中哪些邻接点已存在于最小堆H中，这些邻接点就不需要再次添加至最小堆H中，只需要将最小堆H中没有的目标邻接点添加至最小堆H中即可。

计算出最小堆H中各个目标邻接点分别至起始顶点的最小距离，从各个最小距离中选择出最小值距离作为最新距离以更新距离字典中的当前最小距离，其中，距离字典为预先建立的；也即，计算出这些各个目标邻接点分别至起始顶点的最小距离，其中，针对每个目标邻接点在计算其至起始顶点的最小距离时，可以采用以下方法：

先计算出目标邻接点直接至起始顶点的第一距离以及目标邻接点通过中心点至起始顶点的第二距离，然后将第一距离和第二距离中的较小距离作为目标邻接点至起始顶点的最小距离。

将中心点的信息作为前驱信息存储至预先建立的前驱信息字典中；

将与最新距离对应的目标邻接点作为中心点，并返回从目标加密图像中找出与中心点对应的各个邻接点的步骤，直至确定出与最新距离对应的邻接点为终止顶点后得到最小距离，并根据前驱信息字典中的各个前驱信息得到最短路径。

需要说明的是，在每次确定出新的最新距离后，将与该最新距离对应的目标邻接点作为中心点，也即将该目标邻接点作为新的顶点，然后从该新的顶点的各个邻接点中再筛选出边的标签满足受限边标签集合的各个新的目标邻接点，然后再将这些新的目标邻接点中没有在最小堆H中的新的目标邻接点添加至最小堆H中，进一步计算出各个新的目标邻接点分别至起始顶点的最小距离，然后从这些最小距离中选择出最小值距离，采用该最小值距离作为最小距离更新距离字典中的当前最小距离，同时将该中心点的信息添加至预先建立的前驱信息字典中，然后再将对应的新的目标邻接点作为中心点，并继续对下一个中心点的各个邻接点进行筛选，直至找到的最新距离对应的邻接点为终止顶点，此时结束遍历，并将距离字典中的当前最小距离作为最小距离，然后根据前驱信息字典中的各个前驱信息进一步确定出起始顶点至终止顶点之间的最短路径，也即该最短路径为从起始顶点起依次经过前驱信息字典中的各个前驱信息分别对应的邻接点到达终止顶点的路径。其中，上述将各个目标邻接点中当前没有在最小堆H中的目标邻接点添加至最小堆H中的过程具体可以为：

将各个目标邻接点中当前没有在最小堆H中的目标邻接点的伪随机置换值及伪随机置换值的关键字添加至预先建立的最小堆H中。

最小堆H

在实际应用中，具体可以采用以下操作：

输入为：

则可以预先初始化一个最小堆H←Make-Heap()，初始化两个字典，分别为距离字典ε和前驱信息字典path。设τ

从最小堆H当前存储的各个邻接点中抽取出距离最小的元素<α,key(α)>:＝Extract-MIN(H)，计算

返回前驱信息字典path以及当前最小距离key(α)，前驱信息字典path中保存着每一个顶点的前驱顶点的信息，也即存储着每个中心点的信息，通过回溯查找即可得到对应的密文下的最小路径，key(α)即为对应的密文下的当前最小距离，然后可以将最小路径及距离返回至客户端，客户端收到云服务器返回的结果后使用自己的私钥(与客户端加密图像对应的解密方法)解密即可得到明文下对应的最短路径和距离。

可见，该方法通过接收客户端发送的查询口令信息，其中，查询口令信息为客户端采用预设加密方法对用户输入的目标图像信息、起始顶点信息、终止顶点信息和受限边标签集合进行加密后得到的；然后依据查询口令信息从预先存储的各个加密图像中找到对应的目标加密图像，并获取目标加密图像中加密后的各个顶点、与每个顶点分别对应的各个邻接点；依据加密后的起始顶点信息、终止顶点信息及受限边标签集合，然后从目标加密图像的各个邻接点中确定出满足受限边标签集合的起始顶点至终止顶点的最短路径及最小距离；本发明能够通过对边的标签进行限制，找到满足受限边标签集合的最短路径及最小距离，得到的最短路径更能够满足实际需求。

在上述实施例的基础上，本发明实施例还相应的提供了一种图上最短路径安全查询装置，具体请参照图2。该装置包括：

接收模块21，用于接收客户端发送的查询口令信息；其中，查询口令信息为客户端采用预设加密方法对用户输入的目标图像信息、起始顶点信息、终止顶点信息和受限边标签集合进行加密后得到的；

查找模块22，用于依据查询口令信息从预先存储的各个加密图像中找到对应的目标加密图像；

获取模块23，用于获取目标加密图像中加密后的各个顶点、与每个顶点分别对应的各个邻接点；

筛选模块24，用于依据加密后的起始顶点信息、终止顶点信息及受限边标签集合，从目标加密图像的各个邻接点中确定出满足受限边标签集合的起始顶点至终止顶点的最短路径及最小距离。

需要说明的是，本发明实施例中提供的图上最短路径安全查询装置具有与上述实施例中所提供的图上最短路径安全查询方法相同的有益效果，并且对于本发明实施例中所涉及到的图上最短路径安全查询方法的具体介绍请参照上述实施例，本发明在此不再赘述。

在上述实施例的基础上，本发明实施例还提供了一种图上最短路径安全查询系统，包括：

存储器，用于存储计算机程序；

处理器，用于执行计算机程序时实现如上述图上最短路径安全查询方法的步骤。

例如，本实施例中的处理器还用于实现接收客户端发送的查询口令信息，其中，查询口令信息为客户端采用预设加密方法对用户输入的目标图像信息、起始顶点信息、终止顶点信息和受限边标签集合进行加密后得到的；然后依据查询口令信息从预先存储的各个加密图像中找到对应的目标加密图像，并获取目标加密图像中加密后的各个顶点、与每个顶点分别对应的各个邻接点；依据加密后的起始顶点信息、终止顶点信息及受限边标签集合，然后从目标加密图像的各个邻接点中确定出满足受限边标签集合的起始顶点至终止顶点的最短路径及最小距离。

在上述实施例的基础上，本发明实施例还提供了一种计算机可读存储介质，计算机可读存储介质上存储有计算机程序，计算机程序被处理器执行时实现如上述图上最短路径安全查询方法的步骤。

该计算机可读存储介质可以包括：U盘、移动硬盘、只读存储器(Read-OnlyMemory，ROM)、随机存取存储器(Random Access Memory，RAM)、磁碟或者光盘等各种可以存储程序代码的介质。

本说明书中各个实施例采用递进的方式描述，每个实施例重点说明的都是与其他实施例的不同之处，各个实施例之间相同相似部分互相参见即可。对于实施例公开的装置而言，由于其与实施例公开的方法相对应，所以描述的比较简单，相关之处参见方法部分说明即可。

还需要说明的是，在本说明书中，诸如第一和第二等之类的关系术语仅仅用来将一个实体或者操作与另一个实体或操作区分开来，而不一定要求或者暗示这些实体或操作之间存在任何这种实际的关系或者顺序。而且，术语“包括”、“包含”或者其任何其他变体意在涵盖非排他性的包含，从而使得包括一系列要素的过程、方法、物品或者设备不仅包括那些要素，而且还包括没有明确列出的其他要素，或者是还包括为这种过程、方法、物品或者设备所固有的要素。在没有更多限制的情况下，由语句“包括一个……”限定的要素，并不排除在包括所述要素的过程、方法、物品或者设备中还存在另外的相同要素。

对所公开的实施例的上述说明，使本领域专业技术人员能够实现或使用本发明。对这些实施例的多种修改对本领域的专业技术人员来说将是显而易见的，本文中所定义的一般原理可以在不脱离本发明的精神或范围的情况下，在其他实施例中实现。因此，本发明将不会被限制于本文所示的这些实施例，而是要符合与本文所公开的原理和新颖特点相一致的最宽的范围。