网络与信息安全学报, 2020, 6(3): 14-18 doi: 10.11959/j.issn.2096-109x.2020032

专栏:隐私保护新技术探索

基于差分隐私保护技术的多方求和查询方法

何贤芒,

东莞理工学院网络空间安全学院,广东 东莞 623808

Multi-party summation query method based on differential privacy

HE Xianmang,

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

通讯作者: 何贤芒,x.m.he@163.com

修回日期: 2020-02-22   网络出版日期: 2020-06-15

基金资助: 国家自然科学基金.  61672303
广东省普通高校特色创新项目.  2018KTSCX221

Revised: 2020-02-22   Online: 2020-06-15

Fund supported: The National Natural Science Foundation of China.  61672303
Characteristic Innovation Projects of Universities in Guangdong Province,China.  2018KTSCX221

作者简介 About authors

何贤芒(1981-),男,浙江三门人,东莞理工学院副教授,主要研究方向为数据安全与隐私保护 E-mail:x.m.he@163.com

摘要

差分隐私保护技术因其不需要攻击者先验知识的假设,而被认为是一种非常可靠的保护机制。然而,差分隐私保护技术很少在多方环境下使用。鉴于此,将差分隐私保护技术用于多方环境下数据求和查询问题,详细讨论了如何通过加入噪声的方法来实现数据的保护,并证明该方法安全性。

关键词: 多方求和 ; 隐私保护 ; 差分隐私 ; 数据查询

Abstract

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.

Keywords: multi-party summation ; privacy preservation ; differential privacy ; data query

PDF (704KB) 元数据 多维度评价 相关文章 导出 EndNote| Ris| Bibtex  收藏本文

本文引用格式

何贤芒. 基于差分隐私保护技术的多方求和查询方法. 网络与信息安全学报[J], 2020, 6(3): 14-18 doi:10.11959/j.issn.2096-109x.2020032

HE Xianmang. Multi-party summation query method based on differential privacy. Chinese Journal of Network and Information Security[J], 2020, 6(3): 14-18 doi:10.11959/j.issn.2096-109x.2020032

1 引言

网络技术的飞速发展,促使信息量正以超乎人们想象的速度增长。不同的组织间或个人间的合作计算变得越来越重要。不同的数据拥有者需要通过合作交流计算信息得到更全面、更有价值的计算结果。然而,数据安全与隐私保护问题制约着合作计算的进行,甚至在某些情形下参与各方不得不舍弃合作来确保数据的私有与安全。在商业应用上,多个商家的竞争关系往往为了决策需要合作进行数据挖掘来了解整个市场的情况。例如,不同的手机运营商需要通过合作计算来了解某个地区某些手机品牌的使用情况。各个商家拥有的数据是商家的私有信息,不希望对方知道,也可能商家拥有的数据不宜对外公开(如使用者的通话记录)。在这种情况下,需要多方在合作进行数据挖掘的同时保证各方的私有数据不被泄露。为解决该问题,越来越多的学者将努力方向聚焦在安全多方计算(SMC,secure multi-party computation)[1,2]的研究中,研究与设计在多方参与不泄露各方私有信息的条件下完成合作计算。安全多方计算使不公开私有信息的合作计算成为可能,其研究促进了各个组织或个人之间的信息流通并且在各个领域拥有广阔的应用前景。目前,安全多方计算研究已经取得了较大的进展,并且日益成为现代密码学的重要研究课题。

然而,由于基础理论研究的复杂性和应用问题的多样性,基于传统的安全多方计算协议设计过于复杂,不易操作。差分隐私保护是一种数据失真的隐私保护技术,采用添加噪声的技术使敏感数据失真但同时保持某些数据或数据属性不变,要求保证处理后的数据仍然可以保持某些统计方面的性质,以便进行数据挖掘等操作。本文拟将其应用在多方环境下数据求和查询问题,在保持查询结果精确性的前提下同时保证其安全性。

2 差分隐私保护技术

差分隐私保护技术建立在坚实的数学基础之上,对隐私保护进行了严格的定义并提供了量化评估方法,使不同参数处理下的数据集所提供的隐私保护水平具有可比较性。因此,差分隐私理论迅速被业界认可。

定义1 差分隐私[3,4]。一个随机算法A满足ε-差分隐私保护,当且仅当对于任何相差仅一个元组的两个集合D1、D2和任何输出S,满足如下条件

Pr(A(D1))Pr(A(D2))e

这里的 ε 是使用者指定的常数,D1和 D2至多相差一个元组,e 是自然对数常数。从数学上看,只要这个参数ε足够小,攻击者很难区分出对同样的输出S,查询函数到底是作用在D1还是在D2上。当参数等于0时,输出的仅是噪声才能满足上述要求,所以参数ε只有大于0才有实际的意义。同样条件下,参数ε越小私密性越好。

一般来说,差分隐私保护的实现技术是基于拉普拉斯分布来完成的,对于任何查询函数q作用于数据集D上,返回值是q(D)+x,其中的q(D)是查询的真实值,x 是满足拉普拉斯分布 f (μ,b)的采样值:x∝f (μ,b),这里b=Δqε,Δq定义参考定义2。容易证明,这个方法实现了差分隐私保护技术的要求。可以注意到,ε越大,b就越小。

定义2 敏感度。Δq是查询函数q的敏感度,其定义如下。

Δq=maxD1,D2|q(D1)q(D2)|

数据集D1和D2之间至多相差一个元素。

3 目前方案

多方安全求和协议是一类重要基础的协议。目前已经有一系列文献[5,6,7,8,9,10,11,12,13,14]对安全求和协议进行了研究。这些方法各有优劣。文献[5]提出从多个参与者中选择一个主站点,让其产生一个随机数加上自己的数据发给下一个参与者,后面的参与者加上自己的真实数据依次传下去,最终传回主站点再减去随机数之后进行广播。此方法通信性能好,但安全性太差,相邻的两个参与者共谋便可得到中间参与者的数据。

为了解决合谋问题,文献[6]将每位参与者自己输入的数据随机划分成n份,然后每位参与者把分成的n份分别发给所有的参与者,每位参与者分别计算自己收集到的数据的和,然后广播给其他参与者,最后每位用户再次分别计算自己收集到的数据,计算出总和。这种算法固然相对于文献[5]安全很多,但其通信需要n2次,通信复杂度较高。文献[7]提出基于博弈论的安全多方求和协议,主要考虑了用户不诚实提供数据的情况,每个用户数据分成k份,每次计算做k-轮迭代,做二次前后结果是一致的,发布求和结果,如果不一致,则说明有站点提供不真实数据,主站点重新发起求和运算,直到连续两次运算得到的和一样。文献[8]为了解决通信度高的问题,采用了公钥加密与随机函数,提出了一种能提高安全性又能降低通信复杂度的协议。张恩等[9]结合博弈论和密码算法,提出了一种基于电路计算的理性安全多方求和协议。Mehnaz等[10]提出了一种基于诚实模型的安全求和协议,并且应用在机器学习中。Ashouri-Talouki等[11]提出了无须安全信道的3个安全求和协议。仲红[12]提出了基于安全多方求和的多候选人电子选举方案。文献[13]讨论了在通用可组合框架下研究安全多方计算的公平性问题。Liu 等[14]提出了一种基于双粒子 Bell 态的量子安全多方求和协议。Jung等[15]提出了一种没有安全通信信道或没有可信密钥分发者的安全求和协议。

4 多方环境下求和协议

目前为止,差分隐私保护技术难以做到准确的数据查询,而本文可以用差分隐私这种方法实现在多方参与情况下数据准确求和查询,本文的安全性是基于差分隐私保护这种机制,具有安全性保证;从查询速度来说,与目前的其他数据交换方法相同,因此通信量是一致的。

本节提出一个在多方环境下的数据库统计查询方法,设参与方的数量n至少是3,显而易见,当n=2时,求和查询是无法做到数据安全的,步骤如下。

步骤 1 参与的各方(P1,P2,,Pn)各有一个值xi,各自选择一个比较小的正数εi和一个实数u。

步骤 2 各方Pi生成了n-1个数 xi,1,xi,2,,xi,n1 ,满足拉普拉斯分布f (u,b),这里的b=1ε

步骤3 任意的参与方Pi(1≤i≤n),通过安全通道或者通过加密方法,发送xi,j到参与方Pj(1≤ j≤n,i≠ j)。

步骤4 任意的参与方Pi,计算Yi=xi(xi,1+xi,2++xi,n1)+(x1,i+x2,i++xn,i),并公布Yi的值;其中,xi,j为所述各方中的参与方 Pi中发送给Pj的数值,x j,i为参与方Pi接收参与方Pj发送的数值。

步骤 5 参与的各方Pi,根据各方的公布值Yi计算总和。

例1演示了上述求和全过程,定理1证明上述方法满足隐私保护技术的要求。

定理 1 上述多方求和计算方法满足max{εi}-差分隐私。

证明 设 D1,D2是任意两个兄弟集合,仅差一个数据元组,o是算法A2的一个输出,T是算法A1可能输出集合。

情形1 A1,A2算法输出是离散类型

Pr(A2(A1(D1)=o)=Pr(tTPr(A1(D1)=t))

Pr(A2(t)=o)

根据定义1

Pr(tTPr(A1(D1)=o))ePr(tTPr(A1(D2)=o))

Pr(A2(t)=o)

由上面的式子可以得出

Pr(A2(A1(D1)=o)ePr(tTPr(A1(D2)=t)))

Pr(A2(s)=o)=ePr(A2(A1(D2))=o)

Pr(A2(t)=o)

情形2 A1,A2算法输出是连续类型

Pr(A2(A1(D2))=o)=

tTPr(A1(D1)=t)Pr(A2(t)=o)dt

类似地有

Pr(A2(A1(D1))=o)etTPr(A1(D2)=t)

Pr(A2(t)=o)dt=ePr(A1(D2)=o)

上述的证明表明任意参与方Pi,在其拥有的值xi基础上增减多个满足拉普拉斯分布的数xi,j,其依然满足max{εi}-差分隐私的要求。

从过程来说,这个协议通信次数需要O(n2)。结合博弈论等方法,通信量可以降低到 O(kN), k≥2是可能合谋的参与方的数量。在通信量降低的同时,其安全性依然满足定理1的要求。

从协议的执行过程来看,参数ε的选择与求和查询结果无关,只跟加入的噪声大小有关。考虑到噪声的加入最后全部抵消,因此,定理2是显而易见的,参数ε的选择不影响查询结果。

定理2 参数ε的选择对求和结果没有影响。

例 假设有4个参与方:P1,P 2,P 3,P 4

步骤 1 设P1,P 2,P 3,P 4这 4 个参与方各一个数,x1=3,x2 =4,x3 =6,x4 =7,同时假设各方选定的∈=0.01,u=0。

步骤2 设参与方P1,P 2,P 3,P 4各生成3个满足拉普拉斯 f(100,0),此处的 b=100,由b=1ε=10.01 获得的参数为x1,2=3.5,x1,3=121.2, x1,4=-129.2,x2,1=-2.5,x2,3=87.5,x2,4=-12.5, x3,1=-21.4,x3,2=176.4,x3,4=44.5,x4,1=-12.3, x4,2=20.4,x4,3=78.6。

步骤3 如图1所示,进行数据交换,具体如下。

图1

图1   数据交换示例 Fig 1 Example of data exchange


P 1给P2的数字是 3.5,P1给P3的数字是121.2,P1给P4的数字是-129.2。

P 2给P1的数字是-2.5,P2给P3的数字是87.5,P2给P4的数字是-12.5。

P3给P1的数字是-21.4,P3给P2的数字是176.4,P3给P4的数字是44.5。

P4给P1的数字是-12.3,P4给P2的数字是20.4,P4给P3的数字是78.6。

步 骤 4 根 据 公 式 Yi=xi(xi,1+xi,2++xi,n1)+(x1,i+x2,i++xn,i)

P 1计算如下。

Y1=3(3.5+121.2129.2)+(2.521.412.3) =28.7

P 2计算如下。

Y2=4(2.5+87.512.5)+(3.5+176.4+20.4)=131.8

P 3计算如下。

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

P 4计算如下。

Y4=7(12.3+20.4+78.6)+(129.212.5+44.5)=176.9

步骤5 计算Y1+Y2+Y3+Y4=20,即总和。

根据定理 1,上述的多方求和计算方法满足0.01-差分隐私保护技术。

5 结束语

虽然差分隐私保护技术得到了学者的广泛关注,但如何在实际中、在多方环境下应用差分隐私保护技术依然是个开放问题。鉴于此,本文提出了一个基于差分隐私保护模型多方环境下求和查询方法,下一步将其推广到MAX与MIN查询,并且在这个方面取得进展。

The authors have declared that no competing interests exist.
作者已声明无竞争性利益关系。

参考文献

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.

[本文引用: 1]

LU Y P , DAVID H C D .

Performance study of ISCSI-based storage subsystems

[J]. IEEE Communications Magazine, 2003,41(8): 76-82.

[本文引用: 1]

DWORK C , .

Differential privacy

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

[本文引用: 1]

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

[本文引用: 1]

CLIFTON C , KANTARCIOGLU M , VAIDYA J ,et al.

Tools for privacy preserving distributed data mining

[J]. Sigkdd Explorations, 2002,4(2): 28-34.

[本文引用: 3]

罗永龙, 徐致云, 黄刘生 .

安全多方的统计分析问题及其应用

[J]. 计算机工程与应用, 2005,41(24): 141-143.

[本文引用: 2]

LUO Y L , XU Z Y , HUANG L S .

Multivariate statistical analysis and its application

[J]. Computer Engineering and Applications 200541(24): 141-143.

[本文引用: 2]

张国荣, 印鉴 .

基于博弈论的安全多方求和方法

[J]. 计算机应用研究, 2009,26(4): 1497-1499.

[本文引用: 2]

ZHANG G R , YIN J .

Multi-party secure sum computation based on game theory

[J]. Journal of Computer Applications, 200926(4): 1497-1499.

[本文引用: 2]

王峥, 郝林, 刘义成 .

基于公钥加密的安全多方求和协议

[J]. 计算机应用研究, 2017(4): 179-182.

[本文引用: 2]

WANG Z , HAO L , LIU Y C .

Secure sum protocol based on public key encryption

[J]. Journal of Computer Applications, 2017 (4): 179-182.

[本文引用: 2]

张恩, 朱君哲, 范海菊 ,.

基于电路计算的理性安全多方求和协议

[J]. 密码学报, 2019,6(1): 126-135.

[本文引用: 2]

ZHANG E , ZHU J Z , FAN H J ,et al.

Rational secure multiparty sum protocol based on circuit computing

[J]. Chinese Journal of Cryptography, 20196(1): 126-135.

[本文引用: 2]

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.

[本文引用: 2]

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.

[本文引用: 2]

仲红, 黄刘生, 罗永龙 .

基于安全多方求和的多候选人电子选举方案

[J]. 计算机研究与发展, 2006,43(8): 1405-1410.

[本文引用: 2]

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.

[本文引用: 2]

田有亮, 彭长根, 马建峰 ,.

通用可组合公平安全多方计算协议

[J]. 通信学报, 2014(2): 54-62.

[本文引用: 2]

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.

[本文引用: 2]

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.

[本文引用: 2]

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.

[本文引用: 1]

/