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

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

0 引 言

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

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

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

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

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

1 基礎(chǔ)知識

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

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

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

(1)

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

sup(A)≥min_sup

(2)

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

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

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

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

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

1.2 Paillier加密算法

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

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

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

解密：Bob解密

(3)

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

(4)

則

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

(5)

1.3 惡意模型的安全性定義

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

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

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

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

(6)

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

(2)如果David是誠實(shí)的

(7)

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

(8)

稱Π安全計(jì)算F。

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

2.1 解決思路

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

(9)

則該項(xiàng)可添加到頻繁k項(xiàng)集中。則由上式可得到

(10)

進(jìn)而推出

(11)

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

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

(12)

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

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

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

2.2 具體協(xié)議

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

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

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

協(xié)議開始：

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

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

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

協(xié)議結(jié)束。

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

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

3.1 解決思路

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

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

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

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

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

3.2 具體協(xié)議

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

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

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

協(xié)議開始：

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

協(xié)議結(jié)束。

3.3 正確性分析

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

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

(3)第(7)步中站點(diǎn)S1和站點(diǎn)Sn分別計(jì)算

(13)

(14)

(4)第(8)步通過零知識證明驗(yàn)證雙方是否實(shí)施惡意行為，通過證明后站點(diǎn)S1和站點(diǎn)Sn分別計(jì)算

(15)

(16)

3.4 安全性證明

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

(17)

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

情況一：A1誠實(shí)，A2不誠實(shí)時，則

(18)

(19)

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

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

(20)

(2)實(shí)際情況下A1不公布結(jié)果或不進(jìn)行零知識證明，即

(21)

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

(22)

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

(23)

(24)

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

4 性能分析

4.1 效率分析

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

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

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

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

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

表1 整體性能比較

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

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

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

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

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

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

5 結(jié)束語

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