Could you break it down for me as a process that happens inside Vanitygen rather than using math?
Bitcoin uses Elliptic Curve (EC) Cryptography for its Digital Signature Algorithm (DSA), which is why you'll often see it referred to as ECDSA.
With ECDSA, everyone agrees on a specific point on the curve to be a starting point. This point will generally be written as G when it's being discussed.
The private key is just a large integer. (You'll often see it written as p when it's being discussed). With bitcoin, it's a random number between 1 and 115792089237316195423570985008687907852837564279074904382605163141518161494336
To get your public key (which is a point on the curve that you'll often see written as Q when it's being discussed), you use a point addition process to add the point G to itself, and then add G to that result, and then add G to that result, and so on. Your private key (p) is the number of times to perform that addition.
Think about this in terms of numbers (instead of points) for a moment. If I ADD the number 5 to itself 7 times, the result is the same as the number 5 MULTIPLIED by 7.
5 + 5 + 5 + 5 + 5 + 5 + 5 = 35
5 * 7 = 35
The same is true with point arithmetic in Elliptic Curve Cryptography. If I add the point G to itself p times, the result is the same as multiplying p times G.
G + G + G + . . . + G = p * G
So, now, if I give you a temporary public key (we'll call it Q here), and you add point G to it (using the arithmetic rules of Elliptic Curve Cryptography), the new point that you get is another public key. Since you added G exactly 1 more time, it's the public key for a private key that is exactly 1 + my temporary private key.
So, let's say you start with my temporary public key (Q), and you keep adding G and checking the address associated with each new public key that you get. You keep track of how many times you added G to the starting public key (let's call that number of times r). Eventually, you find an address that meets the "vanity" requirements that I want. You can then report r back to me. I can just add r to the temporary private key (lets call that q) that I used to generate the initial temporary public key (Q), and I'll get the exact private key (p) that will result in that address. However, since I never told you the temporary private key (q) that I used initially to generate the public key (Q) that I gave you, you have no way of knowing what the new private key (p) is. You ONLY know that it is r more than my starting point (q). As such, the new private key (p) is just as secure as the one I gave you (q). As long as nobody ever knows what temporary private key (q) I used to start the process, they don't know what the new number is at the end of the process.
So, using the math that pooya87 supplied earlier there effectively 3 public keys (P, Q, and R) each with their own private key (p, q, and r respectively).
P = Q + R
(Vanity Public Key = Temporary Starting Public Key + the Public Key the searcher added to get the vanity address)
p*G = Final vanity private key (p) times the starting point G.
This is just another representation of the Vanity Public Key P, but it is in terms of the final private key p, as we discussed that the result of p * G is the public key.
q*G = The temporary private key (q) that the requestor started with times the starting point G.
This is just another representation of Q, the temporary public key that the requestor started with and which they gave to the searcher to find the vanity address with, but it is in terms of the temporary private key (q) that the requestor never gave to the searcher.
r*G = The incremental private key (r) times the starting point G.
This is just another representation of the Public Key the searcher added to get the vanity address (R), but in terms of r, the number of times they had to add G to the temporary public key Q to get to the vanity address.
So:
p*G = q*G + r*G
(hopefully, you can see from above that this is just another way of saying P = Q + R)
By factoring out the starting point (G), we are left with what I described earlier... the requestor can just add the incremental value (r) that the searcher used when searching for the vanity address to the temporary starting private key (q), and the result will be the new private key (p) of the vanity address:
p = q+r
Of those three values, the ONLY one that the searcher knows is r. Since he doesn't know the temporary private key (q), it's impossible for him to know the final private key (p), but he can tell the requestor that the private key for the vanity address is exactly (r) more than whatever the temporary private key (q) was for the temporary public key (Q) that he started with.