安全的常数轮多用户k-均值聚类计算协议

秦 红 王 皓,2 魏晓超 郑志华

1(山东师范大学信息科学与工程学院 济南 250358) 2(广西密码学与信息安全重点实验室(桂林电子科技大学) 广西桂林 541004)

随着云计算、物联网及移动互联网等新一代信息技术的迅速发展，新增数据量呈现爆炸式增长态势，人类社会已经进入了大数据时代.利用这些海量的数据执行数据分析，能够创造难以估量的价值.聚类是数据分析中最常使用的技术之一，目前已被广泛应用于信息检索[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+yn+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-均值聚类

安全计算聚类模型的关键，是能够安全地计算样本点到每个聚类中心的距离，并找到与每个样本点距离最近的聚类中心.这里涉及到的基本运算有加(减)法运算、乘法运算、除法运算、比较运算等.

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=λ.

3)Dec(sk,[m])→m，解密算法.以私钥sk=λ和密文[m]为输入，计算

Paillier加密方案具有加法同态性质，对密文执行乘法操作与对明文执行加法操作后再加密等价.假设明文m1,m2∈ZN，则有：

① [m1+m2modN]=[m1]×[m2] modN2；

② [kmmodN]=([m])kmodN2.

由以上性质可以平凡地得到减法计算公式[m1-m2modN]=[m1]×[m2]N-1modN2.

在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]实现对电路的计算.

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) 存在概率多项式时间模拟器S1和S2，使得:

2) 联合输出和功能函数的输出满足:

{outputπ(x,y,κ)}x,y,κ≅{f(x,y)}x,y，

其中,x,y∈{0,1}*,≅表示计算不可区分，则π能够在半诚实模型中安全地计算f.

2 基础功能函数的安全实现

2.1 基于加法同态密文的两方乘法计算

参与方：P1和P2.

初始化：P1调用Paillier加密方案中的密钥生成算法KeyGen，生成公钥pk和私钥sk.

输入：P1的输入为pk,sk,P2的输入为pk以及使用pk加密得到的密文[x]和[y];

输出：P1无输出,P2输出[xy].

①P2均匀随机地选择rx,ry∈ZN，计算x′=[x]×[rx]，y′=[y]×[ry]，并将x′和y′发送给P1；

②P1对x′和y′解密后得到x+rxmodN和y+rymodN，计算h=(x+rx)(y+ry) modN，并对其加密[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 安全性证明

[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的视图为

由于协议中rx,ry是在ZN中均匀随机选择的，因此x+rxmodN和y+rymodN在ZN中是均匀分布的.因此:

从而:

.

2)P2被腐化.根据协议可知P2的视图:

因此:

证毕.

2.2 基于加法同态密文的两方距离计算

参与方：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]);

①P2在本地计算[xi-yi]=[xi]×[yi]N-1，i=1,2,…,l;

③P2在本地计算：

2.2.3 安全性分析

2.3 基于加法同态密文的最小元素标记

参与方：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)中最小元素的序号.

在本协议中，我们先将P2掌握的同态密文转换为P1和P2分享的算术秘密份额，并利用文献[26]中的份额转换技术进行A2Y转换，将算术秘密分享份额转换为Yao分享份额.然后，调用Yao协议安全计算arg min(·)函数获得序列中最小元素序号的Yao分享份额，并通过安全计算equality(·,·)函数获得最小元素标记序列的Yao分享份额.随后调用Y2A转换，得到相应的算术秘密分享份额.最后，将算术秘密分享份额再转换为P2掌握的同态密文形式.以上操作均可通过常数轮交互完成，具体描述为：

2.3.3 安全性证明

证明. 首先我们给出协议的正确性证明.

最后根据Paillier加密方案的加法同态性质可知，P2掌握了向量F=(f1,f2,…,fk)对应的密文向量[F]=([f1],[f2],…,[fk]).

下面，我们在半诚实敌手模型下证明该协议的安全性，分别针对P1被腐化和P2被腐化2种情况讨论.

1)P1被腐化.根据协议可知P1的视图:

因此，对于任意的pk,sk,[D]，

{S1(pk,sk)}pk,sk,[D]≅

2)P2被腐化.根据协议可知P2的视图:

因此，对于任意的pk,sk,[D]，有:

证毕.

2.4 基于加法同态密文的两方除法计算

参与方：P1和P2.

初始化：调用Paillier加密方案中的密钥生成算法KeyGen，生成公钥pk和私钥sk.

输入：P1的输入为pk,sk,P2的输入为pk以及使用pk加密得到的密文[x]和[y];

2.4.3 安全性证明

下面，我们在半诚实敌手模型下证明该协议的安全性，分别针对P1被腐化和P2被腐化2种情况讨论.

1)P1被腐化.根据协议可知P1的视图:

2)P2被腐化.根据协议可知P2的视图:

因此对于任意的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之间运行一个两方安全计算协议，具体描述如下.

参与方：聚类计算方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的具体构造

对于矩阵Mδ的第j列，j=1,2,…,k，AS进行加法同态运算：

4) 对于第j个聚类，j=1,2,…,k，AS计算该聚类中样本数量的密文

作为本轮第j个聚类中心对应的密文.

3.3.3 安全性证明

证明. 首先，对协议的正确性进行分析.

下面对新一轮聚类中心的计算是按向量数据的每一个分量进行的.我们先对明文数据进行分析，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维分量.

1)C被腐化.根据协议可知C的视图:

由于{[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，满足:

2)AS被腐化.根据协议可知AS的视图:

根据Paillier加密方案的IND-CPA安全性可知:

因此对于任意的pk,sk,{[Xi]}i=1,2,…,n，满足:

4 效率分析及性能测试

我们在表1中分析了辅助计算服务器AS和聚类计算方C的计算量.

Table 1 Efficiency Analysis表1 效率分析

我们在配置为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聚类安全计算协议.与以往的同类协议相比，本协议无需对密文进行昂贵的比特分解操作，且仅需要常数轮交互.在本协议中，服务器能够承担大部分计算量，用户仅需少量在线计算.同时，我们在半诚实敌手模型下给出了该协议的安全性证明.