3 ms·

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

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

philipkiely 7y ago
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 7y ago
  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?
Scaevolus 7y ago
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.mediawiki#conventions https://github.com/bitcoin/bips/blob/master/bip-0032.mediawi...
- snarf21 7y ago
  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.
xvector 7y ago
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.
Too 7y ago
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.

philipkiely 7y ago

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 7y ago
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?

Scaevolus 7y ago

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.mediawiki#conventions https://github.com/bitcoin/bips/blob/master/bip-0032.mediawi...

snarf21 7y ago
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.

xvector 7y ago

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.

Too 7y ago

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.