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

在審

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

1.一種安全求解圖的近似最小歸一化割的方法，其特征在于，包括如下步驟：

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

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

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

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

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

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

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

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

2.根據權利要求1所述的安全求解圖的近似最小歸一化割的方法，其特征在于，初等密鑰矩陣P包括：

P＝P_a(n)...P_a(2)P_a(1)P_sP_m,

P_m是對角矩陣，由一個單位矩陣對其每一行或每一列的元素都相應的乘以隨機實數α_i得來，是其逆矩陣；P_s是由一個單位矩陣隨機地交換兩行或者兩列得到的，是其逆矩陣；P_a(1),P_a(2),...,P_a(n)中的每一個矩陣都是由一個單位矩陣的某一行或某一列乘以隨機實數β_i加到另一個行或者另一列上得到的，是其逆矩陣。

3.根據權利要求1所述的安全求解圖的近似最小歸一化割的方法，其特征在于，客戶端驗證返回譜分解結果的正確性的具體步驟包括：

客戶端從集合[2^-γ,2^γ]中選擇一個向量r，其中這個集合是由用戶自己定義的一個集合，γ是安全參數，客戶端驗證下列等式是否成立：

若成立，則進行解密。