邢歡，張琳

（南京郵電大學(xué)計算機(jī)學(xué)院，江蘇 南京 210003）

基于paillier的隱私保護(hù)下關(guān)聯(lián)規(guī)則挖掘方法

邢歡，張琳

（南京郵電大學(xué)計算機(jī)學(xué)院，江蘇 南京 210003）

在基于隱私保護(hù)的數(shù)據(jù)挖掘中，挖掘的精度和安全性一直是一對矛盾，針對該矛盾提出了一種在分布式的環(huán)境下基于paillier同態(tài)加密的關(guān)聯(lián)規(guī)則挖掘方法，該方法將計算方和解密方分離保證了數(shù)據(jù)挖掘的安全性，同時基于同態(tài)加密并不會影響挖掘的精度，并通過蒙哥馬利算法降低了paillier算法的開銷，經(jīng)過實驗發(fā)現(xiàn)在增加加解密過程后算法開銷還是在能接受的范疇內(nèi)。

隱私保護(hù)；關(guān)聯(lián)規(guī)則；同態(tài)加密

1　引言

目前在大數(shù)據(jù)的浪潮下促進(jìn)了一大群學(xué)者針對數(shù)據(jù)挖掘進(jìn)行研究，然而在數(shù)據(jù)的挖掘過程中，隱私保護(hù)的問題日益突出。當(dāng)年啤酒尿布的經(jīng)典案例引發(fā)了人們對于關(guān)聯(lián)規(guī)則挖掘的興趣。而關(guān)聯(lián)規(guī)則挖掘也正是數(shù)據(jù)挖掘中十分重要的一個領(lǐng)域，關(guān)聯(lián)規(guī)則挖掘算法如Apriori算法、FP增長算法等經(jīng)過多年的研究和改進(jìn)已比較成熟。然而在如今的信息時代，關(guān)聯(lián)規(guī)則挖掘早已不再是單方的數(shù)據(jù)挖掘，正是由于多方數(shù)據(jù)挖掘，隱私保護(hù)也越顯重要。關(guān)聯(lián)規(guī)則挖掘存在的隱私保護(hù)問題主要有如下兩種情況：數(shù)據(jù)提供方并不是關(guān)聯(lián)規(guī)則挖掘方，所以數(shù)據(jù)提供方希望在挖掘出正確結(jié)果的同時并不會泄露提供數(shù)據(jù)中的隱私內(nèi)容；另一種情況主要是多個數(shù)據(jù)提供方想要共同進(jìn)行數(shù)據(jù)挖掘，然而多方之間也不想泄露隱私數(shù)據(jù)信息。針對以上的隱私保護(hù)問題，已經(jīng)有很多學(xué)者提出了相關(guān)的協(xié)議以及算法。文獻(xiàn)［1，2］提出了基于差分隱私的算法，差分隱私保護(hù)最大的優(yōu)點是與背景知識無關(guān)，然而差分隱私保護(hù)卻不可避免數(shù)據(jù)失真，改進(jìn)也只是將失真程度減小到最低。文獻(xiàn)［3］利用隨機(jī)響應(yīng)技術(shù)，在概率的基礎(chǔ)上對數(shù)據(jù)進(jìn)行挖掘，雖然在數(shù)據(jù)挖掘的準(zhǔn)確性和安全性方面做了很好的平衡，但也無法完美地解決這兩方面之間的問題。文獻(xiàn)［4］基于 FDM（fast distributedmining of association rules）算法提出了針對上述第2種情況下頻繁項集挖掘的協(xié)議以及算法。文獻(xiàn)［5，6］都提出了基于遺傳算法的隱私保護(hù)下的關(guān)聯(lián)規(guī)則挖掘算法，然而算法在挖掘精度方面并不完美。文獻(xiàn)［7］提出了一種基于重構(gòu)數(shù)據(jù)分布和添加數(shù)據(jù)干擾實現(xiàn)隱私保護(hù)下關(guān)聯(lián)規(guī)則的挖掘算法，但同時由于數(shù)據(jù)的干擾也導(dǎo)致了數(shù)據(jù)屬性的相關(guān)性遭到破壞，數(shù)據(jù)挖掘精度不夠。文獻(xiàn)［8］針對多方進(jìn)行頻繁項集挖掘時存在惡意挖掘其他方信息的情況，提出了一種新的算法，但是算法開銷稍高。文獻(xiàn)［9］根據(jù)不同的安全等級設(shè)置相應(yīng)的數(shù)據(jù)干擾來實現(xiàn)數(shù)據(jù)挖掘中的隱私保護(hù)。文獻(xiàn)［10］提出了一種基于FDM的水平分布式協(xié)議，具有較好的通信效率和安全性。文獻(xiàn)［11］針對多方協(xié)作數(shù)據(jù)挖掘隱私泄露問題提出了一種二進(jìn)制整數(shù)規(guī)劃模型。文獻(xiàn)［12］針對兩方協(xié)作關(guān)聯(lián)規(guī)則挖掘提出了基于可交換加密的協(xié)議。文獻(xiàn)［13］提出了一種基于泛化實現(xiàn)隱私保護(hù)的算法，然而使用泛化不可避免地使數(shù)據(jù)挖掘的精度受到影響。

在基于隱私保護(hù)的關(guān)聯(lián)規(guī)則挖掘中往往數(shù)據(jù)挖掘的安全性和挖掘精度是一對矛盾。在使用同態(tài)加密的情況下，關(guān)聯(lián)規(guī)則挖掘的過程既能保證數(shù)據(jù)的安全性又能保證數(shù)據(jù)挖掘的精度。唯一的不足是算法開銷稍高，然而如今最重要的問題是數(shù)據(jù)挖掘的精度和安全性、算法和技術(shù)的改進(jìn)以及硬件設(shè)備的提升，而算法所需的時間消耗相對沒有數(shù)據(jù)挖掘精度和安全性那么重要。因此，本文提出了一種基于paillier同態(tài)加密的關(guān)聯(lián)規(guī)則挖掘方法。

2　相關(guān)定義

2.1關(guān)聯(lián)規(guī)則

事務(wù)集為D，項集集合為I，事務(wù)t∈T由I中元素組成，支持?jǐn)?shù)是項集A在事務(wù)集D中的計數(shù)|A|，支持度是項集A的支持?jǐn)?shù)在事務(wù)集中的比例最小支持度為minsup，若則A是頻繁項集。關(guān)聯(lián)規(guī)則是形如AB?的表達(dá)式，A是規(guī)則前件，B是規(guī)則后件。置信度是指項集A和項集B的支持度與項集A的支持度的比值

2.2Paillier同態(tài)加密算法

Paillier是基于合數(shù)階剩余類的概率公鑰密碼系統(tǒng)，其理論安全性構(gòu)建在比“RSA假設(shè)”更強(qiáng)的“CCRA假設(shè)”上。Paillier加密算法具有加法同態(tài)和混合乘法同態(tài)的特性。在涉及到多方關(guān)聯(lián)規(guī)則挖掘時，由于各方都不希望泄露自身的數(shù)據(jù)，所以可以將項集的支持?jǐn)?shù)等數(shù)據(jù)特征進(jìn)行加密。關(guān)聯(lián)規(guī)則挖掘的關(guān)鍵在于頻繁項集的挖掘，也就是全局支持?jǐn)?shù)的計算。因此關(guān)鍵在于累加各方的項集支持?jǐn)?shù)，而計算過程不應(yīng)泄露數(shù)據(jù)信息，所以可以利用paillier加密算法的加法同態(tài)特性。

Paillier加密算法的加密過程為

3　算法描述

3.1多方參與的關(guān)聯(lián)規(guī)則挖掘方案

問題：存在多個數(shù)據(jù)提供方，在不泄露自身隱私數(shù)據(jù)的條件下共同挖掘關(guān)聯(lián)規(guī)則。

則將候選k項集 k - Cm添加到頻繁k項集k -L中。由式（5）得到

通過上述方法即可安全挖掘多方頻繁項集，在已有頻繁項集的基礎(chǔ)上再通過ap-genrules產(chǎn)生關(guān)聯(lián)規(guī)則，為方便描述，將關(guān)聯(lián)規(guī)則用A B? 表示，而判斷該關(guān)聯(lián)規(guī)則是否是所需要的還需要進(jìn)行最關(guān)鍵的一步計算：min conf是全局最小置信度閾值。

Pa將和的使用文獻(xiàn)［14］的方法進(jìn)行比較，若則有趣的關(guān)聯(lián)規(guī)則。頻繁項集挖掘和關(guān)聯(lián)規(guī)則挖掘過程中的主要流程相同，如圖1所示。

3.2計算優(yōu)化

圖1　多方規(guī)則挖掘時的同態(tài)加解密過程

步驟4重復(fù)步驟3和步驟4直到m=0， returnD。

算法流程如圖2所示，加解密過程中的模冪運算全部轉(zhuǎn)化為模乘運算，實驗顯示使用蒙哥馬利算法能將計算時間降到極低的標(biāo)準(zhǔn)，使paillier同態(tài)加密算法的開銷達(dá)到令人滿意的程度。

圖2　模冪運算轉(zhuǎn)化成模乘運算

4　算法設(shè)計

4.1頻繁項集挖掘算法

1）每個數(shù)據(jù)提供方 Pi由Apriori-gen算法根據(jù)全局k-1-頻繁項集得到本地候選k-頻繁項集的集合并由本地支持?jǐn)?shù)剪枝得到

2）Pi公布自己的獲得對中每個項集計算使用公鑰對（g， z）加密，其中，和q是大素數(shù)，對其加密得到并將加密結(jié)果發(fā)送給 Pb。

3）Pb計算通過公鑰對加密得到再計算并將結(jié)果發(fā)送給 Pa。

4）Pa根據(jù)解密得到其中

5）使用文獻(xiàn)［8］百萬富翁問題中使用的部分標(biāo)量積保密計算方法比較 Pa的sumC和 Pb的如果將添加到

6）頻繁1項集的獲取由

iP根據(jù)局部最小支持度minsupi得到局部候選1項集再循環(huán)第3）步至第5）步得到頻繁1項集的集合1L-。

4.2關(guān)聯(lián)規(guī)則挖掘算法

1）針對每一個頻繁k項集，使用ap-genrules算法產(chǎn)生候選關(guān)聯(lián)規(guī)則每個數(shù)據(jù)提供方使用公鑰對（g， z）對加密，并將加密結(jié)果發(fā)給Pb。

2）Pb并將結(jié)果再發(fā)給aP。

3）Pa通過私鑰λ解密得到Pa將和的使用文獻(xiàn)［8］的方法進(jìn)行比較，若則是有趣的關(guān)聯(lián)規(guī)則。

5　仿真實驗

本文的方法基于同態(tài)加密技術(shù)，在關(guān)聯(lián)規(guī)則挖掘前并沒有更改數(shù)據(jù)集，所以并不會影響關(guān)聯(lián)規(guī)則挖掘的結(jié)果。本文方法的安全性是基于paillier加密算法的，paillier算法的安全性不弱于“RSA假設(shè)”，并且paillier加密算法是語義安全的，即不存在任何多項式時間算法能夠區(qū)分不同值的加密結(jié)果。所以，本文的關(guān)聯(lián)規(guī)則挖掘的安全性和挖掘精度問題都是能夠保障的。主要通過實驗來測試本文算法開銷。

實驗是由100個項組成的項集和10 000條事務(wù)。將10 000條事務(wù)分成5組，相當(dāng)于每個數(shù)據(jù)方有2 000條數(shù)據(jù)。即仿真5個數(shù)據(jù)方在隱私保護(hù)的前提下共同挖掘關(guān)聯(lián)規(guī)則。算法最主要的消耗在于加解密過程，本文對不同秘鑰長度下paillier加密時間與本文改進(jìn)了paillier的加解密計算過程之后的加密時間進(jìn)行對比。不同秘鑰位數(shù)的算法開銷對比如圖3所示。其中密鑰長度為：16、32、64、128、256、512、1024、2048。而當(dāng)密鑰長度大于1 024時，安全性就相當(dāng)高，從圖3可以看出本文方法在密鑰長度大于1 024時，加密時間能節(jié)省100 ms以上，而在關(guān)聯(lián)規(guī)則挖掘過程中，頻繁項集的挖掘都是呈指數(shù)增長的，所以本文方法有較大優(yōu)勢。

圖3　不同秘鑰數(shù)的算法開銷對比

在關(guān)聯(lián)規(guī)則的挖掘精度、安全性以及算法開銷上，本文基于paillier同態(tài)加密的算法與文獻(xiàn)［5］在分布式環(huán)境下基于遺傳算法的關(guān)聯(lián)規(guī)則挖掘算法以及文獻(xiàn)［3］的使用隨機(jī)響應(yīng)技術(shù)的經(jīng)典算法進(jìn)行了對比。在上述介紹的實驗環(huán)境下對3種方法進(jìn)行對比，為方便描述，將文獻(xiàn)［5］的算法記為GADM算法，將文獻(xiàn)［3］算法記為RRDM算法。實驗首先將10 000條事務(wù)在5組不同的最小支持度和最小置信度閾值下使用Apriori算法進(jìn)行關(guān)聯(lián)規(guī)則挖掘，這5組值如表1所示。然后分別使用本文算法、GADM算法以及RRDM算法在這5組最小支持度和最小置信度閾值下進(jìn)行挖掘，其中規(guī)則準(zhǔn)確率比較結(jié)果如圖4所示。顯然GADM和RRDM規(guī)則挖掘的準(zhǔn)確率并不是很完美，而由于本文使用了加密解密的形式，并不會影響最后規(guī)則的挖掘。3種算法的時間消耗對比如圖5所示，其中本文算法分別使用512 bit、1024 bit、2048 bit密鑰進(jìn)行對比。

表1　測試數(shù)據(jù)

圖4　規(guī)則準(zhǔn)確率對比

圖5　在使用不同秘鑰時的時間對比

由此可見，當(dāng)密鑰數(shù)為512時，與GADM算法消耗相比是可接受的。其中RRDM是矩陣計算，矩陣規(guī)模大算法開銷同樣巨大，而且基于隨機(jī)響應(yīng)的方法存在一定的概率把擾亂后的數(shù)據(jù)還原，所以安全性并不高。然而本文算法在挖掘的精度和安全性方面卻比GADM算法和RRDM算法有較大優(yōu)勢。

6　結(jié)束語

目前針對數(shù)據(jù)挖掘的隱私保護(hù)已經(jīng)有了很多研究，但是數(shù)據(jù)挖掘的精度和數(shù)據(jù)挖掘過程中的安全性一直是一對矛盾。本文提出了一種基于paillier同態(tài)加密的能夠?qū)崿F(xiàn)隱私保護(hù)關(guān)聯(lián)規(guī)則挖掘方法，能很好地解決挖掘精度和安全性問題，雖然增加了加解密過程，但是通過蒙哥馬利算法提高了加解密性能，最終實驗顯示算法消耗還是可接受的。并且本文使用的

paillier加密算法的安全性是建立在比“RSA假設(shè)”更強(qiáng)的“CCRA假設(shè)”上，所以相比于其他多方安全計算中涉及到的加密算法更安全。但是本文方法的算法開銷稍大，這是以后需要繼續(xù)深入研究的內(nèi)容。

［1］ 丁麗萍，盧國慶.面向頻繁模式挖掘的差分隱私保護(hù)綜述［J］.通信學(xué)報，2014，35（10）：200-209.DING L P，LU G Q.Survey of differential privacy in frequent pattern mining［J］.Journal on Communication，2014，35（10）：200-209.

［2］張嘯劍，孟小峰.面向數(shù)據(jù)發(fā)布和分析的差分隱私保護(hù)［J］.計算機(jī)學(xué)報，2014，37（4）：927-949.ZHANG X F，MENG X F.Differential privacy in data publication and analysis［J］.Chinese Journal of Computers，2014，37（4）：927-949.

［3］SUN C J，F(xiàn)U Y，ZHOU J L，et al.Personalized privacy-preserving frequentitemsetmining using randomized response［J］.The Scientific World Journal，2014（3）：686151.

［4］ TASSA T.Secure mining of association rules in horizontally distributed databases［J］.IEEE Transactions on Knowledge and Data Engineering，2014，26（4）：970-983.

［5］KESHAVAMURTHY B H，KHAN A M，TOSHNIWAL D.Privacy preserving association rule mining over distributed databases using genetic algorithm［J］.Neural Comput&Applic，2013，22（1）：351-364.

［6］ LIN C W，ZHANG B B，YANG K T，et al.Efficiently hiding sensitive itemsets with transaction deletion based on geneticalgorithms［J］.The Scientific World Journal，2014：398269.

［7］ANEKRITMONGKOL S，KASEMSAN K.SQL model in language encapsulation and compression technique for association rules mining［J］.International Journal of Intellectual Property Management，2013，4（1）：65-75.

［8］SEKHAVAT Y A，F(xiàn)ATHIAN M.Mining frequent itemsets in the presence of malicious participants［J］.The Institution of Engineering and Technology，2010，4（2）：80-92.

［9］ LI Y P，CHEN M H，LI Q W，et al.Enabling multilevel trust in privacy preserving data mining［J］.IEEE Transactions on Knowledge and Data Engineering，2012，24（9）：1598-1612.

［10］TASSA T.Secure mining of association rules in horizontally distributed databases［J］.IEEE Transactions on Knowledge and Data Engineering，2014，26（4）：970-983.

［11］BHANUMATHI S，SAKTHIVEL A.A new model for privacy preserving multiparty collaborative data mining［C］//International Conference on Circuits，Power and Computing Technologies.c2013：845-850.

［12］ZHANG F，RONG C M，ZHAO G，et al.Privacy-preserving two-party distributed association rules mining on horizontally partitioned data［C］//International Conference on Cloud Computing and Big Data.c2013：633-640.

［13］HAJIAN S， DOMINGO-FERRER J， FARRàS O.Generalization-based privacy preservation and discrimination prevention in data publishing and mining［J］.Data Mining& Knowledge Discovery，2014，28：1158-1188.

［14］李順東，王道順.基于同態(tài)加密的高效多方保密計算［J］.電子

學(xué)報，2013，41（4）：798-803.

LI S D，WANG D S.Efficient secure multiparty computation based on homomorphic encryption［J］.Acta Electronica Sinica，2013，41（4）：798-803.

Privacy-preserving mining of association rules based on paillier encryption algorithm

XING Huan，ZHANG Lin

（College of Computer，Nanjing University of Posts and Telecommunications，Nanjing 210003，China）

In privacy preserving association rule mining，the precision and security of mining are always a pair of contradictions.A method of privacy-preserving mining of association rules based on paillier encryption algorithm over distributed databases was proposed.The method separated calculation and decryption so it can solve the problem of accuracy and security from mining of association rules perfectly.The method can reduce the time cost by Montgomery reduction.The experiment shows that the time cost on the basis of adding the process of encryption and decryption is acceptable.

privacy preserving，association rules，homomorphic encryption

TP311

A

10.11959/j.issn.2096-109x.2016.00014

2015-10-19；

2015-12-30。通信作者：張琳，zhangl@niupt.edu.cn

國家自然科學(xué)基金資助項目（No.61402241）；江蘇省自然科學(xué)基金資助項目（No.BK2012436）；省屬高校自然科學(xué)研究重大基金資助項目（No.12KJA520002，No.14KJA520002）；江蘇省高校自然科學(xué)基金資助項目（No.13KJB520017）

Foundation Items:The National Natural Science Foundation of China（No.61402241），The Natural Science Foundation of Jiangsu Province（No.BK2012436），Natural Science Key Fund for Colleges and Universities of Jiangsu Province（No.12KJA520002 No.14KJA520002），TheNaturalScienceFundforCollegesandUniversitiesofJiangsuProvince（No.13KJB520017）

邢歡（1991-），男，江蘇啟東人，南京郵電大學(xué)碩士生，主要研究方向為分布式計算、數(shù)據(jù)挖掘、隱私保護(hù)等。

張琳（1980-），女，江蘇豐縣人，博士后，南京郵電大學(xué)副教授、碩士生導(dǎo)師，主要研究方向為分布式計算、網(wǎng)絡(luò)安全、隱私保護(hù)等。