[發明專利]最短路徑的隱私保護處理方法及裝置

有效

• 申請號: 202011426818.1
• 申請日: 2020-12-09
• 公開（公告）號: CN112565081B
• 公開（公告）日: 2022-09-13
• 發明（設計）人: 張翰林;趙哲群;李新亮
• 申請（專利權）人: 青島大學
• 主分類號: H04L45/12
• 分類號: H04L45/12;H04L9/40;H04L67/10;G06F21/62
• 代理公司: 北京集佳知識產權代理有限公司 11227
• 代理人: 張春輝

1.一種最短路徑的隱私保護處理方法，其特征在于，基于云服務器，該方法包括：

用戶端將用于計算最短路徑的Dijkstra算法上傳至云服務器；

將待處理的節點圖作為輸入數據進行盲化處理，得到盲化輸入數據；

將所述盲化輸入數據發送給所述云服務器，以便所述云服務器在接收到所述盲化輸入數據后調用所述Dijkstra算法進行最短路徑計算；

接收所述云服務器返回的計算結果，作為盲化計算結果；

對所述盲化計算結果進行驗證；

若通過驗證，對所述盲化計算結果進行恢復，得到期望計算結果；

若未通過驗證，輸出錯誤提示信息；

所述將待處理的節點圖作為輸入數據進行盲化處理，得到盲化輸入數據，包括：

建立二維數組存儲上述待處理的節點圖中節點間的關系，得到矩陣；

在所述矩陣中隨機選擇若干對有路徑的節點，作為目標節點對；

在所述目標節點對的直連接線中確定一個節點，作為新增節點；

增加若干條所述新增節點和與所述目標節點對間有路徑的節點之間的路徑，作為新增路徑；

或者：

建立二維數組存儲上述待處理的節點圖中節點間的關系，得到矩陣；

在所述矩陣中刪除所述待處理的節點圖中度為1的若干節點；

將刪除的度為1的節點與其后繼節點的距離加到其他與上述后繼節點相連的路徑上；

記錄上述刪除的度為1的節點與其后繼節點的前后關系以及路徑長度；

或者：

建立二維數組存儲上述待處理的節點圖中節點間的關系，得到矩陣；

確定所述矩陣中度為2的若干節點，作為待刪除節點；

判斷所述待刪除節點與其后繼節點之間是否存在路徑；

若存在，判斷所述待刪除節點到其后繼節點的距離之和是否大于所述后繼節點之間的距離；

若不大于，刪除所述待刪除節點，并用所述待刪除節點到其所述后繼節點的距離之和代替所述后繼節點之間路徑的值，記錄所述待刪除節點為離所述待刪除節點最近的節點的前驅節點，并且記錄所述待刪除節點到其所述后繼節點的距離；

若大于，刪除所述待刪除節點，記錄所述待刪除節點為距離它最近的后繼節點的前驅節點，并且記錄所述待刪除節點到其所述后繼節點的距離；

若不存在，刪除所述待刪除節點，并將所述待刪除節點與其上述后繼節點之間的距離之和賦值給其所述后繼節點之間的路徑，記錄所述待刪除節點為距離它最近的所述后繼節點的前驅節點，并且記錄所述待刪除節點到其所述后繼節點的距離。

2.如權利要求1所述的最短路徑的隱私保護處理方法，其特征在于，對所述盲化計算結果進行驗證，包括：

隨機選取若干個節點，作為驗證節點；

計算所述驗證節點到所述盲化輸入數據中其他節點的距離，作為驗證值；

比較所述盲化計算結果與所述驗證值是否相同；

若不相同，判定驗證未通過；

若相同，判定驗證通過。