Another thought, and I do believe this is legal (at least it used to be). Request a form from your local Social Security Office for requesting a new copy of your social security card; do this by phone. They mail the form to you. On this form, if I remember correctly, there is an option for changing your name. This is generally used for when a woman marries, but there is no law against ANYONE changing their name for personal reasons. For example, lets say your mother is Jewish and your father is Catholic, and you discover that during your adult life you identify more with your mother's religion and want to take on her name instead. Or, lets say you've been taunted all your life by your peers for a funny-sounding name (and it can be locally funny and not something an 'outsider' might understand), and you have just had it, your therapist has suggested you change it, and you want to make a new start in life. Etc. etc. This was told to me by an actor, who did it himself, for professional reasons; I never learned of his "given name," but I gathered it was completely different.
Using your new social security card, you go on to build other identification forms on top of that.
Note that this changes your name, NOT your social security number. It changes only how you want to be identified in the everyday world. Since your social security number is still the same, the government really doesn't have anything to complain about. Your new identity is legit.
This might not resolve your problem. It certainly won't help if you are trying to disappear from the government itself.
