On Linear Refinement of Differential Privacy-Preserving Query Answering

Recent work showed the necessity of incorporating a user’s background knowledge to improve the accuracy of estimates from noisy responses of histogram queries. Various types of constraints (e.g., linear constraints, ordering constraints, and range constraints) may hold on the true (non-randomized) answers of histogram queries. So the idea was to apply the constraints over the noisy responses and find a new set of answers (called refinements) that are closest to the noisy responses and also satisfy known constraints. As a result, the refinements expect to boost the accuracy of final histogram query results. However, there is one key question: is the ratio of the distributions of the results after refinements from any two neighbor databases still bounded? In this paper, we introduce a new definition,

ρ

-differential privacy on refinement, to quantify the change of distributions of refinements. We focus on one representative refinement, the linear refinement with linear constraints and study the relationship between the classic

ε

-differential privacy ( on responses) and our

ρ

-differential privacy on refinement. We demonstrate the conditions when the

ρ

-differential privacy on refinement achieves the same

ε

-differential privacy. We argue privacy breaches could incur when the conditions do not meet.