# Secure ElGamal with OAEP

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.

• Any reason not just to use Cramer-Shoup? That's a CCA2 extension of ElGamal and doesn't even require random oracles. – Bristol Apr 14 '15 at 12:38
• @Bristol This isn't a practical question at all. In practice I'd use DHIES or ECIES, but thanks for the reference. – SEJPM Apr 14 '15 at 18:55
• OAEP is interesting in case the homomorphic properties of ElGamal are required. – 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.

• 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. – K.G. Jul 25 '15 at 11:08
• 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. – K.G. Jul 25 '15 at 11:25
• @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). – Bristol Jul 27 '15 at 8:07