[SlowRobotAhead]

>can use a single [private] key regardless of which randomized version of her public key was used to encrypt.

I have not seen this before. Trying to wrap my brain around how this works. In terms of ECC I thought public and private were a single pair. Can anyone explain what is going on with public key randomization?

[Scaevolus]

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...

[snarf21]

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.

[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?

[Too]

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.

[xvector]

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.