Is it possible to make ElGamal IND-CCA2 using OAEP or OAEP+?
(OAEP+ from: "OAEP Reconsiderd" by Shoup)

The reason I ask is that I recently answered this question and it came to my mind that OAEP or OAEP+ might be possible solutions.

Note this isn't a practical question at all. There's no intention in implementation, I'm just asking if it would be secure if I would implement it.

  • $\begingroup$ Any reason not just to use Cramer-Shoup? That's a CCA2 extension of ElGamal and doesn't even require random oracles. $\endgroup$ – user2552 Apr 14 '15 at 12:38
  • $\begingroup$ @Bristol This isn't a practical question at all. In practice I'd use DHIES or ECIES, but thanks for the reference. $\endgroup$ – SEJPM Apr 14 '15 at 18:55
  • $\begingroup$ OAEP is interesting in case the homomorphic properties of ElGamal are required. $\endgroup$ – Maarten Bodewes May 27 '17 at 16:45

After some thought, I think the answer is in fact NO, even for IND-1-CCA* and even for Shoup's OAEP+.

RSA-OAEP/OAEP+ work by taking a message $m$, producing a padding $p(m,r)$ and then encrypting this, so $c = f(p(m,r))$ where $f$ is RSA encryption, and $f(u) = u^e \pmod{N}$ is deterministic. In fact, the whole point of OAEP(+) is to inject some entropy into ciphertexts which is required for IND-CPA and higher security.

ElGamal encryption is already randomised. If we try ElGamal-OAEP(+) we get $c = (g^r, y^r \cdot p(m, r'))$ where $y$ is the public key. Since ElGamal is homomorphic, this is obviously not even CCA1: consider an adversary who picks $m_0, m_1$, asks for a challenge ciphertext $c = (u, v)$ and then sets $c' = (u \cdot g^s, v \cdot y^s)$ for randomly chosen $s$. This is still a valid OAEP(+) ciphertext whatever the padding $p$ is (since we're only changing the "outer" randomness $r \mapsto r + s$) so the IND-1-CCA game will happily decrypt this and return $m_0$ or $m_1$ as desired.

This is assuming of course that you can map your padding function's range into the group over which you're doing ElGamal --- for ECC, this should be fine, for $\mathbb Z^\times_p$ groups it's harder. As an alternative one could consider hashed ElGamal-OAEP+ with $c = (g^r, H(y^r) \oplus p(m, r'))$ where $H$ is independent of the hash functions used in the OAEP+ padding $p$. My intuition is that this is still not CCA1, even though it doesn't have the homomorphic property anymore. Certainly if $H$ has some homomorphic properties itself then one should be able to do something like the above counterexample.

IND-1-CCA: Is standard IND-CCA2 where you only get 1 decryption query after seeing the challenge ciphertext instead of polynomially many.

| improve this answer | |
  • 1
    $\begingroup$ Your argument is fine, but only for CCA2 security. (For CCA1, you don't have a decryption oracle after you get the challenge ciphertext.) Also, there are no good CCA1 attacks against ElGamal on its own, and the padding doesn't change that. $\endgroup$ – K.G. Jul 25 '15 at 11:08
  • $\begingroup$ I've briefly considered the hashed ElGamal case, and I can't immediately see a security proof. For certain groups, there are CCA2 attacks, but for other groups, I can't find good attacks. $\endgroup$ – K.G. Jul 25 '15 at 11:25
  • 1
    $\begingroup$ @K.G. : you're right, I confused IND-CCA1 and IND-1-CCA (where you get only a single decryption query, but it may be after you've seen the challenge ciphertext). $\endgroup$ – user2552 Jul 27 '15 at 8:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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