I head that from a public key, you can generate random addresses just by adding a nonce to the public key. Then, you can regenerate all these addresses again when you need, right?
If my wallet has knowledge of my public key (of course it has), it can generate lots of private/public key pairs just by adding a number to it. For example, suppose the private key is
x and its public key is
y. If the wallet deleted the private key
x for a while, it can generate the address
y+1 and be sure that when it does
x+1 it will get the private key for this address in the future when it needs to spend those funds. This is a property of elliptic curve cryptography, because there's a homeomorphism between the sets of private and public keys.
I've heard that if I give someone my public key, he can derive a unique address and send to this address being sure that I'll be able to spend it because I can find the private key for that address just by adding the same nonce he used to generate its public key. The problem is:
He has to tell me which nonce was used, otherwise I'd have to try random ones till I get to the one he used. BUT, if that's how its made, then anyone can pick my public key and find all my addresses. If he really has to tell me the nonce used (suppose it's really big and random so I couldn't guess by brute forcing), then there's the risk that I'll lose it, because I'd have to keep track of all these nonces.
So how is this done? How can I, given the public key of someone, generate a random address for him such that he'll be able to get the private/public key for it later, but such that he does not need to store anything that was used to generate that address?