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.

I'm performing ElGamal encryption algorithm and using the additive homomorphic property so the product of two ciphertexts is the encryption of the sum of the plaintexts.

The problem is that I need to return the original plaintext sum values. How could I get them using decryption? Is there an algorithm I can follow, given that I have both the private and public keys?

I have tried to decrypt it, but it returns the value $((g^{x+y}) \bmod P)$ where $p$ is prime, $g$ is a generator, and $x$ and $y$ are the plaintext which I need to know.

$x+y$ is usually a very large number.

share|improve this question
add comment

2 Answers

unfortunately $x+y$ is usually a very large number so i was just asking if there is any modification that i can do on the decryption so i can get the value without using the discrete logarithm

In general no, but if you know some additional information about $x+y$ it is possible (depending on how good the information is). For example, say $x$ and $y$ come from some process and I know the mean value for $x$ and the mean value for $y$, then I also know the mean value for $x+y$ and can use that to decrypt (compute $g^t$ in the group for values $t$ around the mean of the sum and compare with $g^{x+y}$).

Another example would be in electronic voting. If there are a large number of voters, the value you are trying to decrypt could be very large, but you probably know (approximately) how many people voted and you know polling data which would tell you approximately the percent of people who were going to vote for candidate $C$, so to decrypt candidate $C$'s vote tally, multiply the percent by the approximate number of voters and you have a decent guess as to the number of people who voted for $C$. Use that information to start computing around the guess as before.

share|improve this answer
add comment

Normal El Gamal is multiplicatively homomorphic: $E(x) E(y) = E(xy)$.

If you want to make it additively homomorphic, you fix some generator $g$; then you transform the integer $x$ to the group element $g^x$ before encrypting with El Gamal. With this transformation, $E(g^x) E(g^y) = E(g^x g^y) = E(g^{x+y})$, so now you have an additive homomorphic property.

To decrypt, you need to be able to take the discrete logarithm. This can be done efficiently if the value $x+y$ is known to be "not too large".

For a bit more of an overview of this approach to making El Gamal additively homomorphic, see the following question: Can Elgamal be made additively homomorphic and how could it be used for E-voting?. Then, check out Why is the discrete log problem easy when the exponent comes from a binomial distribution? for details of specifically how to do the decryption, and how small the messages need to be to ensure you can decrypt in a reasonable amount of time. In the future I encourage you to use the search function to check whether the question has been asked before.

If $x+y$ is usually so large that the above methods don't work, then you'll need a different cryptosystem; simple El Gamal isn't gonna work for you. The Paillier cryptosystem might be a good choice.

share|improve this answer
    
Thank you so much for your answer but unfortunately (X+Y) usually in a very large number so i was just asking if there is any modification that i can do on the decryption so i can get the value without using the discrete logarithm –  user2511133 Jul 3 '13 at 9:27
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.