| 摘要: |
| 在差分隐私保护程度确定的条件下使数据的有用性最大化的问题，称为差分隐私的最优机制问题.最优机制问题是差分隐私理论中的一个重要问题，与差分隐私模型的理论基础及应用前景有直接联系.与已有的研究不同，提出一种不基于敏感度的分析方法来寻找最优机制：首先，将最优机制问题构造为一个多目标函数优化问题，并提出了一种差分隐私机制构造方法，在此基础上，对线性查询问题给出了一种近似最优差分隐私机制，该机制达到了差分隐私不等式的边界.此外，大部分分析方法也可对非线性查询的最优机制问题进行分析.该研究揭示了敏感度方法的不足之处，发现其无法刻画数据集的邻居集合对应的查询函数值集合的特性，而该集合包含了差分隐私的一些深层特征. |
| 关键词: 线性查询 差分隐私 最优机制 多目标优化 非敏感度方法 |
| DOI：10.13328/j.cnki.jos.005184 |
| 分类号: |
| 基金项目:中国科学院战略性先导科技专项基金（XDA06010600） |
|
| Near-Optimal Differentially Private Mechanism for Linear Queries |
|
WU Gen-Qiang1,2, HE Ye-Ping1,3, XIA Xian-Yao1
|
|
1.National Engineering Research Center of Fundamental Software, Institute of Software, The Chinese Academy of Sciences, Beijing 100190, China;2.School of Information Engineering, Lanzhou University of Finance and Economics, Lanzhou 730020, China;3.State Key Laboratory of Computer Science, Institute of Software, The Chinese Academy of Sciences, Beijing 100190, China
|
| Abstract: |
| The optimal differentially private mechanism problem is to maximize the data utility on a fixed privacy protection extent. The optimal mechanism problem is an important topic in differential privacy, which has close connection with both theoretical foundation and future applications of differential privacy model. This paper proposes a analyzing method about the topic, which is not based on the sensitivity method. First, the optimal mechanism problem is constructed to be a multi-objective optimization problem, and a new method for constructing differentially private mechanism is introduced. Then, a near-optimal mechanism is provided for the linear queries, which reaches the boundary of the differential privacy inequality. Although this paper focuses on the linear queries, most part of the analyzing method introduced is applicable to the non-linear queries. This paper finds the drawback of the sensitivity method and uncovers some deeper characteristics of differential privacy. |
| Key words: linear query differential privacy optimal mechanism multi-objective optimization non-sensitivity method |
