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