Maybe the solution would be to have Swiss style direct democracy so that people could directly approve or disapprove of any particular system of data collection.
Using current events as an example, I don't think it would be out of the realm of possibility for a national referendum to pass that called for mandatory citizenship checks of people who appeared to be not born in the United States. Direct democracy works for homogenous populations, but I doubt it is the right fit for the United States.