具有隱私保護功能的數據加密算法

王茂華，郝云力，褚亞偉

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