Tools such as
Vanitygen used to generate vanity addresses, Bitcoin addresses which follow a specific pattern, have been somewhat popular.
Generating a vanity address is a computationally intensive task, more so the more specific the pattern. It is conceivable that some people would like a vanity address but lack the appropriate hardware to generate it. Others may have the necessary hardware but not sufficient interest in an address. This suggests the need for a vanity market where clients outsource the production of addresses to generators for an agreed upon fee.
Ostensibly, this suffers from the problem of the need for secrecy - whoever generates the address has access to the corresponding private key, but the client who is to be the owner of the address must remain the sole person knowing the private key. This problem can be solved with some ECDSA magic of the kind discussed
here.
The way it would work is this:
1. Client generates himself a single private key c and corresponding public key c*G. He also chooses a pattern P.
2. Client keeps c secret, but submits c*G and P to the generator.
3. Generator repeatedly generates a private key g, calculates g*c*G and checks if the address generated from the public key g*c*G matches the pattern P.
4. #3 is repeated until a match g is found.
5. Generator submits g to the client. The client uses g*c as a private key and g*c*G as the corresponding public key, which maps to the desired vanity address.
6. The generator, not knowing c or g*c, cannot claim coins from the generated address.
The procedure can be modified so that instead of using g*c as the private key and g*c*G as the public key, the private key will be g+c and the public key will be g*G+c*G. This is deemed less secure, but I believe is suitable for this application and may be less computationally expensive.
