差分隐私的查询一致性约束研究

Query consistency constraints of differential privacy

针对差分隐私直方图发布中区间查询的不一致问题,研究已有需迭代调整的局部最优线性无偏估计算法LBLUE,提出一种不需迭代且满足一致性约束查询的CA算法。通过对1棵添加Laplace噪声的满k-叉区间树进行一致性调整:先利用TDICE算法进行自顶向下的不一致估计,再利用BUCE算法进行自底向上的一致性估计,得到满足一致性约束查询的差分隐私满k-叉区间树,遍历后发布满足一致性约束查询的直方图数据。经过证明和实验分析,一致性调整后的查询区间满足一致性约束查询,且精确度优于Boost-2算法和LBLUE算法的,同时算法的时间效率高于LBLUE算法的。

Aiming at the inconsistency phenomenon of range query in differential privacy histogram publishing,we study the local optimal linear unbiased estimation algorithm LBLUE that needs iterative adjustment and propose a CA algorithm that does not need iteration and satisfies the consistency constraint query.Consistency adjustment is performed on a full k-ary range tree with Laplace noise:the TDICE algorithm is first used for top-down inconsistency estimation,and then the BUCE algorithm is used for bottom-up consistency estimation,so as to obtain a full k-ary range tree with differential privacy,which meets consistency constraint query.The histogram data satisfying the consistency constraint query is published after traversal.Proof and experimental analysis show that the query range after consistency adjustment satisfies the consistency constraint query.It has higher accuracy than Boost-2 algorithm and LBLUE algorithm,and higher time efficiency than LBLUE algorithm.