5
$\begingroup$

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?

Improve this question
$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$
    – Eugene Styer
    Mar 27 at 1:47
  • $\begingroup$ 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. $\endgroup$
    – fgrieu ♦
    Mar 27 at 4:25
  • 2
    $\begingroup$ 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... $\endgroup$
    – poncho
    Mar 27 at 6:25
  • $\begingroup$ @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... $\endgroup$
    – ilkkachu
    Mar 27 at 13:52

1 Answer 1

Reset to default
5
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – Sam Jaques
    Mar 27 at 11:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.