[發明專利]一種面向加密圖的帶約束近似最短距離查詢方法

有效

• 申請號: 201710436415.7
• 申請日: 2017-06-12
• 公開（公告）號: CN107291861B
• 公開（公告）日: 2020-05-12
• 發明（設計）人: 沈蒙;馬寶利;祝烈煌
• 申請（專利權）人: 北京理工大學
• 主分類號: G06F16/901
• 分類號: G06F16/901;G06F16/903;H04L9/08
• 代理公司: 北京理工正陽知識產權代理事務所(普通合伙) 11639
• 代理人: 鮑文娟

本發明提出一種面向加密圖的帶約束近似最短距離查詢方法。帶約束最短距離查詢是一種基本的圖查詢原語，它在給定起始源點、目的地點以及代價閾值，在圖上查找從起始源點到目的地點的不超過代價閾值的最短距離。本發明提出的方法利用了一種基于樹的密文比較協議，并且充分利用了對稱密碼學原語，使之非常高效。通過使用該發明，圖擁有者能夠在圖數據外包到云端服務器之前，首先對圖數據進行加密來保障其數據隱私，而后，能夠在加密圖上進行帶約束最短距離查詢。

技術領域

本發明涉及一種面向加密圖的帶約束近似最短距離查詢方法，屬于云計算安全領域。

背景技術

近年來，基于圖結構的應用蓬勃發展，如在線社交網絡圖、城市道路交通圖、web圖、生物網絡圖以及通信網絡圖。因此，在工業界和學術界產生了諸多管理、查詢、分析圖數據的系統。同時，隨著云計算的發展，圖數據持有者期望將圖數據外包到云端，以節約本地的存儲和計算成本。然而，由于云服務器不可信，這帶來了嚴重的隱私問題，因為云端服務器能夠竊取用戶的圖數據敏感信息。為了克服這種隱私泄露問題，一種直觀的解決方案是首先將圖數據進行加密，然后再將其外包到云端服務器。然而不幸的是，加密操作使得圖數據的有效利用成為了一個棘手的難題，因為在加密數據上很難執行在明文圖上的一些查詢操作。

最短距離查詢作為一種最基本的圖查詢操作，它在給定源點和目的地點時，在圖上尋找兩點之間的最短距離。目前，已經有不少有價值的工作能夠支持在圖上執行隱私保護的最短距離查詢操作。這些方法通常采用了一種新穎的被稱為距離預言機的數據結構來回答任意兩個圖頂點的查詢。

然而，在實際應用中，用戶通常在進行最短距離查詢時需要考慮其他額外的約束。例如，在城市交通道路上，用戶期望知道在交通費不超過一定限額時，從當前位置到目的地點的最短交通時間(或最短交通距離)。這種問題可以被歸類到帶約束的最短距離查詢問題。在帶約束最短距離查詢方面已經都大量的研究工作，不過這些工作全部關注于非加密圖上的查詢。這些方法在執行帶約束最短距離查詢時涉及到諸多復雜操作，倘若這些操作不經過特殊的設計，則無法應用到加密圖上。此外，針對已存在的加密圖上的最短距離查詢方案，由于其不能在云服務器端執行代價約束過濾操作，因此也不能夠應用到帶約束最短距離查詢的語境中。

發明內容

為了實現加密圖上的帶約束最短距離查詢，本發明充分利用了對稱密碼學技術，在很好的保證了查詢的高效性的同時完整的給出了在加密圖上進行帶約束最短距離查詢的方法。

本發明關注的圖為有向圖，具有一個頂點集和邊集。每一條邊具有兩個權重，為了后續描述方便，現考慮一個權重為距離，另外一個權重為代價，也即約束條件。帶約束最短距離查詢就是尋找兩點之間，滿足代價約束的最短距離。

本發明關聯的系統模型涉及兩個實體對象：用戶和云服務器。

本發明的核心工作流程如下：

步驟1：用戶端建立安全的圖索引。

步驟1.1預先通過已有的方法對輸入圖建立非加密兩跳覆蓋標簽索引。

非加密的圖索引包含兩部分，一部分是out_label標簽集，一部分是in_label標簽集。對于每一個頂點u，都關聯一個out_label標簽集合和一個in_label標簽集合。out_label標簽集合中的元素(頂點υ，距離d，代價c)對象表示從頂點u到頂點υ的距離為d，代價為c。in_label標簽集合中的元素(頂點υ，距離d，代價c)對象表示從頂點υ到頂點u的距離為d，代價為c。

步驟1.2給定安全參數，隨機生成兩個二進制比特串作為安全的加密密鑰K₁和K₂。