Malleability of ElGamal and Hashed ElGamal

Question

Question: Suppose A encrypts a number $x$ which indicates her bid on a contract, using ElGamal encryption. Say that the encryption of $x$ produces a ciphertext $c$. Explain how E can modify $c$ to make it an encryption of $100 \cdot x$.

Answer: E is exploiting the malleability of ElGamal. She can take the ciphertext pair $(c_1,c_2)$ Where $c_1$ is $g^y$ and $c_2$ is $m * h^y$ and multiply $c_2$ by $100$ to get the desired results. A can protect herself from this by used a hashed version of ElGamal

Is this correct?

Answer 1

There are different crypto-systems that have been called Hash-Elgamal. The one your exam refers to is likely whatever was included in your course. Without knowing that, we can't necessarily answer your question.

The most common is the Elgamal variant defined with encryption function: $c=\mathsf{Enc}(m,r)=\langle g^r, \mathcal{H}(y^r)\oplus m \rangle$

This is still a malleable encryption function, except that the adversary must xor in the amount they want to change the encrypted message by. So strictly speaking, it may protect against the exact attack of multiplying in constants, but it does not prevent the broader attack of being able to manipulate a message under encryption (without knowing the message).

Hash Elgamal could also refer to the Fujisaki-Okamoto heuristic applied to Elgamal. This prevents malleability but can also lose the CPA-security of Elgamal. Other Elgamal variants that use a hash function are Cramer-Shoup (mentioned by @jalaj) and DHIES. These are both secure against any malleability (they are CCA-secure) however they aren't typically referred to as hash Elgamal.

Answer 2

What you are saying for hashing is actually more commonly known as Cramer-Shoup's crypto-system and yes it is non-malleable. You can read Lecture notes 22 given by Boaz Barak in Fall 2007 for more details.