There's an easy way to do that: pass a law exempting Social Security Numbers from all identity theft and fraud laws.

Make it completely legal and tort-free to lie about social security numbers anytime, anywhere, except when dealing directly with the government (i.e. filing your taxes).

That'll stop them being used, and right quick.