區(qū)塊鏈多鏈下的數(shù)據(jù)隱私保護(hù)K均值聚類算法*

左 力，徐志錕，肖夢(mèng)雪

（西南交通大學(xué)，四川 成都 610031）

0 引言

區(qū)塊鏈?zhǔn)且环N多方參與維護(hù)的塊—鏈?zhǔn)綌?shù)據(jù)結(jié)構(gòu)，利用分布式節(jié)點(diǎn)共識(shí)算法生成和更新數(shù)據(jù)，并利用密碼學(xué)的方式保證數(shù)據(jù)傳輸和訪問的安全，具有去中心化、高透明度、不可篡改、可編程、可追溯等特點(diǎn)[1]。

開源區(qū)塊鏈平臺(tái)以太坊（ethereum）的誕生促使該平臺(tái)上落地了大量的去中心化應(yīng)用（Decentralized Application，DApp），自此，區(qū)塊鏈技術(shù)在越來越多的行業(yè)中得到了應(yīng)用[2]。不局限于金融領(lǐng)域和加密數(shù)字貨幣領(lǐng)域，近年來人們開始嘗試將區(qū)塊鏈應(yīng)用于政務(wù)、醫(yī)療、教育、服務(wù)、物流等眾多領(lǐng)域。

這些不同領(lǐng)域中的每條應(yīng)用鏈相互獨(dú)立地運(yùn)行和存在。為了更好地利用這些區(qū)塊鏈當(dāng)中的數(shù)據(jù)，人們希望對(duì)其進(jìn)行更深層次的分析。利用數(shù)據(jù)挖掘技術(shù)可從這些區(qū)塊數(shù)據(jù)中提取有價(jià)值的信息，因此多鏈之間必定會(huì)發(fā)生跨鏈交互行為。但在區(qū)塊鏈多鏈的應(yīng)用場(chǎng)景下，對(duì)數(shù)據(jù)進(jìn)行挖掘分析需要通過多區(qū)塊鏈應(yīng)用方之間的配合來完成。傳統(tǒng)的集中式數(shù)據(jù)挖掘無法完成該任務(wù)，這是因?yàn)槭紫葏^(qū)塊鏈系統(tǒng)具有去中心化的結(jié)構(gòu)特點(diǎn)，無法將存儲(chǔ)在各條鏈上的數(shù)據(jù)存儲(chǔ)到一個(gè)中心進(jìn)行挖掘；其次在多鏈之間配合進(jìn)行數(shù)據(jù)挖掘時(shí)，考慮到某些區(qū)塊鏈上可能含有具有商業(yè)價(jià)值的信息或者較敏感的隱私數(shù)據(jù)，如醫(yī)學(xué)研究領(lǐng)域和市場(chǎng)動(dòng)態(tài)研究領(lǐng)域的區(qū)塊鏈，數(shù)據(jù)擁有者通常希望能夠在不與他人共享這部分私有數(shù)據(jù)的同時(shí)獲得數(shù)據(jù)的分析結(jié)果[3]。因此在多鏈環(huán)境下提出能保持?jǐn)?shù)據(jù)隱私性的挖掘算法具有重要意義，使得挖掘者只能獲得正確的挖掘結(jié)果，而不會(huì)獲得其他任何信息。

本文結(jié)合聚類挖掘方法中的K均值聚類來對(duì)多條區(qū)塊鏈當(dāng)中的數(shù)據(jù)進(jìn)行分析。K均值是經(jīng)典的基于距離劃分的聚類算法，其具有簡(jiǎn)單高效的特點(diǎn)，在很多領(lǐng)域都得到了廣泛應(yīng)用[4]。綜上，為了解決多鏈合作進(jìn)行聚類挖掘時(shí)帶來的隱私泄露和敏感信息被發(fā)現(xiàn)的問題，本文提出了多鏈下基于同態(tài)加密技術(shù)的數(shù)據(jù)隱私保護(hù)K均值聚類算法。

1 同態(tài)加密算法

20世紀(jì)70年代，Rivest等人[5]首次提出了利用同態(tài)加密（Homomorphic Encryption，HE）技術(shù)來保護(hù)數(shù)據(jù)的安全性。同態(tài)加密是一種利用具有同態(tài)性質(zhì)的加密函數(shù)，允許直接對(duì)密文進(jìn)行操作，并保護(hù)數(shù)據(jù)安全性的加密變換技術(shù)[6]。這一特性使得同態(tài)加密技術(shù)具有保護(hù)數(shù)據(jù)安全性的特點(diǎn)。利用該技術(shù)可以使得區(qū)塊鏈數(shù)據(jù)挖掘方只能獲知最后的挖掘結(jié)果，而無法從獲得的結(jié)果中分析得到其他被挖掘者的任何信息，既滿足了用戶可以對(duì)敏感數(shù)據(jù)進(jìn)行操作的需求，又避免了數(shù)據(jù)信息泄露的風(fēng)險(xiǎn)，提高了信息的安全性。

此外，利用同態(tài)加密技術(shù)可以使得數(shù)據(jù)挖掘者即使在不知曉密鑰的情況下，仍然可以對(duì)密文進(jìn)行計(jì)算，這在一定程度上可以減少通信代價(jià)，并平衡各參與方的計(jì)算代價(jià)。正是因?yàn)橥瑧B(tài)加密技術(shù)在降低通信復(fù)雜度和計(jì)算復(fù)雜度以及保護(hù)數(shù)據(jù)安全性上具有優(yōu)勢(shì)，越來越多的研究者投入到其理論和應(yīng)用的探索中[7]。

1.1 算法主要步驟

為保障密鑰的安全性，密鑰選取應(yīng)當(dāng)滿足以下基本特性：

（1）對(duì)于任何參與者來說，給定的某個(gè)明文信息m∈Zr={0,1,2,3,…,r-1}想要形成加密后的密文z∈Er(m)時(shí)，在計(jì)算上都應(yīng)該是容易的；

（2）對(duì)密文z∈Er(m)進(jìn)行解密后的結(jié)果應(yīng)當(dāng)是唯一的，即如果m1，m2∈Zr，且滿足m1不等于m2，則Er(m1)與Er(m2)的交集應(yīng)當(dāng)為空集，并且擁有私鑰的一方應(yīng)當(dāng)能夠計(jì)算出這個(gè)唯一的解；

（3）在適當(dāng)?shù)拿艽a學(xué)假設(shè)下，僅僅通過加密算法Er和密文z∈Er(m)，想要得到明文m或者私鑰在計(jì)算上是不可行的。

具體的同態(tài)加密密鑰生成算法步驟如下文所述。

（1）選擇兩個(gè)大素?cái)?shù)p和q，并計(jì)算兩數(shù)的乘積n=p×q。

（2）選擇一個(gè)實(shí)數(shù)r，使r滿足r可以整除(p-1)，r與(p-1)/r互素，r與(q-1)互素這3個(gè)條件，如圖1所示為實(shí)數(shù)r的選擇流程。

圖1 滿足條件的實(shí)數(shù)r找尋流程

（3）選擇底數(shù)y，該底數(shù)y的取值范圍應(yīng)為y∈(Zn)*={x∈Zn:gcd(x,n)=1}，并且y需要滿足不等式：

由此3個(gè)步驟可以得到一對(duì)公鑰PK=(y,r,n)與私鑰SK=(p,q)。

明文m必須是集合Zr上的元素，實(shí)數(shù)u為加密時(shí)在集合(Zn)*上產(chǎn)生的隨機(jī)數(shù)，對(duì)明文m的加密算法為：

對(duì)于任意的明文m和隨機(jī)數(shù)u，則有：

因?yàn)閙

1.2 同態(tài)性質(zhì)證明

同態(tài)特性使得同態(tài)加密技術(shù)具有保護(hù)數(shù)據(jù)安全性的特點(diǎn)，因此需要對(duì)其同態(tài)特性進(jìn)行證明。根據(jù)加密算法對(duì)明文m1和明文m2進(jìn)行加密：

將密文相乘，得到：

通過該等式可以證明得到：

基于這個(gè)特性，該同態(tài)加密方案可以使得兩個(gè)密文的乘積在經(jīng)過解密后得到的結(jié)果與對(duì)應(yīng)明文相加后的結(jié)果相等。

1.3 數(shù)據(jù)挖掘中的應(yīng)用

同態(tài)加密在多鏈下的隱私保護(hù)數(shù)據(jù)挖掘當(dāng)中，主要用來解決加權(quán)平均問題（Weighted Average Problem，WAP），該問題定義為，已知(x,n)和(y,m)的兩方Alice和Bob都想要得到雙方數(shù)據(jù)共同的加權(quán)平均值(x+y)/(n+m)，而雙方都不想讓對(duì)方知曉自己所掌握的私密數(shù)據(jù)。

利用同態(tài)加密技術(shù)解決WAP問題的步驟如下文所述。

（1）Alice按照同態(tài)加密算法的密鑰生成方法生成一對(duì)公鑰與私鑰，并公布自己的公鑰給Bob。

（2）Alice使用自己的公鑰通過加密算法加密自己的私有數(shù)據(jù)(x,n)，將加密結(jié)果E(x)和E(n)發(fā)送給Bob。

（3）Bob得到Alice發(fā)來的加密消息E(x)和E(n)后，任意產(chǎn)生一個(gè)隨機(jī)數(shù)z，根據(jù)同態(tài)加密的特性，Bob可以通過求冪運(yùn)算計(jì)算得到兩個(gè)值(E(x))z=E(z×x)和(E(n))z=E(z×n)，并且Bob還可以使用Alice的公鑰加密自己擁有的加入隨機(jī)參數(shù)后的私有數(shù)據(jù)(z×y,z×m)，得到加密結(jié)果E(z×y)和E(z×m)。在得到4個(gè)加密數(shù)據(jù)后，Bob再次利用同態(tài)加密的性質(zhì)向Alice發(fā)送兩條加密消息E(z×x+z×y)=E(z×x)×E(z×y)和E(z×n+z×m)=E(z×n)×E(z×m)。

（4）Alice收到Bob發(fā)送來的加密數(shù)據(jù)E(z×x+z×y)和E(z×n+z×m)后，可以利用自己的私鑰對(duì)其進(jìn)行解密，得到明文z×x+z×y和z×n+z×m，通過求商約分計(jì)算，Alice得到加權(quán)平均值(x+y)/(n+m)。

（5）Alice將計(jì)算得到的結(jié)果發(fā)送給Bob。

同態(tài)加密解決WAP問題的過程如圖2所示。

圖2 同態(tài)加密解決WAP問題的過程

通過同態(tài)加密技術(shù)解決了加權(quán)平均值求取的問題，同理可以將其推廣到多方區(qū)塊鏈應(yīng)用中，用于解決分布式條件下的數(shù)據(jù)挖掘問題。

i條鏈下隱私保護(hù)求取加權(quán)平均值需要除數(shù)據(jù)挖掘方以外的(i-1)條鏈都產(chǎn)生自己私有的隨機(jī)數(shù)z1,z2,…,zi-1，然后利用數(shù)據(jù)挖掘方的公鑰和同態(tài)加密的性質(zhì)，在(i-1)條鏈之間傳送加入了自己私有隨機(jī)數(shù)的明文加密后的密文，最后將加入了所有隨機(jī)數(shù)的密文數(shù)據(jù)E(x1×z1z2…zi-1),…,E(xi×z1z2…zi-1)和E(n1×z1z2…zi-1),…,E(ni×z1z2…zi-1)傳送給數(shù)據(jù)挖掘方，利用自己的私鑰和同態(tài)加密的性質(zhì)，挖掘方便可以獲得加權(quán)平均值。

2 多鏈下的數(shù)據(jù)隱私保護(hù)K均值聚類算法

聚類是指按照某個(gè)特定標(biāo)準(zhǔn)將物理或抽象對(duì)象的集合分割成不同的類或簇的過程[8]。聚類應(yīng)使得同一個(gè)簇內(nèi)的數(shù)據(jù)對(duì)象的相似性盡可能大，同時(shí)不在同一個(gè)簇中的數(shù)據(jù)對(duì)象的差異性也盡可能大[9]。相似性與差異性是根據(jù)數(shù)據(jù)對(duì)象的屬性值進(jìn)行評(píng)估的，通?？梢圆捎镁嚯x進(jìn)行度量[10]。聚類分析就是從給定的數(shù)據(jù)集中搜索數(shù)據(jù)對(duì)象之間所存在的有價(jià)值聯(lián)系[11]。

本文結(jié)合K-means聚類算法對(duì)多鏈數(shù)據(jù)進(jìn)行挖掘，其核心是一種迭代求解的聚類分析算法。隨機(jī)選取k個(gè)對(duì)象作為初始的聚類中心，然后計(jì)算每個(gè)數(shù)據(jù)對(duì)象與各個(gè)種子聚類中心之間的距離，把每個(gè)對(duì)象分配給距離它最近的聚類中心[12]。每分配一個(gè)數(shù)據(jù)對(duì)象，聚類中心就會(huì)根據(jù)當(dāng)前聚類中的所有對(duì)象重新計(jì)算獲得一個(gè)新的聚類中心。不斷重復(fù)這個(gè)過程直到滿足終止條件時(shí)，完成聚類。

假設(shè)有i條鏈的數(shù)據(jù)需要在不泄露隱私的情況下進(jìn)行K-means聚類分析，第1條鏈擁有a個(gè)數(shù)據(jù)(X11,X12,…,X1a)，第2條鏈擁有b個(gè)數(shù)據(jù)(Y11,Y12,…,Y1a)，第i條鏈擁有c個(gè)數(shù)據(jù)(Zi1,Zi2,…,Z1c)，任何一方都需要在不知曉其余參與方具體數(shù)據(jù)的情況下獲得共同K-means聚類結(jié)果。具體的算法流程如圖3所示。

圖3 分布式K-means聚類流程

假設(shè)以第1條鏈為主分析該算法，第1條鏈擁有a個(gè)數(shù)據(jù)(X11,X12,…,X1a)。由第1條鏈產(chǎn)生m個(gè)初始聚類中心(U1,U2,…,Um)，產(chǎn)生的方式可以是隨機(jī)的，也可以通過各種提取初始聚類均值的技術(shù)來選取。將初始化的m個(gè)聚類中心發(fā)送給其余(i-1)條鏈，各鏈根據(jù)初始化的聚類中心來計(jì)算自己擁有的每一個(gè)樣本數(shù)據(jù)到聚類中心的距離，該距離可以用各種度量方式選擇，如歐式度量、分散度量等，若某樣本離某聚類中心的距離最近，則將此樣本歸類為這個(gè)簇中。

依據(jù)此方式，將第1條鏈的樣本數(shù)據(jù)分別進(jìn)行聚類，并且通過計(jì)算可以得到新的聚類中心(U11,U12,…,U1m)和每一個(gè)聚類簇中的樣本數(shù)量(N11,N12,…,N1m)，記每一個(gè)聚類簇中的數(shù)據(jù)和為P1j，j∈[1,m]，其中，Pj=∑Xj=Uj×Nj，記每一個(gè)聚類簇中的樣本數(shù)量為Q1j，j∈[1,m]，其中，Qj=Nj。同樣地，其余(i-1)條鏈也可以得到新的聚類中心(U21,U22,…,U2m),…,(Ui1,Ui2,…,Uim)和每一個(gè)聚類簇中的樣本數(shù)量(N21,N22,…,N2m),…,(Ni1,Ni2,…,Nim)，記每一個(gè)聚類簇中的數(shù)據(jù)和為P2j,…,Pij，j∈[1,m]，記每一個(gè)聚類簇中的樣本數(shù)量為Q2j,…,Qij，j∈[1,m]。

此時(shí)，i條鏈都擁有各自的m組數(shù)據(jù)(Pkj,Qkj)，k∈[1,i]，j∈[1,m]，通過基于同態(tài)加密的隱私保護(hù)協(xié)議，每一條鏈可以在不知道其余鏈任何數(shù)據(jù)的情況下得到共同的聚類中心(U1,U2,…,Um)，即解決隱私保護(hù)下的加權(quán)平均求值問題。

雙方在計(jì)算得到新的聚類中心之后，再次按照上面的步驟進(jìn)行聚類，重復(fù)整個(gè)過程，每次迭代都會(huì)重新分類樣本并計(jì)算均值，當(dāng)檢測(cè)到均值沒有變化的時(shí)候，算法終止。“沒有變化”的精確定義取決于所使用的具體指標(biāo)，可以是沒有對(duì)象被重新分配給不同的聚類，沒有聚類中心再發(fā)生變化，誤差平方和局部最小等。

通過多鏈下的隱私保護(hù)K-means聚類數(shù)據(jù)挖掘方法可以在達(dá)到想要的數(shù)據(jù)挖掘目標(biāo)的同時(shí)，保護(hù)用戶隱私數(shù)據(jù)不被泄露。該算法可以應(yīng)用到許多領(lǐng)域當(dāng)中，并根據(jù)該領(lǐng)域的需求作出調(diào)整，比如應(yīng)用于金融領(lǐng)域中解決金融系統(tǒng)問題時(shí)，需要根據(jù)多個(gè)應(yīng)用上的歷史交易記錄來判定用戶是否可信任，并保證用戶數(shù)據(jù)不泄露；再比如應(yīng)用于推廣領(lǐng)域中時(shí)，需要在不泄露用戶信息的情況下分析客戶的需求，以便向其推廣相應(yīng)的目標(biāo)產(chǎn)品[13]。

3 算法分析

3.1 計(jì)算過程中各鏈數(shù)據(jù)的安全性

由于各鏈進(jìn)行聚類劃分和計(jì)算聚類中心的過程都是在本地完成的，因此多鏈聯(lián)合計(jì)算過程中的安全性問題主要集中在各鏈將自己加密后的數(shù)據(jù)發(fā)送給其他鏈后，其他鏈?zhǔn)欠裼心芰闹蝎@得與原始數(shù)據(jù)有關(guān)的信息。

因?yàn)楦麈湴l(fā)送的數(shù)據(jù)都通過加密，而且其中還受不確定的隨機(jī)數(shù)的影響，而利用同態(tài)加密的性質(zhì)，即使是在對(duì)其他鏈的數(shù)據(jù)進(jìn)行計(jì)算時(shí)也不需要對(duì)數(shù)據(jù)進(jìn)行解密，而是直接對(duì)密文進(jìn)行運(yùn)算操作，這樣保證了在多鏈聯(lián)合計(jì)算時(shí)各鏈的私有信息不被泄露，并且整個(gè)計(jì)算過程的加密和解密操作全由各鏈獨(dú)立完成，所以可以保證在多鏈聯(lián)合計(jì)算過程中各鏈數(shù)據(jù)的安全性。

3.2 通信過程的安全以及防竊聽性

多鏈聯(lián)合計(jì)算的通信過程主要是在計(jì)算加權(quán)平均值問題時(shí)需要傳送信息，在這整個(gè)通信過程中沒有出現(xiàn)明文，都是利用同態(tài)加密的特性直接對(duì)密文進(jìn)行操作完成運(yùn)算。當(dāng)存在竊聽行為時(shí)，假設(shè)多鏈在求解加權(quán)平均值的過程中被竊聽到了密文數(shù)據(jù)，但由于其沒有私鑰，破解密文的難題便歸結(jié)到了大數(shù)分解和素性檢測(cè)上，這無疑是困難的。即便是擁有私鑰的一方與竊聽者合謀共同破解原始數(shù)據(jù)，但由于加密的明文當(dāng)中含有其余方產(chǎn)生的隨機(jī)數(shù)，因此，竊聽者無法還原出原始數(shù)據(jù)，從而保證了多鏈下聯(lián)合計(jì)算的通信過程中的數(shù)據(jù)安全性。

3.3 聚類精度分析

多鏈下的數(shù)據(jù)隱私保護(hù)K均值聚類算法只是將K均值聚類放到了多鏈分布式環(huán)境下，并在過程中加入了數(shù)據(jù)隱私保護(hù)技術(shù)，并沒有改變?cè)瓉淼腒均值聚類的迭代過程。原始的K均值聚類算法結(jié)果的差異性在于初始聚類中心的選取方式和距離的計(jì)算方式上[14]。本文提出的K均值聚類算法并沒有改變兩者，因此仍然可以將其他能夠提高聚類精度的方法嵌入到該算法當(dāng)中，且迭代過程中依然是從第1次迭代到最終次迭代不斷修正聚類中心，所以算法的正確性可以得到保證。

4 結(jié)語

本文針對(duì)區(qū)塊鏈環(huán)境下時(shí)常既需要進(jìn)行多鏈聯(lián)合計(jì)算分析多鏈數(shù)據(jù)中的一些有用信息，又要確保不能泄露任何隱私信息的痛點(diǎn)，提出了一種多鏈下保護(hù)數(shù)據(jù)隱私的K均值聚類挖掘算法。該算法基于同態(tài)加密技術(shù)，在計(jì)算和通信過程中都可以在加密的環(huán)境下進(jìn)行，而不需要對(duì)其進(jìn)行解密，從而達(dá)到不泄露任何私密數(shù)據(jù)的目的。