异方差加噪下的差分隐私直方图发布算法*

康　健，吴英杰，黄泗勇，陈　鸿，孙　岚福州大学 数学与计算机科学学院，福州 350116



异方差加噪下的差分隐私直方图发布算法*

康健，吴英杰+，黄泗勇，陈鸿，孙岚
福州大学 数学与计算机科学学院，福州 350116

KANG Jian,WU Yingjie,HUANG Siyong,et al.Algorithm for differential privacy histogram publication with non-uniform private budget.Journal of Frontiers of Computer Science and Technology,2016,10(6):786-798.

摘要：现有基于区间树结构的差分隐私直方图发布方法大多采用同方差加噪方式，对其进一步研究发现，采用异方差加噪策略可以进一步提升发布直方图的区间计数查询精度，然而当前基于异方差加噪的差分隐私直方图发布方法对区间树结构却有严格的要求，导致灵活性与实用性较低。为此，提出了一种异方差加噪下面向任意区间树结构的差分隐私直方图发布算法LUE-DPTree（inear unbiased estimator for differential private tree）。首先根据区间计数查询的分布，计算区间树中节点的覆盖概率，并据此分配隐私预算，实现异方差加噪；接着经分析指出该异方差加噪策略适用于任意区间树结构，且从理论上证明了在任意区间树结构下进行异方差加噪后，仍可在一致性约束下利用最优线性无偏估计进一步降低区间计数查询的误差。针对算法的区间计数查询精度及执行效率，与同类算法进行了比较分析。实验结果表明，LUE-DPTree算法是有效可行的。

关键词：隐私保护；差分隐私；直方图发布；异方差加噪；区间树

ISSN 1673-9418CODEN JKYTA8

Journal of Frontiers of Computer Science and Technology

1673-9418/2016/10(06)-0786-13

E-mail:fcst@vip.163.com

http://www.ceaj.org

Tel:+86-10-89056056

1　引言

随着信息技术的发展，大量数据的收集与发布在促进科学技术进步的同时，也带来了隐私信息泄露的问题。因此，数据发布隐私保护成为现今一项热门的研究课题。

近年来，在数据发布隐私保护领域，研究人员开展了一系列的研究，主要可分为数据加密、限制发布和数据扰乱等方面[1-3]，包括k-anonymity[4]、l-diversity[5]等保护方法。……