[philipkiely]

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.

[ryanmarsh]

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?