Google may save you a trip to the embassy because this isn't done on a federal level. It's done within the state or between states. As I was born in Wisconsin, I need to get a name change court order in Arizona, bundle it with my gender change paperwork and ship it off to Wisconsin. As you are out of the country, I am not sure if the court of your birth state will recognize an out of the country court but they may have a procedure in place for such cases. The rules are different from state to state so look up the state requirement first. It's all on line and a google of "state birth records" should get you to the correct site.