一种隐私保护的子图匹配方法及系统

摘要

本发明公开了一种隐私保护的子图匹配方法及系统，本发明提供的方法中，将每个属性图节点本身的节点ID以及属性值编码为独热向量，同时对每个属性图节点的邻居节点的ID编码为独热向量并按照不同的节点类型组成倒排表，在倒排表中加入0向量作为虚假节点ID，将属性图数据通过复制秘密共享的方式进行加密后分发至三个计算终端进行计算，并且还采用属性查询谓词对应的目标值的独热向量中非0数值的位置，生成三对函数秘密共享秘钥对，组成三个加密令牌，分发至三个计算终端，三个计算终端基于自身持有的复制秘密共享份额和加密令牌进行子图匹配，使得计算终端在不获得关于属性图以及子图查询隐私信息的情况下，在加密的属性图上进行子图匹配。

权利要求

1.一种隐私保护的子图匹配方法，其特征在于，所述方法包括：

受信终端对属性图数据进行加密，基于复制秘密共享生成所述属性图中每个属性图节点的自身信息和邻居节点信息分别对应的三份复制秘密共享份额，分别发送给第一计算终端、第二计算终端和第三计算终端，其中，目标属性图节点的所述自身信息包括所述目标属性图节点的节点类型，所述目标属性图节点的节点ID对应的独热向量以及所述目标属性图节点的每种属性的各个属性值对应的独热向量，所述目标属性图节点的所述邻居节点信息包括多个倒排表，所述多个倒排表中的目标倒排表中包括所述目标属性图节点的邻居节点中具有目标类型的各个节点的节点ID对应的独热向量以及所述目标属性图节点的虚假邻居节点ID对应的独热向量，所述目标属性图节点的虚假邻居节点ID对应的独热向量为0向量；

所述受信终端对子图查询数据进行加密，基于函数秘密共享生成每个子图节点的每个属性查询谓词对应的加密令牌，所述加密令牌包括第一加密令牌、第二加密令牌和第三加密令牌，分别发送给所述第一计算终端、所述第二计算终端和所述第三计算终端，其中，所述第一加密令牌、所述第二加密令牌和所述第三加密令牌中均包括所述子图节点的节点类型，所述子图节点的一个属性以及秘钥组中的两个秘钥，所述秘钥组中包括三个秘钥对，每个所述秘钥对为基于所述子图节点的一个属性查询谓词对应的目标值的独热向量中非0数值的位置生成的函数秘密共享秘钥对；

所述第一计算终端、所述第二计算终端和所述第三计算终端基于本地持有的属性图节点的所述自身信息的复制秘密共享份额，依次获取每个子图节点的候选节点的复制秘密共享份额，目标子图节点的候选节点的复制秘密共享份额包括候选节点的节点ID和目标属性的属性值的复制秘密共享份额，其中，所述目标属性为所述目标子图节点的查询属性，当所述目标子图节点没有前序子图节点时，所述目标子图节点的候选节点为节点类型与所述目标子图节点的节点类型相同的所述属性图节点，当所述目标子图节点有前序子图节点时，所述目标子图节点的候选节点为所述目标子图节点的匹配节点的邻居节点中与所述目标子图节点的节点类型相同的所述属性图节点；

所述第一计算终端、所述第二计算终端和所述第三计算终端基于本地持有的所述目标子图节点的候选节点的复制秘密共享份额和目标子图节点对应的所述加密令牌，获取每个候选节点是否为匹配节点的判断结果的复制秘密共享份额，匹配节点为所述目标属性的属性值满足所述目标子图节点的属性查询谓词的候选节点；

所述第一计算终端、所述第二计算终端和所述第三计算终端基于本地持有的所述目标子图节点的每个候选节点是否为匹配节点的判断结果的复制秘密共享份额，获取目标数据的复制秘密共享份额，所述目标数据包括所述目标子图节点的匹配节点的节点ID和属性值的复制秘密共享份额；

所述第一计算终端、所述第二计算终端和所述第三计算终端基于本地持有的所述目标子图节点的每个匹配节点的节点ID的复制秘密共享份额、每个候选节点的倒排表的复制秘密共享份额以及目标匹配节点的节点ID，获取下一个子图节点的候选节点的复制秘密共享份额；

所述第一计算终端、所述第二计算终端和所述第三计算终端根据所述子图查询的公共结构将本地持有的每个子图节点的所述目标数据重新组织成候选子图，在所述候选子图中删除与所述子图查询数据中的结构不完全相同的子图，分别输出子图匹配结果的复制秘密共享份额。

2.根据权利要求1所述的隐私保护的子图匹配方法，其特征在于，所述受信终端对属性图数据进行加密之前，包括：

所述受信终端在各个所述属性图节点中选择若干个节点类型为目标节点类型的多个第一节点，任意两个所述第一节点的目标邻居节点的数量的差值在预设范围内，所述目标邻居节点为节点类型为第一节点类型的邻居节点；

所述受信终端在所述第一节点的所述目标邻居节点中加入至少一个虚假邻居节点ID，生成所述第一节点的节点类型为所述第一节点类型的所述倒排表；

每个所述第一节点的节点类型为所述第一节点类型的所述倒排表中包括的节点ID的数量相等。

3.根据权利要求1所述的隐私保护的子图匹配方法，其特征在于，所述第一计算终端、所述第二计算终端和所述第三计算终端基于本地持有的所述目标子图节点的候选节点的复制秘密共享份额和目标子图节点对应的所述加密令牌，获取每个候选节点是否为匹配节点的判断结果的复制秘密共享份额，包括：所述第一计算终端、所述第二计算终端和所述第三计算终端均在本地执行以下运算以获取目标候选节点的所述目标属性的属性值是否满足所述目标子图节点的目标属性查询谓词的判断结果的复制秘密共享份额：基于本地持有的所述目标子图节点的目标属性查询谓词对应的所述加密令牌中的一个秘钥，将本地持有的所述目标候选节点的所述目标属性的属性值的一个复制秘密共享份额中的目标位置序号分别作为函数秘密共享的输入，获取函数秘密共享的第一输出；

将所述第一输出和本地持有的所述目标候选节点的所述目标属性的属性值的复制共享秘密份额中所述目标位置序号对应的比特进行与运算，得到第一与运算结果，对所有的所述第一与运算结果进行异或运算，得到第一异或运算结果；

基于本地持有的所述目标子图节点的目标属性查询谓词对应的所述加密令牌中的另一个秘钥，将本地持有的所述目标候选节点的所述目标属性的属性值的另一个复制秘密共享份额中的所述目标位置序号分别作为函数秘密共享的输入，获取函数秘密共享的第二输出；

将所述第二输出和本地持有的所述目标候选节点的所述目标属性的属性值的复制共享秘密份额中所述目标位置序号对应的比特进行与运算，得到第二与运算结果，对所有的所述第二与运算结果进行异或运算，得到第二异或运算结果；

所述第一异或运算结果和所述第二异或运算结果的异或运算结果为所述目标候选节点是否为匹配节点的判断结果的判断结果的一个加性秘密共享份额，基于所述第一异或运算结果和所述第二异或运算结果得到所述目标候选节点的所述目标属性的属性值是否满足所述目标子图节点的目标属性查询谓词的判断结果的复制秘密共享份额；

所述第一计算终端、所述第二计算终端和所述第三计算终端根据自身持有的所述目标候选节点的所述目标属性的属性值是否满足所述目标子图节点的目标属性查询谓词的判断结果的复制秘密共享份额获取所述目标候选节点是否为所述目标子图节点的匹配节点的判断结果的复制秘密共享份额。

4.根据权利要求3所述的隐私保护的子图匹配方法，其特征在于，所述第一计算终端、所述第二计算终端和所述第三计算终端根据自身持有的所述目标候选节点的所述目标属性的属性值是否满足所述目标子图节点的目标属性查询谓词的判断结果的复制秘密共享份额获取所述目标候选节点是否为所述目标子图节点的候选节点的判断结果的复制秘密共享份额，包括：当所述目标子图节点的属性查询谓词只有一个时，直接将所述目标候选节点的所述目标属性的属性值是否满足所述目标子图节点的目标属性查询谓词的判断结果的复制秘密共享份额作为所述目标候选节点是否为所述目标子图节点的候选节点的判断结果的复制秘密共享份额；

当所述目标子图节点的属性查询谓词有多个时，根据指定的布尔表达式聚合所述目标候选节点的所述目标属性的属性值是否满足所述目标子图节点的目标属性查询谓词的判断结果的复制秘密共享份额，得到所述目标候选节点是否为所述目标子图节点的候选节点的判断结果的复制秘密共享份额。

5.根据权利要求1所述的隐私保护的子图匹配方法，其特征在于，所述第一计算终端、所述第二计算终端和所述第三计算终端基于本地持有的所述目标子图节点的每个候选节点是否为匹配节点的判断结果的复制秘密共享份额，获取目标数据的复制秘密共享份额，包括：当所述目标子图节点的候选节点中只有一个节点为匹配节点时：

所述第一计算终端、所述第二计算终端和所述第三计算终端将本地持有的所述目标子图节点的每个候选节点是否为匹配节点的判断结果的复制秘密共享份额与其节点ID的复制秘密共享份额进行求与操作之后，将所有的求与操作结果进行异或操作，得到匹配节点的节点ID的复制秘密共享份额；

所述第一计算终端、所述第二计算终端和所述第三计算终端将本地持有的所述目标子图节点的每个候选节点是否为匹配节点的判断结果的复制秘密共享份额与其属性值的复制秘密共享份额进行求与操作之后，将所有的求与操作结果进行异或操作，得到匹配节点的节点ID的复制秘密共享份额。

6.根据权利要求1所述的隐私保护的子图匹配方法，其特征在于，所述第一计算终端、所述第二计算终端和所述第三计算终端基于本地持有的所述目标子图节点的每个候选节点是否为匹配节点的判断结果的复制秘密共享份额，获取目标数据的复制秘密共享份额，包括：当所述目标子图节点的候选节点中有两个及两个以上的节点为匹配节点时：

所述第一计算终端、所述第二计算终端和所述第三计算终端均在本地生成第一表格，所述第一表格中的每一行由本地持有的所述目标子图节点的每个候选节点是否为匹配节点的判断结果的复制秘密共享份额、所述目标子图节点的每个候选节点的节点ID的复制秘密共享份额、所述目标子图节点的每个候选节点的属性值的复制秘密共享份额组成；

所述第一计算终端、所述第二计算终端和所述第三计算终端基于安全的置乱技术协作地随机排列所述第一表格中的行并更新本地持有的所述目标子图节点的每个候选节点是否为匹配节点的判断结果的复制秘密共享份额、所述目标子图节点的每个候选节点的节点ID的复制秘密共享份额、所述目标子图节点的每个候选节点的属性值的复制秘密共享份额，以使得所述第一计算终端、所述第二计算终端和所述第三计算终端均在本地持有第一置乱表格，所述第一置乱表格中的每一行由本地持有的所述目标子图节点的每个候选节点是否为匹配节点的判断结果的更新后的复制秘密共享份额、所述目标子图节点的每个候选节点的节点ID的更新后的复制秘密共享份额、所述目标子图节点的每个候选节点的属性值的更新后的复制秘密共享份额组成；

所述第一计算终端、所述第二计算终端和所述第三计算终端分别公开自身持有的所述第一置乱表格中所述目标子图节点的每个候选节点是否为匹配节点的判断结果的复制秘密共享份额的一列，以使得所述第一计算终端、所述第二计算终端和所述第三计算终端获取所述目标子图节点的匹配节点的节点ID和属性值的复制秘密共享份额。

7.根据权利要求1所述的隐私保护的子图匹配方法，其特征在于，所述第一计算终端、所述第二计算终端和所述第三计算终端基于本地持有的所述目标子图节点的每个匹配节点的节点ID的复制秘密共享份额、每个候选节点的倒排表的复制秘密共享份额以及目标匹配节点的节点ID，获取下一个子图节点的候选节点的复制秘密共享份额，包括：所述第一计算终端、所述第二计算终端和所述第三计算终端在本地均执行如下操作：

获取所述目标子图节点的第c个候选节点的第一倒排表中的一个节点ID的复制秘密共享份额与目标匹配节点的节点ID的复制秘密共享份额中的第c位比特进行与运算，得到第三与运算结果，将各个所述第三与运算结果进行异或操作进行聚合，得到所述目标匹配节点的所述第一倒排表中一个节点ID的复制秘密共享份额，其中，所述第一倒排表对应的节点类型为下一个子图节点的节点类型；

对所述目标匹配节点的所述第一倒排表中每个节点ID的复制秘密共享份额中的每个比特执行异或操作，得到所述目标匹配节点的所述第一倒排表中每个节点ID是否为虚假节点ID的判断结果的复制秘密共享份额；

基于所述目标匹配节点的所述第一倒排表中每个节点ID是否为虚假节点ID的判断结果的复制秘密共享份额在所述第一倒排表的复制秘密共享份额中剔除虚假节点ID的复制秘密共享份额；

基于本地持有的所述目标子图节点的候选节点的属性值的复制秘密共享份额和所述目标子图节点的每个匹配节点的所述第一倒排表中的节点ID的复制秘密共享份额获取下一个子图节点的候选节点的所述目标属性的属性值的复制秘密共享份额。

8.根据权利要求7所述的隐私保护的子图匹配方法，其特征在于，所述第一计算终端、所述第二计算终端和所述第三计算终端基于所述目标匹配节点的所述第一倒排表中每个节点ID是否为虚假节点ID的判断结果的复制秘密共享份额在所述第一倒排表的复制秘密共享份额中剔除虚假节点ID的复制秘密共享份额，包括：所述第一计算终端、所述第二计算终端和所述第三计算终端均在本地生成第二表格，所述第二表格中的每一行包括本地持有的所述第一倒排表中一个节点ID的复制秘密共享份额和该节点ID是否为虚假节点ID的判断结果的复制秘密共享份额；

所述第一计算终端、所述第二计算终端和所述第三计算终端基于安全的置乱技术协作地随机排列所述第二表格中的行并更新本地持有的所述第一倒排表中一个节点ID的复制秘密共享份额和该节点ID是否为虚假节点ID的判断结果的复制秘密共享份额，以使得所述第一计算终端、所述第二计算终端和所述第三计算终端均在本地持有第二置乱表格，所述第二置乱表格中的每一行由本地持有的所述第一倒排表中一个节点ID的更新后的复制秘密共享份额和该节点ID是否为虚假节点ID的判断结果的更新后的复制秘密共享份额组成；

所述第一计算终端、所述第二计算终端和所述第三计算终端公开本地持有的所述第二置乱表格中节点ID是否为虚假节点ID的判断结果的复制秘密共享份额的一列，以使得所述第一计算终端、所述第二计算终端和所述第三计算终端剔除虚假ID的复制秘密共享份额。

9.根据权利要求7所述的隐私保护的子图匹配方法，其特征在于，所述基于本地持有的所述目标子图节点的候选节点的属性值的复制秘密共享份额和所述目标子图节点的每个匹配节点的所述第一倒排表中的节点ID的复制秘密共享份额获取下一个子图节点的候选节点的所述目标属性的属性值的复制秘密共享份额，包括：将本地持有的所述目标子图节点的第x个候选节点的所述目标属性的属性值的复制秘密共享份额与下一个子图节点的第一候选节点的第x个比特进行与操作，得到第四与运算结果，将各个所述第四与运算结果进行异或操作，得到所述第一候选节点的所述目标属性的属性值的复制秘密共享份额。

10.一种隐私保护的子图匹配系统，其特征在于，所述系统包括受信终端、第一计算终端、第二计算终端和第三计算终端；所述受信终端、第一计算终端、第二计算终端和第三计算终端协同完成如权利要求1‑9任一项所述的隐私保护的子图匹配方法。

说明书

一种隐私保护的子图匹配方法及系统

技术领域

[0001] 本发明涉及信息安全技术领域，特别涉及一种隐私保护的子图匹配方法及系统。

背景技术

[0002] 属性图(attributed graphs)是一种图数据模型，已被广泛用于建模各种场景中实体之间的交互，如社交网络和金融交易网络等。随着云计算的发展，越来越多的企业利用云计算存储其属性图，以及在属性图上执行各种各样的查询。虽然云计算的优势是众所周知的，但在公共商业云中部署这些图分析服务会对信息丰富的属性图数据的隐私造成严重威胁，而且这可能不符合这些企业的商业利益，因为这些图数据是其专有的数据财富。因此，迫切需要在这类云环境中设计安全性保障协议，为外包的属性图数据的存储和查询提供隐私保护。

[0003] 子图匹配(subgraph matching)是属性图查询中最基本的功能之一，其旨在从一个大的属性图中检索所有与给定小查询图同构的子图。子图匹配在各种应用中都是一个强有力的工具，例如反洗钱、化合物的搜索以及社交网络分析等。一个具体的例子是，从一张大的社交网络图中检索所有与给定的用户社交圈(ego‑network)同构的所有社交圈。不同于常规非属性图的子图匹配仅考虑结构化匹配，面向属性图的子图匹配是更复杂的，因为它额外考虑匹配图节点的属性和类型。

[0004] 当前，考虑隐私的图查询协议设计是一个热点研究问题。然而，大多数现有的工作都聚焦于处理与子图匹配不同的图查询功能，如隐私保护的最短路径搜索和隐私保护的广度优先遍历。还没有涉及面向属性图的隐私保护的子图匹配的现有技术。

[0005] 因此，现有技术还有待改进和提高。

发明内容

[0006] 针对现有技术的上述缺陷，本发明提供一种隐私保护的子图匹配方法及系统，旨在解决现有技术中没有在设计面向属性图的隐私保护的子图匹配的方案的问题。

[0007] 为了解决上述技术问题，本发明所采用的技术方案如下：

[0008] 本发明的第一方面，提供一种隐私保护的子图匹配方法，所述方法包括：

[0009] 受信终端对属性图数据进行加密，基于复制秘密共享生成所述属性图中每个属性图节点的自身信息和邻居节点信息分别对应的三份复制秘密共享份额，分别发送给第一计算终端、第二计算终端和第三计算终端，其中，目标属性图节点的所述自身信息包括所述目标属性图节点的节点类型，所述目标属性图节点的节点ID对应的独热向量以及所述目标属性图节点的每种属性的各个属性值对应的独热向量，所述目标属性图节点的所述邻居节点信息包括多个倒排表，所述多个倒排表中的目标倒排表中包括所述目标属性图节点的邻居节点中具有目标类型的各个节点的节点ID对应的独热向量以及所述目标属性图节点的虚假邻居节点ID对应的独热向量，所述目标属性图节点的虚假邻居节点ID对应的独热向量为0向量；

[0010] 所述受信终端对子图查询数据进行加密，基于函数秘密共享生成每个子图节点的每个属性查询谓词对应的加密令牌，所述加密令牌包括第一加密令牌、第二加密令牌和第三加密令牌，分别发送给所述第一计算终端、所述第二计算终端和所述第三计算终端，其中，所述第一加密令牌、所述第二加密令牌和所述第三加密令牌中均包括所述子图节点的节点类型，所述子图节点的一个属性以及秘钥组中的两个秘钥，所述秘钥组中包括三个秘钥对，每个所述秘钥对为基于所述子图节点的一个属性查询谓词对应的目标值的独热向量中非0数值的位置生成的函数秘密共享秘钥对；

[0011] 所述第一计算终端、所述第二计算终端和所述第三计算终端基于本地持有的属性图节点的所述自身信息的复制秘密共享份额，依次获取每个子图节点的候选节点的复制秘密共享份额，目标子图节点的候选节点的复制秘密共享份额包括候选节点的节点ID和目标属性的属性值的复制秘密共享份额，其中，所述目标属性为所述目标子图节点的查询属性，当所述目标子图节点没有前序子图节点时，所述目标子图节点的候选节点为节点类型与所述目标子图节点的节点类型相同的所述属性图节点，当所述目标子图节点有前序子图节点时，所述目标子图节点的候选节点为所述目标子图节点的匹配节点的邻居节点中与所述目标子图节点的节点类型相同的所述属性图节点；

[0012] 所述第一计算终端、所述第二计算终端和所述第三计算终端基于本地持有的所述目标子图节点的候选节点的复制秘密共享份额和目标子图节点对应的所述加密令牌，获取每个候选节点是否为匹配节点的判断结果的复制秘密共享份额，匹配节点为所述目标属性的属性值满足所述目标子图节点的属性查询谓词的候选节点；

[0013] 所述第一计算终端、所述第二计算终端和所述第三计算终端基于本地持有的所述目标子图节点的每个候选节点是否为匹配节点的判断结果的复制秘密共享份额，获取目标数据的复制秘密共享份额，所述目标数据包括所述目标子图节点的匹配节点的节点ID和属性值的复制秘密共享份额；

[0014] 所述第一计算终端、所述第二计算终端和所述第三计算终端基于本地持有的所述目标子图节点的每个匹配节点的节点ID的复制秘密共享份额、每个候选节点的倒排表的复制秘密共享份额以及目标匹配节点的节点ID，获取下一个子图节点的候选节点的复制秘密共享份额；

[0015] 所述第一计算终端、所述第二计算终端和所述第三计算终端根据所述子图查询的公共结构将本地持有的每个子图节点的所述目标数据重新组织成候选子图，在所述候选子图中删除与所述子图查询数据中的结构不完全相同的子图，分别输出子图匹配结果的复制秘密共享份额。

[0016] 所述的隐私保护的子图匹配方法，其中，所述受信终端对属性图数据进行加密之前，包括：

[0017] 所述受信终端在各个所述属性图节点中选择若干个节点类型为目标节点类型的多个第一节点，任意两个所述第一节点的目标邻居节点的数量的差值在预设范围内，所述目标邻居节点为节点类型为第一节点类型的邻居节点；

[0018] 所述受信终端在所述第一节点的所述目标邻居节点中加入至少一个虚假邻居节点ID，生成所述第一节点的节点类型为所述第一节点类型的所述倒排表；

[0019] 每个所述第一节点的节点类型为所述第一节点类型的所述倒排表中包括的节点ID的数量相等。

[0020] 所述的隐私保护的子图匹配方法，其中，所述第一计算终端、所述第二计算终端和所述第三计算终端基于本地持有的所述目标子图节点的候选节点的复制秘密共享份额和目标子图节点对应的所述加密令牌，获取每个候选节点是否为匹配节点的判断结果的复制秘密共享份额，包括：

[0021] 所述第一计算终端、所述第二计算终端和所述第三计算终端均在本地执行以下运算以获取目标候选节点的所述目标属性的属性值是否满足所述目标子图节点的目标属性查询谓词的判断结果的复制秘密共享份额：

[0022] 基于本地持有的所述目标子图节点的目标属性查询谓词对应的所述加密令牌中的一个秘钥，将本地持有的所述目标候选节点的所述目标属性的属性值的一个复制秘密共享份额中的目标位置序号分别作为函数秘密共享的输入，获取函数秘密共享的第一输出；

[0023] 将所述第一输出和本地持有的所述目标候选节点的所述目标属性的属性值的复制共享秘密份额中所述目标位置序号对应的比特进行与运算，得到第一与运算结果，对所有的所述第一与运算结果进行异或运算，得到第一异或运算结果；

[0024] 基于本地持有的所述目标子图节点的目标属性查询谓词对应的所述加密令牌中的另一个秘钥，将本地持有的所述目标候选节点的所述目标属性的属性值的另一个复制秘密共享份额中的所述目标位置序号分别作为函数秘密共享的输入，获取函数秘密共享的第二输出；

[0025] 将所述第二输出和本地持有的所述目标候选节点的所述目标属性的属性值的复制共享秘密份额中所述目标位置序号对应的比特进行与运算，得到第二与运算结果，对所有的所述第二与运算结果进行异或运算，得到第二异或运算结果；

[0026] 所述第一异或运算结果和所述第二异或运算结果的异或运算结果为所述目标候选节点是否为匹配节点的判断结果的一个加性秘密共享份额，基于所述第一异或运算结果和所述第二异或运算结果得到所述目标候选节点的所述目标属性的属性值是否满足所述目标子图节点的目标属性查询谓词的判断结果的复制秘密共享份额；

[0027] 所述第一计算终端、所述第二计算终端和所述第三计算终端根据自身持有的所述目标候选节点的所述目标属性的属性值是否满足所述目标子图节点的目标属性查询谓词的判断结果的复制秘密共享份额获取所述目标候选节点是否为所述目标子图节点的匹配节点的判断结果的复制秘密共享份额。

[0028] 所述的隐私保护的子图匹配方法，其中，所述第一计算终端、所述第二计算终端和所述第三计算终端根据自身持有的所述目标候选节点的所述目标属性的属性值是否满足所述目标子图节点的目标属性查询谓词的判断结果的复制秘密共享份额获取所述目标候选节点是否为所述目标子图节点的候选节点的判断结果的复制秘密共享份额，包括：

[0029] 当所述目标子图节点的属性查询谓词只有一个时，直接将所述目标候选节点的所述目标属性的属性值是否满足所述目标子图节点的目标属性查询谓词的判断结果的复制秘密共享份额作为所述目标候选节点是否为所述目标子图节点的候选节点的判断结果的复制秘密共享份额；

[0030] 当所述目标子图节点的属性查询谓词有多个时，根据指定的布尔表达式聚合所述目标候选节点的所述目标属性的属性值是否满足所述目标子图节点的目标属性查询谓词的判断结果的复制秘密共享份额，得到所述目标候选节点是否为所述目标子图节点的候选节点的判断结果的复制秘密共享份额。

[0031] 所述的隐私保护的子图匹配方法，其中，所述第一计算终端、所述第二计算终端和所述第三计算终端基于本地持有的所述目标子图节点的每个候选节点是否为匹配节点的判断结果的复制秘密共享份额，获取目标数据的复制秘密共享份额，包括：

[0032] 当所述目标子图节点的候选节点中只有一个节点为匹配节点时：

[0033] 所述第一计算终端、所述第二计算终端和所述第三计算终端将本地持有的所述目标子图节点的每个候选节点是否为匹配节点的判断结果的复制秘密共享份额与其节点ID的复制秘密共享份额进行求与操作之后，将所有的求与操作结果进行异或操作，得到匹配节点的节点ID的复制秘密共享份额；

[0034] 所述第一计算终端、所述第二计算终端和所述第三计算终端将本地持有的所述目标子图节点的每个候选节点是否为匹配节点的判断结果的复制秘密共享份额与其属性值的复制秘密共享份额进行求与操作之后，将所有的求与操作结果进行异或操作，得到匹配节点的节点ID的复制秘密共享份额。

[0035] 所述的隐私保护的子图匹配方法，其中，所述第一计算终端、所述第二计算终端和所述第三计算终端基于本地持有的所述目标子图节点的每个候选节点是否为匹配节点的判断结果的复制秘密共享份额，获取目标数据的复制秘密共享份额，包括：

[0036] 当所述目标子图节点的候选节点中有两个及两个以上的节点为匹配节点时：

[0037] 所述第一计算终端、所述第二计算终端和所述第三计算终端均在本地生成第一表格，所述第一表格中的每一行由本地持有的所述目标子图节点的每个候选节点是否为匹配节点的判断结果的复制秘密共享份额、所述目标子图节点的每个候选节点的节点ID的复制秘密共享份额、所述目标子图节点的每个候选节点的属性值的复制秘密共享份额组成；

[0038] 所述第一计算终端、所述第二计算终端和所述第三计算终端基于安全的置乱技术协作地随机排列所述第一表格中的行并更新本地持有的所述目标子图节点的每个候选节点是否为匹配节点的判断结果的复制秘密共享份额、所述目标子图节点的每个候选节点的节点ID的复制秘密共享份额、所述目标子图节点的每个候选节点的属性值的复制秘密共享份额，以使得所述第一计算终端、所述第二计算终端和所述第三计算终端均在本地持有第一置乱表格，所述第一置乱表格中的每一行由本地持有的所述目标子图节点的每个候选节点是否为匹配节点的判断结果的更新后的复制秘密共享份额、所述目标子图节点的每个候选节点的节点ID的更新后的复制秘密共享份额、所述目标子图节点的每个候选节点的属性值的更新后的复制秘密共享份额组成；

[0039] 所述第一计算终端、所述第二计算终端和所述第三计算终端分别公开自身持有的所述第一置乱表格中所述目标子图节点的每个候选节点是否为匹配节点的判断结果的复制秘密共享份额的一列，以使得所述第一计算终端、所述第二计算终端和所述第三计算终端获取所述目标子图节点的匹配节点的节点ID和属性值的复制秘密共享份额。

[0040] 所述的隐私保护的子图匹配方法，其中，所述第一计算终端、所述第二计算终端和所述第三计算终端基于本地持有的所述目标子图节点的每个匹配节点的节点ID的复制秘密共享份额、每个候选节点的倒排表的复制秘密共享份额以及目标匹配节点的节点ID，获取下一个子图节点的候选节点的复制秘密共享份额，包括：

[0041] 所述第一计算终端、所述第二计算终端和所述第三计算终端在本地均执行如下操作：

[0042] 获取所述目标子图节点的第c个候选节点的第一倒排表中的一个节点ID的复制秘密共享份额与目标匹配节点的节点ID的复制秘密共享份额中的第c位比特进行与运算，得到第三与运算结果，将各个所述第三与运算结果进行异或操作进行聚合，得到所述目标匹配节点的所述第一倒排表中一个节点ID的复制秘密共享份额，其中，所述第一倒排表对应的节点类型为下一个子图节点的节点类型；

[0043] 对所述目标匹配节点的所述第一倒排表中每个节点ID的复制秘密共享份额中的每个比特执行异或操作，得到所述目标匹配节点的所述第一倒排表中每个节点ID是否为虚假节点ID的判断结果的复制秘密共享份额；

[0044] 基于所述目标匹配节点的所述第一倒排表中每个节点ID是否为虚假节点ID的判断结果的复制秘密共享份额在所述第一倒排表的复制秘密共享份额中剔除虚假节点ID的复制秘密共享份额；

[0045] 基于本地持有的所述目标子图节点的候选节点的属性值的复制秘密共享份额和所述目标子图节点的每个匹配节点的所述第一倒排表中的节点ID的复制秘密共享份额获取下一个子图节点的候选节点的所述目标属性的属性值的复制秘密共享份额。

[0046] 所述的隐私保护的子图匹配方法，其中，所述第一计算终端、所述第二计算终端和所述第三计算终端基于所述目标匹配节点的所述第一倒排表中每个节点ID是否为虚假节点ID的判断结果的复制秘密共享份额在所述第一倒排表的复制秘密共享份额中剔除虚假节点ID的复制秘密共享份额，包括：

[0047] 所述第一计算终端、所述第二计算终端和所述第三计算终端均在本地生成第二表格，所述第二表格中的每一行包括本地持有的所述第一倒排表中一个节点ID的复制秘密共享份额和该节点ID是否为虚假节点ID的判断结果的复制秘密共享份额；

[0048] 所述第一计算终端、所述第二计算终端和所述第三计算终端基于安全的置乱技术协作地随机排列所述第二表格中的行并更新本地持有的所述第一倒排表中一个节点ID的复制秘密共享份额和该节点ID是否为虚假节点ID的判断结果的复制秘密共享份额，以使得所述第一计算终端、所述第二计算终端和所述第三计算终端均在本地持有第二置乱表格，所述第二置乱表格中的每一行由本地持有的所述第一倒排表中一个节点ID的更新后的复制秘密共享份额和该节点ID是否为虚假节点ID的判断结果的更新后的复制秘密共享份额组成；

[0049] 所述第一计算终端、所述第二计算终端和所述第三计算终端公开本地持有的所述第二置乱表格中节点ID是否为虚假节点ID的判断结果的复制秘密共享份额的一列，以使得所述第一计算终端、所述第二计算终端和所述第三计算终端剔除虚假ID的复制秘密共享份额。

[0050] 所述的隐私保护的子图匹配方法，其中，所述基于本地持有的所述目标子图节点的候选节点的属性值的复制秘密共享份额和所述目标子图节点的每个匹配节点的所述第一倒排表中的节点ID的复制秘密共享份额获取下一个子图节点的候选节点的所述目标属性的属性值的复制秘密共享份额，包括：

[0051] 将本地持有的所述目标子图节点的第x个候选节点的所述目标属性的属性值的复制秘密共享份额与下一个子图节点的第一候选节点的第x个比特进行与操作，得到第四与运算结果，将各个所述第四与运算结果进行异或操作，得到所述第一候选节点的所述目标属性的属性值的复制秘密共享份额。

[0052] 本发明的第二方面，提供一种隐私保护的子图匹配系统，所述系统包括受信终端、第一计算终端、第二计算终端和第三计算终端；所述受信终端、第一计算终端、第二计算终端和第三计算终端协同完成如上述任一项所述的隐私保护的子图匹配方法。

[0053] 与现有技术相比，本发明提供了一种隐私保护的子图匹配方法及系统，所述的隐私保护的子图匹配方法中，对属性图数据，将每个属性图节点本身的节点ID以及属性值编码为独热向量，同时对每个属性图节点的邻居节点的节点ID编码为独热向量并按照不同的节点类型组成倒排表，在倒排表中加入虚假节点ID，将属性图数据通过复制秘密共享的方式进行加密后分发至三个计算终端进行云计算，并且还进一步地采用属性查询谓词对应的目标值的独热向量中非0数值的位置，生成三对函数秘密共享秘钥对，并组成三个加密令牌，分别分发至三个计算终端，三个计算终端基于自身持有的复制秘密共享份额和加密令牌进行子图匹配，使得计算终端在不获得各种关于属性图以及子图查询隐私信息的情况下，有效地在加密的属性图上执行子图匹配任务，实现了隐私保护的子图匹配。

附图说明

[0054] 图1为本发明提供的隐私保护的子图匹配方法的实施例的流程图；

[0055] 图2为面向属性图的子图匹配的明文示例图；

[0056] 图3为本发明提供的隐私保护的子图匹配方法的实施例中受信终端与计算终端的系统架构图；

[0057] 图4为本发明提供的隐私保护的子图匹配方法的实施例中子图匹配过程的总体算法示意图；

[0058] 图5为本发明提供的隐私保护的子图匹配方法的实施例中安全的候选节点谓词评估算法的示意图；

[0059] 图6为本发明提供的隐私保护的子图匹配方法的实施例中安全的匹配节点获取算法的示意图；

[0060] 图7为本发明提供的隐私保护的子图匹配方法的实施例中安全的邻居节点获取算法的示意图。

具体实施方式

[0061] 为使本发明的目的、技术方案及效果更加清楚、明确，以下参照附图并举实施例对本发明进一步详细说明。应当理解，此处所描述的具体实施例仅用以解释本发明，并不用于限定本发明。

[0062] 实施例一

[0063] 本实施例提供了一种隐私保护的子图匹配方法，旨在以隐私保护的方式实现面向属性图的子图匹配。下面对明文域的面向属性图的子图匹配进行说明：

[0064] 在属性图中，图节点(vertices)表示实体，边(edges)表示实体之间的连接。属性图通常是异构的(heterogeneous)，即节点和边的类型不同，节点也有不同的属性。属性图的正式定义如下：

[0065] 定义1：一个属性图定义为 其中1) 是N个节点组成的集合；2)ε＝{ei，j＝(Vi，Vj)：1≤i，j≤N，i≠j}是图中所有的边组成的集合；3) 是一个类型集合，每个图节点或边有且仅有一种类型；4) 是一个属性集合，每个节点可以有一个或多个属性。

[0066] 给定一个属性图 和一个子图查询q，子图匹配是从 中检索所有与q同构的子图{gm}。本发明中的子图同构的定义如下：

[0067] 定义2：给定 中的一个子图 和一个子图查询 g是同构于q的当且仅当存在一个双射函数 满足1)
和Att(Vi)＝Att(f(Vi))或者Att(Vi)∈Att(f(Vi))；2)
其中T(·)和Att(·)分别代表·的类型和属性。

[0068] 也就是说，在本发明中，将现有工作定义中的“Att(Vi)＝Att(f(Vi))”修改为Att(Vi)＝Att(f(Vi))或者Att(Vi)∈Att(f(Vi))。具体地说，现有工作仅考虑精确的匹配(即等式谓词)，即查询图q中的每个节点附带一个精确的值，只有子图g中的每个节点对应的属性值与查询图q中的每个节点附带的值相等，才认为两个节点是匹配的，即Att(Vi)＝Att(f(Vi))。而本发明中不仅像现有工作一样考虑精确匹配(即等式谓词)，还考虑范围匹配(即范围谓词)，即查询图q中的每个节点附带一个范围(单边的范围或者一个区间)，匹配定义为子图g中的每个节点的属性值在查询图q中对应的节点附带的范围内，即Att(Vi)∈Att(f(Vi))。此外，本发明还考虑灵活地支持混合的匹配，即，查询图q中的一些节点附带一个精确的值而其它的节点附带一个范围。

[0069] 请参照图2，图2中展示了一个子图匹配的例子，该图中 有三种节点即大学(U)、人(P)和公司(C)。不同节点之间的连接暗含了边的类型，例如朋友(P‑P)、工作于(P‑C)和毕业于(P‑U)。图2右边的子图查询q表示用户想要检索两个人其满足下述条件：1)他们都毕业于位置在Harbin的大学(等式谓词)；2)他们的年龄在30～40岁之间(范围谓词)；3)他们中的其中一个在software公司工作而另一个在Internet公司工作(等式谓词)。最后的匹配结果是：

[0070]

[0071] 下面对本实施例提供的隐私保护的子图匹配方法中涉及到的一些背景知识进行说明：

[0072] 1.复制的秘密共享

[0073] 给定一个秘密的比特 复制的秘密共享(replicated secret sharing(RSS))划分x为三个份额1、2和 其中 三对份额(>1，2)、(2，3)和(〈x>3〈，x>1)被三方P1、P2和P3分别持有。为了便于描述，使用i±1表示下一个(+)参与方(或者秘密份额)或者(‑)上一个(+)参与方(或者秘密份额)，特别地，P3+1(或者3+1)表示P1(或者1)，P1‑1(或者1‑1)表示P3(或者3)。通过该表示方法，可以使用(i，i+1)表示Pi(i∈{1，2，3})所持有的秘密共享份额，并且把加密的比特x表示为

[0074] 域的RSS的的基本操作包含以下两个：

[0075] 1)XOR 在秘密分享的比特上的XOR操作仅要求本地计算。为了计算每一方Pi本地计算 和

[0076] 2)AND 为了计算 每一方Pi首先本地计算但该操作将产生加性的秘密共享也即是每一方Pi仅持有>i。为了获得复制的秘密共享以便于后续的计算，Pi之间需要一个重新共享的操作。每一方Pi发送给Pi+1一个噪声化的份额(即masked) 其中<α>i是一个关于0的新的
(fresh)秘密共享份额，即 这样的新的关于0的秘密共享份额可以
通过一个输出域为 的伪随机函数(pseudorandom function：PRF)高效地生成。具体的，在初始化阶段，每一方Pi采样一个PRF密钥ki并发送ki给Pi+1。之后，为了产生第j个新的关于0的秘密共享份额，每一方Pi本地计算 其满足

[0077] 2.函数秘密共享

[0078] 函数密秘共享(FSS)是加性密秘共享的一种扩展，其可以一种较低的通信量完成安全的函数计算。因此，FSS在高延迟的网络下相较于普通的密秘共享具有很大的性能优势。总的来说，一个两方的基于FSS的隐私函数f，由以下两个抽象算法组成：

[0079] 1.(k1，k2)←Gen(1λ，f)：给定一个安全参数λ和一个函数描述f，输出两个FSS密钥k1，k2，每个一个计算参与方。

[0080] 2.i←Eval(ki，x)：给定一个FSS密钥ki和一个评估点x，输出一个评估结果的密秘共享份额

[0081] FSS可以确保如果攻击者仅学习到两个FSS密钥的一个，他无法获得任何关于这个目标函数以及计算输出f(x)的信息。

[0082] 如图3所示，本实施例提供的隐私保护子图匹配方法中，包括受信终端和三个计算终端，所述受信终端为图数据所有者预置的前端 三个计算终端为云服务器 图数据所有者(例如企业或者组织)持有大量的数据，其被建模为属性图。图数据所有者想要利用云计算技术存储和查询该图。图数据所有者希望云服务器能够支持图数据所有者的用户(例如，企业的员工或消费者)在属性图上进行子图匹配查询。

[0083] 本实施例提供的隐私保护的子图匹配方法是基于半诚实和非共谋的对手模型上，其中每个 诚实地遵循本实施例提供的方法，但可能单独地尝试推断敏感信息。此外，本实施例中，假设 和用户是可信的，因为 是属性图的所有者，其可以使用标准的数据库访问控制列表限制不同用户允许进行的查询的范围。基于这个半诚实和非共谋的对手模型下，本实施例提供的隐私保护的子图匹配方法确保计算终端无法学习到以下信息：

[0084] 1)属性图中每个节点的属性值和以及精确的度信息(即degree)，以及这些节点之间的连接(即边edges)；

[0085] 2)子图查询q中的每个节点附带的目标属性的值；

[0086] 3)搜索访问模式。

[0087] 搜索模式和访问模型的定义如下：

[0088] 搜索模式：对于两个子图查询q和q′，定义Sim(q，q′)：＝(q≡q′)，即是否两个查询是一样的。给定q＝{q1，…，qm}是一系列查询。所谓的搜索访问模式 返回一个m×m的对称矩阵，其实体i，j等于Sim(qi，qj)。

[0089] 访问模式：给定属性图 上的一个子图查询q，访问模式定义为其中gm表示 中与q同构的一个子图。

[0090] 在实践中，搜索模式泄漏可以直观地理解为一个新的子图查询是否与历史查询中的某一个一样，也即是新来的查询是否已经被查询过，访问模式泄漏会泄漏属性图 中哪一个节点被“访问过”，即 中哪一个节点与q中的节点匹配。

[0091] 本实施例提供的方法不保护以下信息：

[0092] 1)属性图 和子图查询q的布局参数，包括节点和边的数量、类型、以及节点属性的类型。

[0093] 2)子图查询q中与每个节点关联的谓词类型，即该谓词是“等式谓词”还是“范围谓词”。

[0094] 3)子图查询q的结构。

[0095] 以图2中的查询q为例，攻击者可以学习到该查询是

[0096]

[0097] 下面对本实施例提供的隐私保护的子图匹配方法的具体流程进行说明，如图1所示，本实施例提供的方法，包括步骤：

[0098] S100、受信终端对属性图数据进行加密，基于复制秘密共享生成所述属性图中每个属性图节点的自身信息和邻居节点信息分别对应的三份复制秘密共享份额，分别发送给第一计算终端、第二计算终端和第三计算终端，其中，目标属性图节点的所述自身信息包括所述目标属性图节点的节点类型，所述目标属性图节点的节点ID对应的独热向量以及所述目标属性图节点的每种属性的各个属性值对应的独热向量，所述目标属性图节点的所述邻居节点信息包括多个倒排表，所述多个倒排表中的目标倒排表中包括所述目标属性图节点的邻居节点中具有目标类型的各个节点的节点ID对应的独热向量以及所述目标属性图节点的虚假邻居节点ID对应的独热向量，所述目标属性图节点的虚假邻居节点ID对应的独热向量为0向量。

[0099] 具体地，在本实施例提供的方法中，首先对属性图进行建模以表示一个属性图 的结构和非结构信息，给定一个节点 首先将Vi的每个属性表示为一个元组(tj，dj)，j∈[S]，其中S是节点Vi的属性的数量(本实施例中将集合{1，2，…，S}写作[S])，tj和dj分别表示该属性的类型和值(例如(年龄，35))。之后，节点Vi可以被建模成Vi＝{Ti，idi，{(tj，dj)}j∈[S]}，其中Ti表示节点Vi的类型，idi表示节点Vi的身份标识符(identifier，下文简写成节点ID)。在本报告中，为了便于描述，使用{σi}i∈[μ]表示集合{σ1，…，σμ}，并在不影响表述的情况下省略脚标i∈[μ]。由于属性图中的边类型是多种多样的，所以为了清楚地区分不同类型的边，给每个节点Vi关联几个倒排表(posting lists)，每一个倒排表包含节点Vi的同类型的邻居节点的IDs。具体的，Vi的一个倒排表表示为 其中idi，j，j∈[L]表示Vi的每个类型为Tne的节点的ID，L表示他们的数量，即 因此，节点Vi的邻居节点可以被建模成 其中 表示节点Vi的所有倒排表的类型的集合。

[0100] 现在介绍如何对属性图进行加密，以支持后续的安全的子图匹配服务。这里，需要对每个节点的相关属性值和相关倒排表中的节点ID进行加密。

[0101] 首先，在进行加密之前，首先将每个敏感值编码成独热向量(类似于独热码)的形式。所谓独热向量是指使用一个比特串表示一个敏感值假如需要编码年龄，就可以使用一个130位长的比特串(假设人的最大年龄是130岁)进行编码；假如是48岁，则把第48个位置设为1其他位置都是0。

[0102] 给定 所述受信终端 首先编码它的每个属性值以及每个倒排表中的每个邻居节点的ID为一个独热向量。之后， 将这些独热向量加密成前文中介绍的 或中的RSS的形式：1) 其中黑体表示该值被编码为独热向量；2)
注意到 没有加密类型信息即Ti，{tj}j∈[S]，Tne，因为其是必要的公
共信息。

[0103] 然而，简单地加密每个倒排表中的ID，而不保护倒排表的长度信息(即L)，将泄露每个节点的度信息(即degree)，这可能会导致各种推断攻击。为了解决这个问题，本实施例中采用k‑自同构(即k‑automorphism)的思想。在每个节点Vi的倒排表中混入一些0向量作为假的IDs，使得在该属性图中至少有k‑1个其他与Vi同类型的节点拥有与Vi相等的度。具体地，所述受信终端对属性图数据进行加密之前，包括：

[0104] 所述受信终端在各个所述属性图节点中选择若干个节点类型为目标节点类型的多个第一节点，任意两个所述第一节点的目标邻居节点的数量的差值在预设范围内，所述目标邻居节点为节点类型为第一节点类型的邻居节点；

[0105] 所述受信终端在所述第一节点的所述目标邻居节点中加入至少一个虚假邻居节点ID，生成所述第一节点的节点类型为所述第一节点类型的所述倒排表；

[0106] 每个所述第一节点的节点类型为所述第一节点类型的所述倒排表中包括的节点ID的数量相等。

[0107] 每个相同类型的节点都有相同类型的倒排表，但它们的长度可以不同。例如每个表示“人”的节点都拥有好友列表和粉丝列表，但他们的好友和粉丝的数量是不同的。因此，给定类型为Ti的节点Vi和其倒排表 首先从属性图 中找出k‑1个类型为Ti的节点{Vs}s∈[k‑1]，其中每个Vs的类型为Tne的倒排表的长度与Vi的类型为Tne的倒排表的长度相近，即 之后， 在{Vs}s∈[k‑1]的倒排表中混入一些
0向量作为假的ID，使得 然后， 利用RSS技术加密真
实的和虚假的IDs。具体地，可以将同一类型的倒排表的长度都设置为相等的，加密后的统一类型的倒排表的长度可以等于该类型的邻居节点的最大个数，也可以大于该类型的邻居节点的最大个数，即对于邻居节点的个数没有达到预先设置的该类型的倒排表的长度的情况，则需要添加相应个数的虚假邻居节点ID，对于邻居节点的个数已经达到预先设置的该类型的倒排表的情况，则不需要再添加虚假邻居节点ID，最终的目的是使得同一类型的倒排表的长度均相等。由于每个节点的属性值也被加密成RSS的形式，因此在密文域该属性图是一个k‑自同构图。最后，该属性图 的密文可以表示为
其中 表示节点Vi的倒排表类型的集合，N是属性图 中节点的数量。 将该密文图
的秘密共享份额分别发送给计算终端

[0108] 请再次参阅图1，本实施例提供的方法，还包括步骤：

[0109] S200、所述受信终端对子图查询数据进行加密，基于函数秘密共享生成每个子图节点的每个属性查询谓词对应的加密令牌，所述加密令牌包括第一加密令牌、第二加密令牌和第三加密令牌，分别发送给所述第一计算终端、所述第二计算终端和所述第三计算终端，其中，所述第一加密令牌、所述第二加密令牌和所述第三加密令牌中均包括所述子图节点的节点类型，所述子图节点的一个属性以及秘钥组中的两个秘钥，所述秘钥组中包括三个秘钥对，每个所述秘钥对为基于所述子图节点的一个属性查询谓词对应的目标值的独热向量中非0数值的位置生成的函数秘密共享秘钥对。

[0110] 给定子图查询q中的一个节点Vi(命名为目标节点)，Vi拥有目标类型Ti和目标属性(ti，pdi)，其中ti表示目标属性的类型，pdi表示该目标属性关联的谓词。正如前面所说，谓词pdi可以是一个精确的值也可以是一个范围，其分别对应于精确匹配和范围匹配。因此，一个查询q可以被建模成q＝{Vi＝(Ti，(ti，pdi))}i∈[|q|]，其中|q|表示q中的目标节点的数量。为了使子图查询的建模更加具体，以图2中的查询q为例，其被建模成：

[0111] q：＝{(U，(Place，``Harbin))，(P，(Age，``[30，40]))，

[0112] (P，(Age，``[30，40]))，(C，(Field，``software))，

[0113] (C，(Field，``Internet″))}，

[0114] 其结构(即边)直接使用物理连接，例如C++中的指针。

[0115] 给定一个子图查询q， 需要将其加密成安全的且可使用的搜索令牌。正如前文所述，一个子图查询q可以被建模成q＝{Vi＝(Ti，(ti，pdi))}i∈[|q|](结构信息没有表示出来，节点之间是直接连接的，没有经过特殊处理)。值得注意的是，上述建模中仅有谓词pdi需要被保护，因为Ti和ti都是公开的类型信息。

[0116] 在三个计算终端 之间运行安全的子图匹配服务，需要尽量减少计算终端之间的通信，因为通信开销在云计算中的价格较高。函数秘密共享(FSS)是一个非常适合该场景的工具，它允许在多方之间对谓词进行低交互的安全评估。具体的，两个FSS构建，其非常适合OblivGM所聚焦的两类谓词：分布式点函数(distributed point functions(DPFs))负责等式谓词的评估；分布式比较函数(distributed comparison functions(DCFs))负责范围谓词的评估。基于FSS的DPF允许两个服务器对一个点函数 进行安全的计算，当输入的是α，其输出秘密共享的β，否则输出秘密共享的0。DCF是一个比较函数 当输入的值x＜α其输出秘密共享的β，否则输出秘密共享的0。类似地，DCF也可以描述谓词x＞α、x≤α和x≥α。此外两个DCF还可以描述区间谓词 α≤x＜α′、α＜x≤α′和α≤x≤α′。

[0117] 然而，在本实施例中，要通过FSS技术计算的值不在明文域中，每个计算终端都仅持有这些值的秘密共享份额。然而，基于FSS的评估过程要求计算终端处理相同的明文输入，以产生正确的输出。为了解决这个问题，一种相对简单且有效的方法是让云服务器公开噪声化(masked)的秘密数值，之后产生相应定制的FSS密钥。虽然这种简单方法可以保护秘密值，但它有两个关键的限制：1)在不同的秘密共享的值上评估相同的谓词要求不同的新的FSS密钥，这将导致较高的 则的开销(因为 要负责生成这些密钥)；2)对每个秘密共享值的评估需要计算终端进行一轮通信(为了公开噪声化的秘密值)，这也会导致云端通信开销很高。

[0118] 因此，本实施例中并没有使用上述基本方法，而是进行了定制化的处理，以提高效率。回顾在属性图加密阶段，每个需要保护的值都被编码到一个独热向量中。采用这种编码策略，本实施例中提供了一种替代方法，以避免计算终端在不同属性值上评估相同谓词时在使用新的FSS密钥。这个方法是让计算终端使用FSS密钥将每个独热向量中比特的公共位置作为输入进行评估，也就是说，FSS输出的评估结果是该位置是否为属性谓词对应的非0比特的位置的评估结果。然后，将每个比特的评估结果与其对应的秘密共享的比特相乘，并将所有相乘结果聚合起来，以生成一个独热向量/秘密值的评估结果。

[0119] 根据上面的思路，现在介绍如何生成安全的查询令牌。具体的，给定一个目标节点附带的谓词pdi， 产生三对相同且独立的FSS密钥 其参数设置为α＝pdi和 FSS的输出域设置为 是为了与密文图 相匹配。假设，属性
谓词为年龄等于15，采用分布式点函数实现FSS，年龄的属性值均编码为100位的独热向量，那么明文的符合属性谓词的属性值的独热向量应该是第15位为1，其他位为0，那么将15作为待评估数值，给定一个FSS秘钥，输出的是评估结果(为1)的一个秘密共享份额，将其他的位置作为待评估数值，给定一个FSS秘钥，输出的是评估结果(为0)的一个秘密共享份额，假设属性谓词为年龄小于15，采用分布式比较函数实现FSS，年龄的属性值均编码为100位的独热向量，那么明文的符合属性谓词的属性值的独热向量是第15位为0，其他位为0，将小于
15的位置序号作为待评估数值，给定一个FSS秘钥，输出的是评估结果(为1)的一个秘密共享份额，将大于等于15的位置序号作为待评估数值，给定一个FSS秘钥，输出的是评估结果(为0)的一个秘密共享份额。通过该方法， 可以加密一个子图查询q＝{Vi＝(Ti，(ti，pdi))}i∈[|q|]为对应的查询令牌 最后 发送
和 以及
公共的结构分别给第一计算终端 第二计算终端 和第三计算终端 为了安全的子
图查询令牌更加具体，以图2中的查询q为例，其对应的安全查询令牌是

[0120]

[0121] 其中 有相同的输出域 分别对应于FSS密钥：和

[0122] 在从 端收到安全的查询令牌tokq时，计算终端需要在加密的属性图 上执行安全的子图匹配过程，输出与查询子图q同构的加密的匹配子图 本实施例提供的提供的方法允许计算终端搜索加密的属性图 的同时不泄漏搜索访问模式。本实施例提供的方法由三个组件组成：安全的候选节点谓词评估(称为secEval)、安全的匹配节点获取(称为secFetch)和安全的邻接节点获取(称为secAccess)。下面将首先对这三个模块做简单的功能介绍。

[0123] 给定当前的目标节点Vi∈tokq，secEval让计算终端首先对加密的属性图中的候选节点(即与Vi相同类型的节点)执行安全的谓词计算，并产生加密的谓词计算结果。然后，基于secEval的加密的计算结果，secFetch让计算终端在不知道哪个候选节点满足谓词的情况下获取满足谓词的节点(命名为匹配节点)。之后，基于每个匹配节点的加密ID，secAccess允许计算终端安全地获取每个匹配节点的邻居节点的节点ID和属性值，这些节点将作为tokq中下一跳的目标节点的候选节点。上述过程迭代地运行，直到处理完tokq中的所有目标节点。最后，计算终端根据tokq的公共结构将匹配的节点重新组织成子图，之后删除不具有与tokq的结构完全一样的不完整子图，输出最终的加密的匹配结果 如图4所示，算法1描述了安全的子图匹配的完整过程(main函数)，其由上述三个模块secEval、secFetch和secAccess组成，描述了这三个模块之间是如何配合的。下面将详细介绍这三个模块的具体设计。

[0124] 值得说明的是，在复制秘密共享协议中，对于同一个明文数据，每个计算终端持有一对份额，即持有两个复制秘密共享份额，下文中计算终端对复制秘密共享份额的计算的说明中，都是对持有的两个复制秘密共享份额分别均执行相应的计算。

[0125] S300、所述第一计算终端、所述第二计算终端和所述第三计算终端基于本地持有的属性图节点的所述自身信息的复制秘密共享份额，依次获取每个子图节点的候选节点的复制秘密共享份额，目标子图节点的候选节点的复制秘密共享份额包括候选节点的节点ID和目标属性的属性值的复制秘密共享份额，其中，所述目标属性为所述目标子图节点的查询属性，当所述目标子图节点没有前序子图节点时，所述目标子图节点的候选节点为节点类型与所述目标子图节点的节点类型相同的所述属性图节点，当所述目标子图节点有前序子图节点时，所述目标子图节点的候选节点为所述目标子图节点的匹配节点的邻居节点中与所述目标子图节点的节点类型相同的所述属性图节点。

[0126] 给定目标子图节点 需要首先从加密的属性图中检索其候选节点{Vc}的 (即IDs)和 (即类型为ti的属性的值)。有两种
情况需要分开处理：1)如果Vi是tokq中的没有前序节点的起始节点(例如图2中查询q中的节点U)，Vi的候选节点{Vc}是 中所有类型为Ti的节点。 可以本地设置{Vc}的IDs和类型为ti的属性的值为 和 2)如果Vi有前序节点，{Vc}是Vi的前序节点的匹
配节点的邻居节点， 和 将通过模块secAccess安全地获取。

[0127] S400、所述第一计算终端、所述第二计算终端和所述第三计算终端基于本地持有的所述目标子图节点的候选节点的复制秘密共享份额和目标子图节点对应的所述加密令牌，获取每个候选节点是否为匹配节点的判断结果的复制秘密共享份额，匹配节点为所述目标属性的属性值满足所述目标子图节点的属性查询谓词的候选节点。

[0128] 对每一个候选节点Vc， 需要安全地评估是否它的属性值 满足Vi附带的加密的谓词 回顾前面的加密过程，每个属性值都被编码为一个独热向量，并通过RSS进行加密；并且加密谓词 由三对FSS密钥组成 如图5中示出的算
法2描述了候选节点的安全谓词评估算法secEval。

[0129] 具体地，所述第一计算终端、所述第二计算终端和所述第三计算终端基于本地持有的所述目标子图节点的候选节点的复制秘密共享份额和目标子图节点对应的所述加密令牌，获取每个候选节点是否为匹配节点的判断结果的复制秘密共享份额，包括：

[0130] 所述第一计算终端、所述第二计算终端和所述第三计算终端均在本地执行以下运算以获取目标候选节点的所述目标属性的属性值是否满足所述目标子图节点的目标属性查询谓词的判断结果的复制秘密共享份额：

[0131] 基于本地持有的所述目标子图节点的目标属性查询谓词对应的所述加密令牌中的一个秘钥，将本地持有的所述目标候选节点的所述目标属性的属性值的一个复制秘密共享份额中的目标位置序号分别作为函数秘密共享的输入，获取函数秘密共享的第一输出；

[0132] 将所述第一输出和本地持有的所述目标候选节点的所述目标属性的属性值的复制共享秘密份额中所述目标位置序号对应的比特进行与运算，得到第一与运算结果，对所有的所述第一与运算结果进行异或运算，得到第一异或运算结果；

[0133] 基于本地持有的所述目标子图节点的目标属性查询谓词对应的所述加密令牌中的另一个秘钥，将本地持有的所述目标候选节点的所述目标属性的属性值的另一个复制秘密共享份额中的所述目标位置序号分别作为函数秘密共享的输入，获取函数秘密共享的第二输出；

[0134] 将所述第二输出和本地持有的所述目标候选节点的所述目标属性的属性值的复制共享秘密份额中所述目标位置序号对应的比特进行与运算，得到第二与运算结果，对所有的所述第二与运算结果进行异或运算，得到第二异或运算结果；

[0135] 所述第一异或运算结果和所述第二异或运算结果的异或运算结果为所述目标候选节点是否为匹配节点的判断结果的判断结果的一个加性秘密共享份额，基于所述第一异或运算结果和所述第二异或运算结果得到所述目标候选节点的所述目标属性的属性值是否满足所述目标子图节点的目标属性查询谓词的判断结果的复制秘密共享份额；

[0136] 所述第一计算终端、所述第二计算终端和所述第三计算终端根据自身持有的所述目标候选节点的所述目标属性的属性值是否满足所述目标子图节点的目标属性查询谓词的判断结果的复制秘密共享份额获取所述目标候选节点是否为所述目标子图节点的匹配节点的判断结果的复制秘密共享份额。

[0137] 对于每一个秘密共享的比特 (其中n是独热向量 的长度) 表示向量 的第l个比特(向量 由n个比特组成)，每一个 平估其所持有的FSS密钥，
FSS的输入是公共的位置l，是指输入位置本身的值。比如 表示向量 的第l个比特，那就输入l，例如 之后将FSS的输出与加密的比特 进行AND操作(即比特
“与”)。然后，每一个 本地XOR(即异或)所有的AND操作的输出，从而产生候选节点Vc的加密的谓词评估结果。安全谓词计算可以形式化地描述为公式一：

[0138]

[0139]

[0140]

[0141] 需要指出的是 显示候选节点Vc是否满足加密的谓词 即 表示Vc是匹配的节点而 表示不是。此外，上述公式一
的评估结果 是加性的秘密共享(即每一方仅持有一个秘密份额)的形式。所以为了兼容后续RSS域的计算， 需要使用1.2节中的技术重新共享 使得其是RSS(即复制的秘
密共享，每一方持有两个秘密份额)的形式。

[0142] 为简单起见，在上面的介绍中，我们关注的是查询令牌中目标节点仅附带有单个谓词的情况。而对于目标节点附带多个谓词的情况，假设p个谓词， 可以首先分别对每个候选节点评估每个谓词，输出不同的评估结果 之后 可以根据所指定的布尔表达式灵活地聚合评估结果。例如，如果 要求候选节点Vc需要满足所有谓词，则 可以安全地聚合评估结果 如果 仅要求候选
节点Vc满足其中一个的谓词，则 可以安全地聚合评估结果
即，所述第一计算终端、所述第二计算终端和所述第三计算终端根据自身持有的所述目标候选节点的所述目标属性的属性值是否满足所述目标子图节点的目标属性查询谓词的判断结果的复制秘密共享份额获取所述目标候选节点是否为所述目标子图节点的匹配节点的判断结果的复制秘密共享份额，包括：

[0143] 当所述目标子图节点的属性查询谓词只有一个时，直接将所述目标候选节点的所述目标属性的属性值是否满足所述目标子图节点的目标属性查询谓词的判断结果的复制秘密共享份额作为所述目标候选节点是否为所述目标子图节点的候选节点的判断结果的复制秘密共享份额；

[0144] 当所述目标子图节点的属性查询谓词有多个时，根据指定的布尔表达式聚合所述目标候选节点的所述目标属性的属性值是否满足所述目标子图节点的目标属性查询谓词的判断结果的复制秘密共享份额，得到所述目标候选节点是否为所述目标子图节点的候选节点的判断结果的复制秘密共享份额。

[0145] S500、所述第一计算终端、所述第二计算终端和所述第三计算终端基于本地持有的所述目标子图节点的每个候选节点是否为匹配节点的判断结果的复制秘密共享份额，获取目标数据的复制秘密共享份额，所述目标数据包括所述目标子图节点的匹配节点的节点ID和属性值的复制秘密共享份额。

[0146] 当 已经获得每个候选节点Vc的评估结果 之后， 需要从 中取回所有的匹配节点。所谓匹配节点就是 的候选节点。这里，表示所有的匹配节点为集合{Vm}。一种简单的方法是让 公开每个候选节点的评估结果 然而这会导致访
问模式的泄漏，因为这样 就知道哪些节点是匹配节点了。因此在本实施例中设计了模块secFetch，展示在如图6所示的算法3中，其可以让 从候选节点中获取匹配节点的信息而不知道哪些候选节点是匹配节点。下面介绍具体的设计。

[0147] 需要获取匹配节点{Vm}的 和属性值 而不知道哪些候选节点是匹配节点。这里有两种情况需要分开处理：

[0148] 情况I：仅有一个候选节点是匹配节点。这种情况对应于目标节点Vi∈tokq所附带的目标属性是唯一的，例如目标属性是ID或者Phone number，这些属性在整个属性图中都具有唯一性。

[0149] 情况II：两个或多个候选节点是匹配节点。这种情况对应于目标节点Vi∈tokq所附带的目标属性不是唯一的，例如目标属性是年龄，因为可以有不同的人有一样的年龄。

[0150] 计算终端可以通过目标属性的类型区分以上两种情况，因为目标属性的类型信息是公开的。

[0151] 对于第一种情况：

[0152] 所述第一计算终端、所述第二计算终端和所述第三计算终端基于本地持有的所述目标子图节点的每个候选节点是否为匹配节点的判断结果的复制秘密共享份额，获取目标数据的复制秘密共享份额，包括：

[0153] 当所述目标子图节点的候选节点中只有一个节点为匹配节点时：

[0154] 所述第一计算终端、所述第二计算终端和所述第三计算终端将本地持有的所述目标子图节点的每个候选节点是否为匹配节点的判断结果的复制秘密共享份额与其节点ID的复制秘密共享份额进行求与操作之后，将所有的求与操作结果进行异或操作，得到匹配节点的节点ID的复制秘密共享份额；

[0155] 所述第一计算终端、所述第二计算终端和所述第三计算终端将本地持有的所述目标子图节点的每个候选节点是否为匹配节点的判断结果的复制秘密共享份额与其属性值的复制秘密共享份额进行求与操作之后，将所有的求与操作结果进行异或操作，得到匹配节点的节点ID的复制秘密共享份额。

[0156] 当仅有一个候选节点是匹配节点时，让 将每个候选节点Vc的评估结果与其 和 进行AND(即求 “与”)，之后对所有的AND结果进行异或 则可以获得
仅有的一个匹配节点的 和属性值 上述过程可以形式化地描述为：

[0157]

[0158]

[0159] 其中C是候选节点的数量。上述公式的正确性是由于仅有一个候选节点的评估结果 而其他节点则是 所有仅有匹配节点的信息被保留下来。

[0160] 对于第二种情况：

[0161] 所述第一计算终端、所述第二计算终端和所述第三计算终端基于本地持有的所述目标子图节点的每个候选节点是否为匹配节点的判断结果的复制秘密共享份额，获取目标数据的复制秘密共享份额，包括：

[0162] 当所述目标子图节点的候选节点中有两个及两个以上的节点为匹配节点时：

[0163] 所述第一计算终端、所述第二计算终端和所述第三计算终端均在本地生成第一表格，所述第一表格中的每一行由本地持有的所述目标子图节点的每个候选节点是否为匹配节点的判断结果的复制秘密共享份额、所述目标子图节点的每个候选节点的节点ID的复制秘密共享份额、所述目标子图节点的每个候选节点的属性值的复制秘密共享份额组成；

[0164] 所述第一计算终端、所述第二计算终端和所述第三计算终端基于安全的置乱技术协作地随机排列所述第一表格中的行并更新本地持有的所述目标子图节点的每个候选节点是否为匹配节点的判断结果的复制秘密共享份额、所述目标子图节点的每个候选节点的节点ID的复制秘密共享份额、所述目标子图节点的每个候选节点的属性值的复制秘密共享份额，以使得所述第一计算终端、所述第二计算终端和所述第三计算终端均在本地持有第一置乱表格，所述第一置乱表格中的每一行由本地持有的所述目标子图节点的每个候选节点是否为匹配节点的判断结果的更新后的复制秘密共享份额、所述目标子图节点的每个候选节点的节点ID的更新后的复制秘密共享份额、所述目标子图节点的每个候选节点的属性值的更新后的复制秘密共享份额组成；

[0165] 所述第一计算终端、所述第二计算终端和所述第三计算终端分别公开自身持有的所述第一置乱表格中所述目标子图节点的每个候选节点是否为匹配节点的判断结果的复制秘密共享份额的一列，以使得所述第一计算终端、所述第二计算终端和所述第三计算终端获取所述目标子图节点的匹配节点的节点ID和属性值的复制秘密共享份额。

[0166] 当所述目标子图节点的候选节点中可能有两个或两个以上节点为匹配节点时，首先让计算终端安全地打乱候选节点的加密信息 其中“||”比特串拼接。这里使用的是安全的置乱技术(secret shuffle)。具体的，给定一个秘密共享的数据库(命名为表格table，每一条记录 是该表格中的一行，其可以表示一个候选
节点的加密的信息 )，安全的置乱技术允许持有该表格的云服务器
协作地随机重新排列表格中的每一行，输出加密的置乱后的表格 而云服务
器 不知道具体的排列π(·)是什么。值得说明的是，在置乱后，行间排列顺序被打乱，但是行内的排列逻辑并不会改变，也就是说，假设置乱前每一行的排列为
那么置乱后，每一行的排列仍为 但是置乱后的表
格中的 的数值发生了变化，即秘密共享份额被更新，例如，置乱前的
一行为0||001||110，置乱后的一行为1||010||101，但是，同一数据对应的秘密共享份额对应出的明文数据没有改变，也就是说，采用置乱前的表格进行数据恢复得到的明文数据与采用置乱后的表格进行数据恢复得到的明文数据相同。后面还会用到该技术，所以封装该技术为 由于该技术打乱了原始的候选节点信息
的顺序，所以 可以直接公开每个候选节点的 从而判断哪些候选节点是匹配的
节点。

[0167] 公开后，每个计算终端都持有明文的 交由每个计算中终端自己判断候选节点Vc是不是匹配节点，公开后如果 计算终端就知道Vc是匹配节点了，在这个公开过程中， 并不知道哪些候选节点是匹配节点，因为节点的顺序已经随机排列过了，访问模式不会被泄露。计算终端可以读取所述第一置乱表格中 的那一行的 和这样就使得所述第一计算终端、所述第二计算终端和所述第三计算终端获取所述目标子图节点的匹配节点的节点ID和属性值的复制秘密共享份额。

[0168] S600、所述第一计算终端、所述第二计算终端和所述第三计算终端基于本地持有的所述目标子图节点的每个匹配节点的节点ID的复制秘密共享份额、每个候选节点的倒排表的复制秘密共享份额以及目标匹配节点的节点ID，获取下一个子图节点的候选节点的复制秘密共享份额。

[0169] 当 已经获得每个匹配节点Vm的 之后， 需要获取每个匹配节点的邻居节点的信息，这些信息将被用于tokq中下一跳节点的候选节点。将每个匹配节点的所有邻居节点表示为{Vne}。

[0170] 所述第一计算终端、所述第二计算终端和所述第三计算终端基于本地持有的所述目标子图节点的每个匹配节点的节点ID的复制秘密共享份额、每个候选节点的倒排表的复制秘密共享份额以及目标匹配节点的节点ID，获取下一个子图节点的候选节点的复制秘密共享份额，包括：

[0171] 所述第一计算终端、所述第二计算终端和所述第三计算终端在本地均执行如下操作：

[0172] 获取所述目标子图节点的第c个候选节点的第一倒排表中的一个节点ID的复制秘密共享份额与目标匹配节点的节点ID的复制秘密共享份额中的第c位比特进行与运算，得到第三与运算结果，将各个所述第三与运算结果进行异或操作进行聚合，得到所述目标匹配节点的所述第一倒排表中一个节点ID的复制秘密共享份额，其中，所述第一倒排表对应的节点类型为下一个子图节点的节点类型；

[0173] 对所述目标匹配节点的所述第一倒排表中每个节点ID的复制秘密共享份额中的每个比特执行异或操作，得到所述目标匹配节点的所述第一倒排表中每个节点ID是否为虚假节点ID的判断结果的复制秘密共享份额；

[0174] 基于所述目标匹配节点的所述第一倒排表中每个节点ID是否为虚假节点ID的判断结果的复制秘密共享份额在所述第一倒排表的复制秘密共享份额中剔除虚假节点ID的复制秘密共享份额；

[0175] 基于本地持有的所述目标子图节点的候选节点的属性值的复制秘密共享份额和所述目标子图节点的每个匹配节点的所述第一倒排表中的节点ID的复制秘密共享份额获取下一个子图节点的候选节点的所述目标属性的属性值的复制秘密共享份额。

[0176] 本实施例提供的模块secAccess，展示在如图7所示的算法4中，其让 安全地获取每个匹配节点的邻居节点。具体的， 需要安全地获取{Vne}的IDs： 和属性值 而不知道他们是 和的哪一些节点。

[0177] 首先介绍 如何利用Vm的加密的 安全地获取每个匹配节点Vm的邻居节点的 注意到邻居节点{Vne}的类型是Tne，即查询令牌tokq中下一跳的节点
的类型。因此，Vm的类型为Tne的倒排表 包含所需要的邻居节点的IDs： 所以
需要从所有候选节点{Vc}的加密的倒排表 中安全地检索每个匹配节点Vm的
倒排表 具体的，让 安全地将每一个候选节点Vc，c∈[C](C是候选节点的数量)
的倒排表 与Vm的加密的ID中对应的一位 进行AND(即求 “与”)，即第c个候
选节点的倒排表与Vm的加密的ID中的第c位进行AND操作。之后将所有的AND操作的结果通过异或 进行聚合从而获得匹配节点Vm的倒排表 具体操作可以形式化描述为：

[0178]

[0179] 其中 表示Vc的倒排表 中的第l个ID，Lmax表示所有候选节点的倒排表的最大长度。正确性分析：由于Vm的ID被编码成独热向量的形式，其包含的唯一的一个元素1对应于匹配节点Vm所在的位置，所以仅有匹配节点Vm的倒排表 将被保留下来。

[0180] 然而，由于不同的候选节点的倒排表的长度不同，同时在加密属性图时为了获得k‑自同构的属性图一些倒排表被加入了一些假ID，所以上述方法获得的 中包含一些虚假的节点ID，需要进行剔除。这些虚假的节点ID都是全0向量，所以 首先本地异或中的每个比特。 是一个向量，异或向量中的每个比特是将向量中的每个比特相互异或，比如 可以表示为公式：

[0181]

[0182] 其中X是 的长度，其对应 中类型为Tne节点的数量。 则表示 是一个0向量，即假的ID。之后，一种简单的方法是让 公开计算结果 从而判断哪些ID是假的。然而，这种简单的方法可能泄漏搜索模式，因为相同的查询必定获得相同的公开结果

[0183] 针对这个问题，我们的解决方式是首先让 将 旨作是一个表格，其中每个 是表格中的一行数据，之后让 利用上述安全的置乱技术随机排列这个表
格，再公开 以剔除假的IDs从而保扩搜索模式。

[0184] 具体地，所述第一计算终端、所述第二计算终端和所述第三计算终端基于所述目标匹配节点的所述第一倒排表中每个节点ID是否为虚假节点ID的判断结果的复制秘密共享份额在所述第一倒排表的复制秘密共享份额中剔除虚假节点ID的复制秘密共享份额，包括：

[0185] 所述第一计算终端、所述第二计算终端和所述第三计算终端均在本地生成第二表格，所述第二表格中的每一行包括本地持有的所述第一倒排表中一个节点ID的复制秘密共享份额和该节点ID是否为虚假节点ID的判断结果的复制秘密共享份额；

[0186] 所述第一计算终端、所述第二计算终端和所述第三计算终端基于安全的置乱技术协作地随机排列所述第二表格中的行并更新本地持有的所述第一倒排表中一个节点ID的复制秘密共享份额和该节点ID是否为虚假节点ID的判断结果的复制秘密共享份额，以使得所述第一计算终端、所述第二计算终端和所述第三计算终端均在本地持有第二置乱表格，所述第二置乱表格中的每一行由本地持有的所述第一倒排表中一个节点ID的更新后的复制秘密共享份额和该节点ID是否为虚假节点ID的判断结果的更新后的复制秘密共享份额组成；

[0187] 所述第一计算终端、所述第二计算终端和所述第三计算终端公开本地持有的所述第二置乱表格中节点ID是否为虚假节点ID的判断结果的复制秘密共享份额的一列，以使得所述第一计算终端、所述第二计算终端和所述第三计算终端剔除虚假ID的复制秘密共享份额。

[0188] 之后， 应该安全地获取每个邻居节点Vne的加密的属性值 所述基于本地持有的所述目标子图节点的候选节点的属性值的复制秘密共享份额和所述目标子图节点的每个匹配节点的所述第一倒排表中的节点ID的复制秘密共享份额获取下一个子图节点的候选节点的所述目标属性的属性值的复制秘密共享份额，包括：

[0189] 将本地持有的所述目标子图节点的第x个候选节点的所述目标属性的属性值的复制秘密共享份额与下一个子图节点的第一候选节点的第x个比特进行与操作，得到第四与运算结果，将各个所述第四与运算结果进行异或操作，得到所述第一候选节点的所述目标属性的属性值的复制秘密共享份额。

[0190] 具体的， 首先从 本地检索所有候选节点的属性值 之后再将每个 和比特 进行AND操作(即求 ‘与”)，之后异或 听有AND操作的
输出从而获得邻居节点Vne的属性值 上述过程可以正式地描述为：

[0191]

[0192] 到目前为止 已经可以安全地获得所有邻居节点{Vne}的 和属性值 而不知道他们是 中的哪一个节点。最后，这些信息分别被用于tokq中下
一跳目标节点的候选节点的信息 和 从而进行下一跳的目标节点的匹配。

[0193] S700、所述第一计算终端、所述第二计算终端和所述第三计算终端根据所述子图查询的公共结构将本地持有的每个子图节点的所述目标数据重新组织成候选子图，在所述候选子图中删除与所述子图查询数据中的结构不完全相同的子图，分别输出子图匹配结果的复制秘密共享份额。

[0194] 具体地，考虑两个图 和 虽然它们的部分图，即 可以匹配彼此，但是剩下的节点却不能互相匹配，所以它们两个也不算相互匹配的。因为本实施例提供的方法是逐个节点搜索的，所以会存在上述情况，也即是子图中开始几个节点是与查询图匹配的，但是后面的节点却是不匹配的。但是直到遍历所有节点之前，计算终端是不知道这些情况的。所以需要在遍历完整个大图之后，看哪些子图是不完整的。查询图的结构是公开的，所以在最后计算终端可以根据这个结构重新组织这些加密的匹配节点，判断哪些节点组成的子图是不完整的，从而删除这些子图。

[0195] 综上所述，本实施例提供一种隐私保护的子图匹配方法，在该方法中，对属性图数据，将每个属性图节点本身的节点ID以及属性值编码为独热向量，同时对每个属性图节点的邻居节点的节点ID编码为独热向量并按照不同的节点类型组成倒排表，在倒排表中加入虚假节点ID，将属性图数据通过复制秘密共享的方式进行加密后分发至三个计算终端进行云计算，并且还进一步地采用属性查询谓词的独热向量中非0数值的位置，生成三对函数秘密共享秘钥对，并组成三个加密令牌，分别分发至三个计算终端，三个计算终端基于自身持有的复制秘密共享份额和加密令牌进行子图匹配，使得计算终端在不获得各种关于属性图以及子图查询隐私信息的情况下，有效地在加密的属性图上执行子图匹配任务，实现了隐私保护的子图匹配。

[0196] 应该理解的是，虽然本发明说明书附图中给出的的流程图中的各个步骤按照箭头的指示依次显示，但是这些步骤并不是必然按照箭头指示的顺序依次执行。除非本文中有明确的说明，这些步骤的执行并没有严格的顺序限制，这些步骤可以以其它的顺序执行。而且，流程图中的至少一部分步骤可以包括多个子步骤或者多个阶段，这些子步骤或者阶段并不必然是在同一时刻执行完成，而是可以在不同的时刻执行，这些子步骤或者阶段的执行顺序也不必然是依次进行，而是可以与其它步骤或者其它步骤的子步骤或者阶段的至少一部分轮流或者交替地执行。

[0197] 本领域普通技术人员可以理解实现上述实施例方法中的全部或部分流程，是可以通过计算机程序来指令相关的硬件来完成，所述的计算机程序可存储于一非易失性计算机可读取计算机可读存储介质中，该计算机程序在执行时，可包括如上述各方法的实施例的流程。其中，本发明所提供的各实施例中所使用的对存储器、存储、数据库或其它介质的任何引用，均可包括非易失性和/或易失性存储器。非易失性存储器可包括只读存储器(ROM)、可编程ROM(PROM)、电可编程ROM(EPROM)、电可擦除可编程ROM(EEPROM)或闪存。易失性存储器可包括随机存取存储器(RAM)或者外部高速缓冲存储器。作为说明而非局限，RAM以多种形式可得，诸如静态RAM(SRAM)、动态RAM(DRAM)、同步DRAM(SDRAM)、双数据率SDRAM(DDRSDRAM)、增强型SDRAM(ESDRAM)、同步链路(Synchlink)DRAM(SLDRAM)、存储器总线(Rambus)直接RAM(RDRAM)、直接存储器总线动态RAM(DRDRAM)、以及存储器总线动态RAM(RDRAM)等。

[0198] 实施例二

[0199] 基于上述实施例，本发明还相应提供了一种隐私保护的子图匹配系统，所述系统包括所述系统包括受信终端、第一计算终端、第二计算终端和第三计算终端；所述受信终端、第一计算终端、第二计算终端和第三计算终端用于协同执行实施例一中隐私保护的子图匹配方法中的相关步骤。

[0200] 最后应说明的是：以上实施例仅用以说明本发明的技术方案，而非对其限制；尽管参照前述实施例对本发明进行了详细的说明，本领域的普通技术人员应当理解：其依然可以对前述各实施例所记载的技术方案进行修改，或者对其中部分技术特征进行等同替换；而这些修改或者替换，并不使相应技术方案的本质脱离本发明各实施例技术方案的精神和范围。