Generalized Iterative Bayesian Update and Applications to Mechanisms for Privacy Protection

The iterative Bayesian update (IBU) and the matrix inversion (INV) are the main methods to retrieve the original distribution from noisy data resulting from the application of privacy protection mechanisms. We show that the foundations of IBU established in the literature are flawed, as they rely on an assumption that in general is not satisfied in typical datasets. We then propose an extension of the method, covering a more general privacy model, where different users are allowed to apply different privacy mechanisms. We call our algorithm GIBU, for Generalized IBU, and we prove its convergence to the maximum likelihood estimate, constructing a proof that does not rely on the problematic assumption, thus fixing also the theory of IBU. Finally we evaluate the precision of GIBU on data sanitized with k-RR, Rappor, geo-indistinguishability and exponential mechanisms. We show that, while GIBU and INV are comparable in the first two cases, the performance of GIBU is definitely superior in the latter cases.