基于差分隱私保護(hù)技術(shù)的多方求和查詢方法

何賢芒

基于差分隱私保護(hù)技術(shù)的多方求和查詢方法

何賢芒

（東莞理工學(xué)院網(wǎng)絡(luò)空間安全學(xué)院，廣東 東莞 623808）

差分隱私保護(hù)技術(shù)因其不需要攻擊者先驗(yàn)知識(shí)的假設(shè)，而被認(rèn)為是一種非常可靠的保護(hù)機(jī)制。然而，差分隱私保護(hù)技術(shù)很少在多方環(huán)境下使用。鑒于此，將差分隱私保護(hù)技術(shù)用于多方環(huán)境下數(shù)據(jù)求和查詢問(wèn)題，詳細(xì)討論了如何通過(guò)加入噪聲的方法來(lái)實(shí)現(xiàn)數(shù)據(jù)的保護(hù)，并證明該方法安全性。

多方求和；隱私保護(hù)；差分隱私；數(shù)據(jù)查詢

1 引言

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

然而，由于基礎(chǔ)理論研究的復(fù)雜性和應(yīng)用問(wèn)題的多樣性，基于傳統(tǒng)的安全多方計(jì)算協(xié)議設(shè)計(jì)過(guò)于復(fù)雜，不易操作。差分隱私保護(hù)是一種數(shù)據(jù)失真的隱私保護(hù)技術(shù)，采用添加噪聲的技術(shù)使敏感數(shù)據(jù)失真但同時(shí)保持某些數(shù)據(jù)或數(shù)據(jù)屬性不變，要求保證處理后的數(shù)據(jù)仍然可以保持某些統(tǒng)計(jì)方面的性質(zhì)，以便進(jìn)行數(shù)據(jù)挖掘等操作。本文擬將其應(yīng)用在多方環(huán)境下數(shù)據(jù)求和查詢問(wèn)題，在保持查詢結(jié)果精確性的前提下同時(shí)保證其安全性。

2 差分隱私保護(hù)技術(shù)

差分隱私保護(hù)技術(shù)建立在堅(jiān)實(shí)的數(shù)學(xué)基礎(chǔ)之上，對(duì)隱私保護(hù)進(jìn)行了嚴(yán)格的定義并提供了量化評(píng)估方法，使不同參數(shù)處理下的數(shù)據(jù)集所提供的隱私保護(hù)水平具有可比較性。因此，差分隱私理論迅速被業(yè)界認(rèn)可。

定義1 差分隱私[3-4]。一個(gè)隨機(jī)算法滿足-差分隱私保護(hù)，當(dāng)且僅當(dāng)對(duì)于任何相差僅一個(gè)元組的兩個(gè)集合1、2和任何輸出，滿足如下條件

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

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

數(shù)據(jù)集1和2之間至多相差一個(gè)元素。

3 目前方案

多方安全求和協(xié)議是一類(lèi)重要基礎(chǔ)的協(xié)議。目前已經(jīng)有一系列文獻(xiàn)[5-14]對(duì)安全求和協(xié)議進(jìn)行了研究。這些方法各有優(yōu)劣。文獻(xiàn)[5]提出從多個(gè)參與者中選擇一個(gè)主站點(diǎn)，讓其產(chǎn)生一個(gè)隨機(jī)數(shù)加上自己的數(shù)據(jù)發(fā)給下一個(gè)參與者，后面的參與者加上自己的真實(shí)數(shù)據(jù)依次傳下去，最終傳回主站點(diǎn)再減去隨機(jī)數(shù)之后進(jìn)行廣播。此方法通信性能好，但安全性太差，相鄰的兩個(gè)參與者共謀便可得到中間參與者的數(shù)據(jù)。

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

4 多方環(huán)境下求和協(xié)議

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

本節(jié)提出一個(gè)在多方環(huán)境下的數(shù)據(jù)庫(kù)統(tǒng)計(jì)查詢方法，設(shè)參與方的數(shù)量至少是3，顯而易見(jiàn)，當(dāng)=2時(shí)，求和查詢是無(wú)法做到數(shù)據(jù)安全的，步驟如下。

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

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

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

情形11，2算法輸出是離散類(lèi)型

根據(jù)定義1

由上面的式子可以得出

情形21，2算法輸出是連續(xù)類(lèi)型

類(lèi)似地有

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

從過(guò)程來(lái)說(shuō)，這個(gè)協(xié)議通信次數(shù)需要(2)。結(jié)合博弈論等方法，通信量可以降低到()，≥2是可能合謀的參與方的數(shù)量。在通信量降低的同時(shí)，其安全性依然滿足定理1的要求。

從協(xié)議的執(zhí)行過(guò)程來(lái)看，參數(shù)的選擇與求和查詢結(jié)果無(wú)關(guān)，只跟加入的噪聲大小有關(guān)?？紤]到噪聲的加入最后全部抵消，因此，定理2是顯而易見(jiàn)的，參數(shù)的選擇不影響查詢結(jié)果。

定理2 參數(shù)的選擇對(duì)求和結(jié)果沒(méi)有影響。

步驟3 如圖1所示，進(jìn)行數(shù)據(jù)交換，具體如下。

圖1 數(shù)據(jù)交換示例

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 計(jì)算1+2+3+4=20，即總和。

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

5 結(jié)束語(yǔ)

雖然差分隱私保護(hù)技術(shù)得到了學(xué)者的廣泛關(guān)注，但如何在實(shí)際中、在多方環(huán)境下應(yīng)用差分隱私保護(hù)技術(shù)依然是個(gè)開(kāi)放問(wèn)題。鑒于此，本文提出了一個(gè)基于差分隱私保護(hù)模型多方環(huán)境下求和查詢方法，下一步將其推廣到MAX與MIN查詢，并且在這個(gè)方面取得進(jìn)展。

[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] 羅永龍, 徐致云, 黃劉生. 安全多方的統(tǒng)計(jì)分析問(wèn)題及其應(yīng)用[J]. 計(jì)算機(jī)工程與應(yīng)用, 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] 張國(guó)榮, 印鑒. 基于博弈論的安全多方求和方法[J]. 計(jì)算機(jī)應(yīng)用研究, 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] 王崢, 郝林, 劉義成. 基于公鑰加密的安全多方求和協(xié)議[J]. 計(jì)算機(jī)應(yīng)用研究, 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ì)算的理性安全多方求和協(xié)議[J]. 密碼學(xué)報(bào), 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]. 計(jì)算機(jī)研究與發(fā)展, 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] 田有亮, 彭長(zhǎng)根, 馬建峰, 等. 通用可組合公平安全多方計(jì)算協(xié)議[J]. 通信學(xué)報(bào), 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

國(guó)家自然科學(xué)基金（61672303）；廣東省普通高校特色創(chuàng)新項(xiàng)目（2018KTSCX221）

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

何賢芒. 基于差分隱私保護(hù)技術(shù)的多方求和查詢方法[J]. 網(wǎng)絡(luò)與信息安全學(xué)報(bào), 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? ），男，浙江三門(mén)人，東莞理工學(xué)院副教授，主要研究方向?yàn)閿?shù)據(jù)安全與隱私保護(hù)。