[發明專利]一種隱私保護的子圖匹配方法及系統

有效

• 申請號: 202210579666.1
• 申請日: 2022-05-26
• 公開（公告）號: CN114969406B
• 公開（公告）日: 2023-03-14
• 發明（設計）人: 鄭宜峰;王松磊
• 申請（專利權）人: 哈爾濱工業大學（深圳）
• 主分類號: G06F16/532
• 分類號: G06F16/532;G06F21/62
• 代理公司: 深圳市君勝知識產權代理事務所(普通合伙) 44268
• 代理人: 陳專;李曉鳳

本發明公開了一種隱私保護的子圖匹配方法及系統，本發明提供的方法中，將每個屬性圖節點本身的節點ID以及屬性值編碼為獨熱向量，同時對每個屬性圖節點的鄰居節點的ID編碼為獨熱向量并按照不同的節點類型組成倒排表，在倒排表中加入0向量作為虛假節點ID，將屬性圖數據通過復制秘密共享的方式進行加密后分發至三個計算終端進行計算，并且還采用屬性查詢謂詞對應的目標值的獨熱向量中非0數值的位置，生成三對函數秘密共享秘鑰對，組成三個加密令牌，分發至三個計算終端，三個計算終端基于自身持有的復制秘密共享份額和加密令牌進行子圖匹配，使得計算終端在不獲得關于屬性圖以及子圖查詢隱私信息的情況下，在加密的屬性圖上進行子圖匹配。

技術領域

本發明涉及信息安全技術領域，特別涉及一種隱私保護的子圖匹配方法及系統。

背景技術

屬性圖(attributed graphs)是一種圖數據模型，已被廣泛用于建模各種場景中實體之間的交互，如社交網絡和金融交易網絡等。隨著云計算的發展，越來越多的企業利用云計算存儲其屬性圖，以及在屬性圖上執行各種各樣的查詢。雖然云計算的優勢是眾所周知的，但在公共商業云中部署這些圖分析服務會對信息豐富的屬性圖數據的隱私造成嚴重威脅，而且這可能不符合這些企業的商業利益，因為這些圖數據是其專有的數據財富。因此，迫切需要在這類云環境中設計安全性保障協議，為外包的屬性圖數據的存儲和查詢提供隱私保護。

子圖匹配(subgraph matching)是屬性圖查詢中最基本的功能之一，其旨在從一個大的屬性圖中檢索所有與給定小查詢圖同構的子圖。子圖匹配在各種應用中都是一個強有力的工具，例如反洗錢、化合物的搜索以及社交網絡分析等。一個具體的例子是，從一張大的社交網絡圖中檢索所有與給定的用戶社交圈(ego-network)同構的所有社交圈。不同于常規非屬性圖的子圖匹配僅考慮結構化匹配，面向屬性圖的子圖匹配是更復雜的，因為它額外考慮匹配圖節點的屬性和類型。

當前，考慮隱私的圖查詢協議設計是一個熱點研究問題。然而，大多數現有的工作都聚焦于處理與子圖匹配不同的圖查詢功能，如隱私保護的最短路徑搜索和隱私保護的廣度優先遍歷。還沒有涉及面向屬性圖的隱私保護的子圖匹配的現有技術。

因此，現有技術還有待改進和提高。

發明內容

針對現有技術的上述缺陷，本發明提供一種隱私保護的子圖匹配方法及系統，旨在解決現有技術中沒有在設計面向屬性圖的隱私保護的子圖匹配的方案的問題。

為了解決上述技術問題，本發明所采用的技術方案如下：

本發明的第一方面，提供一種隱私保護的子圖匹配方法，所述方法包括：

受信終端對屬性圖數據進行加密，基于復制秘密共享生成所述屬性圖中每個屬性圖節點的自身信息和鄰居節點信息分別對應的三份復制秘密共享份額，分別發送給第一計算終端、第二計算終端和第三計算終端，其中，目標屬性圖節點的所述自身信息包括所述目標屬性圖節點的節點類型，所述目標屬性圖節點的節點ID對應的獨熱向量以及所述目標屬性圖節點的每種屬性的各個屬性值對應的獨熱向量，所述目標屬性圖節點的所述鄰居節點信息包括多個倒排表，所述多個倒排表中的目標倒排表中包括所述目標屬性圖節點的鄰居節點中具有目標類型的各個節點的節點ID對應的獨熱向量以及所述目標屬性圖節點的虛假鄰居節點ID對應的獨熱向量，所述目標屬性圖節點的虛假鄰居節點ID對應的獨熱向量為0向量；

所述受信終端對子圖查詢數據進行加密，基于函數秘密共享生成每個子圖節點的每個屬性查詢謂詞對應的加密令牌，所述加密令牌包括第一加密令牌、第二加密令牌和第三加密令牌，分別發送給所述第一計算終端、所述第二計算終端和所述第三計算終端，其中，所述第一加密令牌、所述第二加密令牌和所述第三加密令牌中均包括所述子圖節點的節點類型，所述子圖節點的一個屬性以及秘鑰組中的兩個秘鑰，所述秘鑰組中包括三個秘鑰對，每個所述秘鑰對為基于所述子圖節點的一個屬性查詢謂詞對應的目標值的獨熱向量中非0數值的位置生成的函數秘密共享秘鑰對；