# Encrypting a symmetric key which requires 2 keys to decrypt?

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?

• What is your end goal? Maybe if we knew why you wanted two public/private keys we could come up with a different solution that accomplishes the goal. Mar 27 at 1:47
• I confirm double encryption works in principle for every asymmetric encryption scheme. There's a practical detail though: many asymmetric encryption schemes (e.g. RSASSA-OAEP) have a size limit on the plaintext they can encipher, thus it may be necessary to split the first ciphertext into several plaintexts, or adapt the second encryption. There are other methods for specific asymetric encryption, as in this answer.
– fgrieu
Mar 27 at 4:25
• A slightly cleaner approach than double encryption is to do simple (2,2) secret sharing: to encrypt a message $M$, select a random bitpattern $R$ of the same size, and encrypt (with the first public key) $M \oplus R$, and encrypt (with the second public key) $R$. It is easy to see that only one of the private keys yields no information about $M$, and you don't have to worry about either algorithm handling a message of a size larger than $M$. It doesn't address your concerns about efficiency, though... Mar 27 at 6:25
• @poncho, if the public-key encryption is taken as a black box, then we'll anyway need two encryptions using that (one for each key), and the additional step of generating some bits and xor'ing doesn't sound that inefficient... Mar 27 at 13:52

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

• An alternative perspective is that this is a normal elliptic curve key encapsulation, but the service has secret-shared its private key to different parts of itself. Mar 27 at 11:50