If you want address hello and I want Hallo, somebody could search for both and give you and me the respective results.
Exactly. There are services that provide this.
It is utterly stupid to trust any service to generate save addresses for you as there is no way of knowing if he deleted his copy or not. Once he gets cancer or turns into an asshole, he digs out these addresses and spends your money.
AAAHHHHH!!!!! Bitcoin address generation is best never outsourced! Why did 10 replies not mention this?
Because it isn't necessarily true. When done properly, it is possible for someone to generate an address for you without knowing what the private key is.
1) You generate a random 256-bit integer less than the SECP256k1 generator. You keep this secret. (Effectively, an ECDSA private key.)
2) You compute the corresponding EC point on the SECP256k1 curve. You share this with whoever is finding the vanity address for you. (This is the ECDSA public key that corresponds to the private key you generated in step one.)
3) The person working out the vanity address for you tries various 256-bit integers also less than the SECP256k1 generator. They compute the corresponding EC point and add it to the EC point you sent them (from step two). They then hash this and see if it produces the desired vanity address. They repeat this over and over until they find a 256-bit integer that works. They give this integer to you. (And the world, it need not be kept secret.)
4) You add the 256-bit integer they found to the 256-bit integer you generated in step 1 and reduce it modulo the SECP256k1 generator.
5) You now have the private key, and they don't. (And you can prove that they cannot generate the private key from just the information you gave them unless ECDSA is fundamentally broken.)
In ECDSA, you convert a private key to a public key by multiplying by the generator. Division is impossible.
The vanity address generation scheme above works because: (A+B)*G = AG + BG
You generate A and AG, but give them only AG.
They try various different B's, calculating the AG+BG for each one to find the right one for the vanity address.
They give you B. You can now compute A+B (the secret key corresponding to the public key AG+BG) but nobody else can since they do not know A.
Computing A from AG would mean breaking ECDSA fundamentally. All you gave them is AG, an ECDSA public key. If they could figure out the private key to your new account (A+B), they could also figure out A. So if they could figure out the private key to your vanity account, they could also figure out the private key you created in step 1. But all you gave them was the corresponding public key. So any compromise of the vanity account would mean they could compromise a private key given only its corresponding public key.
For one such service, see here:
https://bitcointalksearch.org/topic/vanity-pool-vanity-address-generator-pool-84569
