抗惡意敵手的保密關聯挖掘方案

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

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

0 引 言

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

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

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

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

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

1 基礎知識

1.1 關聯規則相關概念

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

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

(1)

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

sup(A)≥min_sup

(2)

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

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

關聯規則挖掘過程：

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

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

1.2 Paillier加密算法

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

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

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

解密：Bob解密

(3)

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

(4)

則

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

(5)

1.3 惡意模型的安全性定義

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

雙方都是惡意的情況下，是不可能設計出安全計算協議的，這種情況不予考慮。Alice和David分別有數據x和y，他們借助于理想協議中可信任的第三方(trusted third party，TTP)計算f(x，y)=(f1(x，y)，f2(x，y))。執行協議后，雙方分別得到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 半誠實模型下保密關聯挖掘協議

2.1 解決思路

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

(9)

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

(10)

進而推出

(11)

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

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

(12)

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

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

圖1 保密關聯挖掘框架

2.2 具體協議

協議1：半誠實模型下保密關聯挖掘協議

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

輸出：關聯規則。

協議開始：

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

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

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

協議結束。

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

3 惡意模型下保密關聯挖掘協議

3.1 解決思路

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

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

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

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

圖2 惡意模型下保密關聯挖掘

3.2 具體協議

協議2：惡意模型下保密關聯挖掘協議

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

輸出：關聯規則。

協議開始：

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

協議結束。

3.3 正確性分析

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

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

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

(13)

(14)

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

(15)

(16)

3.4 安全性證明

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

(17)

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

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

(18)

(19)

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

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

(20)

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

(21)

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

(22)

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

(23)

(24)

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

4 性能分析

4.1 效率分析

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

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

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

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

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

表1 整體性能比較

4.2 實驗仿真

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

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

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

圖4 不同密鑰數的時間對比

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

5 結束語

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