支持k个无序节点的图加密最短路径查询方法与系统

1.本发明涉及一种支持k个无序节点的图加密最短路径查询方法与系统，属于隐私保护、云服务以及加密图数据导航技术领域。


背景技术：

2.图形数据库用于各种应用，包括万维网、在线社交网络和通信网络。例如，linkedin有一个由810多万用户组成的社交网络图。这些应用程序有助于高效地查询和分析大规模图形。
3.随着云计算的普及，越来越鼓励用户，包括公司和个人，将其图形数据库外包给远程云服务器来降低本地管理成本。然而，将包含敏感信息的图形数据库外包给不受信任的云服务器不仅会导致用户失去数据控制，还会引发他们的安全担忧。这些担忧促进了安全保障的新发展，其中数据加密是一种简单的方法，但会使数据分析变得复杂。
4.此外，现有的使用数据加密的方案，只支持密态下起点终点最短路径查询，只返回起点终点最短路径上的节点，不支持一个重要的图形操作：寻找在途径k无序节点时起点和终点之间的最短路径。这种操作与现实应用中的一个常见用户需求相呼应。例如，用户在智能手机上打开地图应用程序，(1)找到从起点到目的地的最短路径，(2)该路径必须经过其他三个位置节点，即她的工作场所、特定健身房和特定比萨店。同时，用户对访问这三个地点的顺序没有要求，称之为无序节点。这也带来了新的需求，即支持k个无序节点的最短路径查询：云服务器在不知道用户提供的节点下，返回从起点出发途径k个无序节点到达终点的最短路径。
5.现有技术仅通过图加密的方式支持从起点出发到达终点的单一目标最短路径查询，无法完成在用户指定途径k个无序节点情况下的图加密最短路径查询。


技术实现要素：

6.本发明是为了解决上述现有技术存在的不足之处，提出一种支持k个无序节点的图加密最短路径查询方法与系统，以期能在云上密态图数据查询过程中抵抗不可信数据云存储方的安全威胁，并解决k个无序节点的最短路径查询需求问题，从而保护用户的隐私问题，保证用户的出行路线和需求不被不可信数据云存储方知晓。
7.本发明为达到上述发明目的采用如下技术方案：
8.本发明一种支持k个无序节点的图加密最短路径查询系统的特点包括：用户模块与云服务模块；
9.所述用户模块包括：系统初始化单元、用户设置模块、索引生成单元、令牌生成单元、结果解密单元；
10.所述云服务模块包括：索引接收单元、令牌接收单元、路径搜索单元；
11.所述用户模块的系统初始化单元产生伪随机排列函数、伪随机函数、随机预言机函数、抗碰撞的哈希函数并向系统内所有单元公开；
12.所述用户模块的用户设置模块获取用户输入的起点、终点和k个无序节点并发送给所述用户模块的令牌生成单元；
13.所述用户模块的索引生成单元处理自身存储的原始图数据，并产生密钥、公钥和私钥，并使用所述公钥、所述伪随机排列函数、所述伪随机函数、所述随机预言机函数和所述抗碰撞的哈希函数加密处理后的图数据，再由加密后的图数据生成安全索引并发送到云服务模块的索引接收单元，再将所述密钥分别发送到用户模块的令牌生成单元和结果解密单元，再将所述私钥发送到用户模块的结果解密单元；
14.所述云服务模块的索引接收单元接收所述安全索引后，转发至自身的路径搜索单元；
15.所述用户模块的令牌生成单元接收所述密钥，并根据用户选择的起点、终点、k个无序节点以及所述伪随机排列函数、所述伪随机函数、所述抗碰撞的哈希函数产生查询令牌后，转发至云服务模块的令牌接收单元；
16.所述云服务模块的令牌接收单元接收所述查询令牌后，转发至自身的路径搜索单元；
17.所述云服务模块的路径搜索单元使用所述查询令牌搜索所述安全索引，若搜索成功，则向所述用户模块的结果解密单元发送对应的结果数据，若搜索失败，则向所述用户模块的结果解密单元的结果解密单元发送空字符串；
18.所述用户模块的结果解密单元若接收所述结果数据，则使用所述私钥对所述结果数据进行解密获得最短距离，再使用所述伪随机排列函数和所述密钥恢复出从起点出发并经过k个无序节点后到达终点的最短路径。
19.本发明一种支持k个无序节点的图加密最短路径查询方法的特点是应用于由一个用户端与一个云服务方所构成的网络环境中，所述图加密最短路径查询方法是按如下步骤进行：
20.步骤一、构建索引：
21.步骤1.1所述用户端采用基于paillier的密码学方法构建公钥同态加密体系ω，并生成密钥产生函数gen、同态加密函数enc、同态解密函数dec，再使用所述密钥产生函数gen生成私钥sk，公钥pk；
22.所述用户端生成一个伪随机排列函数prp、一个伪随机函数prf、一个随机预言机函数h、一个抗碰撞的哈希函数h以及两个密钥k1,k2；
23.步骤1.2所述用户端使用floyd-warshall算法对由节点集合v和边集合ε的原始图数据g＝{v,ε}进行计算后获得路径距离集合pd，再对所述路径距离集合pd进行随机排列，并初始化一个数组arr；
24.步骤1.3所述用户端对节点集合v中的第i个节点vi随机产生一个密钥一个密钥和一个随机数ri；
25.以所述第i个节点vi为起点，对于所述路径距离集合pd中从起点vi出发到终点vj的第numi条最短路径，所述用户端使用抗碰撞的哈希函数h对终点vj进行处理，产生哈希结果h(vj)，使用公钥pk和同态加密函数enc对起点vi出发到终点vj的最短距离进行处理，获得加密结果使用密钥和伪随机排列函数prp对起点vi出发到终点vj的最短
路径上的途径点v
ij
进行处理，获得路径伪随机排列结果对路径距离集合pd中第num
i+1
条最短路径做随机排列，获得随机排列结果π(num
i+1
)；
26.链接所述哈希结果h(vj)、加密结果路径伪随机排列结果和随机排列结果π(num
i+1
)后产生一个链表结点no；
27.使用随机预言机函数h对所述密钥和随机数rj进行处理，获得随机预言机结果将所述链表结点no和随机预言机结果进行异或运算并产生数组异或结果arr
ij
；
28.最后将数组异或结果arr
ij
和随机数rj存放在数组arr的第numi个位置上；
29.步骤1.4用户端使用伪随机排列函数prp和密钥k2对第i个节点vi进行处理，获得节点伪随机排列结果再使用伪随机函数prf和密钥k1对第i个节点vi进行处理，获得伪随机结果对路径序号numi及其相应起点的密钥与伪随机结果做异或运算获得字典异或结果dxi，其中，||是字符串连接运算；
30.创建一个字典dx用于存储伪随机排列结果和字典异或结果dxi；
31.步骤1.5用户端将数组arr和字典dx组成安全索引index并发送给云服务方；
32.步骤二、标准令牌生成：
33.步骤2.1用户端选取将要查询的起点s、终点d；并使用伪随机排列函数prp和密钥k2对起点s进行处理，获得起点伪随机排列结果并创建一个集合q1用于存放起点伪随机排列结果
34.步骤2.2用户端使用伪随机函数prf和密钥k1对起点s进行处理，获得起点伪随机结果并创建一个集合q2用于存放起点伪随机结果
35.步骤2.3用户端使用抗碰撞的哈希函数h对终点d进行处理，获得终点哈希结果h(d)，并创建一个集合q3用于存放终点哈希结果h(d)；
36.步骤2.4用户端将集合q1、集合q2和集合q3组成标准查询令牌q，并将标准查询令牌q发送给云服务方；
37.步骤三、k个无序节点的令牌生成：
38.步骤3.1用户端选取将要查询的起点s、终点d，并从节点集合v中选取k个无序节点{v1,v2,
…
,vk}；其中，vk表示第k个无序节点；
39.使用伪随机排列函数prp和密钥k2对起点s进行处理，获得起点伪随机排列结果再使用伪随机排列函数prp和密钥k2对k个无序节点进行处理，获得k个无序节点的伪随机排列结果其中，表示第k个无序节点vk的伪随机排列结果，创建一个集合q
*1
用于存放起点伪随机排列结果和k个无序节点伪随机排列结果
40.步骤3.2用户端使用伪随机函数prf和密钥k1对起点s进行处理，获得起点伪随机
结果再使用伪随机函数prf和密钥k1对k个无序节点进行处理，获得k个无序节点的伪随机结果其中，表示第k个无序节点vk的伪随机结果，创建一个集合q
*2
用于存放起点伪随机结果和k个无序节点伪随机结果
41.步骤3.3用户端使用抗碰撞的哈希函数h对终点d进行处理，获得终点哈希结果h(d)，再使用抗碰撞的哈希函数h对k个无序节点(v1,v2,
…
,vk)进行处理，获得k个无序节点的哈希结果(h(v1),h(v2),
…
,h(vk))，其中，h(vk)表示第k个无序节点vk的哈希结果，创建一个集合q
*3
用于存放终点哈希结果h(d)和k个无序节点哈希结果(h(v1),h(v2),
…
,h(vk))；
42.步骤3.4用户端将集合q
*1
、集合q
*2
和集合q
*3
组成查询令牌q
*
，并将查询令牌q
*
发送给云服务方；
43.步骤四、标准查询处理：
44.步骤4.1云服务方从用户端接收到相应的安全索引index和标准查询令牌q；
45.步骤4.2云服务方使用标准查询令牌q中的集合q1对安全索引index中的字典dx检索，获取字典dx中的元素α＝dx[q1]，并与标准查询令牌q中的集合q2做异或运算，获得异或结果β＝nums||ks；其中，nums表示第s条路径序号，ks表示第s个节点的密钥；
[0046]
步骤4.3云服务方使用结果β中的第s条路径序号nums作为入口获得数组arr[nums]中的随机数rs和数组异或结果arrs，使用随机预言机函数h对异或结果β的第s个节点的密钥ks和随机数rs进行处理，获得随机预言机结果h(ks||rs)，再将数组异或结果arrs与随机预言机结果h(ks||rs)做异或运算，获得标识串其中，hs表示第s个节点的哈希结果，sds表示第s条路径的最短距离，sps表示第s条路径的最短路径，num
s+1
表示第s+1条路径序号；
[0047]
步骤4.4云服务方将标识串xs中的第s个节点的哈希结果hs与标准查询令牌q中的q3比对，如果一致，将标识串xs中的第s条路径的最短距离sds和第s条路径的最短路径sps加入结果集合r；否则，截取标识串xs中的第s+1条路径序号num
s+1
作为下一个入口获得arr[num
s+1
]中的随机数和数组异或结果后，按照步骤4.3的过程顺序执行；如果截取标识串xs中的第s+1条路径序号num
s+1
为null，则将结果集合r置为null；
[0048]
步骤4.5云服务方将结果集合r发送给用户端；
[0049]
步骤五、k个无序节点的查询处理：
[0050]
步骤5.1云服务方从用户端接收到相应的安全索引index和查询令牌q
*
；
[0051]
步骤5.2云服务方创建一个长度为k阶乘的最短路径链表sp和一个长度为k阶乘最短距离链表sd，并初始化sd＝{rsd1,rsd2,
…
,rsd
k！
}＝{1,1,
…
,1}；其中，rsd
k！
表示第k阶乘条路径的最短距离；
[0052]
步骤5.3云服务方对查询令牌q
*
进行k阶乘次查询顺序组合，获得查询顺序组合(pq1,pq2,
…
,pqz,
…
,pq
k！
)；其中，pqz表示第z组查询顺序；
[0053]
步骤5.4云服务方对第z组查询顺序其中，表示由起点s出发到达节点v1的查询，表示由节点v
k-1
出发到达节点vk的查询，表示由节点vk出发到达
终点d的查询；
[0054]
定义并初始化第z个路径链表espz为空，定义并初始化第z个距离链表esdz为1；
[0055]
步骤5.5将作为标准查询处理的输入，按照步骤4的过程，获得结果集合r，并结果集合r中的sds存入距离链表esdz中，将中的无序节点v1的伪随机排列结果插入到路径链表espz中；
[0056]
步骤5.6按照步骤5.5的过程对pqz中的进行处理，从而将第z个路径链表espz插入最短路径链表sp，将第z个距离链表esdz插入最短距离链表sd；
[0057]
步骤5.7云服务方对于查询顺序组合(pq1,pq2,
…
,pq
k！
)中的所有组合按照步骤5.4-步骤5.6的过程进行运算，再将最短路径链表sp和最短距离链表sd加入结果集r
′
，并将结果集r
′
发送给用户端；
[0058]
步骤六、处理查询结果：
[0059]
步骤6.1用户端接收到云服务方发送的结果集r
′
；
[0060]
步骤6.2用户端使用同态解密函数dec和私钥sk解密结果集r
′
，得到最短距离链表sd，从而获得从起点s到终点d的最短距离sd；
[0061]
步骤6.3用户端使用伪随机排列函数prp和起点s的密钥k
*s
解密结果集r
′
，从而得到从起点s到终点d的最短路径sp。
[0062]
与现有技术相比，本发明的有益效果在于：
[0063]
1、本发明中用户根据原始图数据及选定的起点、终点和k个无序节点计算安全索引和查询令牌提交给云服务方。云服务方使用查询令牌搜索安全索引并返回最短路径。通过这种方式解决了包含k个无序节点的最短路径查询需求问题，达到了支持k个无序节点的最短路径查询，有效保护了用户的隐私；
[0064]
2、本发明使用同态加密方法使用户生成安全索引，使得恶意的云服务方无法获知用户的加密图数据等信息，达到了强索引安全性；
[0065]
3、本发明使用伪随机排列函数和伪随机函数方法使用户生成查询令牌，解决了k个无序节点的最短路径查询需求问题，并使恶意的云服务方无法获知用户的选定节点信息以及查询路径的相关信息，达到了强令牌隐私；
[0066]
4、本发明实现了在用户与云服务方中各方上的低计算成本计算操作，实现了各方的较低开销通讯，有效降低了查询响应时间，避免了复杂的交互操作，以本地执行为主，k个无序节点的最短路径查询的准确性并未降低。
附图说明
[0067]
图1是本发明支持k个无序节点的最短路径查询系统的模型图；
[0068]
图2是本发明支持k个无序节点的最短路径查询方法的概览图。
具体实施方式
[0069]
本实施例中，用户模块加密图数据并计算安全索引发送至云服务模块，同时用户模块向云服务模块发出k个无序节点最短路径查询并获得返回结果；
[0070]
本实施例中，一种k个无序节点的最短路径查询系统，如图1所示，包括一个用户模块以及一个云服务模块；
[0071]
以一次导航服务中的云上密态路线查询处理为例，用户模块为对图数据加密并选定起点、终点以及k个无序节点查询路线的用户、云服务模块为第三方平台。用户将自己的起点、终点以及k个无序节点提交给第三方平台，由第三方平台匹配合适的最短路线进行导航；
[0072]
用户模块包括：系统初始化单元、用户设置模块、索引生成单元、令牌生成单元、结果解密单元；
[0073]
云服务模块包括：索引接收单元、令牌接收单元、路径搜索单元；
[0074]
用户模块的系统初始化单元产生伪随机排列函数、伪随机函数、随机预言机函数、抗碰撞的哈希函数并向系统内所有单元公开；
[0075]
用户模块的用户设置模块获取用户输入的起点、终点和k个无序节点并发送给用户模块的令牌生成单元；
[0076]
用户模块的索引生成单元处理自身存储的原始图数据，并产生密钥、公钥和私钥，并使用公钥、伪随机排列函数、伪随机函数、随机预言机函数和抗碰撞的哈希函数加密处理后的图数据，再由加密后的图数据生成安全索引并发送到云服务模块的索引接收单元，再将密钥分别发送到用户模块的令牌生成单元和结果解密单元，再将私钥发送到用户模块的结果解密单元；
[0077]
云服务模块的索引接收单元接收安全索引后，转发至自身的路径搜索单元；
[0078]
用户模块的令牌生成单元接收密钥，并根据用户选择的起点、终点、k个无序节点以及伪随机排列函数、伪随机函数、抗碰撞的哈希函数产生查询令牌后，转发至云服务模块的令牌接收单元；
[0079]
云服务模块的令牌接收单元接收查询令牌后，转发至自身的路径搜索单元；
[0080]
云服务模块的路径搜索单元使用查询令牌搜索安全索引，若搜索成功，则向用户模块的结果解密单元发送对应的结果数据，若搜索失败，则向用户模块的结果解密单元的结果解密单元发送空字符串；
[0081]
用户模块的结果解密单元若接收结果数据，则使用私钥对结果数据进行解密获得最短距离，再使用伪随机排列函数和密钥恢复出从起点出发并经过k个无序节点后到达终点的最短路径。
[0082]
如图2所示，支持k个无序节点的最短路径查询方法允许用户将加密后的安全索引和包含k个无序节点的查询令牌发送给云服务方，经过云服务方的最短路径查询搜索，将最终的结果发送给用户，用户在本地解密查询结果后，得到从起点出发途径k个无序节点到达终点的最短路径。
[0083]
本实施例中，一种k个无序节点的最短路径查询方法是应用于由一个用户和一个云服务方所构成的网络环境中，并按如下步骤进行：
[0084]
步骤一、构建索引：
[0085]
步骤1.1用户端采用基于paillier的密码学方案构建公钥同态加密体系ω，生成密钥产生函数gen,同态加密函数enc，同态解密函数dec，并使用密钥产生函数gen生成私钥sk，公钥pk。公钥同态加密体系ω是将一组密文(c1,c2,
…
,cn)作为输入，其中ci＝enc
pk
(mi)，输出为一个密文dec
sk
(c)＝e(m1,m2,
…
,mn)，支持enc
pk
(m1+m2)＝eval(+,enc
pk
(m1),enc
pk
(m2))，其中eval为评估函数。用户端再选取一个伪随机排列函数prp、一个伪随机函数prf、一个随机预言机函数h、一个抗碰撞的哈希函数h以及两个密钥k1,k2；
[0086]
步骤1.2用户端对节点集合v和边集合ε的原始图数据g＝{v,ε}，其中，节点集合v＝{v1,v2,
…
,vn}，ε是边的集合，例如，(vi,vj,w
ij
)是从vi到vj权重为w
ij
的边，(vi,vj,w
ij
)∈ε,vi∈v,vj∈v,使用floyd-warshall算法计算后获得路径距离集合pd。其中，是从vi到vj最短路径上的一系列途径点,再对路径距离集合pd随机排列，并初始化一个数组arr；
[0087]
步骤1.3用户端对节点集合v中的每一个节点vi随机产生一个密钥一个密钥和一个随机数ri。使用密钥vi∈v和一个不同的密钥k1的原因是，为每个节点排列每个路径序列与字典dx中的排列不同。通过这样保护结构的隐私。
[0088]
以所述第i个节点vi为起点，对于所述路径距离集合pd中从起点vi出发到终点vj的第numi条最短路径，所述用户端使用抗碰撞的哈希函数h对终点vj进行处理，产生哈希结果h(vj)，使用公钥pk和同态加密函数enc对起点vi出发到终点vj的最短距离进行处理，获得加密结果使用密钥和伪随机排列函数prp对起点vi出发到终点vj的最短路径上的途径点v
ij
进行处理，获得路径伪随机排列结果对路径距离集合pd中第num
i+1
条最短路径做随机排列，获得随机排列结果π(num
i+1
)；
[0089]
链接所述哈希结果h(vj)、加密结果路径伪随机排列结果和随机排列结果π(num
i+1
)后产生一个链表结点no；
[0090]
使用随机预言机函数h对所述密钥和随机数rj进行处理，获得随机预言机结果将所述链表结点no和随机预言机结果进行异或运算并产生数组异或结果arr
ij
；
[0091]
最后将数组异或结果arr
ij
和随机数rj存放在数组arr的第numi个位置上；
[0092]
步骤1.4用户端使用伪随机排列函数prp和密钥k2对第i个节点vi进行处理，获得节点伪随机排列结果再使用伪随机函数prf和密钥k1对第i个节点vi进行处理，获得伪随机结果对路径序号numi及其相应起点的密钥与伪随机结果做异或运算获得字典异或结果dxi，其中，||是字符串连接运算；
[0093]
创建一个字典dx用于存储伪随机排列结果和字典异或结果dxi；
[0094]
步骤1.5用户端将数组arr和字典dx组成安全索引index并发送给云服务方；
[0095]
步骤二、标准令牌生成：
[0096]
步骤2.1用户端选取将要查询的起点s、终点d；并使用伪随机排列函数prp和密钥k2对起点s进行处理，获得起点伪随机排列结果并创建一个集合q1用于存放起点伪随机排列结果
[0097]
步骤2.2用户端使用伪随机函数prf和密钥k1对起点s进行处理，获得起点伪随机结果并创建一个集合q2用于存放起点伪随机结果
[0098]
步骤2.3用户端使用抗碰撞的哈希函数h对终点d进行处理，获得终点哈希结果h(d)，并创建一个集合q3用于存放终点哈希结果h(d)；
[0099]
步骤2.4用户端将集合q1、集合q2和集合q3组成标准查询令牌q，并将标准查询令牌q发送给云服务方；
[0100]
步骤三、k个无序节点令牌生成：
[0101]
步骤3.1用户端选取将要查询的起点s、终点d，并从节点集合v中选取k个无序节点{v1,v2,
…
,vk}；其中，vk表示第k个无序节点；
[0102]
使用伪随机排列函数prp和密钥k2对起点s进行处理，获得起点伪随机排列结果再使用伪随机排列函数prp和密钥k2对k个无序节点进行处理，获得k个无序节点的伪随机排列结果其中，表示第k个无序节点vk的伪随机排列结果，创建一个集合q
*1
用于存放起点伪随机排列结果和k个无序节点伪随机排列结果
[0103]
步骤3.2用户端使用伪随机函数prf和密钥k1对起点s进行处理，获得起点伪随机结果再使用伪随机函数prf和密钥k1对k个无序节点进行处理，获得k个无序节点的伪随机结果其中，表示第k个无序节点vk的伪随机结果，创建一个集合q
*2
用于存放起点伪随机结果和k个无序节点伪随机结果
[0104]
步骤3.3用户端使用抗碰撞的哈希函数h对终点d进行处理，获得终点哈希结果h(d)，再使用抗碰撞的哈希函数h对k个无序节点(v1,v2,
…
,vk)进行处理，获得k个无序节点的哈希结果(h(v1),h(v2),
…
,h(vk))，其中，h(vk)表示第k个无序节点vk的哈希结果，创建一个集合q
*3
用于存放终点哈希结果h(d)和k个无序节点哈希结果(h(v1),h(v2),
…
,h(vk))；
[0105]
步骤3.4用户端将集合q
*1
、集合q
*2
和集合q
*3
组成查询令牌q
*
，并将查询令牌q
*
发送给云服务方；
[0106]
步骤四、标准查询处理：
[0107]
步骤4.1云服务方从用户端接收到相应的安全索引index和标准查询令牌q；
[0108]
步骤4.2云服务方使用标准查询令牌q中的集合q1对安全索引index中的字典dx检索，获取字典dx中的元素α＝dx[q1]，并与标准查询令牌q中的集合q2做异或运算，获得异或结果β＝nums||ks；其中，nums表示第s条路径序号，ks表示第s个节点的密钥；
[0109]
步骤4.3云服务方使用结果β中的第s条路径序号nums作为入口获得数组arr[nums]中的随机数rs和数组异或结果arrs，使用随机预言机函数h对异或结果β的第s个节点的密钥ks和随机数rs进行处理，获得随机预言机结果h(ks||rs)，再将数组异或结果arrs与随机预言机结果h(ks||rs)做异或运算，获得标识串其中，hs表示第s个节点的哈希结果，sds表示第s条路径的最短距离，sps表示第s条路径的最短路径，num
s+1
表示第s+1条路径序号；
[0110]
步骤4.4云服务方将标识串xs中的第s个节点的哈希结果hs与标准查询令牌q中的q3比对，如果一致，将标识串xs中的第s条路径的最短距离sds和第s条路径的最短路径sps加入结果集合r；否则，截取标识串xs中的第s+1条路径序号num
s+1
作为下一个入口获得arr[num
s+1
]中的随机数和数组异或结果后，按照步骤4.3的过程顺序执行；如果截取标识串xs中的第s+1条路径序号num
s+1
为null，则将结果集合r置为null；
[0111]
步骤4.5云服务方将结果集合r发送给用户端，其中，结果集合r＝(enc
pk
(sd
s,d
),esp
s,d
)；
[0112]
步骤五、k个无序节点查询处理：
[0113]
步骤5.1云服务方从用户端接收到相应的安全索引index和查询令牌q
*
；
[0114]
步骤5.2云服务方创建一个长度为k阶乘的最短路径链表sp和一个长度为k阶乘最短距离链表sd，并初始化sd＝{rsd1,rsd2,
…
,rsd
k！
}＝{1,1,
…
,1}；其中，rsd
k！
表示第k阶乘条路径的最短距离；
[0115]
步骤5.3云服务方对查询令牌q
*
进行k阶乘次查询顺序组合，获得查询顺序组合(pq1,pq2,
…
,pqz,
…
,pq
k！
)；其中，pqz表示第z组查询顺序；
[0116]
步骤5.4云服务方对第z组查询顺序其中，表示由起点s出发到达节点v1的查询，表示由节点v
k-1
出发到达节点vk的查询，表示由节点vk出发到达终点d的查询；
[0117]
定义并初始化第z个路径链表espz为空，定义并初始化第z个距离链表esdz为1；
[0118]
步骤5.5将作为标准查询处理的输入，按照步骤4的过程，获得结果集合r，并结果集合r中的sds存入距离链表esdz中，将中的无序节点v1的伪随机排列结果插入到路径链表espz中；
[0119]
步骤5.6按照步骤5.5的过程对pqz中的进行处理，直到整条路径s-v
1-v2‑…‑vk-d查找结束，从而将第z个路径链表espz插入最短路径链表sp，将第z个距离链表esdz插入最短距离链表sd；
[0120]
步骤5.7云服务方对于查询顺序组合(pq1,pq2,
…
,pq
k！
)中的所有组合按照步骤5.4-步骤5.6的过程进行运算，再将最短路径链表sp和最短距离链表sd加入结果集r
′
，并将结果集r
′
发送给用户端；
[0121]
步骤六、处理查询结果：
[0122]
步骤6.1用户端接收到云服务方发送的结果集r
′
；
[0123]
步骤6.2用户端使用同态解密函数dec和私钥sk解密结果集r
′
，得到最短距离链表sd，从而获得从起点s到终点d的最短距离sd；
[0124]
步骤6.3用户端使用伪随机排列函数prp和起点s的密钥k
*s
解密结果集r
′
，从而得到从起点s到终点d的最短路径sp。
[0125]
综上所述，本发明在图加密最短路径的基础上进行了改进，解决了k个无序节点最短路径查询需求问题，实现了支持k个无序节点的图加密最短路径查询方法与系统，能够有效抵抗不可信云服务方的安全威胁，从而保护用户的隐私安全与数据安全。

技术特征：
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进行随机排列，并初始化一个数组arr；步骤1.3所述用户端对节点集合v中的第i个节点v
i
随机产生一个密钥一个密钥和一个随机数r
i
；
以所述第i个节点v
i
为起点，对于所述路径距离集合pd中从起点v
i
出发到终点v
j
的第num
i
条最短路径，所述用户端使用抗碰撞的哈希函数h对终点v
j
进行处理，产生哈希结果h(v
j
)，使用公钥pk和同态加密函数enc对起点v
i
出发到终点v
j
的最短距离进行处理，获得加密结果使用密钥和伪随机排列函数prp对起点v
i
出发到终点v
j
的最短路径上的途径点v
ij
进行处理，获得路径伪随机排列结果对路径距离集合pd中第num
i+1
条最短路径做随机排列，获得随机排列结果π(num
i+1
)；链接所述哈希结果h(v
j
)、加密结果路径伪随机排列结果和随机排列结果π(num
i+1
)后产生一个链表结点n
o
；使用随机预言机函数h对所述密钥和随机数r
j
进行处理，获得随机预言机结果将所述链表结点n
o
和随机预言机结果进行异或运算并产生数组异或结果arr
ij
；最后将数组异或结果arr
ij
和随机数r
j
存放在数组arr的第num
i
个位置上；步骤1.4用户端使用伪随机排列函数prp和密钥k2对第i个节点v
i
进行处理，获得节点伪随机排列结果再使用伪随机函数prf和密钥k1对第i个节点v
i
进行处理，获得伪随机结果对路径序号num
i
及其相应起点的密钥与伪随机结果做异或运算获得字典异或结果dx
i
，其中，||是字符串连接运算；创建一个字典dx用于存储伪随机排列结果和字典异或结果dx
i
；步骤1.5用户端将数组arr和字典dx组成安全索引index并发送给云服务方；步骤二、标准令牌生成：步骤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,
…
,v
k
}；其中，v
k
表示第k个无序节点；使用伪随机排列函数prp和密钥k2对起点s进行处理，获得起点伪随机排列结果再使用伪随机排列函数prp和密钥k2对k个无序节点进行处理，获得k个无序节点的伪随机排列结果其中，表示第k个无序节点v
k
的伪随机排列结果，
创建一个集合q
*1
用于存放起点伪随机排列结果和k个无序节点伪随机排列结果步骤3.2用户端使用伪随机函数prf和密钥k1对起点s进行处理，获得起点伪随机结果再使用伪随机函数prf和密钥k1对k个无序节点进行处理，获得k个无序节点的伪随机结果其中，表示第k个无序节点v
k
的伪随机结果，创建一个集合q
*2
用于存放起点伪随机结果和k个无序节点伪随机结果步骤3.3用户端使用抗碰撞的哈希函数h对终点d进行处理，获得终点哈希结果h(d)，再使用抗碰撞的哈希函数h对k个无序节点(v1,v2,
…
,v
k
)进行处理，获得k个无序节点的哈希结果(h(v1),h(v2),
…
,h(v
k
))，其中，h(v
k
)表示第k个无序节点v
k
的哈希结果，创建一个集合q
*3
用于存放终点哈希结果h(d)和k个无序节点哈希结果(h(v1),h(v2),
…
,h(v
k
))；步骤3.4用户端将集合q
*1
、集合q
*2
和集合q
*3
组成查询令牌q
*
，并将查询令牌q
*
发送给云服务方；步骤四、标准查询处理：步骤4.1云服务方从用户端接收到相应的安全索引index和标准查询令牌q；步骤4.2云服务方使用标准查询令牌q中的集合q1对安全索引index中的字典dx检索，获取字典dx中的元素α＝dx[q1]，并与标准查询令牌q中的集合q2做异或运算，获得异或结果β＝num
s
||k
s
；其中，num
s
表示第s条路径序号，k
s
表示第s个节点的密钥；步骤4.3云服务方使用结果β中的第s条路径序号num
s
作为入口获得数组arr[num
s
]中的随机数r
s
和数组异或结果arr
s
，使用随机预言机函数h对异或结果β的第s个节点的密钥k
s
和随机数r
s
进行处理，获得随机预言机结果h(k
s
||r
s
)，再将数组异或结果arr
s
与随机预言机结果h(k
s
||r
s
)做异或运算，获得标识串其中，h
s
表示第s个节点的哈希结果，sd
s
表示第s条路径的最短距离，sp
s
表示第s条路径的最短路径，num
s+1
表示第s+1条路径序号；步骤4.4云服务方将标识串x
s
中的第s个节点的哈希结果h
s
与标准查询令牌q中的q3比对，如果一致，将标识串x
s
中的第s条路径的最短距离sd
s
和第s条路径的最短路径sp
s
加入结果集合r；否则，截取标识串x
s
中的第s+1条路径序号num
s+1
作为下一个入口获得arr[num
s+1
]中的随机数和数组异或结果后，按照步骤4.3的过程顺序执行；如果截取标识串x
s
中的第s+1条路径序号num
s+1
为null，则将结果集合r置为null；步骤4.5云服务方将结果集合r发送给用户端；步骤五、k个无序节点的查询处理：步骤5.1云服务方从用户端接收到相应的安全索引index和查询令牌q
*
；步骤5.2云服务方创建一个长度为k阶乘的最短路径链表sp和一个长度为k阶乘最短距离链表sd，并初始化sd＝{rsd1,rsd2,
…
,rsd
k！
}＝{1,1,
…
,1}；其中，rsd
k！
表示第k阶乘条路径的最短距离；步骤5.3云服务方对查询令牌q
*
进行k阶乘次查询顺序组合，获得查询顺序组合(pq1,pq2,
…
,pq
z
,
…
,pq
k！
)；其中，pq
z
表示第z组查询顺序；
步骤5.4云服务方对第z组查询顺序其中，表示由起点s出发到达节点v1的查询，表示由节点v
k-1
出发到达节点v
k
的查询，表示由节点v
k
出发到达终点d的查询；定义并初始化第z个路径链表esp
z
为空，定义并初始化第z个距离链表esd
z
为1；步骤5.5将作为标准查询处理的输入，按照步骤4的过程，获得结果集合r，并结果集合r中的sd
s
存入距离链表esd
z
中，将中的无序节点v1的伪随机排列结果插入到路径链表esp
z
中；步骤5.6按照步骤5.5的过程对pq
z
中的进行处理，从而将第z个路径链表esp
z
插入最短路径链表sp，将第z个距离链表esd
z
插入最短距离链表sd；步骤5.7云服务方对于查询顺序组合(pq1,pq2,
…
,pq
k！
)中的所有组合按照步骤5.4-步骤5.6的过程进行运算，再将最短路径链表sp和最短距离链表sd加入结果集r
′
，并将结果集r
′
发送给用户端；步骤六、处理查询结果：步骤6.1用户端接收到云服务方发送的结果集r
′
；步骤6.2用户端使用同态解密函数dec和私钥sk解密结果集r
′
，得到最短距离链表sd，从而获得从起点s到终点d的最短距离sd；步骤6.3用户端使用伪随机排列函数prp和起点s的密钥k
*s
解密结果集r
′
，从而得到从起点s到终点d的最短路径sp。

技术总结
本发明公开了一种支持k个无序节点的图加密最短路径查询方法与系统，应用于由一个用户模块与一个云服务模块构成的环境；用户模块处理原始图数据计算图加密的安全索引，并根据查询的k个无序节点生成查询令牌，将安全索引同查询令牌上传到云服务模块，等待查询结果发回后解密获得最短路径，否则一直等待查询结果；云服务模块从用户模块接收安全索引和查询令牌，使用查询令牌搜索安全索引并返回经过k个无序节点的最短路径。本发明能够保护用户的路径查询隐私不受不可信云服务的侵害。径查询隐私不受不可信云服务的侵害。径查询隐私不受不可信云服务的侵害。


技术研发人员：李萌 高剑博 祝烈煌
受保护的技术使用者：合肥工业大学
技术研发日：2022.04.08
技术公布日：2022/7/5