Abstract:

Error is a common index to measure the accuracy of differential privacy data publishing algorithm. Most of the existing methods evaluate the accuracy of differential privacy publishing algorithm by simulation experiments. However, the randomness of differential mechanism will make the algorithm running results accidental, and the experimental results will be influenced by the data set. Therefore, the performance evaluation of differential privacy data publishing algorithm based on simulation experiment has great limitations. This paper firstly analyzes the theoretical error of differential privacy data publishing algorithm based on matrix mechanism, and then deduces the corresponding theoretical error formula through the relevant theory of matrix operation. After that, this paper puts forward the accuracy index of performance comparison between different differential privacy publishing algorithms with the same error complexity. Finally, the correctness of the theoretical error formula presented in this paper is verified by comparing the value of theoretical error and experimental error.

Key words: differential privacy, data publishing, matrix mechanism, error analysis, accuracy index

摘要：

误差是衡量差分隐私数据发布算法精度的常用指标。已有的研究大多通过仿真实验评估差分隐私发布算法的精度。然而，差分隐私机制的随机性将使算法运行结果存在偶然性，且实验结果将会受所用数据集的影响，因此基于仿真实验分析的差分隐私数据发布算法性能评估具有较大的局限性。从理论上对基于矩阵机制的差分隐私数据发布算法进行误差分析，利用矩阵运算的相关理论，求出相应的理论误差计算公式，并提出可有效衡量具有相同误差渐进阶的不同差分隐私发布算法之间性能差异的精确度指标。最后通过比对实验误差和理论误差值，验证了所求理论误差公式的正确性。

关键词: 差分隐私, 数据发布, 矩阵机制, 误差分析, 精确度指标