面向高维数据发布的差分隐私保护方法研究

The vast amount of high-dimensional data (such as transaction data and trajectory data) produced by the internet usually contains personal privacy information. Currently, the most representative of the privacy preserving data publishing technique is based on the k-anonymous model. However, due to the limitations of the model and the characteristics of the high dimensional data which is high dimensional and sparse, resulting in lack of the privacy and the utility of published data. Therefore, this project intends to apply the differential privacy model to the privacy protection of high dimensional data. The game theory is used to construct the game model between utility and privacy, and the optimal solution is found based on Nash equilibrium. Including the difficulties and key problems of this subject: (1) according to the characteristics of high dimensional data, we will build the high dimensional data structure (such as the appropriate expression of Trie tree, prefix tree etc.), and then add noise in the structure to meet privacy; (2) for high dimensional data mining tasks (such as different frequent itemsets mining, data query etc.), we will build structure of the utility model, find the optimization of noise to meet utility; (3) constructing game model of privacy and utility, to find the Nash equilibrium make the optimal between privacy and utility; (4) we will expand the Nash equilibrium to the distributed structure, and design the encryption protocol to meet the security. The successful implementation of this project is beneficial to the safe mining of knowledge in high dimensional data.

互联网产生的海量高维数据（如事务数据、轨迹数据）中通常包含个人的隐私信息。当前最具代表性的隐私保护数据发布方法是基于k-匿名模型，但是该类模型的局限性以及高维数据自身高维且稀疏的特征，导致发布数据的隐私性与效用性不足。因此，本项目拟将差分隐私模型应用于高维数据隐私保护发布，采用博弈论方法构建效用性与隐私性之间的博弈模型，并基于纳什均衡寻找最优解。本项目要突破的挑战与关键问题包括：(1) 针对高维数据的特征，采用合适的高维数据表达结构(如Trie树、前缀树等)，添加噪音满足隐私性；(2) 针对不同的高维数据挖掘任务(如频繁项集挖掘、数据查询等)，构造效用性模型，优化噪音满足效用性；(3) 构建隐私性与效用性之间的博弈模型，寻找纳什均衡使隐私性与效用性同时最优；(4) 扩展到分布式结构下，设计加密协议满足安全性。本项目的成功实施有利于安全地挖掘高维数据中的知识。

本项目针对高维稀疏的数据（包括事务数据、集值数据等），采用本地差分隐私模型，围绕高维数据隐私保护收集这一问题，针对高维数据不同的数据分析任务， 以“隐私性”、 “效用性”、 “实用性”为出发点，设计了一系列数据收集隐私保护策略。主要研究内容有三点：（1）研究面向频繁项集挖掘的本地差分隐私事务数据收集方法；（2）研究基于类型层级的本地差分隐私集值型数据收集方法；（3）考虑到差分隐私问题的隐私参数的设置问题，研究差分隐私模型的启发式隐私参数设置策略。.目前已经取得3个重要成果：.（1）差分隐私模型是一种强隐私模型，隐私参数ε的设置依赖于实验或专业人士经验。针对这个问题，基于(ρ1， ρ2)-隐私模型提出一种启发式的隐私参数ε设置策略（LPBDP）．如果攻击者关于目标受害者的先验概率小于阈值ρ1，攻击者得到差分隐私查询策略返回的加噪结果后，关于目标受害者的后验概率必须小于阈值ρ2。.（2）基于压缩的本地差分隐私模型，提出一种事务数据收集方法。首先，定义一种新的候选项集的分值函数；其次，基于该函数将候选项集的样本空间划分为多个子空间；第三，随机选择其中一个子空间，基于该子空间随机生成事务数据并发送给不可信的数据收集者。最后考虑到隐私参数的设置问题，基于最大后验置信度攻击模型设计启发式隐私参数设置策略。.（3）基于集值数据的类型层级提出一种本地差分隐私集值型数据收集方法SetLDP，其核心思想是先对集值数据的类型是否存在进行随机响应，如果类型存在则继续对项的计数进行扰乱，最后基于新的效用性函数随机响应一个候选项集。理论与实验结果表明，SetLDP与已有方法相比不仅能保留更多的信息,而且能够保护集值数据的类型隐私。