How to provide secure "vanity" bitcoin address service? Bitcoin addresses are RIPEMD-160 hashes of the public portion of a public/private ECDSA keypair (along with an abbreviated hash of the hash to provide a check code, as @pulpspy notes in a comment).  They are generally base-58-encoded.  See Address - Bitcoin

In Vanity bitcoin addresses: a new way to keep your CPU busy, user "ByteCoin" says he can create and sell "vanity" bitcoin addresses (like 1ByteCoinsUNJun4KL3HSt1NfFdXpzoRTy) for people.  Furthermore, he states he can use a handshake algorithm to do so without actually getting access to the associated private key (and thus without being able to spend bitcoins which are sent to the address).

What is a fast algorithm for creating vanity bitcoin addresses?  Can they in fact be created and sold in a secure way?
I don't believe that there's any way to generate the vanity hashes without iterating. In base 58, there's $\log_2(58) \approx 5.858$ bits per letter, so fixing 8 letters would need in average $58^8/2 = 2^{\log_2(58)·8}/2 \approx 2^{46}$ iterations. Note that Bitcoin addresses always start with a 1 by convention (this comes from the version field), and the next character in the base 58 representation is usually among "23456789ABCDEFGHJKLMNPQR" (not the full 58 character set), which halves the number of tries once more (if your wished starting character is in this set, otherwise it gets impossible). If you allow your vanity string to appear anywhere in the hash, you can divide this number again by 25, leading to $2^{40.5}$ iterations (on average) (which also are quite good parallelizable).

Also, the actual example he gave had an "s" rather than an "i" in the vanity "ByteCoins" part, so the odds of that are a bit greater (i.e. the needed time is even smaller).

However, you can do it securely (i.e. without the service gaining access to your private key):

Let the user generate a private key, $a$, and submit the corresponding public key, $a·B$ (where $B$ is the base point of the group). The service can then generate public keys as $a·B + x·B$, where $x$ is incremented to generate different public keys.

Actually, if you have $a·B +x·B$, then $a·B + (x+1)·B = (a·B + x·B)+B$, i.e. you need only one EC point addition (of the base point) and the necessary hashes for each try.

Then, by telling the user x, the user has private key $a+x$ with public key $(a+x)·B$ and $H((a+x)·B)$ has the required property, if the service did its job.