  The problem of designing error optimal differentially private algorithms is
well studied. Recent work applying differential privacy to real world settings
have used variants of differential privacy that appropriately modify the notion
of neighboring databases. The problem of designing error optimal algorithms for
such variants of differential privacy is open. In this paper, we show a novel
transformational equivalence result that can turn the problem of query
answering under differential privacy with a modified notion of neighbors to one
of query answering under standard differential privacy, for a large class of
neighbor definitions.
  We utilize the Blowfish privacy framework that generalizes differential
privacy. Blowfish uses a {\em policy graph} to instantiate different notions of
neighboring databases. We show that the error incurred when answering a
workload $\mathbf{W}$ on a database $\mathbf{x}$ under a Blowfish policy graph
$G$ is identical to the error required to answer a transformed workload
$f_G(\mathbf{W})$ on database $g_G(\mathbf{x})$ under standard differential
privacy, where $f_G$ and $g_G$ are linear transformations based on $G$. Using
this result, we develop error efficient algorithms for releasing histograms and
multidimensional range queries under different Blowfish policies. We believe
the tools we develop will be useful for finding mechanisms to answer many other
classes of queries with low error under other policy graphs.
