具有隱私保護(hù)的分布式協(xié)作統(tǒng)計(jì)計(jì)算方案

馬 飛，蔣建國

（1.合肥工業(yè)大學(xué) 計(jì)算機(jī)與信息學(xué)院，安徽 合肥230009；2.北方民族大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，寧夏 銀川750021）

0 引 言

隨著Internet的快速發(fā)展，參與統(tǒng)計(jì)分析的數(shù)據(jù)往往來自于多個(gè)數(shù)據(jù)源，而目前多數(shù)據(jù)源的隱私保護(hù)統(tǒng)計(jì)計(jì)算方案 主要 是基 于 加 密 技 術(shù) 的 方 案［1－4］和SMC （secure multiparty computation）［5－8］方案。由于基于加密的方案涉及過多的加解密過程，較為低效，而SMC由于涉及過多繁瑣的協(xié)議交互過程，不適用于相對計(jì)算簡單的統(tǒng)計(jì)分析問題。如何在互不信任的多數(shù)據(jù)源環(huán)境下對數(shù)據(jù)進(jìn)行統(tǒng)計(jì)計(jì)算且不破壞敏感數(shù)據(jù)的隱私性是一個(gè)具有重要理論意義與實(shí)際應(yīng)用價(jià)值的研究課題。

本文利用Paillier加密 算 法［9－11］的 加 法 同 態(tài) 性 質(zhì)［12，13］設(shè)計(jì)了一種在互不信任的分布式環(huán)境下具有隱私保護(hù)的協(xié)作統(tǒng)計(jì)分析方案。該方案不但使用戶的隱私數(shù)據(jù)在整個(gè)統(tǒng)計(jì)計(jì)算過程中都處于被保護(hù)狀態(tài)，而且充分利用了分布式環(huán)境下的高計(jì)算與存儲能力，由用戶端與服務(wù)器端協(xié)作完成整個(gè)統(tǒng)計(jì)計(jì)算過程。

1 Paillier公鑰加密算法及其加法同態(tài)性

（1）密鑰生成：選擇兩個(gè)素?cái)?shù)p和q，計(jì)算N ＝pq，λ＝lcm（p－1，q－1），然后選擇一個(gè)隨機(jī)數(shù)g ∈Z＊N2，需滿足gcd（L（gλmod N2），N）＝1，此處L（x）＝（x－1）／N。Paillier的公鑰和私鑰分別為＜N，g ＞和λ。

（2）加密操作：令m ∈ZN為明文，r∈ZN為一隨機(jī)數(shù)，用E（·）表示加密操作

（3）解密操作：給定密文c∈ZN2，D（·）表示用私鑰λ進(jìn)行解密，計(jì)算公式如下

為保證Paillier算法語義安全，必須N 與g 足夠大。m1，m2，r1，r2∈ZN，都有下式成立

式 （3）與式 （4）表明：在密文域上做 “乘”運(yùn)算，其運(yùn)算結(jié)果等于明文域上先做 “加”運(yùn)算，然后對結(jié)果進(jìn)行加密之后的輸出，這是Paillier算法的加法同態(tài)性。

2 幾種典型統(tǒng)計(jì)計(jì)算公式變換與同態(tài)計(jì)算

2.1 統(tǒng)計(jì)計(jì)算公式變換

為了能夠應(yīng)用Paillier算法的加法同態(tài)性到統(tǒng)計(jì)計(jì)算中，需對統(tǒng)計(jì)計(jì)算公式做等價(jià)變換：

（1）算術(shù)平均：假設(shè)樣本空間為｛x1，…xn｝，算術(shù)平均可表示為

（2）方差：方差表征變量X 取值的散度，其變換后的計(jì)算公式如下

（3）線 性 回 歸：設(shè) 有 數(shù) 據(jù) 集：｛（x1，y1），…，（xi，yi）…（xn，yn）｝，一元線性回歸的目的是找到線性方程y ＝a＋bx 去擬合這個(gè)數(shù)據(jù)集，最常采用最小二乘法來確定參數(shù)a與b，等價(jià)變換后的計(jì)算公式如下

（4）相關(guān)系數(shù)：變量X 與Y 的相關(guān)系數(shù)是用來衡量兩者之間線性關(guān)系的強(qiáng)度與方向，其變換后的計(jì)算公式如下

2.2 加法同態(tài)性與統(tǒng)計(jì)計(jì)算

符號定義：①Kpk：Paillier加密算法的公鑰，由統(tǒng)計(jì)服務(wù)器提供給參與統(tǒng)計(jì)計(jì)算的各個(gè)客戶端。②Epk（ ）：Paillier加密操作。參與統(tǒng)計(jì)計(jì)算的客戶端用Kpk加密其隱私數(shù)據(jù)。

3 方案拓?fù)浣Y(jié)構(gòu)及計(jì)算步驟

3.1 拓?fù)浣Y(jié)構(gòu)與組成

如圖1所示，方案采用環(huán)形拓?fù)浣Y(jié)構(gòu)，參與統(tǒng)計(jì)計(jì)算的用戶數(shù)據(jù)采用單向傳遞。結(jié)構(gòu)中有3種不同類型的結(jié)點(diǎn)：CClient，KClient，SServer。

圖1 方案拓?fù)浣Y(jié)構(gòu)

（1）SServer：統(tǒng)計(jì)計(jì)算服務(wù)器：①完成最終的統(tǒng)計(jì)計(jì)算并輸出統(tǒng)計(jì)結(jié)果。②給參與統(tǒng)計(jì)計(jì)算的客戶端提供Paillier算法的公鑰。

（2）CClient：參與統(tǒng)計(jì)計(jì)算的用戶客戶端：①提供加密統(tǒng)計(jì)數(shù)據(jù)：用SServer提供的公鑰加密統(tǒng)計(jì)數(shù)據(jù)以保證隱私性。②參與統(tǒng)計(jì)計(jì)算：利用Paillier算法的加法同態(tài)性來參與隱私統(tǒng)計(jì)計(jì)算。

（3）KClient：把各CClient經(jīng)過同態(tài)計(jì)算得到的中間統(tǒng)計(jì)結(jié)果最終交于SServer。若其也有數(shù)據(jù)需參加統(tǒng)計(jì)計(jì)算，則也完成CClient的兩種操作。

3.2 方案執(zhí)行步驟

（1）計(jì)算步驟

1）SServer利用Paillier算法生成一對密鑰，把公鑰廣播給參與統(tǒng)計(jì)計(jì)算的CClient。各CClient用Paillier算法公鑰加密各自的隱私數(shù)據(jù)與整數(shù) “1”，若無隱私數(shù)據(jù)參與統(tǒng)計(jì)計(jì)算，則加密 “0”。

2）加密隱私數(shù)據(jù)在環(huán)中進(jìn)行單向傳遞，參與統(tǒng)計(jì)計(jì)算的CClient用其前趨傳遞過來的加密數(shù)據(jù)與自己的加密數(shù)據(jù)做同態(tài)計(jì)算，把結(jié)果傳遞給其后繼。

3）經(jīng)過計(jì)算與傳遞，加密中間統(tǒng)計(jì)結(jié)果最終到達(dá)KClient，由其交于SServer后由SServer用Paillier加密算法私鑰解密，并將解密結(jié)果帶入到相應(yīng)的統(tǒng)計(jì)計(jì)算公式中，得到最終的統(tǒng)計(jì)結(jié)果并輸出。

說明：每個(gè)有數(shù)據(jù)需要參與統(tǒng)計(jì)計(jì)算的客戶端都加密“1”，并讓其也參與計(jì)算和傳遞，最后參與計(jì)算的客戶端數(shù)n將以加密形式交于統(tǒng)計(jì)計(jì)算服務(wù)器。若客戶端無數(shù)據(jù)參與統(tǒng)計(jì)計(jì)算，則為了滿足協(xié)議的一致性要求，也必須加密“0”，即：EPK（0）。該EPK（0）需要參與以下兩個(gè)運(yùn)算，其結(jié)果并不影響最終的統(tǒng)計(jì)值

（2）分布式隱私保護(hù)計(jì)算 “算術(shù)平均”實(shí)例

輸入：每個(gè)CClient都具有隱私數(shù)據(jù)xi，i ∈N，N 為CClient的個(gè)數(shù)。X ＝｛x1，...，xi，...，xN｝。

目標(biāo)：由各CClient與SServer協(xié)作計(jì)算統(tǒng)計(jì)量X 的“算術(shù)平均”，且不破壞xi的隱私性。

設(shè)CClientX、CClientY、CClientZ為單向邏輯環(huán)中的客戶端，xa、xb、xc分 別 為 它 們 的 隱 私 數(shù) 據(jù)。CClientX 與CC－lientZ分別為CClientY 的前趨與后繼。

步驟1 設(shè)CClientX、CClientY 與CClientZ 的隱私數(shù)據(jù)經(jīng) 加 密 后 分 別 為：Epk（xa）、Epk（xb）、Epk（xc），并 且 每 個(gè)CClient都有一個(gè)Epk（1）。

步驟2 CClientX 把Epk（1）與Epk（xa）傳遞給其后繼CClientY 后，CClientY 進(jìn)行如下計(jì)算

CClientY 把Epk（xa＋xb）與Epk（1＋1）傳遞給其后繼CClientZ，CClientZ做如下計(jì)算

CClientZ把Epk（xa＋xb＋xc）與Epk（1＋1＋1）向其后繼傳遞，其它CClient進(jìn)行類似處理過程。

步驟3 KClient將收到如下加密中間統(tǒng)計(jì)結(jié)果

KClient 把Epk（ux）與Epk（n）交 于SServer，并 被SServer解密得到ux與n，代入式 （5），珚x 即為所求 “算術(shù)平均”。在統(tǒng)計(jì)計(jì)算的整個(gè)過程中，若CClient無統(tǒng)計(jì)數(shù)據(jù)參與統(tǒng)計(jì)計(jì)算，則執(zhí)行Epk（0）操作，并按式 （13）與式（14）參與計(jì)算，然后按協(xié)議要求進(jìn)行數(shù)據(jù)傳遞。

方差、線性回歸、相關(guān)系數(shù)的計(jì)算過程除所用公式不同以外，其它皆與上述計(jì)算步驟一致。

4 方案安全性分析與性能測試

4.1 方案安全性分析

SHM 模式 （semi－h(huán)onest mode）［14］：參 與 統(tǒng) 計(jì) 計(jì) 算 的CClient、KClient和SServer都遵循統(tǒng)計(jì)計(jì)算的步驟，但希望在計(jì)算的過程中能夠獲得除了最終統(tǒng)計(jì)計(jì)算結(jié)果以外的其它額外信息。

（1）攻擊模型：

CASE1：全部CClient可信，SServer不可信；

攻擊目的：所有CClient遵循方案要求的統(tǒng)計(jì)計(jì)算步驟，但非可信SServer想獲得各CClient的隱私數(shù)據(jù)。

CASE2：部分CClient共謀，SServer可信；

攻擊目的：SServer可信，部分共謀CClient希望推出非共謀CClient的隱私數(shù)據(jù)或中間計(jì)算結(jié)果。

CASE3：部分CClient共謀，SServer不可信；

攻擊目的：部分CClient與SServer共謀，希望獲得非共謀CClient的隱私數(shù)據(jù)。

（2）安全性分析：

對于第1種攻擊，方案中，加密數(shù)據(jù)經(jīng)過計(jì)算與單向傳遞后，SServer最終獲得的是加密后的中間結(jié)果，所以即使SServer對其進(jìn)行解密，也無法推出CClient各自的原始隱私數(shù)據(jù)。

對于第2種攻擊，由于所有CClient的隱私信息及中間計(jì)算結(jié)果都被可信的SServer的公鑰所加密，而在SServer私鑰安全的情況下，共謀CClient是無法對其解密，故非共謀CClient的隱私信息在計(jì)算的任何階段都不會被泄露。

對于第3 種攻擊，設(shè)n 為CClient的總數(shù)，m 為共謀CClient的個(gè)數(shù)。①當(dāng)m ＝n－1時(shí)，即只有一個(gè)CClient是非共謀，其它n－1個(gè)CClient都與SServer共謀，當(dāng)非共謀CClient把隱私統(tǒng)計(jì)數(shù)據(jù)用SServer的公鑰加密后交于其后繼結(jié)點(diǎn)，后繼結(jié)點(diǎn)與其它共謀CClient仍然按照協(xié)議要求的步驟執(zhí)行，但都只用加密后的 “0”與非共謀的CClient的加密隱私數(shù)據(jù)做同態(tài)計(jì)算并把結(jié)果按環(huán)拓?fù)浣Y(jié)構(gòu)單向傳遞。最終SServer收到的數(shù)據(jù)其實(shí)就是非共謀CClient的加密隱私數(shù)據(jù)，SServer對其解密即可獲得非共謀CClient的隱私數(shù)據(jù)。②當(dāng)m ＜n－1時(shí)，即非共謀的CClient個(gè)數(shù)≥2時(shí)，按照協(xié)議的計(jì)算步驟，SServer收到的一定是非共謀CClient隱私數(shù)據(jù)做加法之后的中間結(jié)果的加密形式，所以SServer即使對其解密，也無法從隱私數(shù)據(jù) “和”中反推出非共謀CClient各自的隱私數(shù)據(jù)。故對于本方案，只要滿足m ＜n－1條件，則共謀的CClient與SServer不能推出非共謀CClient的隱私數(shù)據(jù)。

4.2 方案性能測試

測試所實(shí)現(xiàn)方案在計(jì)算 “方差”、 “回歸系數(shù)”和 “相關(guān)系數(shù)”時(shí)的時(shí)間代價(jià)。

由于方案采用分布式計(jì)算統(tǒng)計(jì)量，計(jì)算的時(shí)間代價(jià)主要集中在兩方面：①單個(gè)客戶端對數(shù)據(jù)進(jìn)行Paillier算法加密，及進(jìn)行加性同態(tài)計(jì)算時(shí)所用時(shí)間。②統(tǒng)計(jì)服務(wù)器對中間統(tǒng)計(jì)結(jié)果進(jìn)行解密及計(jì)算最終統(tǒng)計(jì)結(jié)果所用時(shí)間。

方案實(shí)現(xiàn)環(huán)境參數(shù)：CClient、KClient、SServer都采用性能一致的Acer筆記本電腦，共設(shè)置了7臺電腦，其中具有CClient身份的電腦共5臺，KClient和SServer各一臺。設(shè)備通過IEEE 802.11g網(wǎng)絡(luò)進(jìn)行互聯(lián)。具體參數(shù)見表1。

表1 方案實(shí)現(xiàn)環(huán)境參數(shù)

為了保證Paillier加密算法有足夠的語義安全［15］，設(shè)置參數(shù)：N ：1024bit g：160bit。公鑰＜N，g ＞：1184bit，密文為2048－bit?；谝陨蠀?shù)，Paillier加密過程實(shí)質(zhì)是做兩次1024－bit的冪運(yùn)算，一次2048－bit的乘法運(yùn)算，而解密過程是做一次2048－bit的冪運(yùn)算。私鑰與公鑰利用生成算法在模型運(yùn)行前按要求位數(shù)已生成。方案的客戶端模塊 （CClient）和服務(wù)器端模塊 （SServer）都處于工作狀態(tài)。共進(jìn)行了30次測試。

符號定義：

tE（·）表示單次Paillier加密操作所用時(shí)間；

tD（·）表示單次Paillier解密操作所用時(shí)間；

tH（·）表示單次同態(tài)操作所用時(shí)間；

Tout：指SServer對收到的中間結(jié)果進(jìn)行解密所用時(shí)間與計(jì)算最終統(tǒng)計(jì)結(jié)果的時(shí)間之和。

計(jì)算 “方差”時(shí)間代價(jià)見表2。

表2 計(jì)算 “方差”時(shí)間代價(jià)

計(jì)算 “回歸系數(shù)”時(shí)間代價(jià)見表3。

表3 計(jì)算 “回歸系數(shù)”時(shí)間代價(jià)

計(jì)算 “相關(guān)系數(shù)”時(shí)間代價(jià)見表4。

表4 計(jì)算 “相關(guān)系數(shù)”時(shí)間代價(jià)

tE（·）和tH（·）是在5臺CClient上分別進(jìn)行測試得到相應(yīng)的數(shù)值，tD（·）與Tout是在SServer上測試得到。單個(gè)CClient做加密及同態(tài)運(yùn)算所花費(fèi)時(shí)間與方案規(guī)模 （參與統(tǒng)計(jì)計(jì)算的用戶端數(shù)）無關(guān)。SServer最后對中間結(jié)果解密及計(jì)算最終統(tǒng)計(jì)結(jié)果所用時(shí)間也與規(guī)模無關(guān)。

4.3 方案特點(diǎn)與應(yīng)用展望

（1）方案特點(diǎn)：①隱私數(shù)據(jù)由客戶端獨(dú)立進(jìn)行存儲，方便用戶對數(shù)據(jù)施加靈活的訪問控制。統(tǒng)計(jì)計(jì)算由客戶端與服務(wù)器共同完成，從而降低了傳統(tǒng)服務(wù)器由于集中進(jìn)行統(tǒng)計(jì)計(jì)算與存儲而帶來的安全隱患及計(jì)算復(fù)雜性過高的問題，適用于大數(shù)據(jù)量計(jì)算。②數(shù)據(jù)的傳遞過程也是統(tǒng)計(jì)計(jì)算的過程，不必事先合并數(shù)據(jù)。除了中間統(tǒng)計(jì)結(jié)果及最終的統(tǒng)計(jì)結(jié)果以外，用戶個(gè)體隱私數(shù)據(jù)在整個(gè)統(tǒng)計(jì)計(jì)算過程中都處于保密狀態(tài)。③加密只在客戶端提供原始統(tǒng)計(jì)數(shù)據(jù)時(shí)出現(xiàn)，而解密操作也僅在統(tǒng)計(jì)服務(wù)器對中間統(tǒng)計(jì)結(jié)果進(jìn)行解密時(shí)發(fā)生，所以方案只涉及很少的加解密過程。

（2）方案不足：對于部分CClient與SServer進(jìn)行共謀的攻擊，必須滿足非共謀CClient的個(gè)數(shù)大于1時(shí)方案才能正確執(zhí)行，這將是以后需要對方案改進(jìn)的地方。

（3）方案應(yīng)用展望：醫(yī)療系統(tǒng)中監(jiān)測患者體征的可穿戴設(shè)備、智能電網(wǎng)中的智能電表等都需要采集設(shè)備環(huán)境或用戶的體征數(shù)據(jù)，而這些數(shù)據(jù)都具有很強(qiáng)的隱私性，對這類數(shù)據(jù)進(jìn)行統(tǒng)計(jì)分析時(shí)，則可采用本文提出的方案。本文只實(shí)現(xiàn)了Windows環(huán)境下的方案，下一步可對方案進(jìn)行Android環(huán)境下的實(shí)現(xiàn)。

5 結(jié)束語

統(tǒng)計(jì)分析是數(shù)據(jù)挖掘領(lǐng)域重要的工具之一，但在分布式環(huán)境下對具有隱私保護(hù)的統(tǒng)計(jì)計(jì)算技術(shù)的研究還比較少。針對該問題，利用Paillier加密算法的加法同態(tài)性，提出了一種在互不信任的分布式環(huán)境下具有隱私保護(hù)的協(xié)作統(tǒng)計(jì)計(jì)算方案。該方案充分利用分布式環(huán)境的計(jì)算能力，由用戶客戶端與統(tǒng)計(jì)服務(wù)器協(xié)作對數(shù)據(jù)進(jìn)行相關(guān)系數(shù)、算術(shù)平均、方差與線性回歸等統(tǒng)計(jì)分析，整個(gè)分析過程對用戶隱私數(shù)據(jù)都進(jìn)行了有效的保護(hù)。最后論證了方案在SHM 模式下的安全性，并對方案進(jìn)行了性能測試。

［1］LI Chaoling，CHEN Yue.Fragmentation and encryption－based pri－vacy－preserving mechanism for cloud database［J］.Journal of Information Engineering University，2012，13 （3）：376－384 （in Chinese）.［李超零，陳越.基于分解與加密的云數(shù)據(jù)庫隱私保護(hù)機(jī)制研究［J］.信息工程大學(xué)學(xué)報(bào)，2012，13 （3）：376－384.］

［2］QIAN Ping，WU Meng.Survey of privacy preserving data mining methods based on homomorphic encryption ［J］.Application Research of Computers，2011，28 （5）：45－50 （in Chinese）. ［錢萍，吳蒙.同態(tài)加密隱私保護(hù)數(shù)據(jù)挖掘方法綜述［J］.計(jì)算機(jī)應(yīng)用研究，2011，28 （5）：45－50.］

［3］ZHANG Bin.Research on efficient secure basic protocols of multiparty computation and their application ［D］.Jinan：Shandong University，2012：77－81 （in Chinese）. ［張斌.高效安全的多方計(jì)算基礎(chǔ)協(xié)議及應(yīng)用研究 ［D］.濟(jì)南：山東大學(xué)，2012：77－81.］

［4］SONG Maohua.Research on secure mulit－party computation and its application ［D］.Beijing：Beijing University of Posts and Telecommunications，2013：37－39 （in Chinese）. ［孫 茂華.安全多方計(jì)算及其應(yīng)用研究 ［D］.北京：北京郵電大學(xué)，2013：37－39.］

［5］WEI Zhiqiang，KANG Mijun.Research on privacy－protection policy for pervasive computing ［J］.Chinese Journal of Computers，2010，33 （1）：128－138 （in Chinese）. ［魏志強(qiáng)，康密軍.普適計(jì)算隱私保護(hù)策略研究 ［J］.計(jì)算機(jī)學(xué)報(bào)，2010，33 （1）：128－138.］

［6］Ziba Eslami，Saideh Kabiri Rad.A new verifiable multi－secret sharing scheme based on bilinear maps［J］.Wireless Personal Communications，2012，63 （2）：459－467.

［7］PANG Lei，SUN Maohua.Full privacy preserving electronic voting scheme［J］.The Journal of China Universities of Posts and Telecommunications，2012，19 （4）：45－48.

［8］YE Yun.Research on protecting and utilizing private data in cooperative computation ［D］.Hefei：University of Science and Technology of China，2012：90－93 （in Chinese）. ［葉云.保護(hù)私有數(shù)據(jù)合作計(jì)算問題及其應(yīng)用研究 ［D］.合肥：中國科學(xué)技術(shù)大學(xué)，2012：90－93.］

［9］BAI Jian，YANG Yatao，LI Zichen.The homomorphism and efficiency and analysis of Paillier cryptosystem ［J］.Journal of Beijing Electronic Science and Technology Institute，2012，25（4）：77－81 （in Chinese）. ［白健，楊亞濤，李子臣.Paillier公鑰密碼體制同態(tài)特性及效率分析 ［J］.北京電子科技學(xué)院學(xué)報(bào)，2012，25 （4）：77－81.］

［10］ZHOU Qinqting.Research on scalar product protocol based on Paillier cryptosystem ［D］.Kunming：Yunnan University，2012：57－60 （in Chinese）.［周青婷.基于Paillier密碼體制的點(diǎn)積協(xié)議研究 ［D］.昆明：云南大學(xué)，2012：57－60.］

［11］LI Meiyun，LI Jian，HUANG Chao.A credible cloud storage platform based on homomorphic encryption ［J］.Netinfo Security，2012，12 （9）：35－40 （in Chinese）.［李美云，李劍，黃超.基于同態(tài)加密的可信云存儲平臺 ［J］.信息網(wǎng)絡(luò)安全，2012，12 （9）：35－40.］

［12］Gentry C.Fully homomorphic encryption using ideal lattices［C］／／Proc of the ACM Int’l Symp on Theory of Computing，2009：13－17.

［13］REN Fule，ZHU Zhixiang.A cloud computing security solution based on fully homomorphic encryption ［J］.Journal of Xi’an University of Posts and Telecommunications，2013，25（5）：56－58 （in Chinese）.［任福樂，朱志祥.基于全同態(tài)加密的云計(jì)算數(shù)據(jù)安全方案 ［J］.西安郵電大學(xué)學(xué)報(bào)，2013，25 （5）：56－58.］

［14］ZHENG Qiang.Study on several secure multi－party computation problem in different models ［D］.Beijing：Beijing University of Posts and Telecommunications，2011：12－15 （in Chinese）.［鄭強(qiáng).不同模型下若干安全多方計(jì)算問題的研究［D］.北京：北京郵電大學(xué)，2011：12－15.］

［15］Dong W，Wang V.Secure friend discovery in mobile social network ［C］／／INFOCOM，2011：46－48.