具有隐私保护的分布式协作统计计算方案

马 飞，蒋建国

（1.合肥工业大学 计算机与信息学院，安徽 合肥230009；2.北方民族大学 计算机科学与工程学院，宁夏 银川750021）

0 引 言

随着Internet的快速发展，参与统计分析的数据往往来自于多个数据源，而目前多数据源的隐私保护统计计算方案 主要 是基 于 加 密 技 术 的 方 案［1－4］和SMC （secure multiparty computation）［5－8］方案。由于基于加密的方案涉及过多的加解密过程，较为低效，而SMC由于涉及过多繁琐的协议交互过程，不适用于相对计算简单的统计分析问题。如何在互不信任的多数据源环境下对数据进行统计计算且不破坏敏感数据的隐私性是一个具有重要理论意义与实际应用价值的研究课题。

本文利用Paillier加密 算 法［9－11］的 加 法 同 态 性 质［12，13］设计了一种在互不信任的分布式环境下具有隐私保护的协作统计分析方案。该方案不但使用户的隐私数据在整个统计计算过程中都处于被保护状态，而且充分利用了分布式环境下的高计算与存储能力，由用户端与服务器端协作完成整个统计计算过程。

1 Paillier公钥加密算法及其加法同态性

（1）密钥生成：选择两个素数p和q，计算N ＝pq，λ＝lcm（p－1，q－1），然后选择一个随机数g ∈Z＊N2，需满足gcd（L（gλmod N2），N）＝1，此处L（x）＝（x－1）／N。Paillier的公钥和私钥分别为＜N，g ＞和λ。

（2）加密操作：令m ∈ZN为明文，r∈ZN为一随机数，用E（·）表示加密操作

（3）解密操作：给定密文c∈ZN2，D（·）表示用私钥λ进行解密，计算公式如下

为保证Paillier算法语义安全，必须N 与g 足够大。m1，m2，r1，r2∈ZN，都有下式成立

式 （3）与式 （4）表明：在密文域上做 “乘”运算，其运算结果等于明文域上先做 “加”运算，然后对结果进行加密之后的输出，这是Paillier算法的加法同态性。

2 几种典型统计计算公式变换与同态计算

2.1 统计计算公式变换

为了能够应用Paillier算法的加法同态性到统计计算中，需对统计计算公式做等价变换：

（1）算术平均：假设样本空间为｛x1，…xn｝，算术平均可表示为

（2）方差：方差表征变量X 取值的散度，其变换后的计算公式如下

（3）线 性 回 归：设 有 数 据 集：｛（x1，y1），…，（xi，yi）…（xn，yn）｝，一元线性回归的目的是找到线性方程y ＝a＋bx 去拟合这个数据集，最常采用最小二乘法来确定参数a与b，等价变换后的计算公式如下

（4）相关系数：变量X 与Y 的相关系数是用来衡量两者之间线性关系的强度与方向，其变换后的计算公式如下

2.2 加法同态性与统计计算

符号定义：①Kpk：Paillier加密算法的公钥，由统计服务器提供给参与统计计算的各个客户端。②Epk（ ）：Paillier加密操作。参与统计计算的客户端用Kpk加密其隐私数据。

3 方案拓扑结构及计算步骤

3.1 拓扑结构与组成

如图1所示，方案采用环形拓扑结构，参与统计计算的用户数据采用单向传递。结构中有3种不同类型的结点：CClient，KClient，SServer。

图1 方案拓扑结构

（1）SServer：统计计算服务器：①完成最终的统计计算并输出统计结果。②给参与统计计算的客户端提供Paillier算法的公钥。

（2）CClient：参与统计计算的用户客户端：①提供加密统计数据：用SServer提供的公钥加密统计数据以保证隐私性。②参与统计计算：利用Paillier算法的加法同态性来参与隐私统计计算。

（3）KClient：把各CClient经过同态计算得到的中间统计结果最终交于SServer。若其也有数据需参加统计计算，则也完成CClient的两种操作。

3.2 方案执行步骤

（1）计算步骤

1）SServer利用Paillier算法生成一对密钥，把公钥广播给参与统计计算的CClient。各CClient用Paillier算法公钥加密各自的隐私数据与整数 “1”，若无隐私数据参与统计计算，则加密 “0”。

2）加密隐私数据在环中进行单向传递，参与统计计算的CClient用其前趋传递过来的加密数据与自己的加密数据做同态计算，把结果传递给其后继。

3）经过计算与传递，加密中间统计结果最终到达KClient，由其交于SServer后由SServer用Paillier加密算法私钥解密，并将解密结果带入到相应的统计计算公式中，得到最终的统计结果并输出。

说明：每个有数据需要参与统计计算的客户端都加密“1”，并让其也参与计算和传递，最后参与计算的客户端数n将以加密形式交于统计计算服务器。若客户端无数据参与统计计算，则为了满足协议的一致性要求，也必须加密“0”，即：EPK（0）。该EPK（0）需要参与以下两个运算，其结果并不影响最终的统计值

（2）分布式隐私保护计算 “算术平均”实例

输入：每个CClient都具有隐私数据xi，i ∈N，N 为CClient的个数。X ＝｛x1，...，xi，...，xN｝。

目标：由各CClient与SServer协作计算统计量X 的“算术平均”，且不破坏xi的隐私性。

设CClientX、CClientY、CClientZ为单向逻辑环中的客户端，xa、xb、xc分 别 为 它 们 的 隐 私 数 据。CClientX 与CC－lientZ分别为CClientY 的前趋与后继。

步骤1 设CClientX、CClientY 与CClientZ 的隐私数据经 加 密 后 分 别 为：Epk（xa）、Epk（xb）、Epk（xc），并 且 每 个CClient都有一个Epk（1）。

步骤2 CClientX 把Epk（1）与Epk（xa）传递给其后继CClientY 后，CClientY 进行如下计算

CClientY 把Epk（xa＋xb）与Epk（1＋1）传递给其后继CClientZ，CClientZ做如下计算

CClientZ把Epk（xa＋xb＋xc）与Epk（1＋1＋1）向其后继传递，其它CClient进行类似处理过程。

步骤3 KClient将收到如下加密中间统计结果

KClient 把Epk（ux）与Epk（n）交 于SServer，并 被SServer解密得到ux与n，代入式 （5），珚x 即为所求 “算术平均”。在统计计算的整个过程中，若CClient无统计数据参与统计计算，则执行Epk（0）操作，并按式 （13）与式（14）参与计算，然后按协议要求进行数据传递。

方差、线性回归、相关系数的计算过程除所用公式不同以外，其它皆与上述计算步骤一致。

4 方案安全性分析与性能测试

4.1 方案安全性分析

SHM 模式 （semi－honest mode）［14］：参 与 统 计 计 算 的CClient、KClient和SServer都遵循统计计算的步骤，但希望在计算的过程中能够获得除了最终统计计算结果以外的其它额外信息。

（1）攻击模型：

CASE1：全部CClient可信，SServer不可信；

攻击目的：所有CClient遵循方案要求的统计计算步骤，但非可信SServer想获得各CClient的隐私数据。

CASE2：部分CClient共谋，SServer可信；

攻击目的：SServer可信，部分共谋CClient希望推出非共谋CClient的隐私数据或中间计算结果。

CASE3：部分CClient共谋，SServer不可信；

攻击目的：部分CClient与SServer共谋，希望获得非共谋CClient的隐私数据。

（2）安全性分析：

对于第1种攻击，方案中，加密数据经过计算与单向传递后，SServer最终获得的是加密后的中间结果，所以即使SServer对其进行解密，也无法推出CClient各自的原始隐私数据。

对于第2种攻击，由于所有CClient的隐私信息及中间计算结果都被可信的SServer的公钥所加密，而在SServer私钥安全的情况下，共谋CClient是无法对其解密，故非共谋CClient的隐私信息在计算的任何阶段都不会被泄露。

对于第3 种攻击，设n 为CClient的总数，m 为共谋CClient的个数。①当m ＝n－1时，即只有一个CClient是非共谋，其它n－1个CClient都与SServer共谋，当非共谋CClient把隐私统计数据用SServer的公钥加密后交于其后继结点，后继结点与其它共谋CClient仍然按照协议要求的步骤执行，但都只用加密后的 “0”与非共谋的CClient的加密隐私数据做同态计算并把结果按环拓扑结构单向传递。最终SServer收到的数据其实就是非共谋CClient的加密隐私数据，SServer对其解密即可获得非共谋CClient的隐私数据。②当m ＜n－1时，即非共谋的CClient个数≥2时，按照协议的计算步骤，SServer收到的一定是非共谋CClient隐私数据做加法之后的中间结果的加密形式，所以SServer即使对其解密，也无法从隐私数据 “和”中反推出非共谋CClient各自的隐私数据。故对于本方案，只要满足m ＜n－1条件，则共谋的CClient与SServer不能推出非共谋CClient的隐私数据。

4.2 方案性能测试

测试所实现方案在计算 “方差”、 “回归系数”和 “相关系数”时的时间代价。

由于方案采用分布式计算统计量，计算的时间代价主要集中在两方面：①单个客户端对数据进行Paillier算法加密，及进行加性同态计算时所用时间。②统计服务器对中间统计结果进行解密及计算最终统计结果所用时间。

方案实现环境参数：CClient、KClient、SServer都采用性能一致的Acer笔记本电脑，共设置了7台电脑，其中具有CClient身份的电脑共5台，KClient和SServer各一台。设备通过IEEE 802.11g网络进行互联。具体参数见表1。

表1 方案实现环境参数

为了保证Paillier加密算法有足够的语义安全［15］，设置参数：N ：1024bit g：160bit。公钥＜N，g ＞：1184bit，密文为2048－bit。基于以上参数，Paillier加密过程实质是做两次1024－bit的幂运算，一次2048－bit的乘法运算，而解密过程是做一次2048－bit的幂运算。私钥与公钥利用生成算法在模型运行前按要求位数已生成。方案的客户端模块 （CClient）和服务器端模块 （SServer）都处于工作状态。共进行了30次测试。

符号定义：

tE（·）表示单次Paillier加密操作所用时间；

tD（·）表示单次Paillier解密操作所用时间；

tH（·）表示单次同态操作所用时间；

Tout：指SServer对收到的中间结果进行解密所用时间与计算最终统计结果的时间之和。

计算 “方差”时间代价见表2。

表2 计算 “方差”时间代价

计算 “回归系数”时间代价见表3。

表3 计算 “回归系数”时间代价

计算 “相关系数”时间代价见表4。

表4 计算 “相关系数”时间代价

tE（·）和tH（·）是在5台CClient上分别进行测试得到相应的数值，tD（·）与Tout是在SServer上测试得到。单个CClient做加密及同态运算所花费时间与方案规模 （参与统计计算的用户端数）无关。SServer最后对中间结果解密及计算最终统计结果所用时间也与规模无关。

4.3 方案特点与应用展望

（1）方案特点：①隐私数据由客户端独立进行存储，方便用户对数据施加灵活的访问控制。统计计算由客户端与服务器共同完成，从而降低了传统服务器由于集中进行统计计算与存储而带来的安全隐患及计算复杂性过高的问题，适用于大数据量计算。②数据的传递过程也是统计计算的过程，不必事先合并数据。除了中间统计结果及最终的统计结果以外，用户个体隐私数据在整个统计计算过程中都处于保密状态。③加密只在客户端提供原始统计数据时出现，而解密操作也仅在统计服务器对中间统计结果进行解密时发生，所以方案只涉及很少的加解密过程。

（2）方案不足：对于部分CClient与SServer进行共谋的攻击，必须满足非共谋CClient的个数大于1时方案才能正确执行，这将是以后需要对方案改进的地方。

（3）方案应用展望：医疗系统中监测患者体征的可穿戴设备、智能电网中的智能电表等都需要采集设备环境或用户的体征数据，而这些数据都具有很强的隐私性，对这类数据进行统计分析时，则可采用本文提出的方案。本文只实现了Windows环境下的方案，下一步可对方案进行Android环境下的实现。

5 结束语

统计分析是数据挖掘领域重要的工具之一，但在分布式环境下对具有隐私保护的统计计算技术的研究还比较少。针对该问题，利用Paillier加密算法的加法同态性，提出了一种在互不信任的分布式环境下具有隐私保护的协作统计计算方案。该方案充分利用分布式环境的计算能力，由用户客户端与统计服务器协作对数据进行相关系数、算术平均、方差与线性回归等统计分析，整个分析过程对用户隐私数据都进行了有效的保护。最后论证了方案在SHM 模式下的安全性，并对方案进行了性能测试。

［1］LI Chaoling，CHEN Yue.Fragmentation and encryption－based pri－vacy－preserving mechanism for cloud database［J］.Journal of Information Engineering University，2012，13 （3）：376－384 （in Chinese）.［李超零，陈越.基于分解与加密的云数据库隐私保护机制研究［J］.信息工程大学学报，2012，13 （3）：376－384.］

［2］QIAN Ping，WU Meng.Survey of privacy preserving data mining methods based on homomorphic encryption ［J］.Application Research of Computers，2011，28 （5）：45－50 （in Chinese）. ［钱萍，吴蒙.同态加密隐私保护数据挖掘方法综述［J］.计算机应用研究，2011，28 （5）：45－50.］

［3］ZHANG Bin.Research on efficient secure basic protocols of multiparty computation and their application ［D］.Jinan：Shandong University，2012：77－81 （in Chinese）. ［张斌.高效安全的多方计算基础协议及应用研究 ［D］.济南：山东大学，2012：77－81.］

［4］SONG Maohua.Research on secure mulit－party computation and its application ［D］.Beijing：Beijing University of Posts and Telecommunications，2013：37－39 （in Chinese）. ［孙 茂华.安全多方计算及其应用研究 ［D］.北京：北京邮电大学，2013：37－39.］

［5］WEI Zhiqiang，KANG Mijun.Research on privacy－protection policy for pervasive computing ［J］.Chinese Journal of Computers，2010，33 （1）：128－138 （in Chinese）. ［魏志强，康密军.普适计算隐私保护策略研究 ［J］.计算机学报，2010，33 （1）：128－138.］

［6］Ziba Eslami，Saideh Kabiri Rad.A new verifiable multi－secret sharing scheme based on bilinear maps［J］.Wireless Personal Communications，2012，63 （2）：459－467.

［7］PANG Lei，SUN Maohua.Full privacy preserving electronic voting scheme［J］.The Journal of China Universities of Posts and Telecommunications，2012，19 （4）：45－48.

［8］YE Yun.Research on protecting and utilizing private data in cooperative computation ［D］.Hefei：University of Science and Technology of China，2012：90－93 （in Chinese）. ［叶云.保护私有数据合作计算问题及其应用研究 ［D］.合肥：中国科学技术大学，2012：90－93.］

［9］BAI Jian，YANG Yatao，LI Zichen.The homomorphism and efficiency and analysis of Paillier cryptosystem ［J］.Journal of Beijing Electronic Science and Technology Institute，2012，25（4）：77－81 （in Chinese）. ［白健，杨亚涛，李子臣.Paillier公钥密码体制同态特性及效率分析 ［J］.北京电子科技学院学报，2012，25 （4）：77－81.］

［10］ZHOU Qinqting.Research on scalar product protocol based on Paillier cryptosystem ［D］.Kunming：Yunnan University，2012：57－60 （in Chinese）.［周青婷.基于Paillier密码体制的点积协议研究 ［D］.昆明：云南大学，2012：57－60.］

［11］LI Meiyun，LI Jian，HUANG Chao.A credible cloud storage platform based on homomorphic encryption ［J］.Netinfo Security，2012，12 （9）：35－40 （in Chinese）.［李美云，李剑，黄超.基于同态加密的可信云存储平台 ［J］.信息网络安全，2012，12 （9）：35－40.］

［12］Gentry C.Fully homomorphic encryption using ideal lattices［C］／／Proc of the ACM Int’l Symp on Theory of Computing，2009：13－17.

［13］REN Fule，ZHU Zhixiang.A cloud computing security solution based on fully homomorphic encryption ［J］.Journal of Xi’an University of Posts and Telecommunications，2013，25（5）：56－58 （in Chinese）.［任福乐，朱志祥.基于全同态加密的云计算数据安全方案 ［J］.西安邮电大学学报，2013，25 （5）：56－58.］

［14］ZHENG Qiang.Study on several secure multi－party computation problem in different models ［D］.Beijing：Beijing University of Posts and Telecommunications，2011：12－15 （in Chinese）.［郑强.不同模型下若干安全多方计算问题的研究［D］.北京：北京邮电大学，2011：12－15.］

［15］Dong W，Wang V.Secure friend discovery in mobile social network ［C］／／INFOCOM，2011：46－48.