[發(fā)明專利]基于向量同態(tài)加密的隱私保護(hù)k-means聚類方法

在審

• 申請?zhí)枺?/td>: 201910451996.0
• 申請日: 2019-05-28
• 公開（公告）號: CN110163292A
• 公開（公告）日: 2019-08-23
• 發(fā)明（設(shè)計(jì)）人: 張小松;何偉超;牛偉納;劉憲;趙藝賓;任仲蔚
• 申請（專利權(quán)）人: 電子科技大學(xué)
• 主分類號: G06K9/62
• 分類號: G06K9/62;H04L9/00
• 代理公司: 成都智言知識產(chǎn)權(quán)代理有限公司 51282
• 代理人: 濮云杉

1.基于向量同態(tài)加密的隱私保護(hù)k-means聚類方法，其特征包括：

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

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

C.根據(jù)所述的密鑰交換矩陣M和比特?cái)U(kuò)展矩陣W，通過AM＝W，計(jì)算得到矩陣A，并且定義中間矩陣H＝A^TA，其中T為隨機(jī)矩陣；

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

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

2.如權(quán)利要求1所述的基于向量同態(tài)加密的隱私保護(hù)k-means聚類方法，其特征為：步驟B中所述的向量同態(tài)加密，包括：

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

B2.設(shè)置密鑰矩陣S1＝[I,T]，其中I為單位矩陣，隨機(jī)矩陣T∈Z^m×m，Z為數(shù)學(xué)里表示所有整數(shù)的通用符，m×m為隨機(jī)矩陣T的維度，Y為隨機(jī)矩陣，E為隨機(jī)噪聲矩陣，m為正整數(shù)；通過得到對應(yīng)的密鑰交換矩陣M，記錄密鑰交換矩陣M和密鑰矩陣S1；

B3.根據(jù)密鑰交換矩陣M和c＝Mx^*，得到密文向量組(c1,c2,…cn)，其中x為明文向量。

3.如權(quán)利要求1或2所述的基于向量同態(tài)加密的隱私保護(hù)k-means聚類方法，其特征為：步驟D中所述的聚類分析包括：

D1.根據(jù)待聚類向量的密文向量組(c1,c2,…,cn)及中間矩陣H，給密文向量組(c1,c2,…,cn)中每個待聚類向量分別附上各不相同的標(biāo)簽；

D2.隨機(jī)產(chǎn)生k個聚類中心(p1,p2,…,pk)，其中k為正整數(shù)；

D3.通過中間矩陣H計(jì)算密文向量組(c1,c2,…,cn)中每個密文向量到每個聚類中心的距離，對于每個密文向量會產(chǎn)生k個距離；

D4.對每個密文向量選擇最小的距離，并將它們歸為一個集合，由此產(chǎn)生k個集合(Q1,Q2,…,Qk)；

D5.計(jì)算(Q1,Q2,…,Qk)中每個集合的平均向量，產(chǎn)生k個新聚類中心(p1',p2',…,pk')；

D6.重復(fù)步驟D3～D5，直到集合(Q1,Q2,…,Qk)不再改變。

4.如權(quán)利要求3所述的基于向量同態(tài)加密的隱私保護(hù)k-means聚類方法，其特征為：步驟D3中所述每個密文向量會產(chǎn)生k個距離為：D_ij＝(c_i-p_j)^TH(c_i-p_j)，i＝1,…,n；j＝1,…,k。

5.如權(quán)利要求3所述的基于向量同態(tài)加密的隱私保護(hù)k-means聚類方法，其特征為：聚類中心(p1,p2,…,pk)為維度與密文向量組(c1,c2,…,cn)一致的整數(shù)向量。

6.如權(quán)利要求3所述的基于向量同態(tài)加密的隱私保護(hù)k-means聚類方法，其特征為：所述集合(Q1,Q2,…,Qk)中的每個的元素均為向量。