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

邢歡，張琳

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

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

邢歡，張琳

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

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

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

1　引言

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

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

2　相關(guān)定義

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

事務(wù)集為D，項(xiàng)集集合為I，事務(wù)t∈T由I中元素組成，支持?jǐn)?shù)是項(xiàng)集A在事務(wù)集D中的計(jì)數(shù)|A|，支持度是項(xiàng)集A的支持?jǐn)?shù)在事務(wù)集中的比例最小支持度為minsup，若則A是頻繁項(xiàng)集。關(guān)聯(lián)規(guī)則是形如AB?的表達(dá)式，A是規(guī)則前件，B是規(guī)則后件。置信度是指項(xiàng)集A和項(xiàng)集B的支持度與項(xiàng)集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í)，由于各方都不希望泄露自身的數(shù)據(jù)，所以可以將項(xiàng)集的支持?jǐn)?shù)等數(shù)據(jù)特征進(jìn)行加密。關(guān)聯(lián)規(guī)則挖掘的關(guān)鍵在于頻繁項(xiàng)集的挖掘，也就是全局支持?jǐn)?shù)的計(jì)算。因此關(guān)鍵在于累加各方的項(xiàng)集支持?jǐn)?shù)，而計(jì)算過程不應(yīng)泄露數(shù)據(jù)信息，所以可以利用paillier加密算法的加法同態(tài)特性。

Paillier加密算法的加密過程為

3　算法描述

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

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

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

通過上述方法即可安全挖掘多方頻繁項(xiàng)集，在已有頻繁項(xiàng)集的基礎(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)鍵的一步計(jì)算：min conf是全局最小置信度閾值。

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

3.2計(jì)算優(yōu)化

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

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

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

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

4　算法設(shè)計(jì)

4.1頻繁項(xiàng)集挖掘算法

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

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

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

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

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

6）頻繁1項(xiàng)集的獲取由

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

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

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

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

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

5　仿真實(shí)驗(yàn)

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

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

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

在關(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)行了對(duì)比。在上述介紹的實(shí)驗(yàn)環(huán)境下對(duì)3種方法進(jìn)行對(duì)比，為方便描述，將文獻(xiàn)［5］的算法記為GADM算法，將文獻(xiàn)［3］算法記為RRDM算法。實(shí)驗(yàn)首先將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)確率并不是很完美，而由于本文使用了加密解密的形式，并不會(huì)影響最后規(guī)則的挖掘。3種算法的時(shí)間消耗對(duì)比如圖5所示，其中本文算法分別使用512 bit、1024 bit、2048 bit密鑰進(jìn)行對(duì)比。

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

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

圖5　在使用不同秘鑰時(shí)的時(shí)間對(duì)比

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

6　結(jié)束語

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

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

［1］ 丁麗萍，盧國慶.面向頻繁模式挖掘的差分隱私保護(hù)綜述［J］.通信學(xué)報(bào)，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ì)算機(jī)學(xué)報(bào)，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ì)算［J］.電子

學(xué)報(bào)，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é)基金資助項(xiàng)目（No.61402241）；江蘇省自然科學(xué)基金資助項(xiàng)目（No.BK2012436）；省屬高校自然科學(xué)研究重大基金資助項(xiàng)目（No.12KJA520002，No.14KJA520002）；江蘇省高校自然科學(xué)基金資助項(xiàng)目（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é)碩士生，主要研究方向?yàn)榉植际接?jì)算、數(shù)據(jù)挖掘、隱私保護(hù)等。

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