Modified ECIES using EC point ADD with DH key

Question

I have questions about ECIES.

ECIES

Vanillia ECIES

Encryption side (Alice's side)

In "vanilla" ECIES when Alice wants to send Bob an encrypted message:

1. Alice uses some Elliptic Curve, e.g. secp256k1, knowing its order G and field P (mod).
2. Alice does not know Bob's private key b, but his public key B (= b*G)
3. Alice generates an ephemeral key pair r and R (=r*G)
4. Alice uses ephemeral private key r and Bobs public key to produce a secret: S = B * r.
5. Alices uses S as input to KDF to create symmetric (en-/de-)cryption key and MAC key used in subsequent steps.
6. [Rest of ECIES steps omitted]
7. Alice sends R alongside encrypted ciphertext and a MAC over potentially unsafe communication channel (of course, r is never sent anywhere).

Decryption side (Bob's side)

1. Receiving R, Bob is able to compute S = Rb.
2. Using S Bob is able to calculate same symmetric (de-/en-)cryption key as Alice
3. [Rest of ECIES steps omitted]

Observation

Vanilla ECIES is essentially Diffie-Hellman between Bob's key pair (b,B) and ephemeral key pair R.

⚠️ Disadvantage

This has one disadvantage. Alice cannot decrypt her messages sent to Bob if she does not keep the r around. Or in other words, if r is not kept around, Alice is unable to calculated S = B * r. This is kind of awkward that the sender cannot decrypt her own messages if she does not keep a list of outgoing rs.

✅ Nested ECIES

A solution to the problem of Alice being unable to decrypt is using application layer constructs to make it possible for the sender - and potentially other third parties - to decrypt the messages. It relies on nested ECIES and an additional application layer ephemeral shared key.

Encryption

1. Alice creates an application layer shared ephemeral key pair K (= k*G).
2. Alices creates a list of public keys for readers of the encrypted message that should be able to decrypt it, typically she includes her own public key and Bobs and potentially Franks F => readers = [A, B, F]
3. Alice encrypts k (application layer shared ephemeral private key) with each reader public key: protectors = [A, B, F].forEach(readerPubKey => ECIES.encrypt(data: k, with: readerPubKey) )
4. Alice encrypt her message m using K(application layer shared ephemeral public key): ECIES.encrypt(data: m, with: K)
5. Alice sends to Bob (and optionally Frank) the encrypted message from the last step, as well the list of encrypted messages called protectors.

Decryption

Any reader, be it Bob, Alice or even Frank, can then iterate through the list of protectors and try to decrypt it with hers/his private key, which will fail for two of the items in the list, but succeed for one item in the list, now she/he has obtained k, and using k she/he can decrypt the encrypted message.

Advantages

The advantage of the solution above is that it uses vanilla ECIES "under the hood" and it supports an arbitrary amount of readers being able to decrypt the message, which is cool and powerful!

Disadvantages

Btw, I don't know if this solution has any name? It is just something older colleagues of mine (who have left the company) had done before me. Anyway, the disadvantage with this is that it is quite complex and results in a much larger payload being sent over the wire. Sometimes this increased size can be ok, but for my business, it is really a strong wish to keep down the size of the payload. Made even worse, as we add more and more readers to the list, the size of the payload increases linearly.

💡 Cyon ECIES

This weekend I came up with my own modified ECIES variant that enables for sender Alice and potentially third parties to decrypt the message as well, while not requiring any application-layer constructs such as the protectors above, nor does it include the extra ephemeral key pair K = k*G.

Even though I came up with this solution myself, I recognize that the solution is quite simple and thus someone must have come up with this solution before me? If that is the case please point me to some references, and I can rename this algorithm that I so presumptuously named after me.

Encryption side (Alice's side)

1. Alice performs Diffie-Hellman with hers and recipient Bob's (and potentially other parties (multiparty DH)) keys, resulting DH = aB (= bA)
2. Alice generates an ephemeral key pair r and R (=r*G)
3. Alice uses ephemeral public key R and DH in EC point addition to produce secret: S = R + DH.
4. Alices uses S as input to create a symmetric (en-/de-)cryption key and MAC key used in subsequent steps.
5. [Rest of ECIES steps omitted]
6. Alice sends R alongside encrypted ciphertext and a MAC. r and DH is kept secret to Bob, over a potentially unsafe communication channel.

Decryption side (Bob's side)

1. Receiving R and knowing Alice's public key A, Bob is able to compute DH = bA and then S = DH + R.
2. Using S Bob is able to calculate the same symmetric (de-/en-)cryption key as Alice
3. [Rest of ECIES steps omitted]

☣️ Disadvantages

I just came up with this, so if you can't point me to a reference where this has been documented as safe, the safety of this is not known. I believe it to be safe. Why? Well, we still only share R over the wire, that is unchanged. Sensitive S is still just an internal state of ECIES used as input KDF.

Note: the sender keeps 𝑟 and 𝐷𝐻 secret and is never sent anywhere. (thx for the suggestion of clarification @sejpm)

Advantages

The sender can decrypt her own messages, and by using multiparty DH we can add third party readers as well. The size of the payload is as large as in vanilla ECIES, since no extra application data such as protectors above needs to be sent over the wire.

The solution is pretty simple and relies on EC primitive point addition which most EC libraries expose as an API (they really should!).

Questions

• Q1: Is there a name for (what I so presumptuously) called Cyon ECIES?
• Q2: Is Cyon ECIES safe? What is your cryptoanalysis of it?
• Q3: Taking a step back - are there any other good alternatives to ECIES using Elliptic Keys?

Answer 1

Is there a name for (what I so presumptuously) called Cyon ECIES?

No. Though it comes close to how crypto_box works: Using static Diffie-Hellman with extra randomness.

Is Cyon ECIES safe?

Yes, it should offer about the same security as any other static Diffie-Hellman based encryption scheme with extra randomness.

Taking a step back - are there any other good alternatives to ECIES using Elliptic Keys?

It seems what you're looking for is indeed static Diffie-Hellman. Now the standard way to convert that into an ECIES-like encryption scheme is to run the DH computation as in Cyon ECIES and then simply pick a random string $r$ which then gets fed as an additional input ("salt") into the key-derivation step. Then $r$ is added to the ciphertext, similar to $R$ but bypassing the extra scalar multiplication.

_{Note: I assume here that the sender keeps $r$ and $DH$ secret and they don't magically show up at the receiver's end.}