Two methods for privacy preserving data mining with malicious participants

Privacy preserving data mining addresses the need of multiple parties with private inputs to run a data mining algorithm and learn the results over the combined data without revealing any unnecessary information. Most of the existing cryptographic solutions to privacy-preserving data mining assume semi-honest participants. In theory, these solutions can be extended to the malicious model using standard techniques like commitment schemes and zero-knowledge proofs. However, these techniques are often expensive, especially when the data sizes are large. In this paper, we investigate alternative ways to convert solutions in the semi-honest model to the malicious model. We take two classical solutions as examples, one of which can be extended to the malicious model with only slight modifications while another requires a careful redesign of the protocol. In both cases, our solutions for the malicious model are much more efficient than the zero-knowledge proofs based solutions.     

基于博弈论的隐私保护分布式数据挖掘

隐私保护的分布式数据挖掘问题是数据挖掘领域的一个研究热点,而基于经济视角,利用博弈论的方法对隐私保护分布式数据挖掘进行研究只是处于初始阶段。基于收益最大化,研究了完全信息静态博弈下分布式数据挖掘中参与者(两方或多方)的策略决策问题,得出了如下结论:数据挖掘在满足一定的条件下,参与者(两方或多方)的准诚信攻击策略是一个帕累托最优的纳什均衡策略;在准诚信攻击的假设下,参与者(多方)的非共谋策略并不是一个纳什均衡策略。同时给出了该博弈的混合战略纳什均衡,它对隐私保护分布式数据挖掘中参与者的决策具有一定的理论和指导意义。     

基于理性密码学的分布式隐私保护数据挖掘框架

在数据挖掘的应用中,隐私保护非常重要。在数据中加上噪声可以在一定程度上保护用户的隐私,但会降低数据的准确性,进而影响数据挖掘结果的有效性。提出一种高效的基于理性密码学的分布式隐私保护数据挖掘框架,在此框架中每个参与方都被认为是理性的,而不像在经典密码学中简单地把每个参与方认为是恶意的或诚实的。基于此种假设和一个半可信的第三方,许多数据挖掘函数,如求和、求平均值、求积、比较、和求频繁项等,都可以在本框架下高效地实现。     

Privacy-preserving algorithms for distributed mining of frequent itemsets

Standard algorithms for association rule mining are based on identification of frequent itemsets. In this paper, we study how to maintain privacy in distributed mining of frequent itemsets. That is, we study how two (or more) parties can find frequent itemsets in a distributed database without revealing each party’s portion of the data to the other. The existing solution for vertically partitioned data leaks a significant amount of information, while the existing solution for horizontally partitioned data only works for three parties or more. In this paper, we design algorithms for both vertically and horizontally partitioned data, with cryptographically strong privacy. We give two algorithms for vertically partitioned data; one of them reveals only the support count and the other reveals nothing. Both of them have computational overheads linear in the number of transactions. Our algorithm for horizontally partitioned data works for two parties and above and is more efficient than the existing solution.     

隐私保护数据挖掘算法综述

如何保护私有信息或敏感知识在挖掘过程中不被泄露,同时能得到较为准确的挖掘结果,目前已经成为数据挖掘研究中的一个很有意义的研究课题。本文通过对当前隐私保护数据挖掘中具有代表性的算法按照数据分布对其中的数据更改方法、数据挖掘算法、数据或规则隐藏等进行了详细阐述,并对各自的优缺点进行了分析和比较,总结出了各种算法的特性。此外,通过对比提出了隐私保护数据挖掘算法的评价标准,即保密性、规则效能、算法复杂性、扩展性,以便在今后的研究中提出新的有效算法。     

Privacy-preserving collaborative data mining

Data collection is a necessary step in data mining process. Due to privacy reasons, collecting data from different parties becomes difficult. Privacy concerns may prevent the parties from directly sharing the data and some types of information about the data. How multiple parties collaboratively conduct data mining without breaching data privacy presents a challenge. The objective of this paper is to provide solutions for privacy-preserving collaborative data mining problems. In particular, we illustrate how to conduct privacy-preserving naive Bayesian classification which is one of the data mining tasks. To measure the privacy level for privacy- preserving schemes, we propose a definition of privacy and show that our solutions preserve data privacy.     

Privacy-Preserving Computation of Bayesian Networks on Vertically Partitioned Data

Traditionally, many data mining techniques have been designed in the centralized model in which all data is collected and available in one central site. However, as more and more activities are carried out using computers and computer networks, the amount of potentially sensitive data stored by business, governments, and other parties increases. Different parties often wish to benefit from cooperative use of their data, but privacy regulations and other privacy concerns may prevent the parties from sharing their data. Privacy-preserving data mining provides a solution by creating distributed data mining algorithms in which the underlying data need not be revealed. In this paper, we present privacy-preserving protocols for a particular data mining task: learning a Bayesian network from a database vertically partitioned among two parties. In this setting, two parties owning confidential databases wish to learn the Bayesian network on the combination of their databases without revealing anything else about their data to each other. We present an efficient and privacy-preserving protocol to construct a Bayesian network on the parties' joint data.     

FREPD: A Robust Federated Learning Framework on Variational Autoencoder

Federated learning is an ideal solution to the limitation of not preserving the users’ privacy information in edge computing. In federated learning, the cloud aggregates local model updates from the devices to generate a global model. To protect devices’ privacy, the cloud is designed to have no visibility into how these updates are generated, making detecting and defending malicious model updates a challenging task. Unlike existing works that struggle to tolerate adversarial attacks, the paper manages to exclude malicious updates from the global model’s aggregation. This paper focuses on Byzantine attack and backdoor attack in the federated learning setting. We propose a federated learning framework, which we call Federated Reconstruction Error Probability Distribution (FREPD). FREPD uses a VAE model to compute updates’ reconstruction errors. Updates with higher reconstruction errors than the average reconstruction error are deemed as malicious updates and removed. Meanwhile, we apply the Kolmogorov-Smirnov test to choose a proper probability distribution function and tune its parameters to fit the distribution of reconstruction errors from observed benign updates. We then use the distribution function to estimate the probability that an unseen reconstruction error belongs to the benign reconstruction error distribution. Based on the probability, we classify the model updates as benign or malicious. Only benign updates are used to aggregate the global model. FREPD is tested with extensive experiments on independent and identically distributed (IID) and non-IID federated benchmarks, showing a competitive performance over existing aggregation methods under Byzantine attack and backdoor attack.     

一种基于格的隐私保护聚类数据挖掘方法

由于云计算的诸多优势,用户倾向于将数据挖掘和数据分析等业务外包到专业的云服务提供商,然而随之而来的是用户的隐私不能得到保证.目前,众多学者关注云环境下敏感数据存储的隐私保护,而隐私保护数据分析的相关研究还比较少.但是如果仅仅为了保护数据隐私,而不对大数据进行挖掘分析,大数据也就失去了其潜在的巨大价值.本文提出了一种云计算环境下基于格的隐私保护数据发布方法,利用格加密构建隐私数据的安全同态运算方法,并且在此基础上实现了支持隐私保护的云端密文数据聚类分析数据挖掘服务.为保护用户数据隐私,用户将数据加密之后发布到云服务提供商,云服务提供商利用基于格的同态加密算法实现隐私保护的k-means、隐私保护层次聚类以及隐私保护DBSCAN数据挖掘服务,但云服务提供商并不能直接访问用户数据破坏用户隐私.与现有的隐私数据发布方法相比,论文的隐私数据发布基于格的最接近向量困难问题（CVP）和最短向量困难问题（SVP）,具有很高的安全性.同时算法有效保持了密文数据间距离的精确性,与现有研究相比挖掘结果也具有更高的精确性和可用性.论文对方法的安全性进行了理论分析并设计实验对提出的隐私保护数据挖掘方法效率进行评估,实验结果表明本文提出的基于格的隐私保护数据挖掘算法与现有的方法相比具有更高的数据分析精确性和更高的计算效率.     

隐私保护数据挖掘系统的设计与实现

随着网络安全问题受到越来越多的关注,隐私保护数据挖掘问题已经成为数据挖掘领域中的研究热点。该文设计与实现了一个隐私保护数据挖掘系统,系统的算法可以帮助用户完成一些简单的隐私保护数据挖掘工作。在实际系统应用中,用户可以根据实际需要加入新的算法来完成隐私保护数据挖掘工作。     

基于随机博弈的机会网络隐私保护机制

机会网络在数据转发过程中,由于需要依靠陌生节点帮助转发信息或者接收来自陌生节点的数据,这种数据转发机制对普通用户来说具有严重的隐私安全隐患。因此,本文针对机会网络中存在恶意节点窃取用户隐私等安全问题,为机会网络中的用户设计出一种最佳防御策略来防止个人隐私泄露。首先,建立机会网络下的系统模型,使用马尔科夫链刻画普通用户的个人信息的变化过程。在系统模型的基础上,采用随机博弈理论对用户与攻击者之间的攻防关系进行建模;然后,提出一种基于极小极大学习算法的防御策略;最后,通过与传统防御算法的对比实验,证明该算法不但具有较快的收敛速度,且在满足一定用户服务质量的前提下,性能始终优于其他防御策略,是机会网络下一种高效的隐私保护安全机制。     

分布式隐私保护FHE-DBIRCH模型研究

隐私保护数据挖掘是当前数据挖掘领域中一个十分重要的研究问题,其目标是在无法获得原始明文数据时可以进行精确的数据挖掘,且挖掘的规则和知识与明文数据挖掘的结果相同或类似。为了强化数据的隐私保护、提高挖掘的准确度,针对分布式环境下聚类挖掘隐私保护问题,结合完全同态加密、解密算法,提出并实现了一种基于完全同态加密的分布式隐私保护FHE DBIRCH模型。模型中数据集传输采用完全同态加密算法加密、解密,保证原始数据的隐私。理论分析和实验结果表明,FHE-DBIRCH模型不仅具有很好的数据隐私性且保持了聚类精度。     

差分隐私综述

差分隐私是2006年由DWORK提出的一种新型的隐私保护机制,它主要针对隐私保护中,如何在分享数据时定义隐私,以及如何在保证可用性的数据发布时,提供隐私保护的问题,这两个问题提出了一个隐私保护的数学模型。由于差分隐私对于隐私的定义不依赖于攻击者的背景知识,所以被作为一种新型的隐私保护模型广泛地应用于数据挖掘,机器学习等各个领域。本文介绍了差分隐私的基础理论和目前的研究进展,以及一些已有的差分隐私保护理论和技术,最后对未来的工作和研究热点进行了展望。     

基于隐私保护的关联规则挖掘算法

基于隐私保护的关联规则挖掘在挖掘项集之间的相关联系的同时,可以保护数据提供者的隐私。基于数据变换法,提出使用高效数据结构即倒排文件的隐私保护关联规则挖掘算法IFB-PPARM。针对特定的敏感规则以及给定的最小支持度和置信度,得到所需要修改的敏感事务并对其做适当的处理。算法只需对事务数据库做一次扫描,并且所有对事务的处理操作都在事务数据库映射成的倒排文件中进行。分析表明,该算法具有较好的隐私性和高效性。     

k-Anonymous data collection

To protect individual privacy in data mining, when a miner collects data from respondents, the respondents should remain anonymous. The existing technique of Anonymity-Preserving Data Collection partially solves this problem, but it assumes that the data do not contain any identifying information about the corresponding respondents. On the other hand, the existing technique of Privacy-Enhancing k-Anonymization can make the collected data anonymous by eliminating the identifying information. However, it assumes that each respondent submits her data through an unidentified communication channel. In this paper, we propose k-Anonymous Data Collection, which has the advantages of both Anonymity-Preserving Data Collection and Privacy-Enhancing k-Anonymization but does not rely on their assumptions described above. We give rigorous proofs for the correctness and privacy of our protocol, and experimental results for its efficiency. Furthermore, we extend our solution to the fully malicious model, in which a dishonest participant can deviate from the protocol and behave arbitrarily.     

A reliable recommendation and privacy-preserving based cross-layer reputation mechanism for mobile cloud computing

Mobile cloud computing (MCC) is gaining popularity due to anywhere anytime data access. However, at the same time it also introduces the new privacy and security threats that have become an obstacle to the widespread use and popularity of MCC. In this paper, we propose a reliable recommendation and privacy preserving based cross-layer reputation mechanism (RP-CRM) to provide secure and privacy-aware communication process in wireless mesh networks (WMNs) based MCC (WM-MCC). RP-CRM integrates the cross-layer design with recommendation reputation reliability evaluation mechanism and the privacy preserving scheme to identify and manage the internal malicious nodes and protect the security and privacy against internal multi-layer attack, bad mouthing attack and information disclosure attack. Simulation results and performance analysis demonstrate that RP-CRM can provide rapid and accurate malicious node identification and management, and provide security and privacy protection against aforementioned attacks more effectively and efficiently.     

面向隐私保护的数据挖掘技术研究

隐私与安全是数据挖掘中一个越来越重要的问题。隐私与安全问题的解决能破坏图谋不轨的挖掘工程。文中研究了数据挖掘中隐私保护技术的发展现状,总结出了隐私保护技术的分类,详细讨论了隐私保护技术中最重要的隐私保持技术,最后得出了隐私保护技术算法的评估指标。     

Privacy-preserving distributed association rule mining via semi-trusted mixer

Distributed data mining applications, such as those dealing with health care, finance, counter-terrorism and homeland defence, use sensitive data from distributed databases held by different parties. This comes into direct conflict with an individual’s need and right to privacy. In this paper, we come up with a privacy-preserving distributed association rule mining protocol based on a new semi-trusted mixer model. Our protocol can protect the privacy of each distributed database against the coalition up to n − 2 other data sites or even the mixer if the mixer does not collude with any data site. Furthermore, our protocol needs only two communications between each data site and the mixer in one round of data collection.     

Outlier-eliminated k-means clustering algorithm based on differential privacy preservation

Individual privacy may be compromised during the process of mining for valuable information, and the potential for data mining is hindered by the need to preserve privacy. It is well known that k-means clustering algorithms based on differential privacy require preserving privacy while maintaining the availability of clustering. However, it is difficult to balance both aspects in traditional algorithms. In this paper, an outlier-eliminated differential privacy (OEDP) k-means algorithm is proposed that both preserves privacy and improves clustering efficiency. The proposed approach selects the initial centre points in accordance with the distribution density of data points, and adds Laplacian noise to the original data for privacy preservation. Both a theoretical analysis and comparative experiments were conducted. The theoretical analysis shows that the proposed algorithm satisfies ε-differential privacy. Furthermore, the experimental results show that, compared to other methods, the proposed algorithm effectively preserves data privacy and improves the clustering results in terms of accuracy, stability, and availability.     

Privacy-Preserving Backpropagation Neural Network Learning

With the development of distributed computing environment , many learning problems now have to deal with distributed input data. To enhance cooperations in learning, it is important to address the privacy concern of each data holder by extending the privacy preservation notion to original learning algorithms. In this paper, we focus on preserving the privacy in an important learning model, multilayer neural networks. We present a privacy-preserving two-party distributed algorithm of backpropagation which allows a neural network to be trained without requiring either party to reveal her data to the other. We provide complete correctness and security analysis of our algorithms. The effectiveness of our algorithms is verified by experiments on various real world data sets.