[發明專利]基于向量同態加密的隱私保護k-means聚類方法

在審

• 申請號: 201910451996.0
• 申請日: 2019-05-28
• 公開（公告）號: CN110163292A
• 公開（公告）日: 2019-08-23
• 發明（設計）人: 張小松;何偉超;牛偉納;劉憲;趙藝賓;任仲蔚
• 申請（專利權）人: 電子科技大學
• 主分類號: G06K9/62
• 分類號: G06K9/62;H04L9/00
• 代理公司: 成都智言知識產權代理有限公司 51282
• 代理人: 濮云杉

本發明涉及基于向量同態加密的隱私保護k?means聚類方法，包括：A.客戶端接收待聚類向量組；B.通過向量同態加密的方法對所述待聚類向量組進行加密，在加密過程中保留密鑰交換矩陣M和比特擴展矩陣W，加密后得到密文向量組；C.根據通過AM＝W得到矩陣A，定義中間矩陣H＝A^TA；D.將中間矩陣H與密文向量組傳送至聚類服務器進行聚類分析，將密文向量組中的每一個向量附上聚類標簽；E.聚類服務器將完成聚類分析的密文向量組發送回客戶端解密，根據各個向量的標簽組合得到聚類結果。本發明解決了密文數據云傳輸的安全性問題，保證了數據的隱私可靠性，同時還提高了對向量類型判斷的效率，擴大了向量類型判斷的應用范圍。

技術領域

本發明涉及k-means聚類算法在隱私保護下的向量聚類方法，具體的講是基于向量同態加密的隱私保護k-means聚類方法。

背景技術

k-means聚類方法(k means clustering)原本是一種信號處理方法，后來被廣泛應用在數據挖掘中。k-means聚類方法的目的是將n個觀測值根據相應的規則劃分為k個簇，其中每個觀測值都以最小的均值隸屬于對應簇中，最終的結果是將一個空間劃分為多個小空間。這個問題是一個NP-hard問題，但是很多高效的啟發式算法可以讓待優化函數收斂到局部最優解。這些通常類似于通過高斯混合模型的迭代方法來求解最優解，它們都使用模型數據的聚類中心。k-means聚類方法的核心在于度量向量到聚類中心的距離。這在明文下是非常容易辦到的，但在密文下卻是非常困難。密文下度量兩個向量之間的相似性一直都是一個非常困難的問題。

發明內容

針對現有技術中存在的將k-means聚類分析遷移至云服務器后產生的數據隱私泄露的問題，本發明提供了一種基于向量同態加密的隱私保護k-means聚類方法，以使隱私數據在云傳輸后具有高安全性。

本發明基于向量同態加密的隱私保護k-means聚類方法，包括：

A.客戶端接收待聚類向量組(x₁,x₂,…x_n)，待聚類向量組(x₁,x₂,…x_n)由n個待聚類的樣本構成，其中n為正整數；

B.通過向量同態加密的方法對所述待聚類向量組(x₁,x₂,…x_n)進行加密，并且在加密過程中保留密鑰交換矩陣M和比特擴展矩陣W，加密后得到密文向量組(c₁,c₂,…,c_n)；

C.根據所述的密鑰交換矩陣M和比特擴展矩陣W，通過AM＝W，計算得到矩陣A，并且定義中間矩陣H＝A^TA，其中T為隨機矩陣；

D.將所述的中間矩陣H與密文向量組(c₁,c₂,…,c_n)傳送至聚類服務器進行聚類分析，并將密文向量組(c₁,c₂,…,c_n)中的每一個向量附上聚類標簽；

E.聚類服務器將完成聚類分析的密文向量組(c₁,c₂,…,c_n)發送回客戶端，由客戶端使用密鑰矩陣S1進行解密，根據各個向量的標簽組合得到聚類結果。

具體的，步驟B中所述的向量同態加密，包括：

B1.生成隨機矩陣T，隨機矩陣T中的每個元素都為計算機生成的隨機數，同時生成大整數w及整數l，大整數w＞＞隨機矩陣T中的任一元素，并且2^l大于待聚類向量組(x₁,x₂,…x_n)中的任一元素；