线性查询的一种近似最优差分隐私机制

在差分隐私保护程度确定的条件下使数据的有用性最大化的问题称为差分隐私的最优机制问题.最优机制问题是差分隐私理论中的一个重要问题，与差分隐私模型的理论基础及应用前景有直接联系.与已有的研究不同，本文提出一种新的不基于敏感度的分析方法，来寻找最优机制.首先，本文将最优机制问题构造为一个多目标函数优化问题并提出了一种新的差分隐私机制构造方法.在此基础上，本文对线性查询问题给出了一种近似最优差分隐私机制（定理2），该机制达到了差分隐私不等式的边界.此外，本文的大部分分析方法也可对非线性查询的最优机制问题进行分析.本文的研究揭示了敏感度方法的不足之处，发现其无法刻画数据集的邻居集合对应的查询函数值集合的特性，而该集合包含了差分隐私的一些深层特征.

Near-Optimal Differentially Private Mechanism for Linear Queries

The optimal differentially private mechanism problem is to maximize the data utility on the fixed privacy protection extent. The optimal mechanism problem is an important topic in differential privacy, which has large connection with both theoretical foundation and future applications of differential privacy model. This paper proposes a new 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, we give a near-optimal mechanism for the linear queries (Theorem 2), which reaches the boundary of the differential privacy inequality. Although this paper focuses on the linear queries, most part of the analyzing method we 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.