You can derive a new public key from someone's ECC public key, and they can derive the corresponding private key by applying the same transformation. It's somewhat magical! I wouldn't be surprised if Apple is using a scheme based on this instead of ElGamal, they already use ECC extensively.

https://github.com/bitcoin/bips/blob/master/bip-0032.mediawi...

Interesting, I hadn't thought of using the techniques of deterministic cryptocurrency wallets to solve this problem. I need to read more about exactly how they work.

It is also easy to solve this simply using ECC and ECDH. I just wrote a scheme on the board in the office. It might have slightly larger data payload than the deterministic wallets approach.

Warning: this is baseless speculation from someone with only a semester of cryptography experience.

If you asked me to implement "randomized public keys" I would generate a master key pair (MPUB and MPRIV). Then, I would combine MPRIV and a random value N in a one-way function to make a new key K. I would use K as effectively a "random public key" and use it as if it was MPUB (the one-way function would have to output a K that is in the same format / usable like MPUB). I would distribute N along with K, as N is useless without MPRIV.

I have no idea if that is how they did it but that's what comes to mind.

Warning, no academic crypto experience but I've used it in production systems. Oh the horror.

Couldn't "random value N" just be a nonce that only Apple knows?

Just speculating but would something like random_key=hash(static_key + datetime) work? static_key is pre-shared between cloud and device and datetime is also known by both device and cloud if rounded down to some accuracy.

The article gives the example of El Gamal encryption [1]. Looking at the key generation section, it seems like you could keep a single (q, x) pair and create a new (G, g, h) for the same x.