基于差分隱私保護技術的多方求和查詢方法

何賢芒

基于差分隱私保護技術的多方求和查詢方法

何賢芒

（東莞理工學院網絡空間安全學院，廣東 東莞 623808）

差分隱私保護技術因其不需要攻擊者先驗知識的假設，而被認為是一種非?？煽康谋Ｗo機制。然而，差分隱私保護技術很少在多方環境下使用。鑒于此，將差分隱私保護技術用于多方環境下數據求和查詢問題，詳細討論了如何通過加入噪聲的方法來實現數據的保護，并證明該方法安全性。

多方求和；隱私保護；差分隱私；數據查詢

1 引言

網絡技術的飛速發展，促使信息量正以超乎人們想象的速度增長。不同的組織間或個人間的合作計算變得越來越重要。不同的數據擁有者需要通過合作交流計算信息得到更全面、更有價值的計算結果。然而，數據安全與隱私保護問題制約著合作計算的進行，甚至在某些情形下參與各方不得不舍棄合作來確保數據的私有與安全。在商業應用上，多個商家的競爭關系往往為了決策需要合作進行數據挖掘來了解整個市場的情況。例如，不同的手機運營商需要通過合作計算來了解某個地區某些手機品牌的使用情況。各個商家擁有的數據是商家的私有信息，不希望對方知道，也可能商家擁有的數據不宜對外公開（如使用者的通話記錄）。在這種情況下，需要多方在合作進行數據挖掘的同時保證各方的私有數據不被泄露。為解決該問題，越來越多的學者將努力方向聚焦在安全多方計算（SMC，secure multi-party computation）[1-2]的研究中，研究與設計在多方參與不泄露各方私有信息的條件下完成合作計算。安全多方計算使不公開私有信息的合作計算成為可能，其研究促進了各個組織或個人之間的信息流通并且在各個領域擁有廣闊的應用前景。目前，安全多方計算研究已經取得了較大的進展，并且日益成為現代密碼學的重要研究課題。

然而，由于基礎理論研究的復雜性和應用問題的多樣性，基于傳統的安全多方計算協議設計過于復雜，不易操作。差分隱私保護是一種數據失真的隱私保護技術，采用添加噪聲的技術使敏感數據失真但同時保持某些數據或數據屬性不變，要求保證處理后的數據仍然可以保持某些統計方面的性質，以便進行數據挖掘等操作。本文擬將其應用在多方環境下數據求和查詢問題，在保持查詢結果精確性的前提下同時保證其安全性。

2 差分隱私保護技術

差分隱私保護技術建立在堅實的數學基礎之上，對隱私保護進行了嚴格的定義并提供了量化評估方法，使不同參數處理下的數據集所提供的隱私保護水平具有可比較性。因此，差分隱私理論迅速被業界認可。

定義1 差分隱私[3-4]。一個隨機算法滿足-差分隱私保護，當且僅當對于任何相差僅一個元組的兩個集合1、2和任何輸出，滿足如下條件

這里的是使用者指定的常數，1和2至多相差一個元組，e是自然對數常數。從數學上看，只要這個參數足夠小，攻擊者很難區分出對同樣的輸出，查詢函數到底是作用在1還是在2上。當參數等于0時，輸出的僅是噪聲才能滿足上述要求，所以參數只有大于0才有實際的意義。同樣條件下，參數越小私密性越好。

定義2 敏感度。Δ是查詢函數的敏感度,其定義如下。

數據集1和2之間至多相差一個元素。

3 目前方案

多方安全求和協議是一類重要基礎的協議。目前已經有一系列文獻[5-14]對安全求和協議進行了研究。這些方法各有優劣。文獻[5]提出從多個參與者中選擇一個主站點，讓其產生一個隨機數加上自己的數據發給下一個參與者，后面的參與者加上自己的真實數據依次傳下去，最終傳回主站點再減去隨機數之后進行廣播。此方法通信性能好，但安全性太差，相鄰的兩個參與者共謀便可得到中間參與者的數據。

為了解決合謀問題，文獻[6]將每位參與者自己輸入的數據隨機劃分成份，然后每位參與者把分成的份分別發給所有的參與者，每位參與者分別計算自己收集到的數據的和，然后廣播給其他參與者，最后每位用戶再次分別計算自己收集到的數據，計算出總和。這種算法固然相對于文獻[5]安全很多，但其通信需要2次，通信復雜度較高。文獻[7]提出基于博弈論的安全多方求和協議，主要考慮了用戶不誠實提供數據的情況，每個用戶數據分成份，每次計算做-輪迭代，做二次前后結果是一致的，發布求和結果，如果不一致，則說明有站點提供不真實數據，主站點重新發起求和運算，直到連續兩次運算得到的和一樣。文獻[8]為了解決通信度高的問題，采用了公鑰加密與隨機函數，提出了一種能提高安全性又能降低通信復雜度的協議。張恩等[9]結合博弈論和密碼算法, 提出了一種基于電路計算的理性安全多方求和協議。Mehnaz等[10]提出了一種基于誠實模型的安全求和協議, 并且應用在機器學習中。Ashouri-Talouki等[11]提出了無須安全信道的3個安全求和協議。仲紅[12]提出了基于安全多方求和的多候選人電子選舉方案。文獻[13]討論了在通用可組合框架下研究安全多方計算的公平性問題。Liu等[14]提出了一種基于雙粒子Bell 態的量子安全多方求和協議。Jung等[15]提出了一種沒有安全通信信道或沒有可信密鑰分發者的安全求和協議。

4 多方環境下求和協議

目前為止，差分隱私保護技術難以做到準確的數據查詢，而本文可以用差分隱私這種方法實現在多方參與情況下數據準確求和查詢，本文的安全性是基于差分隱私保護這種機制，具有安全性保證；從查詢速度來說，與目前的其他數據交換方法相同，因此通信量是一致的。

本節提出一個在多方環境下的數據庫統計查詢方法，設參與方的數量至少是3，顯而易見，當=2時，求和查詢是無法做到數據安全的，步驟如下。

例1演示了上述求和全過程，定理1證明上述方法滿足隱私保護技術的要求。

定理1 上述多方求和計算方法滿足max{ε}-差分隱私。

證明 設1,2是任意兩個兄弟集合，僅差一個數據元組，是算法2的一個輸出，是算法1可能輸出集合。

情形11，2算法輸出是離散類型

根據定義1

由上面的式子可以得出

情形21，2算法輸出是連續類型

類似地有

上述的證明表明任意參與方P，在其擁有的值x基礎上增減多個滿足拉普拉斯分布的數x，其依然滿足max{ε}-差分隱私的要求。

從過程來說，這個協議通信次數需要(2)。結合博弈論等方法，通信量可以降低到()，≥2是可能合謀的參與方的數量。在通信量降低的同時，其安全性依然滿足定理1的要求。

從協議的執行過程來看，參數的選擇與求和查詢結果無關，只跟加入的噪聲大小有關?？紤]到噪聲的加入最后全部抵消，因此，定理2是顯而易見的，參數的選擇不影響查詢結果。

定理2 參數的選擇對求和結果沒有影響。

步驟3 如圖1所示，進行數據交換，具體如下。

圖1 數據交換示例

Fig 1 Example of data exchange

1=3?(3.5+121.2?129.2)+(?2.5?21.4?12.3) =?28.7

2=4?(?2.5+87.5?12.5)+(3.5+176.4+20.4)=131.8

3=6?(?21.4+176.4+44.5)+(121.2+ 87.5+78.6)=93.8

4=7?(?12.3+20.4+78.6)+(?129.2?12.5+44.5)=?176.9

步驟5 計算1+2+3+4=20，即總和。

根據定理1，上述的多方求和計算方法滿足0.01-差分隱私保護技術。

5 結束語

雖然差分隱私保護技術得到了學者的廣泛關注，但如何在實際中、在多方環境下應用差分隱私保護技術依然是個開放問題。鑒于此，本文提出了一個基于差分隱私保護模型多方環境下求和查詢方法，下一步將其推廣到MAX與MIN查詢，并且在這個方面取得進展。

[1] BARVE R, SHRIVER E, GIBBONS P B. Modeling and optimizing I/O throughput of multiple disks on a bus[J]. ACM Sigmetrics Performance Evaluation Review, 1999, 27(1): 83-92.

[2] LU Y P, DAVID H C D. Performance study of ISCSI-based storage subsystems[J]. IEEE Communications Magazine, 2003, 41(8): 76-82.

[3] DWORK C. Differential privacy[C]//International Colloquium on Automata, Languages, & Programming. 2006: 1-12

[4] PROSERPIO D, GOLDBERG S, MCSHERRY F. Calibrating data to sensitivity in private data analysis[C]//The Third Conference on Theory of Cryptography. 2006: 265-284

[5] CLIFTON C, KANTARCIOGLU M, VAIDYA J, et al. Tools for privacy preserving distributed data mining [J]. Sigkdd Explorations, 2002, 4(2): 28-34.

[6] 羅永龍, 徐致云, 黃劉生. 安全多方的統計分析問題及其應用[J]. 計算機工程與應用, 2005, 41(24): 141-143.

LUO Y L, XU Z Y, HUANG L S. Multivariate statistical analysis and its application[J]. Computer Engineering and Applications, 2005, 41 (24): 141-143.

[7] 張國榮, 印鑒. 基于博弈論的安全多方求和方法[J]. 計算機應用研究, 2009, 26(4): 1497-1499.

ZHANG G R, YIN J. Multi-party secure sum computation based on game theory[J]. Journal of Computer Applications, 2009, 26 (4): 1497-1499.

[8] 王崢, 郝林, 劉義成. 基于公鑰加密的安全多方求和協議[J]. 計算機應用研究, 2017(4):179-182.

WANG Z, HAO L, LIU Y C. Secure sum protocol based on public key encryption [J]. Journal of Computer Applications, 2017 (4): 179-182.

[9] 張恩, 朱君哲, 范海菊, 等. 基于電路計算的理性安全多方求和協議[J]. 密碼學報, 2019, 6(1): 126-135.

ZHANG E, ZHU J Z, FAN H J, et al. Rational secure multiparty sum protocol based on circuit computing [J]. Chinese Journal of Cryptography, 2019, 6 (1): 126-135.

[10] MEHNAZ S, BELLALA G, BERTINO E. A secure sum protocol and its application to privacy-preserving multiparty analytics[C]//The 22nd ACM on Symposium on Access Control Models and Technologies. 2017: 219-230.

[11] ASHOURI-TALOUKI M, BARAANI-DASTJERDI A. Cryptographic collusion-resistant protocols for secure sum[J]. International Journal of Electronic Security and Digital Forensics, 2017, 9(1): 19-34.

[12] 仲紅, 黃劉生, 羅永龍. 基于安全多方求和的多候選人電子選舉方案[J]. 計算機研究與發展, 2006, 43(8): 1405-1410. ZHONG H, HUANG L S, LUO Y L. A multi-candidate electronic voting scheme based on secure sum protocol[J]. Journal of Computer Research and Development, 2006, 43(8): 1405-1410.

[13] 田有亮, 彭長根, 馬建峰, 等. 通用可組合公平安全多方計算協議[J]. 通信學報, 2014(2):54-62.

TIAN Y L, PENG C G, MA J F, et al. Universally composable secure multiparty computation protocol with fairness[J]. Jounral on Communications, 2014(2): 54-62.

[14] LIU W, WANG Y B, FAN W Q. An novel protocol for the quantum secure multi-party summation based on two-particle bell states[J]. International Journal of Theoretical Physics, 2017, 56(9): 2783-2791.

[15] JUNG T, LI X Y, WAN M. Collusion-tolerable privacy-preserving sum and product calculation without secure channel[J]. IEEE Transactions on Dependable and Secure Computing, 2015, 12(1): 45–57.

Multi-party summation query method based on differential privacy

HE Xianmang

School of Cyberspace Science, Dongguan University of Technology, Dongguan 623808, China

Differential privacy is considered to be a very reliable protection mechanism because it does not require the a prior knowledge for the attacker. However, differential privacy is rarely used in a multi-party environment. In view of this, the differential privacy is applied to the data summation query in multi-party environment. This method was described in detail and proved the security of the method.

multi-party summation, privacy preservation, differential privacy, data query

TP301

A

10.11959/j.issn.2096?109x.2020032

2019?10?08；

2020?02?22

何賢芒，x.m.he@163.com

國家自然科學基金（61672303）；廣東省普通高校特色創新項目（2018KTSCX221）

The National Natural Science Foundation of China (61672303), Characteristic Innovation Projects of Universities in Guangdong Province, China (2018KTSCX221)

何賢芒. 基于差分隱私保護技術的多方求和查詢方法[J]. 網絡與信息安全學報, 2020, 6(3): 14-18.

HE X M. Multi-party summation query method based on differential privacy[J]. Chinese Journal of Network and Information Security, 2020, 6(3): 14-18.

何賢芒（1981? ），男，浙江三門人，東莞理工學院副教授，主要研究方向為數據安全與隱私保護。