馬 飛，蔣建國

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

0 引 言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.2 方案執(zhí)行步驟

（1）計算步驟

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

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

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

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

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

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

目標(biāo)：由各CClient與SServer協(xié)作計算統(tǒng)計量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），并 且 每 個CClient都有一個Epk（1）。

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

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

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

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

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

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

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

4.1 方案安全性分析

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

（1）攻擊模型：

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

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

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

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

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

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

（2）安全性分析：

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

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

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

4.2 方案性能測試

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

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

方案實現(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 方案實現(xiàn)環(huán)境參數(shù)

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

符號定義：

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

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

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

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

計算 “方差”時間代價見表2。

表2 計算 “方差”時間代價

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

表3 計算 “回歸系數(shù)”時間代價

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

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

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

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

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

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

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

5 結(jié)束語

統(tǒng)計分析是數(shù)據(jù)挖掘領(lǐng)域重要的工具之一，但在分布式環(huán)境下對具有隱私保護的統(tǒng)計計算技術(shù)的研究還比較少。針對該問題，利用Paillier加密算法的加法同態(tài)性，提出了一種在互不信任的分布式環(huán)境下具有隱私保護的協(xié)作統(tǒng)計計算方案。該方案充分利用分布式環(huán)境的計算能力，由用戶客戶端與統(tǒng)計服務(wù)器協(xié)作對數(shù)據(jù)進(jìn)行相關(guān)系數(shù)、算術(shù)平均、方差與線性回歸等統(tǒng)計分析，整個分析過程對用戶隱私數(shù)據(jù)都進(jìn)行了有效的保護。最后論證了方案在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ù)庫隱私保護機制研究［J］.信息工程大學(xué)學(xué)報，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)加密隱私保護數(shù)據(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）. ［張斌.高效安全的多方計算基礎(chǔ)協(xié)議及應(yīng)用研究 ［D］.濟南：山東大學(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）. ［孫 茂華.安全多方計算及其應(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）. ［魏志強，康密軍.普適計算隱私保護策略研究 ［J］.計算機學(xué)報，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）. ［葉云.保護私有數(shù)據(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é)報，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密碼體制的點積協(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)加密的云計算數(shù)據(jù)安全方案 ［J］.西安郵電大學(xué)學(xué)報，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）.［鄭強.不同模型下若干安全多方計算問題的研究［D］.北京：北京郵電大學(xué)，2011：12－15.］

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