基于同态加密的统计数据处理

【 摘 要 】 数据挖掘和数据统计技术在为人们带来便利的同时也对用户隐私造成了一定的威胁，针对数据挖掘中的个人隐私泄漏问题，利用Paillier算法和RSA算法设计了一个全同态加密算法，基于该算法提出了一种数据统计方案，该方案的使用能够保证在只需对用户数据的密文操作的情况下便能完成数据统计。最后将该方案应用于医疗数据统计，并进行了模拟实现，实现结果表明可以利用全同态加密技术对数据密文进行统计操作。

【 关键词 】 同态密码；统计计算；Java语言；隐私信息

【 中图分类号 】 TP 【 文献标识码 】 A

【 Abstract 】 Data mining and data statistical techniques bring convenience for the people，but at the same time，to some extent， they caused the threat of user’s privacy.According to the reveal problem of user’s privacy in data mining，we designed a fully homomorphic encryption algorithm by using Paillier algorithm and RSA algorithm，based on which，a data statistics scheme is presented ，which can ensure that the user can complete data statistics just under the condition of cipher operation.Finally the scheme was applied to the medical data statistics，and is simulated.Results show that it is available to use the homomorphic encryption technology to the statistical data cipher operation.

【 Keywords 】 homomorphism password； statistics calculation； the Java language； privacy information

1 引言

隐私数据与人们的生活息息相关。然而，一些不法分子通过非法渠道，获取他人的隐私信息，这样的行为，严重影响了人们的生活。不法分子通过黑客技术窃取隐私信息，并利用窃取到的隐私信息进行非法交易和买卖。这种问题屡见不鲜，且在近期内仍然没有得到有效解决。

现阶段，随着大数据时代的到来，越来越多决策的制定需要对隐私数据进行挖掘和统计处理。而在进行这些操作的时候，隐私数据很容易在传输过程中被人截取。因此，数据挖掘和数据统计处理在对隐私数据的保护方面仍然面临着诸多挑战。越来越多的人也对隐私数据的安全问题表示担忧，甚至拒绝提供真实数据。这样的现象，严重阻碍了大数据时代下社会的进步和发展，同时也影响了科学技术的提高和创新。自然而然地，如何在不暴露个人隐私信息的前提下安全地进行数据挖掘，成为了大家高度关注也亟待解决的课题。

1978年，由Rivest等人首次提出了同态加密（Homomorphic Encryption）的概念，是一种允许直接对密文进行操作的加密技术。

以往加密手段的一个弊端在于它通常是将数据保存在盒子内而不让外界使用或者分析数据，除非使用解密密钥将盒子打开，而完全同态加密方案可以让你在数据加密的情况下对数据进行分析和计算。这就相当于将数据放在一个黑盒子里，不用钥匙打开，也能够对这些数据进行相关操作。

如果说，一种加密算法，对于乘法和加法都能找到对应的操作，就称其为全同态加密算法。换句话说，它的意义就在于，对于允许任意复杂的明文操作，都能构造出相应的加密操作。但直到目前还没有真正可用的全同态加密算法，因为“在同态加密方案成为实用工具前，还需要进行很多理论上的工作以提高其效率”。不过，目前相关研究人员正在对其进行研究，算法的有效性正在逐步提高。

同态密码这项技术的关键点在于“双盲”设计――可以检测加密漏洞并进行修复，而不会造成信息泄露。

2 背景知识

2.1 同态密码

同态加密是满足一定性质的加密算法。公钥密码体制下的同态加密算法可描述如下：

定义1 同态加密算法体制是满足下列条件的一个六元组{M，C，K，E，D，}：

（1） M是明文空间；（2） C是密文空间；（3） K是公私钥对集合；（4） 是同态运算符；（5） 对于任意的（pk，sk）∈K（pk称作公钥，sk称作私钥），对应一个加密算法Epk∈E（E是加密算法集合，E：MC）和解密算法Dsk∈D（D是解密算法集合，D：CM），且对任意的m∈M，满足c=Epk（m），m=Dsk（c）=Dsk（Epk（m）），其中Epk、Dsk都是多项式时间内可执行的；（6） 对于所有的（pk，sk）∈K，由Epk推出Dsk是计算上不可能的；（7） 对任意的x，y∈M，Epk（x）Epk（y）=Epk（xy）。

根据运算符的不同，可分为加同态算法和乘同态算法。满足加同态性的算法可表述为Epk（m1）Epk（m2）=Epk（m1+m2）；乘同态性的算法可表述为Epk（m1）Epk（m2）=Epk（m1，m2）。以此，我们可以对同态加密进行分类，仅仅能实现一种同态性的算法称为部分同态加密算法；满足所有同态性质的算法称为全同态加密算法。

2.2 统计数据处理

在当前信息化时代，数据成为人们关注研究的重点。数据需要经过统计处理才能够实现其价值，而统计也需要数据作为支撑。统计数据处理过程通常包括数据采集、数据过滤、数据存储、数据管理、数据分析、数据结果、数据结果、数据失效。相关统计部门可以通过抽查、问卷、调查等方式进行数据的收集，这一过程中得到的数据有些是无效数据，需要进行数据的预处理，过滤出行之有效的数据，然后就可以对有效数据进行存储，为之后的统计操作做好准备。数据会随着时间的推移而不断增长，因此需要对数据进行系统化的管理和分类。数据分析就是对数据进行挖掘，通过求和、筛选、方差等方法进行统计计算，挖掘出有用信息，然后由相关部门进行信息，产生对社会和国民有意义的导向作用。最后就是需要对数据进行定期清理，因为有些数据在当下可能已经没加任何价值了。这就是统计数据处理的整个过程，不难发现，数据里面暗藏着巨大的价值，特别是人们最关心的个人隐私数据。从数据安全角度出发，数据泄露将会产生不可估量的后果，文章基于数据统计安全，利用同态密码使之既能进行统计计算，又能保证数据不被泄露。

3 方案设计

基于全同态密码算法的优势，我们结合了Paillier算法[3]和RSA算法[4]构成一个全同态加密算法，用以满足加法同态和乘法同态。下面我们先对Paillier算法和RSA算法进行简要的介绍。

3.1 Paillier算法

密钥生成：设p、q是两个大素数，n=pq，g∈Z，记L（x）=，公钥pk=（n，g），密钥sk=λ（n）=lcm（p-1，q-1）。

加密阶段：任意明文m∈Zn，随机选择r∈Z*n，那么密文c=Epk（m）=gm rn mod n2。

解密阶段：解密得明文m=Dsk（c）=mod n。

Paillier算法是安全性基于DCR假设的一种概率公钥加密算法，具有加法同态性。

3.2 RSA算法

密钥生成：设p、q是两个大素数，n=pq，根据欧拉定理φ（n）=（p-1）（q-1），随机选择整数d、e，使得gcd（e，φ（n））=1，ed1（mod φ（n）），则公钥pk=（n，e），私钥sk=d。

加密阶段：明文空间M中的任意一消息m，对应密文c=Epk（m）=me（mod n）。

解密阶段：m=Dsk（c）=md（mod n）。

RSA算法是目前应用比较广泛的一种同态加密算法，不难发现其满足乘法同态。

3.3 一种新的全同态密码方案

通过上述介绍，我们知道了Paillier算法具有加法同态性，即对任意经过Paillier算法加密的密文进行加法操作其结果等于原始明文进行加法操作的结果；RSA算法具有乘法同态性，即任意经过RSA算法加密的密文进行乘法操作其结果等于原始明文进行乘法操作的结果。那么当我们需要进行加法操作时就选择Paillier算法，需要进行乘法时就选择RSA算法。方案模型如图1所示。

（1） 对已有明文数组m=（m1，m2，...，mt）分别进行Paillier加密和RSA加密。用户首先任取两个大素数p和q，然后计算n=pq。对于Paillier算法加密，需要计算公钥pk=（n，g）和私钥sk=λ（n），具体计算步骤如下：

首先计算λ（n）=lcm（p-1，q-1），在Z中选取g，使其满足gcd（L（gλ mod n2 ），n）=1，其中L（x）=。

得到Paillier算法的公钥pk和私钥sk。现在开始加密，密文计算方法如下：Cp=gm * rn mod n2

于是得到Paillier密文数组Cp=（cp1，cp2，...，cpt）；对于RSA算法加密，同样需要计算公钥pk=（n，e）和私钥sk=d，具体计算步骤如下：

首先计算φ（n）=（p-1）*（q-1），在1和φ（n）之间随机选取e，其中e需要满足gcd（e，φ（n））=1。然后计算d，使得ed1（mod φ（n））。

完成之后得到RSA算法的公钥pk=（n，e）和私钥sk=d，现在开始加密，密文计算方法如下：CR=me（mod n）。

最终得到两分密文：Cp=（cp1，cp2，...，cpt）和CR=（cR1，cR2，...，cRt）

（2） 判断统计方法，这里主要运算有两种，一种是求和，另一种是求积。求和的算法如下：c+ =c1*c2 。

求积的算法如下：c* =c1*c2 。

需要注意的是求和运算需要用Paillier密文数组Cp=（cp1，cp2，...，cpt），求积运算需要用RSA密文数组CR=（cR1，cR2，...，cRt）。

（3） 判断是否继续。如果运算继续那么返回（2）继续执行，否则就进行解密。通过Paillier加密的就执行3.1中的解密阶段，通过RSA加密的就执行3.2中的解密阶段。

通过上述分析，将Paillier算法和RSA算法的结合，设置特定的运算方式，就能够使得既满足了加法同态性，又满足了乘法同态性。根据定义1，该方案为“全同态加密方案”。有了这个加密算法之后，我们就可以将其应用在统计计算中。众所周知，统计计算其实就是一些四则运算的组合。鉴于当前的统计计算都是对明文进行直接处理，这就使得数据的安全性得不到保障，而且数据被泄露的概率比较高。所以，统计过程中，我们要想数据尽可能不被别人窃取，那么就不要直接对明文进行操作。可以将数据先分别进行Paiiiler加密和RSA加密，然后再让相应人员对密文进行统计操作。我们知道，数据的加密过程需要使用“全同态加密方案”，对加密出来的密文进行相应的四则运算，就相当于对明文进行操作一样。这就使得数据的安全性大大提高，有效的防止了源数据的泄露问题。

4 全同态密码方案在医疗数据统计中的应用

为了验证文章中提出的全同态加密方案，我们对某医院的病例情况做了统计处理（在检验结果准确性时，为了对数据进行保密，我们仅提供了部分原数据）。

其原始数据如下（姓名为化名）：

现要求对数据进行统计，计算数据中的平均年龄。

（1）利用系统的加密客服端对原始数据进行加密并获得密文文件。这里我们在系统中，选择姓名、性别以及年龄属性分别进行Paillier加密和RSA加密，具体加密流程参照3.3节。得到两份密文文件，分别命名为Paillier密文和RSA密文，如图3、4所示。

（2）对密文文件进行统计处理，并生成密文统计结果。首先对年龄列进行求和，即采用Paillier密文，计算完毕后得到求和密文CP，对其进行解密，得到求和明文mP=619.5，然后对mP进行RSA加密，加密的公钥和私钥采用之前对文件进行加密的公钥和私钥，这样保证一致性。然后进行除法运算，得到密文结果CR。对CR进行RSA解密，得到明文结果mR=30。

由此，我们计算得到该数据表中平均年龄为30岁。当然这一个数据是肯定无法说明什么问题的，但是按照这种想法继续进行计算，那么将会得到更多可用有效信息。

通过上述测试，文章提出的方案可以正确执行。当然这只能是在数据量较少，统计计算方法比较简单的情况下能够计算。如果要进行实际应用，那么还需进行深入研究，继续改进并优化算法。

5 结束语

本文提出了一种基于同态密码的数据统计方案，并给出了该方案的详细操作过程和计算方法。在此方案的基础上，将同态密码应用在数据的统计计算上，实现了在不知道明文的情况下，对密文进行统计操作，保证了隐私数据的安全性。

但是本文所用方案依然存在一些问题，运算效率不高以及运算能力较弱，这些问题都有待于进一步深入研究。

参考文献

[1] Rivest R L， Adleman L， Dertouzos M L. On data banks and privacy homomorphisms[J]. Foundations of secure computation， 1978， 4（11）： 169-180.

[2] http：///wiki/同态加密.

[3] 白健. Paillier公钥密码体制同态特性及效率分析[J].北京电子科技学院学报， 2012，20（4）：1-5.

[4] 宋晓莉. RSA算法的研究与实现[J].信息安全与通信保密， 2005， （12）：70-72. DOI：10.3969/j.issn.1009-8054.2005.12.037.

[5] 汤殿华，祝世雄，曹云飞.一个较快速的整数上的全同态加密方案[J]. 计算机工程与应用， 2012，48（28）：117-122.

[6] 冯登国，张敏，李昊.大数据安全与隐私保护[J].计算机学报， 2014，37（1）：.246-258.

[7] 张福泰，李继国等.密码学教程[M].武汉：武汉大学出版社，2006.

[8] 徐鹏，刘超，斯雪明.基于整数多项式环的全同态加密算法[J].计算机工程，2012，38（24）：1-4.

[9] 陈志伟，白健等.基于同态加密的密文数据库统计模型的设计与实现[J].技术研究，2013，3：12-15.

[10] Hirt M， Sako K. International Conference on Theory & Application of Cryptographic Techniques[M]. Springer Berlin Heidelberg， 2000：539-556.

基金项目：

国家自然科学基金项目（No. 61262073）；全国统计科学研究计划项目（No. 2013LZ46）；贵州省自然科学基金项目（No.20092113）；大学生创新创业训练计划项目（贵大（国）创字2014005）。

作者简介：

李雪松（1992-），男，贵州铜仁人，贵州大学，本科在读；主要研究方向和关注领域：密码学与信息安全。

彭长根（1963-），男，贵州贵阳人，贵州大学，工学博士学位，博士生导师，教授；主要研究方向和关注领域：密码学与信息安全。

李明伟（1992-），男，贵州凯里人，贵州大学，本科在读；主要研究方向和关注领域：密码学。

陶江航（1995-），男，贵州毕节人，贵州大学，本科在读；主要研究方向和关注领域：移动应用开发。

李贵珍（1993-4），女，河北安国人，贵州大学，本科在读；主要研究方向和关注领域：统计学。