fuzzy search or phonetic search with hash

My business requirements are as follow: I need to be able to do a fuzzy or phonetic search over names. For example, if my database has the string "Müller", I want to get matches for "Muller", "Müler" and so forth.

On top of that, for privacy reasons, I don't want to store the names as plain text. I thought about just storing the hash of the names, and also hashing the search strings and search based on that, but I don't know how to reconcile this with the fuzzy search requirement stated above.

I'll be running this on WSO2 server acessing a MySQL database. Ideally the string match would be done at the dabatase level, but I could also execute some Java library if necessary.

Any suggestions?