# Encrypt using ECDH with two different EC public keys, minimizing payload size

Let's say Alice has the private EC keys $a$ and $b$, with a base point of prime order $G$. Alice computes the corresponding public keys $A = aG$ and $B = bG$, and sends them to Bob.

Bob now wants to encrypt asymmetrically a message $m$, so that only Alice can decrypt it. Furthermore, Bob wants the encryption to be "maximally" protected by both secrets ($a$ and $b$). He will use ECDHE to derive one or more shared secrets, and encrypt the message with AES, XOR, or some such.

The thing is, we want the payload (ciphertext and metadata) to be as small as possible.

Ideas:

1. Bob could create two different ephemeral private keys ($e_1$ and $e_2$), derive two different shared secrets ($s_1 = e_1A$ and $s_2 = e_2B$), and cascade encrypt the message with these two secrets: $x = Enc_{s_1}(Enc_{s_2}(m))$.
2. Derive $s_1$ and $s_2$ in the same way as in (1), but instead of using cascade encryption, generate a single secret, for example by doing $s = s_1 \oplus s_2$. Then $x = Enc_s(m)$.
3. Do the same thing as in (2), but re-using the ephemeral private key, ie. $e_1 = e_2$.
4. Do just a regular ECDHE to compute a single shared secret using the public key $C = A + B = aG + bG = (a + b)G$. To recover the shared secret, Alice will have to use the private key $c = a + b$.

Observations:

We want to minimize the ciphertext payload and thus, the metadata. In both (1) and (2), two ephemeral public keys have to be transmitted to Alice in order for her to decrypt the ciphertext. In both (3) and (4) only one ephemeral keypair is used, so they are preferred from the point of view of message compactness.

Questions:

• Is (2) at least as secure as (1)?
• Would it be better to use a KDF for combining the shared secrets in (2)?
• Is it safe in (3) to re-use the ephemeral key?
• Is it secure to use the construction in (4)?
• What are the trade-offs between (2) and (4)?

Thanks!

• (4) works, but is really not any more secure than using a single public key – poncho May 24 '18 at 19:20
• Given the scenario where both private keys ($a$ and $b$) are never in the same place until decryption, would it be safe to say that before decryption getting hold of the decryption key $c = a + b$ is as difficult as getting hold of both $a$ and $b$? Alternatively, is there any information leakage about $b$ if an attacker gets hold of $a$ and the ciphertext $x = Enc_s(m)$? – esneider May 25 '18 at 0:21
• No; in (4), the public key is effectively $(a+b)G$, and the private key is $a+b$; unless you are concerned with state recover attacks (where the attacker learns some of the private state), this is just standard ECDH – poncho May 25 '18 at 3:28
• Using $[a\cdot b]G$ and $a\cdot b$ instead of $[a + b]G$ and $a + b$ lets you use an $x$-restricted DH ladder like X25519, with some caveats about possible implementation limitations on the structure of the scalars. – Squeamish Ossifrage Mar 8 at 6:00