基于paillier的隱私保護下關聯規則挖掘方法

邢歡，張琳

（南京郵電大學計算機學院，江蘇 南京 210003）

基于paillier的隱私保護下關聯規則挖掘方法

邢歡，張琳

（南京郵電大學計算機學院，江蘇 南京 210003）

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

隱私保護；關聯規則；同態加密

1　引言

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

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

2　相關定義

2.1關聯規則

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

2.2Paillier同態加密算法

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

Paillier加密算法的加密過程為

3　算法描述

3.1多方參與的關聯規則挖掘方案

問題：存在多個數據提供方，在不泄露自身隱私數據的條件下共同挖掘關聯規則。

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

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

Pa將和的使用文獻［14］的方法進行比較，若則有趣的關聯規則。頻繁項集挖掘和關聯規則挖掘過程中的主要流程相同，如圖1所示。

3.2計算優化

圖1　多方規則挖掘時的同態加解密過程

步驟4重復步驟3和步驟4直到m=0， returnD。

算法流程如圖2所示，加解密過程中的模冪運算全部轉化為模乘運算，實驗顯示使用蒙哥馬利算法能將計算時間降到極低的標準，使paillier同態加密算法的開銷達到令人滿意的程度。

圖2　模冪運算轉化成模乘運算

4　算法設計

4.1頻繁項集挖掘算法

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

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

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

4）Pa根據解密得到其中

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

6）頻繁1項集的獲取由

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

4.2關聯規則挖掘算法

1）針對每一個頻繁k項集，使用ap-genrules算法產生候選關聯規則每個數據提供方使用公鑰對（g， z）對加密，并將加密結果發給Pb。

2）Pb并將結果再發給aP。

3）Pa通過私鑰λ解密得到Pa將和的使用文獻［8］的方法進行比較，若則是有趣的關聯規則。

5　仿真實驗

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

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

圖3　不同秘鑰數的算法開銷對比

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

表1　測試數據

圖4　規則準確率對比

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

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

6　結束語

目前針對數據挖掘的隱私保護已經有了很多研究，但是數據挖掘的精度和數據挖掘過程中的安全性一直是一對矛盾。本文提出了一種基于paillier同態加密的能夠實現隱私保護關聯規則挖掘方法，能很好地解決挖掘精度和安全性問題，雖然增加了加解密過程，但是通過蒙哥馬利算法提高了加解密性能，最終實驗顯示算法消耗還是可接受的。并且本文使用的

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

［1］ 丁麗萍，盧國慶.面向頻繁模式挖掘的差分隱私保護綜述［J］.通信學報，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］張嘯劍，孟小峰.面向數據發布和分析的差分隱私保護［J］.計算機學報，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，FU 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，FATHIAN 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］李順東，王道順.基于同態加密的高效多方保密計算［J］.電子

學報，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

國家自然科學基金資助項目（No.61402241）；江蘇省自然科學基金資助項目（No.BK2012436）；省屬高校自然科學研究重大基金資助項目（No.12KJA520002，No.14KJA520002）；江蘇省高校自然科學基金資助項目（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-），男，江蘇啟東人，南京郵電大學碩士生，主要研究方向為分布式計算、數據挖掘、隱私保護等。

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