The troubling truth is that many people would be either happy (or at least accepting) if the people doing the monitoring were also making big dents in the amount of spam being sent, or catching major criminals.
That's actually simple - public should use strong encryption. That's it. I.e. those who care about such violation of civil freedoms have no other option anyway, if attempts to prevent this surveillance will continue to fail (and with the current power - they most probably will).
I predict in the future after a couple of high profile scape goat cases where a famous suspected terrorist, illegal movie downloader, or say whistle blower, cannot be prosecuted because they used encryption, the use of encryption will become illegal.
The problem with outlawing encryption is: everyone needs it for business purposes and to protect public / private infrastructure. If SSL encryption were to be forbidden, e-commerce would become very difficult...
Also interesting: http://en.wikipedia.org/wiki/Chaffing_and_winnowing ("Chaffing and winnowing is a cryptographic technique to achieve confidentiality without using encryption")
http://www.theregister.co.uk/2012/03/01/forced_decryption_ru...
However I think if some state is to ban encryption, it can be called a police state without any doubt.
For instance many care about some "moral" or "religious" issues that have no bearing with objective reality. So a lot time, mental and emotional effort goes into those issues.
It is kind of interesting that caring about privacy in general is become weird it is almost demonized and relegated to criminal sphere by default -- terrorism, child pornography, drug dealing, piracy all those "hot" issues can be triggered in order to argue against privacy. A few fear words sprinkled here and there, a scapegoat show trial and we are not too far from just using encryption becoming illegal. By default it has become "weird" defending privacy when the opposite should be true -- it should feel "weird" defending erosion of privacy (at least in this country given its Constitutional principles).
The messaging/stimulus/response isn't fully ingrained into people yet, but there is a strong need of an equally useful counter narrative.
So the problem is, what does it mean for the public in general to care? Or rather, what is the value of truth in a world where we have no agency?