ThePiachu explains it like this:
The idea is, that you can generate a vanity address without even
knowing what private key it will actually belong to. One party grabs a
random ECDSA keypair and saves the private key for themselves. They
later can issue a request for a vanity address to be created, by
supplying the public key form that keypair, their desired pattern and
so forth. A person takes with looking for the vanity address is
required to brute force random ECDSA private keys, get their
corresponding public keys, add them to the provided public key, and
proceed normally with SHA, RIPEMD and base58 until they receive the
desired pattern. Then they give the private key they found to the
first person, which adds the two private keys in order to get their
vanity address. The best thing about it - the person looking for the
solution won't know what the resulting private key is! This means that
you can outsource your vanity key generation without needing to trust
any third party.
An example (available from gobittest website): We have a private key:
maps to public key:
and say we want to find a pattern "166". One of the solutions takes a
form of a private key
mapping to public key:
If we add the two public keys (like the person looking for the
solution would do), we get a public key:
54436A1283210CCEFBB6B16CB9A86B009488922A8F302A27487 which is
equivalent to this address: 166ev9JXn2rFqiPSQAwM7qJYpNL1JrNf3h
If we add the two private keys (like the person requesting the address
would), we get:
maps to the same public key as the sum of the public keys, and thus -
to the same address.
Since this is a model that requires basically no trust from any party,
I've decided to create this "Vanity Pool" to enable people to easily
outsource their vanity address creation, as well as enable people
wanting to earn some Bitcoins to use their machines for something
different from traditional mining.
The simplest option to get the keypair to get started with the vanitypool is to go to https://www.bitaddress.org/ and generate a new address. Note down the private key. Now switch the tab to "Wallet Details" and enter the private key. One of the resulting fields is the "Public Key (130 characters [0-9A-F])" which has exactly the required format that is needed for the vanity pool.
Once a solution is found just combine the result that is mailed to you with the private key you noted before and you can import it into your Bitcoin client.