Although of course that's a lot more in principle than in practice! Like rolling your own crypto, I think experience shows that, against determined de-anonymizers, there is basically nothing you can do to preserve anonymity except to severely limit the information, and the only way definite feedback you get is if you don't succeed and someone discloses the de-anonymized information that they were able to reconstruct.
Your argument makes me think we really SHOULD make all government data public. Then people would have an incentive to not let governments have so much of their private data.
Also, I hope you don't mean the federal government should know if you've been arrested. I don't think that should be available to them at all.