具有隐私保护功能的数据加密算法

王茂华，郝云力，褚亚伟

1.阜阳师范学院 数学和金融学院，安徽 阜阳 236037

2.阜阳师范学院 信息工程学院，安徽 阜阳 236037

具有隐私保护功能的数据加密算法

王茂华1，郝云力2，褚亚伟2

1.阜阳师范学院 数学和金融学院，安徽 阜阳 236037

2.阜阳师范学院 信息工程学院，安徽 阜阳 236037

1 引言

随着计算机技术的迅速发展，数据库技术日益成熟，各行各业积累了大量的有用数据，尤其当前云计算存储技术的广泛应用，隐私信息安全问题更加令人担忧，如何对数据库中一些隐私信息进行有效保护，引起了各界的广泛关注[1]。调查研究显示，大多数人不愿意将自己的隐私信息提供给网站，而一些人在只有隐私信息得到保护的条件下才愿意提供给网站，因此在充分利用累积的数据，挖掘其中潜在规律的同时，有效保护个人隐私成为当前一个很有意义的研究课题[2]。

针对数据库中隐私数据的保护问题，国内外相关学者、专家以及企业投了大量的时间和金钱，进行了深入、广泛的研究，使非法用户无法获得有用信息，并取得了一些可喜的成果[3-4]。加密技术作为信息安全的核心技术，被广泛应用于数据库隐私数据保护中。最原始加密算法为基于“消息摘要”的加密技术，通过采用一定运算规则提取原数据的“摘要”，使反向运算不能得到原数据内容，是一种不可逆加密算法，具有速度快、加密程度强等优点，其中，最具代表性为MD5算法[5]。但由于在数据库的应用中，隐私数据需要进行查询、更新等操作，需要能可逆，因此“消息摘要”的加密算法应用范围受限[6]。基于“对称密钥”的加密算法是一种数据“可逆”的加密技术，首先通过一个“密钥”加密数据，然后再通过一个“密钥”解密数据，主要有数据加密标准（Data EncryptionStandard，DES）算法、RC4、RC和保持顺序加密（Order Preserving Encryption，OPE）算法[7-8]，这些算法具有加密操作易实现，在未知密钥条件下，难以破解等优点，但是该类算法缺陷也比较明显：操作开销大，对数据库的查询性能产生不利影响，影响数据库在线和实时查询[9]。非对称加密算法（Asymmetric Encryption，AE）是解决该问题的另一种方案，该算法使用不同的密钥，其基于某些数学上的难解问题，密钥的长度比对称加密算法大得多，存在加速度慢、加密效率低等缺陷[10]。同时当前数据库加密算法均没有考虑数据库隐私数据特殊性，因此需要引入新的工具以获得更加理想的保护结果。

为了提高数据安全性，更好保护数据库中的隐私数据，提出一种具有隐私保护功能的数据加密算法。首先将查询的数字与操作符按一定规则转化为特殊的加密关键字，然后服务器将该关键字输入布隆过滤器（Bloom Filter，BF）中进行命中判定，从而间接实现数据的比较，以达到保护数据的目的，最后采用仿真实验测试本文算法的有效性和优越性。仿真结果表明，本文算法提高了数据的安全性，并且易实现、实用性强，可以满足各种条件的数据保护。

2 隐私与隐私度量

2.1 隐私的定义

隐私保护伴随着数据应用而产生，通俗地说，隐私指个人、机构等不愿意让别人知道的一些信息。在实际应用中，隐私常常被认为是数据所有者不愿意被披露的敏感信息，如个人密码、薪资、公司的重要文件以及病人的病历等。对于不同的数据所有者，什么叫隐私也各不相同，从隐私所有者的角度而言，隐私分为两种类型：

（1）个人隐私。与特定个人相关的但不愿被披露的信息，如银行密码、薪资、身份证号等。

（2）共同隐私。指不仅与个人相关，而且还与其他人员相关的不愿被披露的信息，如公司的薪资分布、公司的年终奖等[11]。

2.2 隐私的度量

由于隐私保护优劣主要根据攻击者披露隐私的多少来描述，因此当前隐私度量基本采用披露风险进行衡量。披露风险定义为攻击者根据所发布的数据和其他相关知识可能披露隐私的概率。设s为隐私数据，Sk定义为攻击者根据相关知识K可以揭露隐私数据s，那么披露风险可以采用如下式进行描述：

3 经典数据加密算法

3.1 DES加密算法

DES算法对二元数据进行加密，数据和密文分组均为64 bit，其加密和解密过程具体如下：

加密过程：

其中，i代表迭代次数变量；⊕表示逐位模2求和。

解密过程：

3.2 保序加密算法

保持顺序加密算法（Order Preserving Encryption，OPE）算法又称为保序加密算法，是由Pailie提出的一种数值型数据加密方案，可以直接应用在加密数据上，对于一些查询操作如：等式和范围查询等能够直接应用于加密数据，而且加密后不影响系统查询、更新等功能。OPE算法具有如下优点：

（1）采用OPE算法对数据查询进行加密处理，较好地防止了过滤无关元组过程，而且结果可靠、完整。

（2）在不改变别的加密值的条件下，OPE算法可以修改数据库中的值，能够很好地处理数据更新问题。

（3）OPE算法允许数据库在加密表上建立索引，而且可以与现有数据库系统进行整合，这主要是由于OPE算法运用B树形式索引结构[12]。

4 具有隐私保护功能的数据加密算法

4.1 布隆过滤器

1970年Howard Bloom提出了布隆过滤器算法，其实质是一种多个哈希函数映射的快速查找算法，采用一系列的bit位来保存数据，用于判别某一个元素是否存在于一个集合中。相对于哈希判别算法，布隆过滤器算法的空间复杂度小，因此具有很好的空间利用率，可以节约计算机内存。

布隆过滤器的工作核心思想为：布隆过滤器由k个哈希函数h1，h2，…，hk以及1个位向量组成，每一个函数满足hi:{0，1}*→[1，m]，初始化时，全部位向量的值为0，当有新数据s1插入时，采用k个哈希函数将数据映射到位向量中，那么该位向量对应地址序列的位置为1，称该位相量装入了s1。当需要查询集合中是否存某个数据对象s2时，首先检查表示s2的位相量地址序列位，若全部为1，那么表示s2属于位相量集。布隆过滤器算法的原理具体如图1所示。

图1 布隆过滤器算法的工作原理

布隆过滤器算法工作过程中，存在误判现象，但误判的概率比较小，在错判率为(1/2)r时，布隆过滤器长度（比特）的最优解为m=nr/ln2[13]。

4.2 本文加密算法描述

4.2.1 算法的思想

设数据值域为 N 个离散的点 A ={a1，a2，…，aN}，且满足a1＜a2＜…＜aN，五个查询操作符集分别如下：

本文算法的基本思想为：将数据转化为操作符集中的元素，对于 V1，一个数字标签 a∈(a1，aN]，若满足 ai＜a＜ai+2（或 a=ai+1），则可以表达为 i个关键字 a'={＞a1，＞a2，…，＞ai}，这些关键字存储在一个BF中。假设用户查询w∈(a1，aN]，并将该查询转化成为字符串“＞w”，则范围数据查询变为查询字符串“＞w”是否在BF中。

对于 BF，定义 r个独立的哈希函数 h1，h2，…，hr。定义一个伪随机置换函数为：f:{0，1}k×{0，1}l→{0，1}l，k为密钥长度，l为操作符链接数据的字符串长度。

4.2.2 加密过程

步骤1输入数字标签 L={L1，L2，…，Ln}。

步骤2for each标签 Lx(1≤x≤n)do

步骤3设值域为 N，将 Lx=ai转化为2N+1个字符串：

步骤4初始化一个BF过滤器Bx，所有比特置0。

步骤5for each w∈{v1∪v2∪v3∪v4∪v5}do

步骤6计算t←f(K，w)。

步骤7计算r个位置 y1=h1(d||t)，…，yr=hr(d||t)。

步骤8将 Bx的位置 y1，y2，…，yr置为1。

步骤9end for

步骤10 end for

4.2.3 解密过程

步骤1输入标识 d、可查询密文 S={B1，B2，…，Bn}、令牌t和标签索引i。

步骤2计算r个位置 y1=h1(d||t)，…，yr=hr(d||t)。

步骤3如果 Bi在任一位置为0，则输出0，否则输出1。

5 仿真实验

5.1 仿真环境

为了验证本文加密算法的有效性，在处理器为双核CPU，主频为2.85 GHz，RAM为4 GB，1 TB硬盘，Winowds 7的操作系统计算机上进行仿真实验，采用VC++编程实现加密算法，同时，为了使本文算法的结果更具说服力，采用文献[14-15]的加密算法进行对比实验。

5.2 结果与分析

5.2.1 哈希函数量对算法性能的影响

对本文加密算法来说，哈希函数量r至关重要，哈希函数量r与本文加密算法的运行时间变化关系如图2所示。从图2可以知道，随着哈希函数量r的增加，加密算法的计算开销随之增加，但是两者之间不是一种线性变化关系，为了兼顾各方面的平衡，本文算法取r=8进行仿真实验。

图2 哈希函数量与计算开销之间的变化关系

5.2.2 加密时间比较

文献[14-15]以及本文加密算法的加密时间如图3所示。从图3可以看出，随着数字标签数量的增加，所有加密算法的运行时间相应增加，然而在相同的条件下，本文加密算法的运行时间相对较少，而且运行时间增加的幅度比较平稳，而文献[14-15]加密算法的增加幅度比较大，变化比较剧烈，对比结果表明，本文算法采用较少的计算开销，获得了更好的加密效果，可以满足数据加密的实时性和在线要求，具有较强的实用性。

图3 不同算法的加密时间比较

5.2.3 解密时间比较

文献[14-15]以及本文算法的解密时间如图4所示。从图4可以清楚看出，当数字标签数量比较小的时候，本文加密算法几乎没有什么优势，但是随着数字标签数量增加，本文加密算法优越性就体现出来，在相同条件下，本文加密算法的计算开销增幅相对较小，实验结果再一次证明了本文加密算法的优越性。

图4 不同算法的解密时间比较

6 结束语

为了提高数据加密过程中的隐私泄漏问题，提出一种具有隐私保护功能的数据加密算法，并通过仿真实验测试算法的有效性。实验结果表明，本文算法不仅具有较好的加密性能，同时具有较好的运行效率，可以较好地防止隐私泄漏，具有良好的实用价值。

[1]周水庚，李丰，陶宇飞，等.面向数据库应用的隐私保护研究综述[J].计算机学报，2009，32（5）：847-861.

[2]钱萍，吴蒙.同态加密隐私保护数据挖掘方法综述[J].计算机应用研究，2011，28（5）：1614-1617.

[3]Yu Yu，Leiwo J，Premkumar B.A study on the security of privacy homomorphism[C]//Proc of the 3rd International Conference on Information Technology，2006，10：470-475.

[4]Xiang Guangli，Chen Xinmeng，Zhu Ping.A method of homomorphic encryption[J].Wuhan University Journal of Natural Sciences，2006，11（1）：181-184.

[5]Zhan J，Chang Ziwu，Matwin S.Using homomorphic encryption forprivacy-preserving collaborative decision tree classification[C]//Proc of Computational Intelligence and Data Mining，2007，11：637-645.

[6]Agrawal R，Kieran J，Srikant R，et al.Order preserving encryption for numeric data[C]//Proceedings of the 2004 ACM SIGMOD InternationalConferenceonManagement of Data，2004，8：563-574.

[7]王贵林，卿斯汉.对一种多重密钥共享认证方案的分析和改进[J].软件学报，2006，17（7）：1627-1632.

[8]吴克寿，陈玉明，李仁发，等.针对IDEA加密算法的差分功耗攻击[J].计算机工程与应用，2012，48（29）：64-66.

[9]闫海成，李晖，张文.一种IBE机制下的端到端密钥管理方案[J].计算机工程与应用，2012，48（1）：116-119.

[10]张睿，蒋华，杨亚涛.一种基于SGC-PKE的SIP可认证密钥协商方案[J].计算机工程与应用，2010，46（5）：80-82.

[11]Boldyreva A，Chenette N，Oneill A.Order-preserving encryption revisited：improved security analysis and alternative solutions[C]//Advances in Cryptology，2011，8：578-595.

[12]冯加军，王晓琳，田青.基于计数型布隆过滤器的文本检索模型[J].计算机工程，2014，40（2）：58-61.

[13]彭凝多，罗光春，秦科，等.一种基于对称加密的范围数据查询算法[J].计算机应用研究，2014，31（10）：165-168.

[14]王正飞，汪卫，施伯乐.加密数据的一种高效查询方法[J].计算机工程与应用，2010，46（5）：80-82.

[15]石井，吴哲，谭璐，等.RSA数据加密算法的分析与改进[J].济南大学学报：自然科学版，2013，27（3）：283-286.

WANG Maohua1,HAO Yunli2,CHU Yawei2

1.School of Mathematics and Finance,Fuyang Teachers College,Fuyang,Anhui 236037,China
2.College of Information Engineering,Fuyang Teachers College,Fuyang,Anhui 236037,China

In order to improve the security of data privacy and prevent data leakage,a novel data encryption algorithm is proposed in this paper based on privacy preserving.Digital and operator are encrypted into key special word,and the key word is input to the bloom filter to hit and decided to achieve the data comparison and protect the data,the validity and superiority of algorithm are tested by simulation experiments.The simulation results show that the proposed algorithm can enhance the security of data,and has the advantages of easy implementation,high practicability,so it can meet all kinds of data protection conditions.

data encryption;privacy preserving;order preserving encryption;bloom filter

为了提高数据的安全性，防止隐私数据被泄漏，提出一种具有隐私保护功能的数据加密算法。将数字与操作符转化为特殊的加密关键字，将该关键字输入到布隆过滤器进行命中判定，实现数据间接比较保护数据，采用仿真实验测试算法的有效性和优越性。仿真结果表明，该算法可以提高数据的安全性，并且具有易实现、实用性强等优点，可以满足各种条件的数据保护。

数据加密；隐私保护；保序加密；布隆过滤器

A

TP301

10.3778/j.issn.1002-8331.1404-0061

WANG Maohua,HAO Yunli,CHU Yawei.Data encryption method based on privacy preserving.Computer Engineering and Applications,2014,50（23）：87-90.

国家特色专业（数学与应用数学TS11496）；安徽省高等学校省级教学质量与教学改革工程重点项目（No.20101984）。

王茂华（1980—），男，讲师，研究方向为数据挖掘和人工智能；郝云力（1984—），男，讲师，研究方向为模糊控制和人工智能；褚亚伟（1977—），男，博士，副教授，研究方向为人工智能。

2014-04-04

2014-06-11

1002-8331（2014）23-0087-04

CNKI网络优先出版：2014-09-18,http://www.cnki.net/kcms/doi/10.3778/j.issn.1002-8331.1404-0061.html