How to generate random addresses from public key such that they're recoverable later using pub key only

Question

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?

Answer 1

I believe you are talking about HD derived keys, as is the previous question you linked. HD wallet structure is laid out in BIP 32.

If someone has your parent extended public key, they can derive public extended child keys using it and an index/nonce. They must have the extended key (including the chain code) But they cannot derive the child private keys. Only you can do that, using the parent extended private key. So they can tell you the index, and anyone else with the index and the extended parent public key can see which public key was used, but the only one with the private key is you.

To derive the child keys you have to at least keep the master extended private key (or the seed it came from). Without that, you cannot derive any private keys.