Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question
add comment

2 Answers

up vote 3 down vote accepted

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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