1 差分隐私技术

1.1 中心化差分隐私

1.1.1 中心化差分隐私模型

定义1 ($ε$-DP)  扰动机制$K$, 其中$D$为机制$K$输出的集合。对于任意的一对相邻数据集$A$和$A$′, 如果机制$K$满足:

$ \operatorname{Pr}[K(A) \in D] \leqslant \mathrm{e}^{\varepsilon} \operatorname{Pr}\left[K\left(A^{\prime}\right) \in D\right] $

(1)

则称$K$满足$ε$-DP, 其中参数$ε$为隐私预算。

当参数$ε$越小时, $K$对数据的保护程度就越高, 即扰动后和扰动前的数据概率分布情况接近, 这样攻击者就很难分辨了。相反, 隐私预算越高, 保护程度就越低。中心化差分隐私保护模型如图 1所示。

图 1 中心化差分隐私模型

1.1.2 中心化差分隐私框架

中心化差分隐私有交互式和非交互式两种数据保护框架^[20]。在交互式保护模型下, 数据管理者会根据数据应用需求设计出相应的差分隐私算法$K$, 当用户对数据服务器发出查询时, 返回的结果将经过中心化差分隐私的处理才返回给用户。这一框架下存在的最大问题是隐私预算耗尽, 然而解决这个问题的现有方法是限制查询数目, 这也使得其在应用中具有一定的局限性。交互式保护模型如图 2所示。

图 2 交互式保护模型

在非交互式保护模型下, 数据的管理者会根据数据信息的特点来设计要发布哪些统计信息, 并设计出隐私算法来进行处理发布。此时, 用户只能对发布后的合成数据库进行查询或者挖掘任务来获得近似的结果。如何合理分配隐私预算, 并尽可能地提高发布数据的可用性, 是此框架下的研究重点。非交互式保护模型如图 3所示。

图 3 非交互式保护模型

1.2 本地化差分隐私

1.2.1 本地化差分隐私模型

近年来, 许多研究都投入到本地化差分隐私中。本地化差分隐私与中心化差分隐私的功能一样, 最大的区别在于其在用户端对数据进行随机扰动, 而非在数据库中。本地化保护模型如图 4所示。

图 4 本地化差分隐私保护模型

定义2 ($ε$-LDP)  对于一组用户, 每个用户拥有一条数据, 若随机机制$K$在任意两条数据$x$和$x′$上得到结果$z$满足式(2), 则称机制$K$满足$ε$-LDP。

$ \operatorname{Pr}[K(x)=z] \leqslant \mathrm{e}^{\varepsilon} \operatorname{Pr}\left[K\left(x^{\prime}\right)=z\right] $

(2)

1.2.2 本地化差分隐私框架

本地化差分隐私保护数据的框架^[17]也有交互式和非交互式两种, 如图 5和图 6所示。

图 5 交互式框架

图 6 非交互式框架

其最大特点是针对单个用户而言, 充分考虑了数据间的关联关系。图 5和图 6中, 当${X_1}, {X_2}, {X_3}, \ldots, {X_n}$为输入序列, ${Z_1}, {Z_2}, {Z_3}, \ldots, {Z_n}$为输出序列, 箭头表示依赖关系, 则整个框架表示为:$Q({Z_j}|{X_j})$, $Q$表示查询。

在交互式框架中, 第$j$个输出${Z_j}$依赖于第$j$个输入${X_j}$以及前$j$-1个输出${Z_1}, {Z_2}, {Z_3}, \ldots, {Z_{j - 1}}$, 但与前$j$-1个输入无依赖关系。因此, 本地化差分隐私的形式定义为:对任意的$x$和$x$′, 给定隐私预算$ε$, 若查询$Q$满足式(3), 则认为${Z_j}$是${X_j}$的一个满足$ε$-LDP保护的表示, 即

$ \sup\limits _{\mathrm{s}} \frac{Q\left(Z_{j} \mid X_{j}=x, Z_{1}, \cdots, Z_{j-1}\right)}{Q\left(Z_{j} \mid X_{j}=x^{\prime}, Z_{1}, \cdots, Z_{j-1}\right)} \leqslant \mathrm{e}^{\varepsilon} $

(3)

在非交互式框架中, 第$j$个输出${Z_j}$仅依赖于第$j$个输入${X_j}$。因此, 非交互式框架下的本地化差分隐私可以表示为:对任意的$x$和$x$′, 给定隐私预算$ε$, 若查询$Q$满足式(4), 则认为${Z_j}$是${X_j}$的一个满足$ε$-LDP保护的表示, 即

$ \sup \limits_{\mathrm{s}} \frac{Q\left(Z_{j} \mid x\right)}{Q\left(Z_{j} \mid x^{\prime}\right)} \leqslant \mathrm{e}^{\varepsilon} $

(4)

2 敏感数据挖掘方法介绍

2.1 敏感数据频繁项挖掘

2.2 敏感数据的回归与分类

2.3 敏感数据的深度学习

3 性能分析

3.1 基于差分隐私的频繁项挖掘

本文选择了数据挖掘中几个经典的方案进行性能分析。具体分析结果如表 1所示。

表 1 差分隐私在敏感数据频繁项挖掘中方案比较

下载CSV

方案	优点	缺点
文献[19]	发布误差较小, 数据可用性高	需考虑Bloom filter参数的设置问题
文献[25]	弱化高维度对精度的影响	高昂的通信代价和计算开销
文献[26]	时间复杂度低, 发布误差小, 数据可用性高	个体数据偏离原始数据的程度大
文献[27]	容易实现, 分类准确率高	不易控制隐私预算系数分配
文献[30]	模型简单, 易于实现, 能处理多分类任务	依赖于对数据分布的假设, 而且数据集越小噪声越大
文献[31]	模型更安全, 通信代价低	降维技术可能会对精度产生影响

3.2 基于差分隐私的回归与分类

目前, 中心化差分隐私发展比较成熟, 在敏感数据挖掘中的应用也比较广泛。本文主要分析了本地化差分隐私在回归与分类中的应用。具体分析结果如表 2所示。

表 2 差分隐私在敏感数据的回归与分类中方案比较

下载CSV

方案	优点	缺点
文献[36]	噪声误差小	仅适用于目标函数一阶和二阶导数的绝对值受常数约束的情况
文献[37]	满足差分隐私, 防止敏感信息泄露	回归分类精度低, 噪声误差大
文献[38]	满足差分隐私, 防止敏感信息泄露	权向量的灵敏度计算开销大, 仅适用于约束条件强的目标函数、凸函数和对偶可微函数
文献[39]	分类精度高, 噪声误差小	仅适用于线性表示的目标函数
文献[40]	满足差分隐私, 防止敏感信息泄露	权向量的灵敏度计算开销高, 仅适用于约束条件强的目标函数
文献[41]	高精度, 低噪声	仅适用于特定数据集
文献[42]	在本地差分隐私下用指数机制寻找局部最优解的一种优选方法	计算开销大

3.3 基于差分隐私的敏感数据的深度学习

文献[43]为不共享输入数据集的神经网络开发了一种分布式多方学习机制, 称为[SS15]。该方法基于随机梯度下降优化算法, 其隐私损失根据模型的参数计算。由于存在许多模型参数, 通常会有数千个这样的模型参数, 因此, 该方法可能会导致大量的隐私损失。文献[44]引入了一种基于中心差分隐私的高效差分隐私机制, 称为[ACG+16]。该模型运行在用于机器学习的TensorFlow软件库上, 能够在适度的隐私预算下实现较高的效率和性能。其算法是基于随机梯度下降的差分隐私保护。此外, 他们还引入了一种跟踪隐私损失的机制, 即隐私会计, 允许对隐私损失进行严密的自动化分析。但当该方法用于更大的数据集时, 其差分隐私机制的错误率可能会导致不稳定的隐私泄漏。文献[36]提出了一种基于本地差分隐私的一元编码机制, 称为LATENT。他们将优化的一元编码进行改进, 引入上界定理, 并提出了隐私预算系数的概念, 将隐私保护程度转移到了隐私预算系数上。该模型在本地进行数据的扰动, 并在云端进行模型的训练, 可以既安全又高效地实现数据的处理任务。[SS15]、[ACG+16]、LATENT 3种方法的性能对比如图 7所示。

图 7 3种方法在敏感数据深度学习中的性能比较

由图 7可知, LATENT即使是在扰动较大的情况下仍能保持较高的精度; 而[SS15]和[ACG+16]只有在扰动较小的情况下才能体现出令人满意的精度。此外, [SS15]和[ACG+16]的另一个缺点是需要可信的第三方。因此, 在对安全性要求较高的场景下, 可使用LATENT方法; 在对安全性要求较低的场景, 推荐使用[SS15]方法。

4 基于差分隐私的敏感数据挖掘技术面临的挑战

5 结语

参考文献

[1]
魏为民, 孔志伟, 杨朔, 等. 基于大数据的安全威胁情报研究[J]. 上海电力学院学报, 2018, 34(1): 53-58.
[2]
YANG K, HAN Q, LI H, et al. An efficient and fine-grained big data access control scheme with privacy-preserving policy[J]. IEEE Internet of Things Journal, 2017, 4(2): 563-571. DOI:10.1109/JIOT.2016.2571718
[3]
ATSALAN D, SEHILI Z, CHRISTEN P, et al.Privacy-preserving record linkage for big data: current approaches and research challenges[M]//ZOMAYA A Y, SAKR S.Handbook of Big Data Technologies.Berlin: Springer, 2017: 851-895.
[4]
CHEN K K, LIU L.A random rotation perturbation approach to privacy preserving data classification[EB/OL].(2015-01-01)[2020-03-18].https://corescholar.libraries.wright.edu/knoesis/916/.
[5]
KERSCHBAUM F, HÄRTERICH M.Searchable encryption to reduce encryption degradation in adjustably encrypted databases[C]//IFIP Annual Conference on Data and Applications Security and Privacy.Springer, 2017: 325-336.
[6]
GAI K, QIU M, ZHAO H, et al.Privacy-aware adaptive data encryption strategy of big data in cloud computing[C]//2016 IEEE 3rd International Conference on Cyber Security and Cloud Computing (CSCloud).Beijing, China: IEEE, 2016: 273-278.
[7]
XU H, GUO S, CHEN K. Building confidential and efficient query services in the cloud with rasp data perturbation[J]. IEEE Transactions on Knowledge and Data Engineering, 2014, 26(2): 322-335. DOI:10.1109/TKDE.2012.251
[8]
CHAMIKARA M A P, BERTOK P, LIU D, et al. Efficient data perturbation for privacy preserving and accurate data stream mining[J]. Pervasive and Mobile Computing, 2018(5): 1-19.
[9]
MACHANAVAJJHALA A, KIFER D. Designing statistical privacy for your data[J]. Communications of the ACM, 2015, 58(3): 58-67. DOI:10.1145/2660766
[10]
CHAMIKARA M A P, BERTOK P, LIU D, et al. Efficient privacy preservation of big data for accurate data mining[J]. Information Sciences, 2019(5): 420-443.
[11]
LI N, LI T, VENKATASUBRAMANIAN S V.T-closeness: privacy beyond k-anonymity and l-diversity[C]//2007 IEEE 23rd International Conference on Data Engineering.Istanbul, Turkey: IEEE, 2007: 106-115.
[12]
ZHANG L, JAJODIA S, BRODSKY A.Information disclosure under realistic assumptions: privacy versus optimality[C]//Proceedings of the 14th ACM Conference on Computer and Communications Security.Alexandria, Virginia, USA: ACM.2007: 573-583.
[13]
GANTA S R, KASIVISWANATHAN S P, SMITH A.Composition attacks and auxiliary information in data privacy[C]//Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.ACM, 2008: 265-273.
[14]
WONG R C W, FU A W C, WANG K, et al. Can the utility of anonymized data be used for privacy breaches?[J]. ACM Transactions on Knowledge Discovery from Data, 2011, 5(3): 16.
[15]
DWORK C.The differential privacy frontier[C]//Proceedings of the 6th Theory of Cryptography Conference, 2009: 496-502.https://doi.org/10.1007/978-3-642-00457-5_290
[16]
MOHAMMED N, CHEN R, FUNG B, et al.Differentially private data release for data mining[C]//Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.San Diego, CA, USA: ACM.2011: 493-501.
[17]
KASIVISWANATHAN S P, LEE H K, NISSIM K, et al. What can we learn privately?[J]. SIAM Journal on Computing, 2011, 40(3): 793-826. DOI:10.1137/090756090
[18]
DUCHI J C, JORDAN M I, WAINWRIGHT M J.Local privacy and statistical minimax rates[C]//2013 IEEE 54th Annual Symposium on Foundations of Computer Science (FOCS).Berkeley, CA, USA: IEEE, 2013: 429-438.
[19]
ERLINGSSON Ú, PIHUR V, KOROLOVA A.Rappor: randomized aggregatable privacy-preserving ordinal response[C]//Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security.ACM, 2014: 1054-1067.DOI.10.1145/2660267.2660348.
[20]
ZHANG X, MENG X. Differential privacy in data publication and analysis[J]. Chinese Journal of Computers, 2014(4): 927-949.
[21]
BHASKAR R, LAXMAN S, SMITH A, et.al.Discovering frequent patterns in sensitive data[C]//Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.Washington DC, USA: ACM.2010: 503-512.
[22]
LI N H, QARDAJI W, SU D, et al. Privbasis:frequent itemset mining with differential privacy[J]. Proceedings of the VLDB Endowment, 2012, 5(11): 1340-13510. DOI:10.14778/2350229.2350251
[23]
LEE J, CLIFTON C W.Top-k frequent itemsets via differentially private FP-trees[C]//Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.ACM, 2014: 931-940.
[24]
FANTI G, PIHUR V, ERLINGSSON U.Building a rappor with the unknown: privacy-preserving learning of associations and data dictionaries[EB/OL].(2015-03-04)[2019-12-15].https://arxiv.org/abs/1503.01214v1.
[25]
REN X B, YU C M, YU W R, et al. LoPub:high-dimensional crowdsourced data publication with local differential privacy[J]. IEEE Transactions on Information Forensics and Security, 2018, 13(9): 2151-2166. DOI:10.1109/TIFS.2018.2812146
[26]
NGUYÊN T T, XIAO X K, YANG Y, et al.Collecting and analyzing data from smart device users with local differential privacys[EB/OL].(2016-06-16)[2019-12-15].https://arxiv.org/abs/1606.05053.
[27]
JAGANNATHAN G, PILLAIPAKKAMNATT K, WRIGHT R N.A practical differentially private random decision tree classifier[C]//2009 IEEE International Conference on Data Mining Workshops.Miami, FL, USA, 2009: 114-121.
[28]
PATHAK M A, RAJ B. Large margin gaussian mixture models with differential privacy[J]. IEEE Transactions on Dependable and Secure Computing, 2012, 9(4): 463-469. DOI:10.1109/TDSC.2012.27
[29]
RAJKUMAR A, AGARWAL S.A differentially private stochastic gradient descent algorithm for multiparty classification[C]//Proceedings of the 15th International Conference on Artificial Intelligence and Statistics.PMLR, 2012: 933-941.
[30]
VAIDYA J, SHAFIQ B, BASU A, et al.Differentially private naive bayes classification[C]//2013 IEEE/WIC/ACM International Joint Conferences on Web Intelligence (WI) and Intelligent Agent Technologies (IAT).Atlanta, GA, USA, 2013: 571-576.
[31]
YILMAZ F, AL-RUBAIE M, CHANG J M.Locally differentially private naive bayes classification[EB/OL].(2019-03-03)[2019-12-28].https://arxiv.org/abs/1905.01039v1.
[32]
ZHENG K, MOU W L, WANG L W.Collect at once, use effectively: making non-interactive locally private learning possible[EB/OL].(2017-01-11)[2019-12-18].https://arxiv.org/abs/1706.03316.
[33]
PHAN N, WANG Y, WU X, et al.Differential privacy preservation for deep auto-encoders: an application of human behavior prediction[C]//Proceedings of the 30th AAAI Conference on Artificial Intelligence.Phoenix, Arizona, USA, 2016: 1309-1316.
[34]
ZHANG X, JI S, WANG T.Differentially private releasing via deep generative model[EB/OL].(2018-03-25)[2019-12-15].https://arxiv.org/abs/1801.01594.
[35]
XIE L Y, LIN K X, WANG S, et al.Differentially private generative adversarial network[EB/OL].(2018-02-19)[2019-12-15].https://arxiv.org/abs/1802.06739.
[36]
CHAMIKARA M A P, BERTOK P, KHALIL I, et al.Local differential privacy for deep learning[EB/OL].(2019-08-08)[2019-12-28].https://arxiv.org/abs/1908.02997?context=cs.CR.
[37]
SMITH A.Privacy-preserving statistical estimation with optimal convergence rates[C]//Proceeding of ACM Symposium on Theory of Computing.San Jose, CA, USA: ACM.2011.
[38]
SAMET S. Privacy-preserving logistic regression[J]. Journal of Advances in Information Technology, 2015, 6(3): 88-95.
[39]
ZHANG J, ZHANG Z J, XIAO X K, et al. Functional mechanism:regression analysis under differential privacy[J]. Proceeding of VLDB Endowment, 2012, 5(11): 1364-1375. DOI:10.14778/2350229.2350253
[40]
CHAUDHURI K, MONTELEONI C, SARWATE A D. Differentially private empirical risk minimization[J]. J Mach Learn Res, 2011, 12: 1069-1109.
[41]
LEI J.Differentially private m-estimators[C]//Proceedings of the 24th International Conference on Neural Information Processing Systems, 2011: 361-369.
[42]
ZHANG J, XIAO X, YANG Y, et al.Privgene: differentially private model fitting using genetic algorithms[C]//Proceeding of ACM SIGMOD International Conference on Management of Data.ACM, 2013: 665-676.
[43]
SHOKRI R, SHMATIKOV V.Privacy-preserving deep learning[C]//201553rd Annual Allerton Conference on Communication, Control, and Computing.Monticello, IL, USA, 2015: 1310-1321.
[44]
ABADI M, CHU A, GOODFELLOW I, et al.Deep learning with differential privacy[C]//Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security.ACM, 2016: 308-318.