5
$\begingroup$
  1. In normal ElGamal encryption, the encrypted message is a pair (gb, gabM) - that is, the actual "encryption" is simply multiplication by the shared secret gab.

  2. A common pattern with public-key encryption is to encrypt a symmetric key using PK, and then encode the actual message with the symmetric key.

It seems to me that you could simply use the shared secret gab as your symmetric key instead - so your pair would be (gb, AES(M, gab)). (This looks extremely similar to agreeing on an AES key via Diffie-Hellman.) This would take up less space, putting it on even footing with RSA + AES for a given key-/group-size.

So: has anybody heard of a scheme like this? If so, does it have a name, and is it actually used? As for why I'm interested:

Possible advantage: semantic security without DDH?

In normal ElGamal, we lose semantic security if we don't have DDH (given ga, gb and c, we can test whether c = gab). AFAIU, this is because the message is encoded as E = gabM mod p, so you can divide by your suspected message (c = gabM/Mguess), and test whether it matches gab.

It seems to me that if we use gab to provide an AES key instead, then recovering a candidate c is equivalent to recovering an AES key from a plaintext/ciphertext pair. I understand that AES is not susceptible to known-plaintext attacks, so does this mean we have semantic security even without DDH?

Possible advantage: easier generation of private keys?

With RSA, it takes a reasonable chunk of computational effort to generate a new public/private key pair (because you have to find a probably prime). With ElGamal, it seems much easier, which means you could rotate your short-term keys much more often, without draining a low-power device.

The more often you rotate your short-term keys, the "better" your forward secrecy is. (After all, if you rotated your keys so often that each one was only ever used once, then you're basically doing Diffie-Hellman, just re-ordered a bit.)

$\endgroup$
3
  • $\begingroup$ You may look at ECIES. $\endgroup$
    – DrLecter
    Jun 27, 2014 at 23:07
  • $\begingroup$ Perfect! ECIES/DLIES was pretty much exactly what I was thinking of. Could you give that as an answer so I can accept it? $\endgroup$
    – cloudfeet
    Jun 27, 2014 at 23:34
  • $\begingroup$ Good to hear that :) $\endgroup$
    – DrLecter
    Jun 27, 2014 at 23:56

1 Answer 1

4
$\begingroup$

What you are envisioning has basically been standardized as the integrated encryption scheme being a hybrid encryption scheme providing message authenticity (IND-CCA security).

$\endgroup$

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.