Way back in 1978, Demillo, Lipton and Dobkin published a note in the IEEE Transactions on Software Engineering (SE-4(1):73- 75 ยท February 1978) called "Even databases that lie can be compromised" The basic idea was to look at the idea of giving slightly wrong answers to median type queries in order to protect results for individuals. They showed that, even when the query system deliberately lied, it was possible to compromise the data base. I am surprised that this note is not listed in the bibliography of the differential privacy article.
