栗維勛，馬 斌，王 琛，何紀(jì)成，高明慧，徐 劍

1(國(guó)網(wǎng)河北省電力有限公司，石家莊 050000)

2(南瑞集團(tuán)有限公司(國(guó)網(wǎng)電力科學(xué)研究院)，南京 210061)

3(北京科東電力控制系統(tǒng)有限責(zé)任公司，北京 100192)

4(東北大學(xué) 軟件學(xué)院，沈陽(yáng) 110169)

E-mail：1193328465@qq.com

1 引 言

聚類作為典型的數(shù)據(jù)分析與挖掘技術(shù)，在眾多領(lǐng)域發(fā)揮著重要作用[1-3].聚類屬于機(jī)器學(xué)習(xí)中的無(wú)監(jiān)督學(xué)習(xí)，目的是把數(shù)據(jù)點(diǎn)劃分成若干類，同一個(gè)類中的數(shù)據(jù)點(diǎn)有很大的相似性，而不同類的數(shù)據(jù)點(diǎn)有很大的相異性.聚類可以在大量數(shù)據(jù)中獲取有用的知識(shí)，找出數(shù)據(jù)之間的潛在關(guān)系，是智能推薦、信息檢索、圖像模式識(shí)別、網(wǎng)絡(luò)實(shí)時(shí)監(jiān)控和預(yù)警等領(lǐng)域中的常用技術(shù)手段[4-6].

隨著云計(jì)算、物聯(lián)網(wǎng)以及5G技術(shù)的飛速發(fā)展，催生大數(shù)據(jù)時(shí)代快速到來(lái).但是，在實(shí)際應(yīng)用場(chǎng)景中，部分?jǐn)?shù)據(jù)擁有者由于資源受限，需要將數(shù)據(jù)進(jìn)行外包.因此，外包聚類服務(wù)也隨之產(chǎn)生，成為聚類方法發(fā)展的新趨勢(shì)[7-9].數(shù)據(jù)外包后，如何保障其隱私性是一個(gè)具有挑戰(zhàn)性的問(wèn)題.外包的數(shù)據(jù)常常包括金融、生物醫(yī)學(xué)等個(gè)人敏感信息，一旦發(fā)生數(shù)據(jù)泄露問(wèn)題，對(duì)個(gè)人或社會(huì)將產(chǎn)生嚴(yán)重的負(fù)面影響[10].針對(duì)上述問(wèn)題，目前，通常的做法是對(duì)外包的數(shù)據(jù)進(jìn)行加密處理.然而，傳統(tǒng)的聚類方法僅能對(duì)明文數(shù)據(jù)進(jìn)行聚類，不支持密文數(shù)據(jù)的聚類.因此，研究密文數(shù)據(jù)上的聚類方法就變的重要而迫切.

在密文數(shù)據(jù)上實(shí)現(xiàn)聚類是當(dāng)前隱私保護(hù)機(jī)器學(xué)習(xí)研究的熱點(diǎn)問(wèn)題之一[11-13].目前，眾多學(xué)者采用同態(tài)加密來(lái)支持密文數(shù)據(jù)上的運(yùn)算[13，14-17].Cheon等人[13]實(shí)現(xiàn)了密文上的均值漂移算法，將非多項(xiàng)式內(nèi)核替換為多項(xiàng)式內(nèi)核，以便可以在同態(tài)加密下高效的計(jì)算，降低了傳統(tǒng)均值漂移算法的超線性復(fù)雜度，在速度和準(zhǔn)確性方面有了提升.Almutairi等人[14]利用同態(tài)加密技術(shù)設(shè)計(jì)了一種可更新距離矩陣，利用矩陣計(jì)算的性質(zhì)來(lái)對(duì)密文進(jìn)行計(jì)算.Hyeong等人[15]提出了支持比較操作的安全協(xié)議，首先使用Paillier密碼系統(tǒng)對(duì)明文數(shù)據(jù)進(jìn)行加密，然后將明文運(yùn)算操作替換成密文安全協(xié)議.雖然使用Paillier算法可以保證語(yǔ)義安全性，但是計(jì)算消耗較高.Chen等人[16]設(shè)計(jì)了一種基于Paillier加密的智能電表數(shù)據(jù)聚合方案，保護(hù)用戶的隱私信息.該方案引入可信的第三方密鑰生成中心，為用戶生成合法的密鑰，用戶密鑰保存在服務(wù)器中用于驗(yàn)證用戶的合法身份.Angela等人[17]則解決了密文運(yùn)算中的除法問(wèn)題，同態(tài)加密中不允許兩個(gè)密文數(shù)據(jù)直接相除，但可以用一個(gè)密文數(shù)據(jù)除以常數(shù)，這個(gè)常數(shù)代表數(shù)據(jù)總和，即使暴露也不會(huì)泄露關(guān)鍵信息.Xing等人[18]提出了一種基于同態(tài)加密的K-means聚類方案，該方案既不會(huì)泄露個(gè)人信息，也不會(huì)泄漏社區(qū)的特征數(shù)據(jù).在該方案中，聚類的每次迭代調(diào)用的隱私保護(hù)算法，可在不泄漏每個(gè)參與者標(biāo)簽的情況下計(jì)算簇類中心.參與者無(wú)法獲知同一簇類中的其他參與者信息.通過(guò)安全性分析，即使存在共謀參與者，也不會(huì)泄露其余參與者的私人信息.Almutairi等人[19]考慮到現(xiàn)有方法都需要所有數(shù)據(jù)擁有者參與，參與的數(shù)據(jù)量過(guò)于龐大，客戶端計(jì)算能力不足，因此引入可信第三方，將計(jì)算外包給第三方，節(jié)約計(jì)算成本，同時(shí)保證相互之間的隱私性.

綜上所述，在密文聚類方面，學(xué)者們已經(jīng)提出了較多的研究方案.但是，仍存在如下問(wèn)題：

1)多數(shù)密文上的聚類方案都是利用同態(tài)加密算法結(jié)合K-means算法實(shí)現(xiàn)，基于密度聚類的算法較少.而K-means算法存在需要預(yù)先輸入聚類簇?cái)?shù)以及對(duì)初始聚類中心過(guò)于依賴等缺點(diǎn)，無(wú)法滿足某些場(chǎng)景的實(shí)際應(yīng)用需求，因此還需在密文上實(shí)現(xiàn)其他聚類算法.

2)已有方案很多采用同態(tài)加密算法，該算法僅能支持加法或者乘法運(yùn)算，而全同態(tài)加密可同時(shí)支持密文下的加法和乘法運(yùn)算，構(gòu)建的通信協(xié)議也更加簡(jiǎn)單.

因此，本文利用全同態(tài)加密技術(shù)研究面向密文數(shù)據(jù)的密度聚類模型，并將密度聚類的典型代表OPTICS算法作為研究切入點(diǎn).首先，設(shè)計(jì)了面向密文數(shù)據(jù)的OPTICS聚類模型(OPTICS-CMED)，對(duì)OPTICS-CMED的實(shí)體構(gòu)成和形式化定義進(jìn)行了描述；設(shè)計(jì)了對(duì)應(yīng)于基本操作的通信協(xié)議，包括：距離計(jì)算協(xié)議和排序協(xié)議.基于上述通信協(xié)議，構(gòu)建OPTICS-CMED的聚類過(guò)程.對(duì)OPTICS-CMED的正確性、安全性進(jìn)行了分析，結(jié)果表明該模型可以同時(shí)保證正確性和安全性.最后，利用標(biāo)準(zhǔn)實(shí)驗(yàn)數(shù)據(jù)進(jìn)行性能測(cè)試，結(jié)果表明該模型可以在保證聚類準(zhǔn)確性的前提下實(shí)現(xiàn)密文數(shù)據(jù)聚類.

2 OPTICS概述

OPTICS是一種無(wú)需用戶提供特定密度閾值的密度聚類算法，是DBSCAN(Density-Based Spatial Clustering of Applications with Noise)的改進(jìn)算法，其不明顯的產(chǎn)生類簇，而是通過(guò)對(duì)結(jié)果隊(duì)列中的樣本點(diǎn)進(jìn)行排序，來(lái)表達(dá)數(shù)據(jù)的基于密度的聚類結(jié)構(gòu)[20].由于OPTICS算法輸出的是一個(gè)排好順序的樣本點(diǎn)隊(duì)列，稱為結(jié)果隊(duì)列，相較于DBSCAN，OPTICS算法對(duì)輸入的參數(shù)不敏感.

OPTICS算法的核心思想：對(duì)于簇Ci中任意對(duì)象p，在其ε鄰域Nε(p)中，至少存在MinPts-1個(gè)其他對(duì)象，其中ε代表歐氏距離半徑，MinPts表示使得對(duì)象p作為核心對(duì)象在它的ε鄰域中至少應(yīng)含有的對(duì)象數(shù)量.

OPTICS算法中，存在核心距離core-distance(cd)和可達(dá)距離reachability-distance(rd)兩個(gè)概念.

定義1.對(duì)象p的核心距離cdε，MinPts(p).設(shè)半徑參數(shù)為ε′，使得p的ε′鄰域剛好包含MinPts個(gè)對(duì)象，若p不是關(guān)于ε′和MinPts的核心對(duì)象，則p的核心距離沒(méi)有定義，如式(1)所示：

(1)

定義2.對(duì)象p到對(duì)象q的可達(dá)距離rdε，MinPts(p，q).是使p從q密度可達(dá)的最小半徑值，其中q必須是核心對(duì)象，并且p必須在q的領(lǐng)域內(nèi)，如式(2)所示：

rdε，MinPts(p，q)=

(2)

OPTICS聚類算法，最終將根據(jù)識(shí)別結(jié)果輸出數(shù)據(jù)集的簇排序，該排序給出了對(duì)數(shù)據(jù)結(jié)構(gòu)化和聚類的一般觀察.

3 模型構(gòu)建

3.1 模型描述

OPTICS-CMED包括兩方實(shí)體，即客戶(Client，C)和服務(wù)器(Server，S)，如圖1所示.

圖1 面向密文數(shù)據(jù)的OPTICS聚類模型Fig.1 OPTICS clustering model over encrypted data

在OPTICS-CMED模型中，聚類過(guò)程由S與C通過(guò)安全通信協(xié)議交互完成.C將加密的樣本數(shù)據(jù)集發(fā)送給S，S進(jìn)行聚類，并生成種子隊(duì)列和結(jié)果隊(duì)列，其中結(jié)果隊(duì)列包含著表示聚類結(jié)構(gòu)的簇排序?qū)ο罅斜恚瑥慕Y(jié)果隊(duì)列中可以得到聚類結(jié)果.整個(gè)過(guò)程在密文下進(jìn)行，在計(jì)算樣本點(diǎn)與中心點(diǎn)的距離時(shí)不會(huì)泄露隱私，通過(guò)隱藏類簇中心來(lái)防止攻擊者推斷出用戶所屬的類簇分組.在圖1中虛線區(qū)域表示需要保護(hù)隱私的數(shù)據(jù)及模型，其中聚類模型僅能被S獲知，而明文聚類結(jié)果僅能被C獲知.

定義3是對(duì)OPTICS-CMED的描述.

定義3.密文數(shù)據(jù)的OPTICS聚類模型(OPTICS-CMED)可以由如下元組表示{C，S，Distance，getOrder}.

1)Distance(E(x)，E(y))：安全距離計(jì)算協(xié)議，將FHE加密的數(shù)據(jù)E(x)，E(y)作為參數(shù)輸入，得到加密向量的乘法平方結(jié)果，即歐幾里德距離結(jié)果，保存到數(shù)組中；

2)getOrder(E(rd0)，…，E(rdm-1))：排序協(xié)議，將FHE加密的可達(dá)距離數(shù)組rd作為參數(shù)輸入，完成密文下可達(dá)距離的排序.

3.2 通信協(xié)議

OPTICS-CMED的通信協(xié)議包括安全距離計(jì)算協(xié)議和排序協(xié)議.安全距離計(jì)算協(xié)議用于實(shí)現(xiàn)兩個(gè)加密的向量的歐氏距離計(jì)算；排序協(xié)議用于實(shí)現(xiàn)對(duì)多個(gè)加密數(shù)據(jù)進(jìn)行從小到大排序.

3.2.1 安全距離計(jì)算協(xié)議

安全距離計(jì)算協(xié)議是利用FHE的加法同態(tài)和乘法同態(tài)性質(zhì)，計(jì)算由FHE加密的兩個(gè)向量的歐氏距離的平方，返回一個(gè)FHE加密的運(yùn)算結(jié)果.在安全距離計(jì)算協(xié)議中，S的輸入是兩個(gè)加密的向量數(shù)據(jù)和用于加密的密鑰，距離計(jì)算僅由S即可完成.S獲得FHE加密的向量點(diǎn)乘結(jié)果用于后續(xù)計(jì)算核心距離和可達(dá)距離，同時(shí)保證數(shù)據(jù)的隱私.

協(xié)議1是安全距離計(jì)算協(xié)議的描述.

協(xié)議1.安全距離計(jì)算協(xié)議distance(E(x)，E(y))

S：E(x)=(E(x1)，…，E(xd))，E(y)=(E(y1)，…，E(yd))，pk；

S：E(s)

1.S：Ef(s)←Ef(0)

2.S：for1≤i≤d：

3.S：E(zi)←(E(xi)⊙E(yi))×(E(xi)⊙E(yi))

4.S：E(s)←E(s)⊕E(zi)

5.S：returnE(s)

3.2.2 排序協(xié)議

圖2 排序過(guò)程Fig.2 Process diagram of ordering

在排序過(guò)程中，找到數(shù)組中最小值，將它與數(shù)組的第1個(gè)元素交換位置；再在剩下的元素中找到最小值，與數(shù)組的第2個(gè)元素交換位置.循環(huán)下去，直到完成對(duì)整個(gè)數(shù)組的排序.而獲取最小值的方法：利用兩個(gè)元素的比較協(xié)議，對(duì)數(shù)組中的元素進(jìn)行兩兩比較，找到數(shù)值較小的一方賦值給下標(biāo)小的一方，放入另一個(gè)數(shù)組中；同時(shí)使下標(biāo)較大的一方數(shù)值為0，直到所有比較完成.再對(duì)另一個(gè)數(shù)組中的元素進(jìn)行兩兩比較，重復(fù)上述過(guò)程，最后得到一個(gè)最小值.

協(xié)議2是對(duì)排序協(xié)議的具體描述.

協(xié)議2.排序協(xié)議getOrder(E(rd[0])，…，E(rd[m-1]))

輸入S：E(rd[0])，…，E(rd[m-1])，公鑰pk；

輸入C：私鑰sk；

輸出S：有序數(shù)組E(Qorder[k])

1.S：for0≤k≤m

2.S：for0≤i≤m：

3.S：E(rd′[i])←E(rd[i])

4.S：num←m

6.S：for1≤j≤?num/2」

7.C，S：flag=Compare(E(rd′[2i(j-1)])，E(rd′[2i(j-1)+2i-1]))

9.S：E(rd1)←E(rd′[2i(j-1)])⊕E(r1)

10.S：E(rd2)←E(rd′[2i(j-1)+2i-1])⊕E(r2)

11.S： sendE(rd1)E(rd2)toC

12.C：if(flag==1)

13.C：E(rdmin)←E(rd1)

14.C：else：

15.C：E(rdmin)←E(rd2)

16.C： sendE(rdmin) andE(flag)toS

17.S：E(rd′[2i(j-1)])←E(rdmin)⊕(E(flag)⊙E(1))?r2⊙E(flag)?r1

18.S：E(rd′[2i(j-1)+2i-1])←E(0)

19.S：num←「num/2?

20.S：E(rdmin)←E(rd′[0])

21.S：E(Qorder[k])←E(rdmin)

3.3 聚類過(guò)程

在OPTICS-CMED模型的聚類過(guò)程中，S將半徑ε和最小點(diǎn)數(shù)MinPts兩個(gè)參數(shù)作為輸入，計(jì)算每個(gè)元素的核心距離(cd)和可達(dá)距離(rd)，完成后續(xù)聚類過(guò)程.

OPTICS-CMED的聚類過(guò)程如下：

Step 1.C對(duì)數(shù)據(jù)進(jìn)行處理，將浮點(diǎn)數(shù)轉(zhuǎn)化成整型，對(duì)數(shù)據(jù)進(jìn)行加密，發(fā)送待聚類數(shù)據(jù)集x、半徑ε和最小點(diǎn)數(shù)MinPts給S，并向S提交聚類服務(wù)請(qǐng)求；

Step 2.S收到C的聚類服務(wù)請(qǐng)求后，開始進(jìn)行聚類，創(chuàng)建兩個(gè)隊(duì)列，種子隊(duì)列Qorder和結(jié)果隊(duì)列Qreachdist；

Step 3.如果x中的數(shù)據(jù)全部處理完，則算法結(jié)束；否則，從x中選擇一個(gè)未被處理的核心對(duì)象，找出它的所有直接密度可達(dá)點(diǎn)，如果該點(diǎn)不存在于Qreachdist中，則將其存入Qorder中，并調(diào)用getOrder協(xié)議，與C共同完成可達(dá)距離rd排序；

Step 4.如果Qorder為空，則執(zhí)行Step 3；否則，從Qorder中取出第一個(gè)樣本點(diǎn)：

Step 4.1.判斷該點(diǎn)是否為核心對(duì)象，如果不是，則跳至Step 4；否則將該點(diǎn)存入Qreachdist；

Step 4.2.若該點(diǎn)是核心對(duì)象，找到它的所有直接密度可達(dá)點(diǎn)，存入Qorder，并調(diào)用getOrder協(xié)議，將Qorder的點(diǎn)按照rd重新排序.如果該點(diǎn)已經(jīng)在Qorder中且新的rd較小，則更新該點(diǎn)的rd；

Step 4.3.若Qorder中不存在直接密度可達(dá)樣本點(diǎn)，插入Qorder中，調(diào)用getOrder協(xié)議，將Qorder的點(diǎn)按照rd重新排序；

Step 5.輸出Qreachdist中的有序樣本點(diǎn)，發(fā)送給C；

Step 6.C進(jìn)行解密得到明文聚類結(jié)果.

4 正確性與安全性分析

4.1 正確性分析

首先對(duì)安全距離計(jì)算協(xié)議和排序協(xié)議進(jìn)行分析，并進(jìn)而證明OPTICS-CMED的正確性.

1)安全距離計(jì)算協(xié)議

綜上所述，本文的安全距離計(jì)算協(xié)議是正確的.

2)排序協(xié)議

排序協(xié)議中主要采用了選擇排序的思想，在未排序序列中找到最小值放在序列起始位置；在剩余的數(shù)據(jù)中繼續(xù)排序找出最小值，將其放在已排序序列的隊(duì)尾；重復(fù)上述過(guò)程直到處理完所有數(shù)據(jù).

在求最小值協(xié)議中，通過(guò)調(diào)用加密數(shù)據(jù)的比較協(xié)議Compare()實(shí)現(xiàn)兩個(gè)密文數(shù)據(jù)的比較，由C得到比較結(jié)果flag.然后，S將兩個(gè)增加隨機(jī)值的待比較的數(shù)據(jù)d1，d2發(fā)送給C，其中d1=dl+r1，d2=dr+r2，r1，r2，是隨機(jī)數(shù)，dl表示左值，dr表示右值.

當(dāng)flag=1時(shí)，dmin←d1；

當(dāng)flag=0時(shí)，dmin←d2.

保證dmin記錄的是最小值.C將dmin和flag一同發(fā)送給S，S根據(jù)dmin=dmin+(flag-1)×r2-flag×r1去除干擾值得到真實(shí)的最小值dmin.

當(dāng)flag=1時(shí)，dmin=d1=dleft+r1，則：

dmin=dleft+r1+(1-1)×r2-1×r1=dleft；

當(dāng)flag=0時(shí)，dmin=d1=dright+r2，則：

dmin=dright+r2+(0-1)×r2-0×r1=dright.

因此，S可以成功去除干擾值獲得明文最小值dmin，并用下標(biāo)較小的數(shù)組存儲(chǔ)最小值，同時(shí)將下標(biāo)較大數(shù)組置0，最后d0存儲(chǔ)m個(gè)元素中的最小值.

綜上所述，本文的排序協(xié)議是正確的.

3)OPTICS-CMED

在OPTICS-CMED中，首先調(diào)用比較協(xié)議判斷當(dāng)前加密的樣本數(shù)據(jù)點(diǎn)是否是核心對(duì)象，再利用一個(gè)輔助數(shù)組vi來(lái)判斷該數(shù)據(jù)點(diǎn)是否被訪問(wèn)過(guò).由于在密文下無(wú)法得知vi的值，需要C的幫助，為防止數(shù)據(jù)泄露，S對(duì)其增加干擾值后發(fā)送給C進(jìn)行解密，最后S再去除干擾值得到真正的vi值.若vi=0表示當(dāng)前數(shù)據(jù)點(diǎn)未被訪問(wèn)過(guò)，vi=1表示當(dāng)前數(shù)據(jù)點(diǎn)已經(jīng)被訪問(wèn)過(guò).再調(diào)用排序協(xié)議對(duì)可達(dá)距離進(jìn)行排序，保證最后可以得到有序的數(shù)組E(Qreachdist[d]).由于安全距離計(jì)算協(xié)議和排序協(xié)議都是正確的，得到包含聚類結(jié)果的E(Qreachdist[d])邏輯上也是正確的.

綜述所述，OPTICS-CMED也是正確的.

4.2 安全性分析

本節(jié)在半誠(chéng)實(shí)模型下對(duì)通信協(xié)議和OPTICS-CMED的安全性進(jìn)行分析，C和S都是半誠(chéng)實(shí)的參與方，它們誠(chéng)實(shí)地遵循協(xié)議的執(zhí)行，允許從協(xié)議執(zhí)行過(guò)程中獲取的數(shù)據(jù)進(jìn)行推斷.其輸入數(shù)據(jù)是隱私數(shù)據(jù)，僅能被個(gè)人獲知.

1)安全距離計(jì)算協(xié)議

在安全距離計(jì)算協(xié)議中，S的視圖為VS=(E(yi)，E(xi)，E(zi)，E(s)).由于FHE是語(yǔ)義安全的，S無(wú)法從E(xi)，E(yi)，E(zi)和E(s)中提取出明文xi，yi，zi，s，保證了數(shù)據(jù)xi，yi，zi，s的隱私；此協(xié)議僅由S執(zhí)行，C無(wú)法獲得隱私信息.

因此，本文設(shè)計(jì)的安全距離計(jì)算協(xié)議在半誠(chéng)實(shí)模型下是安全的.

2)排序協(xié)議

在排序協(xié)議中，S的視圖為VS=(E(rd[m])，pk，r1，r2，E(rdmin)，E(Qorder[k]))，其中r1，r2是隨機(jī)數(shù).C和S首先調(diào)用加密數(shù)據(jù)的比較協(xié)議對(duì)S的加密數(shù)據(jù)E(rd[m])進(jìn)行比較，C獲得明文的比較結(jié)果flag，由于加密數(shù)據(jù)的比較協(xié)議的安全性，保證了C和S比較過(guò)程中數(shù)據(jù)的隱私.接著，S將增加隨機(jī)干擾的密文數(shù)據(jù)E(rd1)和E(rd2)發(fā)送給C，C根據(jù)比較結(jié)果flag，將密文E(rd1)和E(rd2)賦值為E(rdmin)，再返回給S.由于FHE加密算法是語(yǔ)義安全的，C即使對(duì)密文數(shù)據(jù)E(rdmin)與EP(rd[m])解密也無(wú)法獲取明文rdmin和rd[m].由于比較結(jié)果僅被C獲知，C將更新后的密文發(fā)送給S，因此S無(wú)法通過(guò)密文E(rdmin)，E(rd[m])，獲知左值和右值哪個(gè)是最小值，保證了待比較數(shù)據(jù)在S方的隱私.C的視圖為VC=(skP，flag，E(rd1)，E(rd2))，由于E(rd1)，E(rd2)是增加隨機(jī)干擾值的密文數(shù)據(jù)，即使C可以使用私鑰解密也很難從明文rd1和rd2中提取出真實(shí)值，從而保證了待比較數(shù)據(jù)在C方的隱私.雖然C能夠獲知比較結(jié)果，但其無(wú)法獲知待比較數(shù)據(jù)的真實(shí)值，無(wú)法進(jìn)行推斷.因此，本文的排序協(xié)議在半誠(chéng)實(shí)模型下是安全的.

綜上所述，本文所設(shè)計(jì)的通信協(xié)議在半誠(chéng)實(shí)模型下都是安全的.

3)OPTICS-CMED

在OPTICS-CMED中，首先，調(diào)用比較協(xié)議用于判定該加密數(shù)據(jù)點(diǎn)是否為核心對(duì)象.比較協(xié)議在半誠(chéng)實(shí)模型下是安全的，S將增加噪聲干擾的最高位發(fā)送給C，保證其解密后無(wú)法得到最高位的明文，從而不知道數(shù)據(jù)的大小.S不擁有FHE私鑰，無(wú)法解密，因此比較過(guò)程是安全的.

通過(guò)調(diào)用安全距離計(jì)算協(xié)議計(jì)算兩個(gè)加密數(shù)據(jù)點(diǎn)的歐氏距離的平方，即核心距離.安全距離計(jì)算協(xié)議在半誠(chéng)實(shí)模型下是安全的，整個(gè)過(guò)程僅在S方進(jìn)行，未向C方發(fā)送任何數(shù)據(jù)，保證了S方加密數(shù)據(jù)的安全性.S方不擁有私鑰，無(wú)法解密待計(jì)算的數(shù)據(jù)，又因?yàn)镕HE的加法與乘法同態(tài)性，保證計(jì)算過(guò)程的安全性，因此安全距離計(jì)算時(shí)是安全的.

最后，先調(diào)用更新數(shù)組函數(shù)將未訪問(wèn)的數(shù)據(jù)點(diǎn)放入種子數(shù)組中，再調(diào)用排序協(xié)議獲取有序數(shù)組，由于S對(duì)數(shù)組下標(biāo)填加干擾值，即使C擁有解密的私鑰也無(wú)法獲知真正的下標(biāo)順序.協(xié)議2在半誠(chéng)實(shí)模型下是安全的，得到的數(shù)據(jù)也是安全的，C無(wú)法得知密文的最小值，無(wú)法獲取待比較數(shù)據(jù)的大小關(guān)系，保證了數(shù)組元素的大小關(guān)系不會(huì)泄露給C.

綜上所述，基于安全距離計(jì)算協(xié)議與排序協(xié)議進(jìn)行構(gòu)造的OPTICS-CMED在半誠(chéng)實(shí)模型下也是安全的.

5 實(shí)驗(yàn)分析

本文的實(shí)驗(yàn)環(huán)境如表1所示.加密方案中的密鑰長(zhǎng)度為1024位，安全參數(shù)λ=100.由于FHE方案僅能對(duì)整數(shù)進(jìn)行操作，本節(jié)使用IEEE 754雙精度浮點(diǎn)數(shù)代表實(shí)數(shù)，精度為52位，然后通過(guò)乘以大的實(shí)數(shù)來(lái)進(jìn)行變換.

表1 實(shí)驗(yàn)環(huán)境Table 1 Test environment

實(shí)驗(yàn)采用4種FCPS標(biāo)準(zhǔn)數(shù)據(jù)集(1)http：//uni-marburg.de/fb12/datenbionik/data?language svnc=1/，分別為：Hepta、Lsun、Tetra、Wingnut公共數(shù)據(jù)集.OPTICS聚類的性能主要由參數(shù)ε與MinPts決定，為了獲得最優(yōu)的聚類效果，對(duì)參數(shù)ε與MinPts的不同取值情況下的OPTICS聚類性能進(jìn)行測(cè)試，采用輪廓系數(shù)來(lái)評(píng)價(jià)聚類效果.利用4種數(shù)據(jù)集，對(duì)OPTICS-CMED與明文下的OPTICS進(jìn)行對(duì)比，參數(shù)與輪廓系數(shù)關(guān)系如圖3-圖6所示.參數(shù)ε越小，明文OPTICS聚類算法與OPTICS-CMED的輪廓系數(shù)均越來(lái)越大，說(shuō)明聚類效果得到提升.

由圖3和圖4對(duì)比可知，MinPts值越大，輪廓系數(shù)越小，表示其聚類性能有所下降.當(dāng)參數(shù)ε小到超過(guò)數(shù)據(jù)閾值時(shí)，將無(wú)法完成聚類.

圖3 參數(shù)與輪廓系數(shù)關(guān)系(Hepta數(shù)據(jù)集)Fig.3 Relationship between parameters and silhouette coefficient(Hepta dataset)

圖4 參數(shù)與輪廓系數(shù)關(guān)系(Lsun數(shù)據(jù)集)Fig.4 Relationship between parameters and silhouette coefficient(Lsun dataset)

從圖4～圖6中數(shù)據(jù)分析可知，OPTICS-CMED聚類輪廓系數(shù)比明文OPTICS算法低1.3%～8.1%，且輪廓系數(shù)均超過(guò)0.6，在可接受范圍內(nèi)，因此OPTICS-CMED可以在密文下完成聚類，且聚類效果可以得到有效保障.

圖5 參數(shù)與輪廓系數(shù)關(guān)系(Tetra數(shù)據(jù)集)Fig.5 Relationship between parameters and silhouette coefficient(Tetra dataset)

圖6 參數(shù)與輪廓系數(shù)關(guān)系(Wingnut數(shù)據(jù)集)Fig.6 Relationship between parameters and silhouette coefficient(Wingnut dataset)

采用F1-score對(duì)本方案進(jìn)行實(shí)驗(yàn)分析.在聚類中，精確率(Precision)和召回率(Recall)是相互矛盾的，F(xiàn)1-score會(huì)同時(shí)考慮精確率和召回率，重新計(jì)算新的分?jǐn)?shù)，如式(3)所示，當(dāng)F1-score較高時(shí)則能說(shuō)明實(shí)驗(yàn)方法有效.

(3)

表2給出了參數(shù)ε與MinPts的不同取值情況下的OPTICS-CMED與明文OPTICS對(duì)比結(jié)果.

表2 OPTICS-CMED與明文OPTICS的F1-score對(duì)比結(jié)果Table 2 F1-score comparison of OPTICS-CMED and plaintext clustering

表2中1與2、5與6對(duì)照數(shù)據(jù)可知，當(dāng)MinPts相同時(shí)，參數(shù)ε越小，F(xiàn)1-score越來(lái)越大，整體性能得到提升；但當(dāng)參數(shù)ε達(dá)到最低閾值時(shí)，將無(wú)法聚類.由2與4、6與7組對(duì)比數(shù)據(jù)可知，MinPts值越大，F(xiàn)1-score也越來(lái)越大.

綜合分析輪廓系數(shù)與F1-score可知，當(dāng)OPTICS參數(shù)ε=0.01且MinPts=10時(shí)，聚類效果最優(yōu).

在參數(shù)為ε=0.01且MinPts=10情況下，利用Lsun數(shù)據(jù)集(n表示數(shù)據(jù)總數(shù)，取n=50、100、200、300、400)分別進(jìn)行實(shí)驗(yàn).

表3給出了當(dāng)n變化時(shí)明文聚類與OPTICS-CMED模型客戶端和服務(wù)器運(yùn)行時(shí)間的對(duì)比.數(shù)據(jù)表明，其運(yùn)行時(shí)間隨n線性增長(zhǎng)，服務(wù)器承擔(dān)了主要的開銷，減輕了客戶端的負(fù)擔(dān).

表3 明文聚類與OPTICS-CMED的時(shí)間開銷對(duì)比Table 3 Time cost comparison of plaintext clutering and OPTICS-CMED

6 結(jié)束語(yǔ)

針對(duì)面向密文數(shù)據(jù)的OPTICS聚類研究成果較少的問(wèn)題，利用全同態(tài)加密構(gòu)建了面向密文數(shù)據(jù)的OPTICS聚類模型(OPTICS-CMED).首先，對(duì)OPTICS-CMED的實(shí)體構(gòu)成進(jìn)行介紹，給出了形式化定義，詳細(xì)描述了模型的通信協(xié)議及其在聚類過(guò)程中的調(diào)用方式，從正確性、安全性兩方面進(jìn)行理論分析，通過(guò)實(shí)驗(yàn)對(duì)模型進(jìn)行性能測(cè)試，結(jié)果表明本文設(shè)計(jì)的OPTICS-CMED能夠在密文下完成聚類運(yùn)算，同時(shí)可以保證在密文下的聚類效果，具有一定的實(shí)際應(yīng)用價(jià)值.