具有隱私保護的分布式協作統計計算方案

馬 飛，蔣建國

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

0 引 言

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

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

1 Paillier公鑰加密算法及其加法同態性

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

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

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

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

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

2 幾種典型統計計算公式變換與同態計算

2.1 統計計算公式變換

為了能夠應用Paillier算法的加法同態性到統計計算中，需對統計計算公式做等價變換：

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

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

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

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

2.2 加法同態性與統計計算

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

3 方案拓撲結構及計算步驟

3.1 拓撲結構與組成

如圖1所示，方案采用環形拓撲結構，參與統計計算的用戶數據采用單向傳遞。結構中有3種不同類型的結點：CClient，KClient，SServer。

圖1 方案拓撲結構

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

（2）CClient：參與統計計算的用戶客戶端：①提供加密統計數據：用SServer提供的公鑰加密統計數據以保證隱私性。②參與統計計算：利用Paillier算法的加法同態性來參與隱私統計計算。

（3）KClient：把各CClient經過同態計算得到的中間統計結果最終交于SServer。若其也有數據需參加統計計算，則也完成CClient的兩種操作。

3.2 方案執行步驟

（1）計算步驟

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

2）加密隱私數據在環中進行單向傳遞，參與統計計算的CClient用其前趨傳遞過來的加密數據與自己的加密數據做同態計算，把結果傳遞給其后繼。

3）經過計算與傳遞，加密中間統計結果最終到達KClient，由其交于SServer后由SServer用Paillier加密算法私鑰解密，并將解密結果帶入到相應的統計計算公式中，得到最終的統計結果并輸出。

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

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

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

目標：由各CClient與SServer協作計算統計量X 的“算術平均”，且不破壞xi的隱私性。

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

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

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

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

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

步驟3 KClient將收到如下加密中間統計結果

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

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

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

4.1 方案安全性分析

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

（1）攻擊模型：

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

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

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

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

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

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

（2）安全性分析：

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

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

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

4.2 方案性能測試

測試所實現方案在計算 “方差”、 “回歸系數”和 “相關系數”時的時間代價。

由于方案采用分布式計算統計量，計算的時間代價主要集中在兩方面：①單個客戶端對數據進行Paillier算法加密，及進行加性同態計算時所用時間。②統計服務器對中間統計結果進行解密及計算最終統計結果所用時間。

方案實現環境參數：CClient、KClient、SServer都采用性能一致的Acer筆記本電腦，共設置了7臺電腦，其中具有CClient身份的電腦共5臺，KClient和SServer各一臺。設備通過IEEE 802.11g網絡進行互聯。具體參數見表1。

表1 方案實現環境參數

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

符號定義：

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

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

tH（·）表示單次同態操作所用時間；

Tout：指SServer對收到的中間結果進行解密所用時間與計算最終統計結果的時間之和。

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

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

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

表3 計算 “回歸系數”時間代價

計算 “相關系數”時間代價見表4。

表4 計算 “相關系數”時間代價

tE（·）和tH（·）是在5臺CClient上分別進行測試得到相應的數值，tD（·）與Tout是在SServer上測試得到。單個CClient做加密及同態運算所花費時間與方案規模 （參與統計計算的用戶端數）無關。SServer最后對中間結果解密及計算最終統計結果所用時間也與規模無關。

4.3 方案特點與應用展望

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

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

（3）方案應用展望：醫療系統中監測患者體征的可穿戴設備、智能電網中的智能電表等都需要采集設備環境或用戶的體征數據，而這些數據都具有很強的隱私性，對這類數據進行統計分析時，則可采用本文提出的方案。本文只實現了Windows環境下的方案，下一步可對方案進行Android環境下的實現。

5 結束語

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

［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）.［李超零，陳越.基于分解與加密的云數據庫隱私保護機制研究［J］.信息工程大學學報，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）. ［錢萍，吳蒙.同態加密隱私保護數據挖掘方法綜述［J］.計算機應用研究，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）. ［張斌.高效安全的多方計算基礎協議及應用研究 ［D］.濟南：山東大學，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）. ［孫 茂華.安全多方計算及其應用研究 ［D］.北京：北京郵電大學，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］.計算機學報，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）. ［葉云.保護私有數據合作計算問題及其應用研究 ［D］.合肥：中國科學技術大學，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公鑰密碼體制同態特性及效率分析 ［J］.北京電子科技學院學報，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密碼體制的點積協議研究 ［D］.昆明：云南大學，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）.［李美云，李劍，黃超.基于同態加密的可信云存儲平臺 ［J］.信息網絡安全，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）.［任福樂，朱志祥.基于全同態加密的云計算數據安全方案 ［J］.西安郵電大學學報，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］.北京：北京郵電大學，2011：12－15.］

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