[發明專利]一種安全求解圖的近似最小歸一化割的方法

在審

• 申請號: 202210067678.6
• 申請日: 2022-01-20
• 公開（公告）號: CN114429183A
• 公開（公告）日: 2022-05-03
• 發明（設計）人: 高鵬;魏萌萌
• 申請（專利權）人: 三未信安科技股份有限公司
• 主分類號: G06K9/62
• 分類號: G06K9/62;H04L9/08
• 代理公司: 北京首捷專利代理有限公司 11873
• 代理人: 梁婧宇

本發明提供了一種安全求解圖的近似最小歸一化割的方法，包括根據圖生成相應的度矩陣，鄰接矩陣以及拉普拉斯矩陣；生成一系列的初等變換矩陣；將關于圖的原始矩陣加密并發送給云服務器；云服務器對接收的矩陣進行譜分解，并返回結果給用戶；用戶驗證返回結果的正確性。驗證通過，則進行解密，恢復出原始的結果；執行K?means算法得到圖的近似最小歸一化割。本發明在保護隱私和確保結果的可驗證性的情況下，能夠有效求解圖的近似最小歸一化割問題。

技術領域

本發明涉及信息安全技術領域，具體涉及一種安全求解圖的近似最小歸一化割的方法。

背景技術

尋找一個大規模稠密圖的最小歸一化割是圖論里面一個基礎的問題，被廣泛地應用在圖像分割，社區發現以及網絡劃分中。例外，圖的歸一化割在機器學習領域也有著廣泛的應用。譜聚類算法就是基于圖的歸一化割，適合于對高維的數據進行聚類劃分。對于一個大規模稠密圖G(V,E)來說,它的歸一化割可以表示成以下形式：

其中A_i代表的是每一個子圖，代表著子圖和其補圖之間的權重，代表著每一個子圖的度的和,k代表子圖的數量。最小化Ncut(A₁,A₂,...,A_k)可以被轉化為下面的優化問題：

其中D是圖G(V,E)的度矩陣，L＝D-W是圖的拉普拉斯矩陣，其中W是圖的鄰接矩陣。

矩陣取F的值有k2ⁿ種可能。因此，求解一個圖的最小歸一化割是一個NP難問題。但是通過譜分解可以近似地解決這個問題。

對于一些資源受限的設備來說，沒有足夠的計算資源和存儲資源執行這項計算任務。然而云計算的出現，提供了一種切實可行的方法。資源受限的用戶可以將計算任務委派給一個具有強大計算能力的云服務器來完成。但是這種方法也帶來了一些問題：

云服務器并不被用戶信任，如何保護用戶數據的隱私性；

云服務器返回的結果可能是錯誤的，如何驗證返回結果的正確性。

因此，如何在保護隱私和確保結果的可驗證性的情況下，求解圖的近似最小歸一化割問題是當下急需解決的問題。

發明內容

有鑒于此，本發明基于隨機盲化技術設計了一個保護隱私的求解圖的近似最小歸一化割的方法，能夠有效保障用戶的隱私性。

為了實現上述目的，本發明采用如下技術方案：

一種安全求解圖的近似最小歸一化割的方法，包括如下步驟：

客戶端根據圖生成相應的度矩陣D，鄰接矩陣W以及拉普拉斯矩陣L＝D-W，得到關于圖的原始矩陣

客戶端生成初等密鑰矩陣P；

客戶端將所述原始矩陣利用初等密鑰矩陣P加密為并發送給云服務器，加密方式為：

其中μ和ν是兩個隨機實數，I為單位矩陣；

云服務器對接收的進行譜分解并返回譜分解結果和給客戶端，是一個加密的正交矩陣，是一個加密的對角矩陣；

客戶端驗證返回譜分解結果的正確性，驗證通過，則進行解密并將矩陣Q單位正交化，恢復出原始的結果Q和Λ：

Q的每一列都是矩陣B的特征向量；Λ對角線上的每一個元素λ_i都是矩陣B的特征值；

在矩陣Λ中，客戶端選擇前k個最小的特征值所對應的特征向量組成矩陣F；客戶端對矩陣F執行K-means算法得到圖的近似最小歸一化割。