  Differentially private mechanisms protect privacy by introducing additional
randomness into the data. Restricting access to only the privatized data makes
it challenging to perform valid statistical inference on parameters underlying
the confidential data. Specifically, the likelihood function of the privatized
data requires integrating over the large space of confidential databases and is
typically intractable. For Bayesian analysis, this results in a posterior
distribution that is doubly intractable, rendering traditional MCMC techniques
inapplicable. We propose an MCMC framework to perform Bayesian inference from
the privatized data, which is applicable to a wide range of statistical models
and privacy mechanisms. Our MCMC algorithm augments the model parameters with
the unobserved confidential data, and alternately updates each one conditional
on the other. For the potentially challenging step of updating the confidential
data, we propose a generic approach that exploits the privacy guarantee of the
mechanism to ensure efficiency. We give results on the computational
complexity, acceptance rate, and mixing properties of our MCMC. We illustrate
the efficacy and applicability of our methods on a na\"ive-Bayes log-linear
model as well as on a linear regression model.
