5
$\begingroup$

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.

$\endgroup$
3
  • $\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, 2015 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, 2015 at 18:55
  • $\begingroup$ OAEP is interesting in case the homomorphic properties of ElGamal are required. $\endgroup$
    – Maarten Bodewes
    May 27, 2017 at 16:45

1 Answer 1

5
$\begingroup$

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.

$\endgroup$
3
  • 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, 2015 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, 2015 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, 2015 at 8:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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