Score:5

Crypto

Encrypting a symmetric key which requires 2 keys to decrypt?

Bakudo81

3/27/24, 12:49 AM

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.

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?
Or some other way or protocol which suits this purpose?

1886

1 + 4

Eugene Styer

3/27/24, 1:47 AM

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.

fgrieu

3/27/24, 4:25 AM

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](https://pkcs1.grieu.fr/#%5B%7B%22num%22%3A44%2C%22gen%22%3A0%7D%2C%7B%22name%22%3A%22XYZ%22%7D%2C118%2C640%2Cnull%5D)) 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](https://crypto.stackexchange.com/a/105841/555).

poncho

3/27/24, 6:25 AM

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

ilkkachu

3/27/24, 1:52 PM

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

Score:5

Crypto

knaccc

3/27/24, 1:54 AM

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

+ 1

Sam Jaques

3/27/24, 11:50 AM

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.

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: Encrypting a symmetric key which requires 2 keys to decrypt?

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.