抗惡意敵手的保密關聯(lián)挖掘方案

劉 新，徐 陽，李寶山，弓彥章，羅 丹

(1.內(nèi)蒙古科技大學 信息工程學院，內(nèi)蒙古 包頭 014010；2.北京郵電大學 網(wǎng)絡空間安全學院，北京 100876；3.包頭市紀委監(jiān)委 信息網(wǎng)絡技術中心，內(nèi)蒙古 包頭 014030；4.天津仁愛學院 計算機科學與技術系，天津 301636)

0 引 言

數(shù)據(jù)挖掘技術為紀檢監(jiān)察部門提供技術支持，但是紀檢監(jiān)察部門僅對本地數(shù)據(jù)進行挖掘時難以分析出更精準的職務犯罪關聯(lián)，而跨市區(qū)、跨部門、多站點分析海量數(shù)據(jù)又難免會造成敏感信息的泄漏。因此，在這種大規(guī)模的分布式環(huán)境中，如何在不泄漏隱私信息的情況下進行關聯(lián)挖掘成為研究焦點[1-3]。近年來保密關聯(lián)挖掘研究包括：差分隱私關聯(lián)挖掘[4]、基于數(shù)據(jù)隨機響應的關聯(lián)挖掘[5]以及匿名化的保密關聯(lián)挖掘[6]等。

安全多方計算(secure multi-party computation，MPC)[7]是近年來實現(xiàn)隱私計算的核心技術，已有許多學者將安全多方計算運用到關聯(lián)挖掘中[8-10]，利用MPC和同態(tài)加密技術在數(shù)據(jù)挖掘中對隱私信息進行保密計算，可得到與傳統(tǒng)數(shù)據(jù)挖掘一樣的結果。由于參與者們大多是半誠實的，所以研究最多的半誠實模型下MPC方案，而在現(xiàn)實生活中可能存在惡意攻擊行為，因此研究在惡意模型下MPC協(xié)議尤為重要[11]。本文主要貢獻如下：

(1)首先計算關聯(lián)規(guī)則中所需的最小支持度及最小置信度，利用Paillier加密體制，設計了半誠實模型下的保密關聯(lián)挖掘協(xié)議。

(2)針對半誠實模型協(xié)議中可能存在的惡意行為，借助零知識證明和分割-選擇方法，設計出可抵抗惡意敵手攻擊的保密關聯(lián)挖掘協(xié)議，并利用理想-實際范例方法證明了協(xié)議的安全性。

(3)通過實驗仿真，與現(xiàn)有方案對比，所設計的協(xié)議仍然保持高效，具有實用價值。

1 基礎知識

1.1 關聯(lián)規(guī)則相關概念

假設一個項集(Items)中包含若干個項，每個項就是一個特征屬性，一些項組成一個事務，在數(shù)據(jù)挖掘過程中，每個事務就是一組特征信息。

定義1 支持度(Support)：支持度表示該項集A在事務T中出現(xiàn)的頻度，即包含項集的事務數(shù)量與總事務數(shù)量之比，即

(1)

定義2 頻繁項集(Frequent itemset)的定義請參考文獻[12]。即

sup(A)≥min_sup

(2)

定義3 關聯(lián)規(guī)則(Association rules)：若A、B均為項集，且A，B?I，并且A∩B=?，用式子A?B表示一個關聯(lián)規(guī)則，它表示某些項(項集A)在一個事務中的出現(xiàn)，可推導出另一些項(項集B)在同一事務中也出現(xiàn)，這里“?” 稱為“關聯(lián)”操作。

定義4 剪枝(Prune)：由于存在先驗性質(zhì)：任何非頻繁的k-1項集都不是頻繁k項集的子集。若不符合先驗性質(zhì)，將進行剪枝。詳細定義請參考文獻[12]。

關聯(lián)規(guī)則挖掘過程：

(1)找出所有頻繁項集，即找出存在于數(shù)據(jù)庫中所有支持度sup(A) 大于等于最小支持度min_sup的項集A。

(2)利用頻繁項集產(chǎn)生強關聯(lián)規(guī)則，這些規(guī)則的支持度sup(A) 與置信度conf(A?B) 必須同時滿足最小支持度min_sup和最小置信度min_conf。

1.2 Paillier加密算法

MPC中數(shù)據(jù)加密技術建立起一種安全可靠的保密機制。本文基于Paillier加密算法的加法同態(tài)性[13]，應用于多站點的全局支持度保密運算。

(1)密鑰生成：Bob選取兩個大素數(shù)p，q，保證gcd(pq，(p-1)(q-1))=1；計算N=pq和λ(N)=lcm(p-1，q-1)；選取隨機數(shù)g(g∈ZN2*)，使得滿足N整除g的階。最后得到公鑰：(N，g)，私鑰：(λ，μ)。

加密：Alice選取隨機數(shù)r(0

解密：Bob解密

(3)

(2)Paillier加密算法具有加法同態(tài)性：在保密m1與m2的前提下，能通過E(m1) 與E(m2) 計算出E(m1+m2)，即

(4)

則

E(m1+m2)=c1c2=gm1+m2(r1r2)NmodN2

(5)

1.3 惡意模型的安全性定義

惡意模型下安全多方計算協(xié)議的安全性詳細定義請參考文獻[14](這里只做簡要說明，方便理解后面協(xié)議的安全性證明)。

雙方都是惡意的情況下，是不可能設計出安全計算協(xié)議的，這種情況不予考慮。Alice和David分別有數(shù)據(jù)x和y，他們借助于理想?yún)f(xié)議中可信任的第三方(trusted third party，TTP)計算f(x，y)=(f1(x，y)，f2(x，y))。執(zhí)行協(xié)議后，雙方分別得到f1(x，y) 和f2(x，y)，但不泄漏x和y。步驟如下：

(1)如果Alice是誠實的，那么有

γ(x，y，z，r)=(f1(x，y′)，B2(y，z，r，f2(x，y′)))

(6)

其中，y′=B2(y，z，r)。

(2)如果David是誠實的

(7)

在兩種情況下x′=B1(x，z，r)。

(8)

稱Π安全計算F。

2 半誠實模型下保密關聯(lián)挖掘協(xié)議

2.1 解決思路

假設有n個站點S1，S2，…，Sn，站點S1，S2，…，Sn上分別存放事務數(shù)據(jù)庫D1，D2，…，Dn。各站點保證傳輸?shù)臄?shù)據(jù)準確無誤，即所有數(shù)據(jù)均水平分布儲存在各站點，且各站點之間相互不進行通信。

(9)

則該項可添加到頻繁k項集中。則由上式可得到

(10)

進而推出

(11)

所以，只要考慮上式是否成立就能得到頻繁k項集。

關聯(lián)規(guī)則挖掘：關聯(lián)規(guī)則挖掘和頻繁項集挖掘過程中的主要流程基本相同。關聯(lián)規(guī)則(記作A?B)，關聯(lián)規(guī)則通過conf(A?B)≥min_conf來進行判斷，min_conf是最小置信度。全局的置信度只要滿足

(12)

即可求得到A?B滿足強關聯(lián)規(guī)則，其中，|A∪B|i和|A|i是站點上一項集A∪B和A的支持數(shù)。但由每個站點直接公布supi(CA)-min_sup·|Di|和|A∪B|i-min_conf·|A|i，二者求和就會存在隱私數(shù)據(jù)被泄漏的風險，這里利用Paillier算法來加密原始數(shù)據(jù)。

本文設計在半誠實模型下的保密關聯(lián)挖掘協(xié)議，此協(xié)議模型由多個站點及其數(shù)據(jù)庫兩部分組成，該協(xié)議的保密關聯(lián)挖掘流程如圖1所示。①站點利用Paillier加密算法把各自數(shù)據(jù)加密，隨后將各個站點的數(shù)據(jù)提供給其它站點；②各站點與上一站點發(fā)來的密文相乘，發(fā)送給下一個站點，最后的站點將累乘后的數(shù)據(jù)發(fā)送給第一個站點；③第一個站點將數(shù)據(jù)解密并進行對比得出挖掘結果，最后將結果公布；④各站點根據(jù)數(shù)據(jù)挖掘結果對數(shù)據(jù)進行分類。

圖1 保密關聯(lián)挖掘框架

2.2 具體協(xié)議

協(xié)議1：半誠實模型下保密關聯(lián)挖掘協(xié)議

輸入：站點S1，S2，…，Sn分別擁有數(shù)據(jù)庫D1，D2，…，D3。

輸出：關聯(lián)規(guī)則。

協(xié)議開始：

(1)各站點Si(0≤i≤n) 根據(jù)全局k-1頻繁項集的集合Lk-1，利用最小支持度min_sup通過剪枝從各自數(shù)據(jù)庫Di(0≤i≤n) 中得到本地候選k項集的集合Ci。

(3)站點S1將加密后的數(shù)據(jù)發(fā)送給站點S2，站點S2計算E(X1)·E(X2)，將得到的數(shù)據(jù)發(fā)送給下一個站點，以此類推。

(5)利用上述得到的全局頻繁k項集Lk，各個站點使用站點S1公開的公鑰 (N，g) 以及各站點生成的隨機數(shù)ri對|A∪B|i-min_conf·|A|i=Yi進行加密得到E(Yi)，站點S1將加密后的數(shù)據(jù)E(Y1) 發(fā)送給站點S2，站點S2計算E(Y1)·E(Y2)，并將得到的數(shù)據(jù)發(fā)送給下一個站點，以此類推。

協(xié)議結束。

上述協(xié)議1是在半誠實模型下設計的，在協(xié)議中的第(2)步、第(5)步的各站點數(shù)據(jù)加密過程，以及第(4)步、第(6)步的站點S1解密公開挖掘結果中可能會存在惡意行為(在3.1節(jié)中闡述)，所以針對這些可能出現(xiàn)的惡意行為進行分析，設計出在惡意模型下的保密關聯(lián)挖掘協(xié)議。

3 惡意模型下保密關聯(lián)挖掘協(xié)議

3.1 解決思路

在設計惡意模型下的保密關聯(lián)挖掘協(xié)議之前，首先分析半誠實模型下協(xié)議1中可能出現(xiàn)的惡意行為，針對這些惡意行為一一解決，最后使得惡意參與者無法實施或者實施惡意行為被發(fā)現(xiàn)。在理想情況下也無法阻止的惡意行為，同樣在惡意模型下也無法阻止，具體包括：①拒絕進行協(xié)議；②輸入虛假的明文；③在得到自己想要的結果后終止協(xié)議，阻止其它參與者執(zhí)行協(xié)議。除此以外，上述協(xié)議1中可能存在以下惡意行為：

(1)各站點加密數(shù)據(jù)時選擇假的隨機數(shù)，這種情況不予考慮，因為這與提供錯誤輸入一樣。

(2)站點S1在解密后告訴各站點錯誤的頻繁項集A和錯誤的關聯(lián)規(guī)則，使得各站點得到了錯誤的結論，這樣對于其它參與者很不公平。惡意模型下的協(xié)議應能夠發(fā)現(xiàn)惡意行為或者使其無法實施。

解決思路：頻繁項集A的挖掘以及關聯(lián)規(guī)則的生成均由各站點共同挖掘出來，惡意模型下保密關聯(lián)挖掘流程如圖2所示。站點S1可作為發(fā)起者，與剩下 (n-1) 個站點選出的公認誠信站點Sn，與S1執(zhí)行協(xié)議。站點S1和站點Sn利用零知識證明和分割-選擇方法，來抵抗惡意敵手攻擊。

圖2 惡意模型下保密關聯(lián)挖掘

3.2 具體協(xié)議

協(xié)議2：惡意模型下保密關聯(lián)挖掘協(xié)議

輸入：站點S1，S2，…，Sn分別持有數(shù)據(jù)庫D1，D2，…，Dn。

輸出：關聯(lián)規(guī)則。

協(xié)議開始：

(1)各站點Si(0≤i≤n) 根據(jù)全局k-1頻繁項集的集合Lk-1，利用最小支持度min_sup通過剪枝從各自數(shù)據(jù)庫Di(0≤i≤n) 中得到本地候選k項集的集合Ci。

協(xié)議結束。

3.3 正確性分析

通過協(xié)議2站點S1和Sn雙方都能在信息沒有泄漏的情況下，公平正確地得到全局強關聯(lián)規(guī)則。分析如下：

(2)第(6)步的目的是為了驗證雙方是否公布正確的密文。

(3)第(7)步中站點S1和站點Sn分別計算

(13)

(14)

(4)第(8)步通過零知識證明驗證雙方是否實施惡意行為，通過證明后站點S1和站點Sn分別計算

(15)

(16)

3.4 安全性證明

證明：協(xié)議2在惡意模型下是安全的。

(17)

協(xié)議2中，不允許站點S1和站點Sn雙方都存在惡意行為，所以分為以下兩種情況，其中，A1，B1與A2，B2分別代表站點S1和站點Sn。

情況一：A1誠實，A2不誠實時，則

(18)

(19)

情況二：A1不誠實，A2誠實時，則分為兩種情況：

(1)實際情況下A1完成零知識證明并公布結果，即

(20)

(2)實際情況下A1不公布結果或不進行零知識證明，即

(21)

(1)在理想情況下，TTP不給B2發(fā)送結果時

(22)

(2)在理想情況下，TTP給B2發(fā)送結果時

(23)

(24)

因此，協(xié)議2在惡意模型下是安全的。

4 性能分析

4.1 效率分析

計算復雜性：將協(xié)議1、協(xié)議2與文獻[15]、文獻[16]進行效率分析對比。文獻[15]中基于動態(tài)關聯(lián)挖掘的匿名化保密協(xié)議共用了t(v+1) 次模指數(shù)運算，文獻[16]中利用ElGamal同態(tài)加密技術設計的關聯(lián)挖掘協(xié)議中共用了4n+10d+8次模指數(shù)運算。

協(xié)議1執(zhí)行過程中，一次頻繁項集A的挖掘過程共進行了n+1次模指數(shù)運算(具體根據(jù)站點個數(shù)判斷n+1的大小)；一次關聯(lián)規(guī)則的挖掘過程同樣進行了n+1次模指數(shù)運算。共進行2n+2次模指數(shù)運算。

協(xié)議2執(zhí)行過程中，一次頻繁項集A的挖掘過程共需要進行n+6m+10次模指數(shù)運算(通過分析，一般m=20即可)。一次關聯(lián)規(guī)則的挖掘過程同樣進行了n+6m+10次模指數(shù)運算。因此，共進行2(n+6m+100) 次模乘運算。

通信復雜性：協(xié)議1中一共進行了n輪通信；協(xié)議2一共進行了n+8輪通信。文獻[15]和文獻[16]分別進行了n(n+1) 和3n輪通信。

文獻[15]、文獻[16]與協(xié)議1、協(xié)議2的整體性能比較見表1。

表1 整體性能比較

4.2 實驗仿真

為驗證上述協(xié)議有效性，在實驗環(huán)境為Windows10(64位)操作系統(tǒng)、Intel(R)Core(TM)i7-5500U CPU @ 2.40 GHz處理器、內(nèi)存為8.00 GB進行實驗。

圖3是協(xié)議1、協(xié)議2、文獻[15]和文獻[16]隨著項集數(shù)的增加對應的執(zhí)行時間(設最小支持度為0.7)。由圖3實驗結果可知，在提前設定的實驗參數(shù)下，隨著n項集的增大，算法運行的時間也逐步增加。n越大，協(xié)議2的運行時間也在指數(shù)增加，但當n≤5時，協(xié)議2相比于其它3個協(xié)議，還保持著比較高的運行效率。

圖4是協(xié)議1、協(xié)議2、文獻[15]和文獻[16]隨著不同密鑰數(shù)的變化執(zhí)行時間的對比圖。將10 000個數(shù)據(jù)分成5個2000條數(shù)據(jù)的數(shù)據(jù)庫，這5個數(shù)據(jù)庫就是5個站點，一起執(zhí)行協(xié)議，執(zhí)行時間有很大一部分取決于加解密所消耗的時間，所以設置不同長度的密鑰，將實驗消耗的時間進行比較，從圖4可以看出本文協(xié)議在密鑰長度大于512時，協(xié)議1、協(xié)議2、文獻[15]和文獻[16]所消耗的時間均開始指數(shù)型增大。但當密鑰數(shù)≤512時，協(xié)議2相較于其它協(xié)議還保持著比較好的運行效率。

圖4 不同密鑰數(shù)的時間對比

綜上所述，協(xié)議2相比于協(xié)議1、文獻[15]和文獻[16]來說，在小數(shù)據(jù)量及低密鑰數(shù)時其執(zhí)行時間沒有很大的差距，但安全性卻提高了。協(xié)議1與協(xié)議2、文獻[15]和文獻[16]在應用場景上來說并不具有可比性，與半誠實模型下協(xié)議相比，協(xié)議2的安全性更高，實用性更強(注：在惡意模型中，所選用的密碼學工具如：分割-選擇等將會增加執(zhí)行時間，因此可以利用外包和預處理的方法來提升效率)。

5 結束語

本文分析了半誠實模型下保密挖掘可能存在的惡意行為，結合分割-選擇、零知識證明等密碼學工具，設計出了惡意模型下的保密關聯(lián)挖掘協(xié)議，并對協(xié)議進行了安全性證明、效率分析以及實驗仿真。通過分析表明，本文提出的惡意模型下保密關聯(lián)挖掘協(xié)議協(xié)議仍然保持高效，且對比現(xiàn)有半誠實模型下的協(xié)議更加安全穩(wěn)定。未來將會研究出更多的抗惡意敵手的安全多方計算協(xié)議，使其在實際應用中更加安全有效。