随着云计算、物联网及移动互联网等新一代信息技术的迅速发展，新增数据量呈现爆炸式增长态势，人类社会已经进入了大数据时代.利用这些海量的数据执行数据分析，能够创造难以估量的价值.聚类是数据分析中最常使用的技术之一，目前已被广泛应用于信息检索[1-2]、机器学习[3]和模式识别[4]等诸多领域.k-均值(k-means)聚类算法[5-6]是一种最为典型的聚类算法，它能快速有效地处理较大的数据集合.该算法采用迭代更新的方式，并分为初始化和聚类计算2个阶段.在初始化阶段，随机选定k个数据点作为初始簇的簇中心；在聚类计算阶段，计算数据点到簇中心的距离，并将数据划分到距离它最近的簇中心所在的簇，然后重新计算新簇的中心，即新簇内数据点的几何均值.重复执行上述过程直到计算收敛或达到算法的终止条件，则聚类结束.
通常，如果样本数据属于单个实体(本文称为用户)，则可以采用本地计算的方式完成聚类计算.然而，在实际应用场景中，样本数据往往属于不同的用户(如政府、企业、机构、个人等)，并需要在其联合数据集上进行聚类计算.出于隐私保护的目的，用户不希望与其他用户共享私有数据，因此，如何在保护数据隐私性的前提下实现多用户的k-均值聚类计算受到了广泛关注.
2000年Lindell和Pinkas[7]首次将安全多方计算技术用于解决隐私保护的决策树训练问题，随后基于安全多方计算技术解决各类数据挖掘与机器学习场景中的隐私保护问题成为了研究热点[8-10].其中针对聚类计算问题，Jha等人[11]针对两方水平分割数据的场景设计了安全的聚类计算协议.协议中，参与方P1和P2分别持有样本数据集D1和D2，他们希望在样本数据集D1∪D2上运行k-均值算法.在每次迭代过程中，参与方独立地在本地数据集上计算聚类中心和聚类的大小，然后调用安全的聚合协议，求得本轮迭代的聚类结果.安全的聚合协议可以抽象为P1持有(x,n)，P2持有(y,m)，P1和P2联合计算x+y
n+m的问题.Jha等人分别使用不经意多项式求值和同态加密安全地实现了上述功能.同年，Jagannathan和Wright[12]在两方的场景下引入了任意分割数据的概念，作为垂直和水平分割数据的一般化形式，并在半诚实模型下提供了一个保护双方隐私的k-means聚类算法.然而，他们的协议泄露了中间信息，即迭代的中间过程对样本分配的簇号，因此安全性存在局限.随后，Bunn和Ostrovsky[13]也针对任意分区的数据提出了一个通用的两方隐私保护k-means聚类协议，他们将解决单个数据集的k-means聚类算法扩展到2个数据集上，并在不泄露中间信息的前提下有效计算了算法的输出结果.具体地，该方案在处理数据时，使用同态加密计算新“簇”的加权平均值，从而将单数据集k-means算法[14]扩展为半诚实安全模型下的两方k-means聚类算法.他们协议的通信成本与文献[12]相似，但实现了抵抗半诚实敌手的安全性保证.
除了两方持有数据的情况外，n方持有数据的场景也得到了研究者的关注.2003年Vaidya和Clifton[15]借助同态加密和随机置换技术构造了安全的n方聚类计算协议.在该协议中，设置了3个不合谋的特殊参与方P1,P2和Pn.P1负责为每个参与方生成用于盲化的随机向量，且满足n个向量的和为0向量.同时，P1秘密地选择一个随机置换，其余参与方能够获得置换后的盲化向量，但并不清楚该置换具体是什么.P2和Pn负责执行安全的加法和比较运算，最后P1通过拟置换获取结果.该方案能够支持对数据集的垂直分割.Doganay等人[16]使用了类似的思想，但与文献[15]不同的是，他们使用秘密分享代替了同态加密.
在外包计算场景中，解决聚类模型的安全训练问题也得到了研究者们的关注.在文献[17]中，Upmanyu等人使用支持加法同态和乘法同态的余数系统，解决了聚类计算的安全外包问题，该方案要求至少有3个不合谋的云服务器提供外包计算服务，可以支持n个用户数据的聚类计算;随后，Liu等人[18]提出了单用户聚类计算的安全外包协议，该协议使用了同态加密[19]和保序加密[20]，然而该协议在执行过程中，需要用户参与;随后Liu等人[21]同样使用文献[18]中的密码技术，提出两方聚类计算的安全外包协议;2015年Rao等人[22]基于2个不合谋的服务器C1和C2，使用加法同态加密、保序加密、比特分解[23]等技术，解决了n方安全的聚类计算问题.在该方案中，服务器C2生成Paillier加密的公私钥，用户使用公钥加密数据后，将数据交由C1计算.C1和C2通过交互，完成密文乘法和比较等运算;然而，比特分解的计算复杂度较高，每一次比特分解过程需要3|m|+1次加密和4|m|+2次求幂运算，其中|m|为整数m的位长度.很明显，当处理较长的数据时，协议的效率较低;在Rao等人[22]工作的基础上，Kim和Chang[24]对安全比较子协议进行了简化，他们的方法无需使用比特分解技术，然而方案存在信息泄露，无法给出形式化的安全性证明;近期，Jiang等人[25]针对外包场景的聚类计算协议使用了新的安全比较子协议，然而该比较协议仍然需要基于昂贵的比特分解技术，且具有较高的交互复杂度.
本文基于Demmler等人提出的ABY框架[26]设计了对同态密文的最小元素标记协议和除法协议，协议使用同态密文与算术分享份额、算术分享份额与Yao分享份额之间的相互转换，通过常数轮交互实现了对密文序列中最小元素的标记以及密文的除法运算，且无需使用昂贵的比特分解技术.在此基础上，我们设计了常数轮的多用户k-均值聚类安全计算协议，并在半诚实模型下给出了协议形式化的安全性证明.
1 预备知识
1.1 k-均值聚类
聚类模型试图将数据集中的样本划分为若干个不相交的子集，每个子集称为一个“簇”(cluster).具体地，假定样本集D={X1,X2,…,Xn}包含n个无标记样本，每个样本Xi=(xi,1,xi,2,…,xi,l)是一个l维特征向量，则聚类算法将样本集D划分为k个不相交的簇{Ci|i=1,2,…,k}，其中
且
相应地，我们用λj∈{1,2,…,k}表示样本Xj的“簇标记”(cluster label)，即Xj∈Cλj.于是，聚类的结果可用包含n个元素的簇标记向量λ=(λ1,λ2,…,λn)表示.直观上，我们希望聚类结果的“簇间相似度”(inter-cluster similarity)低且“簇内相似度”(intra-cluster similarity)高.k-means算法[4-5]作为一种常用的聚类方法，在实际应用中有显著成效.该算法针对聚类所得簇划分C={C1,C2,…,Ck}最小化平方误差
其中
是簇Ci的均值向量，E值越小则簇内样本的相似度越高.k-means算法通过迭代计算来不断优化聚类结果，其步骤是首先随机选取k个初始的聚类中心，然后计算各样本与各聚类中心的距离并将样本分配给距离它最近的聚类中心所组成的簇.每完成一次样本分类后，就要重新计算一次新“簇”的加权平均值并作为新簇的聚类中心，这个过程将不断重复直到满足设定的终止条件，比如E取最小值，或迭代轮数到达预设的最大值.
安全计算聚类模型的关键，是能够安全地计算样本点到每个聚类中心的距离，并找到与每个样本点距离最近的聚类中心.这里涉及到的基本运算有加(减)法运算、乘法运算、除法运算、比较运算等.
1.2 同态加密
同态加密是一种具有特殊性质的加密方案，支持对密文进行运算，其运算结果等同于先对明文进行运算后再进行加密.正是由于这种特殊性质，使得同态加密在构造各类密码方案和安全协议中起着关键作用.具体地，对于一个加密方案E=(KeyGen,Enc,Dec)(其中KeyGen是密钥生成算法，Enc是加密算法，Dec是解密算法)，如果给定2个密文c1=Enc(pk,m1)和c2=Enc(pk,m2)(pk为公钥)，在不掌握私钥和明文的前提下可以高效计算c1⊕c2满足c1⊕c2=Enc(pk,m1+m2)，则称该加密方案满足加法同态，其中⊕可视为对密文进行广义的加法操作，要求c1⊕c2是对m1+m2进行加密所得的密文.类似地，若c1⊗c2=Enc(pk,m1×m2)，则称该加密方案满足乘法同态，其中⊗可视为对密文进行广义的乘法操作.
本文用到具备加法同态性质的Paillier加密方案[19]，该方案包含3个算法：
1) KeyGen(1k)→pk,sk，密钥生成算法.任选2个大素数p和q，其中|p|=|q|=1k，计算N=pq和λ=φ(N).输出公钥pk=N和私钥sk=λ.
2) Enc(pk,m)→[m]，加密算法.以公钥pk=N和明文m∈ZN为输入，选择一个随机的
计算密文[m]=(1+N)mrNmod N2.
3) Dec(sk,[m])→m，解密算法.以私钥sk=λ和密文[m]为输入，计算
Paillier加密方案具有加法同态性质，对密文执行乘法操作与对明文执行加法操作后再加密等价.假设明文m1,m2∈ZN，则有：
① [m1+m2mod N]=[m1]×[m2] mod N2；
② [km mod N]=([m])kmod N2.
由以上性质可以平凡地得到减法计算公式[m1-m2 mod N]=[m1]×[m2]N-1 mod N2.
在Paillier加密方案的同态运算中，对密文的乘法操作均是在模N2下进行的，相应明文的加法操作均是在模N下进行的，我们在后文的描述中不再逐一说明.此外，Paillier加密方案具有选择明文攻击下的不可区分性(indistinguishability under chosen plaintext attack， IND-CPA)[27]，即对于等长的消息m0和m1，其密文是计算不可区分的[m0]≅[m1].
1.3 ABY混合协议
2015年Demmler等人[26]提出了支持两方混合协议的ABY框架，该框架支持算术分享(arithmetic sharing, A)、布尔分享(Boolean sharing, B)、Yao分享(Yao sharing, Y)之间的快速转换，其中算术分享使用Beaver乘法三元组[28]实现加法、乘法等算术计算，布尔分享使用GMW协议[29]实现异或、逻辑与等布尔计算，Yao分享使用Yao混乱电路协议[30]实现对电路的计算.
我们采用与文献[26]相同的表达方式，即x的分享份额分别记为
和
在本文中，仅用到算术分享和Yao分享以及对应的2种转换方式A2Y和Y2A.
A2Y转换是指将两方持有的算术分享份额转换为对应的Yao分享份额，而Y2A是指将Yao分享份额转换为对应的算术分享份额.
1.4 两方安全计算
1.4.1 形式化定义
安全两方计算[31]是一个两方的随机过程，将一对输入(每个参与方对应一个输入)映射为一对输出(每个参与方对应一个输出)，同时保持一系列安全性，如正确性、隐私性、输入独立性等.该随机过程被称为功能函数(functionality)，可以形式化地表示为一个双输出的函数f=(f1,f2)，即f:{0,1}*×{0,1}*→{0,1}*×{0,1}*.对于输入(x,y)，其中x为P1的输入，y为P2的输入，输出(f1(x,y),f2(x,y))，其中f1(x,y)为P1的输出，f2(x,y)为P2的输出.在这个过程中，任何参与方无法获得输出之外的任何信息.
1.4.2 安全模型
定义1. 半诚实模型[32].令f=(f1,f2)是一个确定性的功能函数，π是计算f两方协议.对于安全参数κ，以及一对输入(x,y)(其中x是P1的输入，y是P2的输入)，协议π中Pi(i=1,2)的视图表示为
其中w∈{x,y}，ri代表Pi所使用的随机性，
代表Pi接收到的第j条消息，其中j∈{1,2,…,t}.Pi的输出使用
表示，两方的联合输出表示为
我们说如果满足：
1) 存在概率多项式时间模拟器S1和S2，使得:
2) 联合输出和功能函数的输出满足:
{outputπ(x,y,κ)}x,y,κ≅{f(x,y)}x,y，
其中,x,y∈{0,1}*,≅表示计算不可区分，则π能够在半诚实模型中安全地计算f.
2 基础功能函数的安全实现
本节介绍了设计多用户k-means聚类安全计算协议所需要的基础功能函数，其中乘法计算协议
和距离计算协议
参考了文献[33]的方法.此外，我们设计了常数轮交互的最小元素标记协议
和除法计算
协议，并对以上4类基础协议进行了形式化的安全性证明.
2.1 基于加法同态密文的两方乘法计算
2.1.1 功能函数
参与方：P1和P2.
初始化：P1调用Paillier加密方案中的密钥生成算法KeyGen，生成公钥pk和私钥sk.
输入：P1的输入为pk,sk,P2的输入为pk以及使用pk加密得到的密文[x]和[y];
输出：P1无输出,P2输出[xy].
2.1.2 协议
的具体构造
① P2均匀随机地选择rx,ry∈ZN，计算x′=[x]×[rx]，y′=[y]×[ry]，并将x′和y′发送给P1；
② P1对x′和y′解密后得到x+rxmod N和y+rymod N，计算h=(x+rx)(y+ry) mod N，并对其加密[h]=Enc(pk,h)，将密文[h]发送给P2；
③ P2计算[x]N-ry=[-xry]，[y]N-rx=[-yrx]，[rxry]N-1=[-rxry]，然后计算:
[h]×[-xry]×[-yrx]×[-rxry]=[xy].
2.1.3 安全性证明
定理1. 协议在半诚实模型中安全计算了
证明. 协议的正确性由：
[h]×[-xry]×[-yrx]×[-rxry]=
[(x+rx)(y+ry)]×[-xry]×[-yrx]×
[-rxry]=[xy+xry+yrx+rxry-
xry-yrx-rxry]=[xy]
保证.
我们在半诚实敌手模型下证明该协议的安全性，分别针对P1被腐化和P2被腐化2种情况讨论.
1) P1被腐化.根据协议可知P1的视图为
(pk,sk,[x]×[rx],[y]×[ry])，
构造模拟器S1，其输入为pk,sk(P1在该协议中没有输出).模拟器均匀随机选择
使用公钥pk加密得到
模拟器的输出
由于协议中rx,ry是在ZN中均匀随机选择的，因此x+rxmod N和y+rymod N在ZN中是均匀分布的.因此:
从而:
{S1(pk,sk)}pk,sk,[x],[y]≅
.
2) P2被腐化.根据协议可知P2的视图:
(pk,[x],[y],[xy],rx,ry,[h])，
构造模拟器S2，其输入是pk,[x],[y],[xy].模拟器均匀随机地选择
计算
并使用公钥pk加密得到
模拟器的输出:
S2(pk,[x],[y],[xy])=
由于Paillier加密算法满足IND-CPA安全性，因此对于任意的pk,sk,[x],[y]，以及随机选择的
满足:
[h]=[(x+rx)(y+ry)]≅
因此:
{S2(pk,[x],[y],[xy])}pk,sk,[x],[y]≅
证毕.
2.2 基于加法同态密文的两方距离计算
2.2.1 功能函数
参与方：P1和P2.
初始化：P1调用Paillier加密方案中的密钥生成算法KeyGen，生成公钥pk和私钥sk.
输入：P1的输入为pk,sk,P2的输入为pk以及使用pk加密2个l维向量X=(x1,x2,…,xl)和Y=(y1,y2,…,yl)得到的密文向量([x1],[x2],…,[xl])和([y1],[y2],…,[yl]);
输出：P1无输出,P2输出距离值
对应的密文
2.2.2 协议
的具体构造
① P2在本地计算[xi-yi]=[xi]×[yi]N-1，i=1,2,…,l;
② P2与P1调用两方乘法功能函数
得到[(xi-yi)2]，i=1,2,…,l.
③ P2在本地计算：
2.2.3 安全性分析
根据Paillier算法的安全性以及协议
的安全性，该协议显然在
模型下是安全的.
2.3 基于加法同态密文的最小元素标记
2.3.1 功能函数
参与方：P1和P2.
初始化：P1调用Paillier加密方案中的密钥生成算法KeyGen，生成公钥pk和私钥sk.
输入：P1的输入为pk,sk,P2的输入为使用pk加密k维向量D=(d1,d2,…,dk)得到的密文向量[D]=([d1],[d2],…,[dk]);
输出：P1无输出,P2输出一个k维的密文向量[F]=([f1],[f2],…,[fk])，其中ft=1，fj∈[1,k],j≠t=0，t=arg min(D)，表示向量D=(d1,d2,…,dk)中最小元素的序号.
2.3.2 协议
的具体构造：
在本协议中，我们先将P2掌握的同态密文转换为P1和P2分享的算术秘密份额，并利用文献[26]中的份额转换技术进行A2Y转换，将算术秘密分享份额转换为Yao分享份额.然后，调用Yao协议安全计算arg min(·)函数获得序列中最小元素序号的Yao分享份额，并通过安全计算equality(·,·)函数获得最小元素标记序列的Yao分享份额.随后调用Y2A转换，得到相应的算术秘密分享份额.最后，将算术秘密分享份额再转换为P2掌握的同态密文形式.以上操作均可通过常数轮交互完成，具体描述为：
① 对于j=1,2,…,k，P2均匀随机地选择
作为dj的算术秘密分享份额(P2掌握[dj]),计算
将
发送给P1.
② 对于j=1,2,…,k，P1运行解密算法，得到
从而得到
③ P1和P2分别拥有向量D=(d1,d2,…,dk)的算术秘密份额
和
和P2分别以
和
为输入，运行A2Y转换，得到向量D=(d1,d2,…,dk)的Yao分享份额
和
在A2Y转换以及后文对Yao协议的应用中，我们不妨规定P1为电路构造方，P2为电路计算方.
④ 双方调用Yao协议，计算函数arg min(D)[34]，并分别得到D中最小元素的序号t对应的Yao分享份额
和
⑤ 对于j=1,2,…,k，双方调用Yao协议，计算函数equality(j,t)，并将输出结果记为fj.当j=t时，equality(j,t)=1，双方获得1的Yao分享份额，即
当j≠t时，equality(j,t)=0，双方获得0的Yao分享份额，即
⑥ P1持有
持有
其中ft=1，fj∈[1,k],j≠t=0，t=arg min(D).双方运行Y2A转换，分别得到对应的算术秘密分享份额
和
⑦ P1以pk和
为输入，调用加密算法Enc，得到
并将其发送给P2.
⑧ 对于j=1,2,…,k，P2同样调用加密算法Enc得到
计算
得到k维密文向量[F]=([f1],[f2],…,[fk]).
2.3.3 安全性证明
定理2. 协议在半诚实模型中安全计算了
证明. 首先我们给出协议的正确性证明.
根据Paillier加密方案的加法同态性质可知
即P1和P2分别掌握dj的算术秘密份额
和
其中j=1,2,…,k.
根据文献[26]中，A2Y转换的性质，P1和P2分别掌握向量D=(d1,d2,…,dk)的Yao分享份额
和
根据Yao协议的正确性，t为向量D中最小元素的序号.对于j=1,2,…,k，测试j与t的相等性，则可以得到向量F=(f1,f2,…,fk)，其中ft=1，fj∈[1,k],j≠t=0.由于使用了Yao协议，P1和P2分别掌握向量F=(f1,f2,…,fk)的Yao分享份额，即
和
根据文献[26]中Y2A转换的性质，P1和P2将Yao分享份额转换为算术分享份额和
即对于j=1,2,…,k，有
最后根据Paillier加密方案的加法同态性质可知，P2掌握了向量F=(f1,f2,…,fk)对应的密文向量[F]=([f1],[f2],…,[fk]).
下面，我们在半诚实敌手模型下证明该协议的安全性，分别针对P1被腐化和P2被腐化2种情况讨论.
1) P1被腐化.根据协议可知P1的视图:
构造模拟器S1，其输入为pk,sk(P1在该协议中没有输出).模拟器均匀随机地选择
使用公钥pk加密得到
模拟器针对arg min(·)和equality(·,·)电路的每条输入、输出线w，随机选择
(η为Yao协议的安全参数)作为线路w上的Yao分享份额，即随机生成
模拟器均匀随机地选择
模拟器S1的输出:
由于在协议中，
是在ZN中均匀随机选取的，因此
在ZN中是均匀分布的，因此
根据A2Y转换的安全性，
根据Yao协议的安全性，
根据Y2A转换的安全性，
因此，对于任意的pk,sk,[D]，
{S1(pk,sk)}pk,sk,[D]≅
2) P2被腐化.根据协议可知P2的视图:
构造模拟器S2，其输入为pk,[D],[F]，模拟器均匀随机地选择
并针对arg min(·)和equality(·,·)电路的每条输入、输出线w，随机选择kw∈{0,1}η(η为Yao协议的安全参数)作为线路w上的Yao分享份额，即随机生成
模拟器均匀随机地选择
并使用公钥pk加密V得到[V]=([v1],[v2],…,[vk])，并计算[U]=([f1-v1],[f2-v2],…,[fn-vn]).模拟器S2的输出
S2(pk,[D]，[F])=(pk,[D]，[F],S,
由于协议中是在
中均匀随机地选择的，因此
根据A2Y转换的安全性，
根据Yao协议的安全性，
根据Y2A转换的安全性，
根据Paillier加密所满足的IND-CPA安全性，
因此，对于任意的pk,sk,[D]，有:
{S2(pk,sk)}pk,sk,[D]≅
证毕.
2.4 基于加法同态密文的两方除法计算
2.4.1 功能函数
参与方：P1和P2.
初始化：调用Paillier加密方案中的密钥生成算法KeyGen，生成公钥pk和私钥sk.
输入：P1的输入为pk,sk,P2的输入为pk以及使用pk加密得到的密文[x]和[y];
输出：P1无输出,P2输出
2.4.2 协议
的具体构造
① P2均匀随机地选择
作为x的算术分享份额，
作为y的算术分享份额，计算
和
并发送给P1；
② P1解密后得到
和
此时P1和P2已掌握x和y的算术秘密份额；
③ P1和P2分别以
和
作为输入执行A2Y转换，得到对应的Yao分享份额
和
④ 双方调用Yao协议，计算函数
并将结果记为z，此时P1得到
得到
④ P1和P2分别以
和
作为输入执行Y2A转换，分别得到z的算术秘密分享份额
和
⑤ P1对进行加密得到
并发送给P2；
⑥ P2对
进行加密得到
并计算
2.4.3 安全性证明
定理3. 协议在半诚实模型中安全计算了
证明. 首先，我们给出协议的正确性证明.
根据Paillier加密方案的加法同态性质可知，P1和P2分别掌握(x,y)的算术分享份额和
根据文献[26]中A2Y的性质，经过A2Y转换后，P1和P2分别掌握(x,y)的Yao分享份额和
根据Yao协议的正确性知
且P1和P2分别掌握z的Yao分享份额和
根据文献[26]中Y2A转换的性质，经过Y2A转换后，P1和P2分别掌握z的算术分享份额和
即
最后根据Paillier加密方案的加法同态性质可知，P2输出
下面，我们在半诚实敌手模型下证明该协议的安全性，分别针对P1被腐化和P2被腐化2种情况讨论.
1) P1被腐化.根据协议可知P1的视图:
构造模拟器S1，其输入为pk,sk(P1在该协议中没有输出).模拟器随机选择
使用公钥pk加密得到
模拟器针对DIV(x,y)电路的每条输入、输出线w，随机选择(η为Yao协议的安全参数)作为线路w上的Yao分享份额，即随机生成
模拟器在ZN范围内均匀随机的选择
并输出
由于在协议中，
和
是均匀随机选取的，因此和
是在ZN中均匀分布的，因此
根据A2Y转换的安全性，
根据Yao协议的安全性，
根据Y2A转换的安全性，
因此，对于任意的pk,sk,[x],[y]，有:
{S1(pk,sk)}pk,sk,[x],[y]≡
2) P2被腐化.根据协议可知P2的视图:
构造模拟器S2，其输入是
模拟器随机选择
并使用公钥pk加密得到
模拟器针对DIV(x,y)电路的每条输入、输出线w，随机选择kw∈{0,1}η(η为Yao协议的安全参数)作为线路w上的Yao分享份额，即随机生成
并在ZN范围内均匀随机的选择
模拟器的输出
根据Paillier加密算法满足IND-CPA安全性，
根据A2Y转换的安全性，
根据Yao协议的安全性，
根据Y2A转换的安全性，
因此对于任意的pk,sk,[x],[y]，满足:
证毕.
3 常数轮多用户k-均值聚类安全计算协议
3.1 系统模型
Fig. 1 System model of secure k-means clustering
图1 k-means聚类安全计算系统模型
系统中存在n个数据拥有方(data owner) DO1,DO2,…,DOn，1个聚类计算方(cluster calculator, C)和1个辅助计算服务器(assisted server， AS).每个数据拥有方DOi独立地拥有计算聚类所需的私有数据Xi，他们愿意配合聚类计算方C在他们的全体数据上进行聚类计算，然而出于隐私保护的考虑，DOi不希望其他实体(包括聚类计算方C、辅助计算方AS以及其他数据拥有者DOj，j≠i)能够获取其私有数据.在这里，我们假设系统中的所有实体都是半诚实的，并且聚类计算方C与辅助计算服务器AS之间不能合谋.系统运行共分为2个阶段：初始化阶段和聚类计算阶段.系统模型如图1所示：
3.2 初始化阶段
1) 聚类计算方调用Paillier加密方案的密钥生成算法KeyGen，生成一对公私钥pk和sk.
2) 数据拥有者DOi(i=1,2,…,n)使用公钥pk对其矢量数据Xi=(xi,1,xi,2,…,xi,l)加密，我们规定
[Xi]=Enc(pk,Xi)=(Enc(pk,xi,1),
Enc(pk,xi,2),…,Enc(pk,xi,l))=
([xi,1],[xi,2],…,[xi,l]),
将[Xi]=([xi,1],[xi,2],…,[xi,l])发送给辅助计算服务器AS.由于我们假设聚类计算方C与辅助计算服务器AS之间不能合谋，因此在初始化阶段数据的安全性可以由Paillier加密方案的安全性保障.
3.3 聚类计算阶段
在本阶段中，聚类计算方C与辅助计算服务器AS之间运行一个两方安全计算协议，具体描述如下.
3.3.1 功能函数
参与方：聚类计算方C、辅助计算方AS.
输入：聚类计算方C的输入为Paillier加密方案的公钥pk，私钥sk；辅助计算方AS的输入为公钥pk以及原始数据对应的密文{[Xi]=([xi,1],[xi,2],…,[xi,l])}i=1,2,…,n.
输出：聚类计算方C输出k个聚类中心Y1,Y2,…,Yk，其中,Yj=(yj,1,yj,2,…,yj,l)；辅助计算服务器AS无输出.
3.3.2 协议πCluster的具体构造
1) 辅助计算服务器AS根据预设的聚类中心的数量k，均匀随机地选择k个初始的聚类中心
并使用公钥pk对
进行加密得到密文
2) 辅助计算服务器AS与聚类计算方C执行运算：AS以[Xi],i∈{1,2,…,n}和
为输入，与C调用两方距离计算功能函数
，其中C作为P1，AS作为P2，τ表示聚类计算过程中迭代的轮数.AS得到
yj,k)2].然后，AS以k维密文向量[Di]=([Di,1],[Di,2],…,[Di,k])为输入，与C调用最小元素标记功能函数
其中C作为P1，AS作为P2.AS得到k维密文向量[fi]=([fi,1],[fi,2],…,[fi,k])，其中fi,t=1，其余fi,j≠t=0，t为向量(Di,1,Di,2,…,Di,k)中最小元素的序号.
3) 对于δ=1,2,…,l，AS分别以[xi,δ]和[fi,1],[fi,2],…,[fi,k]为输入与C调用两方乘法功能函数
其中C作为P1，AS作为P2.将结果记为
对于矩阵Mδ的第j列，j=1,2,…,k，AS进行加法同态运算：
4) 对于第j个聚类，j=1,2,…,k，AS计算该聚类中样本数量的密文
AS以([Σ1,j],[Σ2,j],…,[Σl,j])和[NUMj]为输入，与C调用两方除法功能函数
其中C作为P1，AS作为P2.AS得到
作为本轮第j个聚类中心对应的密文.
5) 重复步骤2)～4)，直到达到设定的最大轮数τMax(通常为小常数，在本文的测试中τMax=8)，AS将
发送给C.
6) C解密得到k个聚类中心
3.3.3 安全性证明
定理4. 协议πCluster在
(混合)模型中能够抵御半诚实敌手，即安全计算
证明. 首先，对协议的正确性进行分析.
通过调用功能函数，AS能够得到每一个数据{Xi}i∈[1,n]到所有聚类中心距离对应的密文向量{([Di,1],[Di,2],…,[Di,k])}i=1,2,…,n，其中Di,j代表数据Xi到聚类中心Yj的距离.然后通过调用功能函数
得到一个m维密文向量([fi,1],[fi,2],…,[fi,k])，其中fi,t=1，其余fi,j≠t=0，t为向量(Di,1,Di,2,…,Di,k)中最小元素的序号，代表数据Xi距离第t个聚类中心最近，即在本轮迭代中，数据Xi属于第t个聚类.
下面对新一轮聚类中心的计算是按向量数据的每一个分量进行的.我们先对明文数据进行分析，xi,δ代表数据Xi的第δ维分量，那么:
xi,δ(fi,1,fi,2,…,fi,k)=
(xi,δfi,1,xi,δfi,2,…,xi,δfi,k)=
(0,0,…,0,xi,δ,0,…,0).
其中,只有第t个分量是xi,δ，其余分量均为0.
因此，对于矩阵Q，
按列相加的结果为第j个聚类(对应第j列)中所有数据第k个分量相加之和，再除以该聚类中数据的数量(即计算算术平均值)，就可以得到新一轮聚类中心的第k维分量.
在协议中以上数据是以密文的方式计算的，其正确性分别由
以及Paillier加密方案的加法同态性保证，在此不再展开说明.
下面，我们在
模型下证明该协议的安全性，分别针对C被腐化和AS被腐化2种情况讨论.为了方便讨论，我们仅考虑一轮迭代的情况，多轮迭代仅是对一轮迭代的重复.
1) C被腐化.根据协议可知C的视图:
vie
({pk,sk},{pk,{[Xi]}i=1,2,…,n})=
构造模拟器SC，其输入为
模拟器使用公钥pk对
进行加密得到
因此模拟器的输出:
由于{[Yj]}j=1,2,…,k和{[Yj]*}j=1,2,…,k是对{Yj}j=1,2,…,k在不同加密(随机算法)过程得到的密文，且Paillier加密方案满足IND-CPA安全性，因此:
从而，对于任意的pk,sk,{[Xi]}i=1,2,…,n，满足:
{
({pk,sk},{pk,
{[Xi]}i=1,2,…,n})}pk,sk,{[Xi]}i=1,2,…,n≅
2) AS被腐化.根据协议可知AS的视图:
vie
({pk,sk},{pk,{[Xi]}i=1,2,…,n})=
{[Di]}i=1,2,…,n,{[fi]}i=1,2,…,n,
构造模拟器SAS，其输入为pk,{[Xi]}i=1,2,…,n.模拟器均匀随机地选择
使用pk对
加密得到
均匀随机地选择
并使用pk对其加密得到
求
然后根据
设置
并使用pk对其加密得到
模拟器以
和{[Xi]}i=1,2,…,n为输入，利用Paillier加密方案明文与密文相乘的运算规则，计算
模拟器的输出:
SAS(pk,{[Xi]}i=1,2,…,n)=
由于
是均匀随机选择的，因此:
根据Paillier加密方案的IND-CPA安全性可知:
因此对于任意的pk,sk,{[Xi]}i=1,2,…,n，满足:
{
({pk,sk},
{pk,{[Xi]}i=1,2,…,n})}pk,sk,{[Xi]}i=1,2,…,n≅
{SAS(pk,{[Xi]}i=1,2,…,n)}pk,sk,{[Xi]}i=1,2,…,n.
4 效率分析及性能测试
我们在表1中分析了辅助计算服务器AS和聚类计算方C的计算量.
Table 1 Efficiency Analysis
表1 效率分析
PartyComputationAS(2nkl+kl+3l+2nk2)E+(nk2)D+(3nkl+nk2)X+2nYEC(nkl+4nk2+4kl+l)E+(2nkl+nk2+kl+2l)D+2nYC
Note: n is the number of samples; k is the number of clusters; l is dimensions of sample; E is the computation for one encryption; D is the computation for one decryption; X is the computation for one modular exponentiation; YC is the computation of constructor in Yao protocol; YE is the computation of evaluator in Yao protocol.
我们在配置为i5-4200H,8 G的笔记本电脑上，借助MIRACL开源库[36]和ABY开源库[37]对协议性能进行了测试.具体地，我们把样本数据的维数固定为2，使用50～500个随机样本，针对聚类数量k取值6,8,10这3种情况进行性能测试.由于在初始化阶段，数据拥有者可以离线加密各自的数据，在聚类计算阶段，可以使用性能强大的云计算服务作为辅助计算服务器，因此我们只关注了聚类计算方的运行时间，如图2所示:
Fig. 2 Running time of cluster calculator
图2 聚类计算方运行时间
图3为随机选取500个样本、聚类中心设为6时的效果图.
Fig. 3 Cluster result
图3 聚类效果图
5 总 结
本文针对多用户持有数据的场景，对k-means聚类的安全计算问题进行了研究，借助Paillier加密、ABY混合协议框架等密码学工具以及独立的辅助计算服务器实现了对密文乘、除、欧氏距离的计算和最小元素的标记.在此基础上，设计了常数轮交互的多用户k-means聚类安全计算协议.与以往的同类协议相比，本协议无需对密文进行昂贵的比特分解操作，且仅需要常数轮交互.在本协议中，服务器能够承担大部分计算量，用户仅需少量在线计算.同时，我们在半诚实敌手模型下给出了该协议的安全性证明.
[1]Pantel P, Lin Dekang. Document clustering with committees[C] //Proc of the 25th Annual Int ACM SIGIR Conf on Research and Development in Information Retrieval. New York: ACM, 2002: 199-206
[2]Liu Ming, Liu Bingquan, Liu Yuanchao. A fast clustering algorithm for information retrieval[J]. Journal of Computer Research and Development, 2013, 50(7): 1452-1463 (in Chinese)(刘铭, 刘秉权, 刘远超. 面向信息检索的快速聚类方法[J]. 计算机研究与发展, 2013, 50(7): 1452-1463)
[3]Lin Xiaodong, Clifton C, Zhu M Y. Privacy-preserving clustering with distributed EM mixture modeling[J]. Knowledge & Information Systems, 2005, 8(1): 68-81
[4]Baraldi A, Blonda P. A survey of fuzzy clustering algorithms for pattern recognition[J]. IEEE Transactions on System Man & Cybernetics, 1999, 29(6): 778-785
[5]Wagstaff K, Cardie C, Rogers S, et al. Constrained k-means clustering with background knowledge[C] //Proc of the 18th Int Conf on Machine Learning. New York: ACM, 2001: 577-584
[6]Likas A, Vlassis N, Verbeek J J. The global k-means clustering algorithm[J]. Pattern Recognition, 2003, 36(2): 451-461
[7]Lindell Y, Pinkas B. Privacy preserving data mining[C] //Proc of the 20th Annual Int Cryptology Conf. Berlin: Springer, 2000: 36-54
[8]Nikolaenko V, Weinsberg U, Ioannidis S, et al. Privacy-preserving ridge regression on hundreds of millions of records[C] //Proc of the 2013 IEEE Symp on Security and Privacy. Piscataway, NJ: IEEE, 2013: 334-348
[9]Mohassel P, Zhang Yupeng, Secure M L. A system for scalable privacy-preserving machine learning[C] //Proc of the 2017 IEEE Symp on Security and Privacy. Piscataway, NJ: IEEE, 2017: 19-38
[10]Zhang Yudi, He Debiao, Zhang Mingwu, et al. A provable-secure and practical two-party distributed signing protocol for SM2 signature algorithm[J]. Frontiers of Computer Science, 2020, 14(3): No.143803
[11]Jha S, Kruger L, McDaniel P D. Privacy preserving clustering[C] //Proc of the 10th European Conf on Research in Computer Security. Berlin: Springer, 2005: 397-417
[12]Jagannathan G, Wright R N. Privacy-preserving distributed k-means clustering over arbitrarily partitioned data[C] //Proc of the 11th ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining. New York: ACM, 2005: 593-599
[13]Bunn P, Ostrovsky R. Secure two-party k-means clustering[C] //Proc of the 14th ACM Conf on Computer and Communications Security. New York: ACM, 2007: 486-497
[14]Ostrovsky R, Rabani Y, Schulman L J, et al. The effectiveness of Lloyd-type methods for the k-Means problem[C] //Proc of the 47th IEEE Symp on Foundations of Computer Science. Piscataway, NJ: IEEE, 2006: 165-176
[15]Vaidya J, Clifton C. Privacy-preserving k-means clustering over vertically partitioned data[C] //Proc of the 9th ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining. New York: ACM, 2003: 206-215
[16]Doganay M C, Pedersen T B, Saygin Y, et al. Distributed privacy preserving k-means clustering with additive secret sharing[C] //Proc of the 2008 Int Workshop on Privacy and Anonymity in Information Society. New York: ACM, 2008: 3-11
[17]Upmanyu M, Namboodiri A M, Srinathan K, et al. Efficient privacy preserving k-means clustering[C] //Proc of the 2010 Pacific Asia Conf on Intelligence and Security Informatics. Berlin: Springer, 2010: 154-166
[18]Liu Dongxi, Bertino E, Xun Yi. Privacy of outsourced k-means clustering[C] //Proc of the 9th ACM Symp on Information, Computer and Communications Security. New York: ACM, 2014: 123-134
[19]Paillier P. Public-Key cryptosystems based on composite degree residuosity classes[C] //Proc of the Int Conf on the Theory and Application of Cryptographic Techniques. Berlin: Springer, 1999: 223-238
[20]Liu Dongxi, Wang Shenlu. Programmable order-preserving secure index for encrypted database query[C] //Proc of the 2012 IEEE Int Conf on Cloud Computing. Piscataway, NJ: IEEE, 2012: 502-509
[21]Liu Xiaoyan, Jiang Z L, Yiu S M, et al. Outsourcing two-party privacy preserving k-means clustering protocol in wireless sensor networks[C] //Proc of the 2015 IEEE Int Conf on Mobile Ad-hoc and Sensor Networks. Piscataway, NJ: IEEE, 2015: 124-133
[22]Rao F Y, Samanthula B K, Bertino E, et al. Privacy-preserving and outsourced multi-user k-means clustering[C] //Proc of the 2015 IEEE Conf on Collaboration and Internet Computing. Piscataway, NJ: IEEE, 2015: 80-89
[23]Samanthula B K, Hu Chun, Jiang Wei. An efficient and probabilistic secure bit-decomposition[C] //Proc of the 8th ACM SIGSAC Symp on Information, Computer and Communications Security. New York: ACM, 2013: 541-546
[24]Kim H J, Chang J W. A privacy-preserving k-means clustering algorithm using secure comparison protocol and density-based center point selection[C] //Proc of the 2018 IEEE Int Conf on Cloud Computing. Piscataway, NJ: IEEE, 2018: 928-931
[25]Jiang Z L, Guo Ning, Jin Yabin, et al. Efficient two-party privacy-preserving collaborative k-means clustering protocol supporting both storage and computation outsourcing[J]. Information Sciences, 2020, 518: 168-180
[26]Demmler D, Schneider T, Zohner M. ABY-A framework for efficient mixed-protocol secure two-party computation[C] //Proc of the Network and Distributed System Security Symp. Reston, VA: The Internet Society, 2015
[27]Fujisaki E, Okamoto T. How to enhance the security of public-key encryption at minimum cost[C] //Proc of the 2nd Int Workshop on Practice and Theory in Public Key Cryptography. Berlin: Springer, 1999: 53-68
[28]Beaver D. Efficient multiparty protocols using circuit randomization[C] //Proc of the 11th Annual Int Cryptology Conf. Berlin: Springer, 1991: 420-432
[29]Goldreich O, Micali S, Wigderson A. How to play any mental game or a completeness theorem for protocols with honest majority[C] //Proc of the 19th Annual ACM Symp on Theory of Computing. New York: ACM, 1987: 218-229
[30]Yao A C. Protocols for secure computations (extended abstract)[C] //Proc of IEEE Symp on Foundations of Computer Science. Piscataway, NJ: IEEE, 1982: 160-164
[31]Goldreich O. Foundations of Cryptography: Volume 2, Basic Applications[M]. Cambridge, UK: Cambridge University Press, 2009
[32]Hazzy C, Lindell Y. Efficient Secure Two-party Protocols: Techniques and Constructions[M]. Berlin: Springer, 2010
[33]Elmehdwi Y, Samanthula B K, Jiang Wei. Secure k-nearest neighbor query over encrypted data in outsourced environments[C] //Proc of the 30th IEEE Int Conf on Data Engineering. Piscataway, NJ: IEEE, 2014: 664-675
[34]Kolesnikov V, Sadeghi A, Schneider T. Improved garbled circuit building blocks and applications to auctions and computing minima[C] //Proc of the 8th Int Conf on Cryptology and Network Security. Berlin: Springer, 2009: 1-20
[35]Demmler D. Towards practical privacy-preserving protocols[D]. Darmstadt, Germany: Technische Universität, 2019
[36]Scott M, Spector B, McCusker K, et al. MIRACL Cryptographic SDK[OL]. [2020-05-10]. https://github.com/miracl/MIRACL
[37]Demmler D, Braun L, Schoppmann P, et al. ABY Framework[OL]. [2020-05-16]. https://github.com/encryptogroup/ABY
