Encrypting a symmetric key which requires 2 keys to decrypt?

Question

Let's say a device has 2 private keys and service has the 2 corresponding public keys. Is there an efficient way to encrypt a symmetric key from the service side utilizing the 2 public keys, such that on the client, it requires both private keys in order to decrypt?

I.e if I only have private key 1, I am unable to decrypt the encrypted symmetric key.

I believe one way could be double encrypting it? I.e take the symmetric key and encrypt it using pub key A, and then take the output and encrypt using pub key B. On the client, the reverse operations are done, but this could be expensive.

1. Is there some way to derive a key using the 2 pub keys on the service and encrypt using that, such that client can run the same derivation on their side using both private keys during decryption?

2. Or some other way or protocol which suits this purpose?

Answer 1

With elliptic-curve cryptography, a private key $a$ has the corresponding public key $A = aG$, where $G$ is a well-known generator point on the curve and $aG$ means elliptic-curve scalar multiplication of the point $G$ with the scalar $a$.

If you have two (private, public) key pairs $(a, A=a G)$ and $(b, B=b G)$, then the private key $(a+b)$ corresponds to the public key $(A+B)$.

If you're only encrypting a symmetric key, then you can use a Diffie-Hellman exchange as follows:

The device knows private keys $a,b$ and wants to learn the private key $c$ corresponding to the public key $C$.

The service knows $c$, and generates an ephemeral key pair $(e, E=e G)$.

The service sends $x = \operatorname{HKDF}(e (A+B)) \oplus c$ to the device, where $\oplus $ is the XOR operation.

The device recovers the key as $c=\operatorname{HKDF}((a+b) E) \oplus x$.

The device verifies that $cG\overset{?}{=} C$.

This works because $e (A+B)=ea G+eb G=a E+b E=(a+b) E$.