文章总结： 本文提出一种隐私保护图匹配查询方案，支持快速子图提取。通过两个非串谋云服务器CS1和CS2分别存储加密信息，利用度表剪枝和邻接矩阵验证构造matchedmatrix，用户端子图提取复杂度降为O(m²)。解决了已有方案只返回布尔结果、用户需重新执行子图同构的问题，提升了查询结果可用性。 综合评分： 84 文章分类： 数据安全,云安全,安全建设,解决方案

隐私保护图匹配查询：如何实现快速子图提取

原创

李萌 李萌

信息网络安全杂志

2026年7月13日 12:00 上海

在小说阅读器读本章

去阅读

引子：随着图数据库在社交网络、生物信息、化合物检测和犯罪关系分析等场景中的广泛应用，图匹配查询逐渐成为云端数据服务中的核心问题。然而，图数据往往包含高度敏感的信息，例如用户身份、社交关系、行为模式或生物结构特征，直接外包给云服务器会带来严重隐私泄漏风险。已有隐私保护图匹配方案虽然能够在加密图上判断“是否匹配”，但当用户想进一步定位并提取真正匹配的子图时，仍然需要在本地重新执行复杂的子图同构操作。由于子图同构本身是 NP-complete 问题，这使得所谓的隐私保护查询在最后一步又退回到了高开销、低可用的老路上。本文正是抓住了这一痛点：隐私保护图匹配不应只告诉用户“有没有”，更应让用户快速知道在哪里。

速览：本文提出了一种支持快速子图提取的隐私保护图匹配查询方案。其核心设计是引入两个非串谋云服务器CS1和CS2，将图的不同加密信息分别存储和处理：图所有者将度表、密钥矩阵、邻接矩阵等信息以不同形式加密后分发给两个云端，查询时由CS1根据加密度信息缩小候选范围，并进一步构造表示数据图顶点与查询图顶点对应关系的matched matrix；随后 CS1与CS2通过交互式矩阵运算验证该匹配矩阵的正确性。这样，用户拿到结果后不再需要重新求解子图同构，而是可以直接根据matched matrix 定位查询图中每个顶点在数据图中的对应顶点，从而恢复出同构子图。论文明确指出，该方案中用户端子图提取复杂度降为 O(m²)，其中 m 是查询图顶点数，相比已有方案中用户端必须执行复杂子图同构算法，效率优势非常明显。

深度解剖：这项工作的价值不只在于把计算交给云，而在于它重新定义了隐私保护图匹配的返回结果形态。以往方案往往把查询结果压缩成一个布尔判断或候选图集合，即只回答“该数据图是否包含查询图”，却没有返回足以支撑快速定位的结构化映射关系。本文的 matched matrix 则相当于在隐私保护条件下生成了一张加密世界中的结构对齐表，把图匹配从单纯的存在性判断推进到可提取、可验证、可恢复的阶段。更重要的是，该方案将 degree table 用于候选剪枝，将 adjacency matrix 用于结构验证，将双云模型用于分离敏感信息，使得计算效率、隐私保护和结果可用性三者形成了较清晰的分工。这种设计对于后续加密图查询研究很有启发意义：安全查询系统不能只追求云端能算，还要考虑用户拿到结果后能不能低成本使用。

局限：尽管该方案有效解决了匹配后子图提取效率低的问题，但其安全性仍然建立在两个云服务器非串谋且诚实但好奇的假设之上，一旦CS1与CS2出现串谋，分离存储和交互验证带来的隐私屏障可能会被削弱。此外，该方案主要面向静态图数据库中的精确子图匹配，对于动态图、带权图、属性丰富图以及近似匹配场景的支持仍不充分。论文虽然通过真实图数据库实验展示了效率优势，但在更大规模、更高动态图更新频率、以及更复杂标签/属性约束下的可扩展性仍有进一步验证空间。未来研究可以考虑将该思路扩展到动态图安全查询、可验证外包计算以及支持更复杂图语义的隐私保护匹配框架中。

启示：本文给图数据隐私保护研究提供了一个非常重要的提醒：查询结果的可用性本身也是安全系统设计的一部分。一个方案如果只能返回候选结果，却把最复杂的验证和提取任务留给用户，那么它在真实部署中仍然是不完整的。本文通过matched matrix 将云端匹配结果转化为用户可直接使用的结构映射，体现了从安全可计算走向安全可应用的设计思路。对于后续隐私保护图计算研究而言，如何在不泄露图结构与查询意图的前提下，让云端返回更可验证、更可恢复、更接近真实业务需求的结果，将是提升方案实用性的关键方向。

本人仅代表作者个人观点

本期点评论文

作者：陈毅飞、胡耀、吴梦、乔焰副教授、童秋云讲师、李萌（合肥工业大学计算机与信息学院数据安全与隐私保护领域）

原文标题：

Privacy-Preserving Graph Matching Query Supporting Quick Subgraph Extraction

原文作者：

Xinrui Ge、Jia Yu、Rong Hao

期刊/会议：

IEEE Transactions on Dependable and Secure Computing, Vol. 21, No. 3, May-June 2024

版权与来源声明：本文依据《中华人民共和国著作权法》第二十四条之规定，为介绍、评选之目的，在此适当引用。原文版权归原作者所有。

信息网络安全

《信息网络安全》创刊于2001年，是由公安部主管，公安部第三研究所、中国计算机学会主办，面向国内外公开发行的国内首批信息安全类期刊之一，于2015年成为中国科技核心期刊，2017年成为中国科学引文数据库来源期刊，2018年成为中文核心期刊，2022年入选CCF计算领域高质量科技期刊分级目录。

中文核心期刊

中国科技核心期刊

中国科学引文数据库来源期刊

CCF计算领域高质量科技期刊

我们在不断努力和完善中，期待您的关注和支持！

免责声明：

本文所载程序、技术方法仅面向合法合规的安全研究与教学场景，旨在提升网络安全防护能力，具有明确的技术研究属性。

任何单位或个人未经授权，将本文内容用于攻击、破坏等非法用途的，由此引发的全部法律责任、民事赔偿及连带责任，均由行为人独立承担，本站不承担任何连带责任。

本站内容均为技术交流与知识分享目的发布，若存在版权侵权或其他异议，请通过邮件联系处理，具体联系方式可点击页面上方的联系我。

本文转载自：信息网络安全杂志 李萌 李萌《隐私保护图匹配查询：如何实现快速子图提取》