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.

Elgamal is a cryptosystem that is homomorphic over multiplication.

  1. How can I convert it to an additive homomorphic cryptosystem?
  2. How can I use this additive homomorphic Elgamal cryptosystem for E-voting purpose?

Please explain with examples.

share|improve this question
add comment

1 Answer 1

up vote 5 down vote accepted

Elgamal can be made additive by encrypting $g^m$ instead of $m$ with traditional Elgamal for some generator $g$ (usually the same one used to generate the public key). This variant is sometimes called exponential Elgamal. The difficulty is decryption: running the standard decryption gives you $g^m$ and recovering $m$ requires you to solve the discrete log. As long as $m$ is small, this can be done algorithmically or with a lookup table.

See this answer for how to build a voting scheme from it (or this paper for the full description). Exponential Elgamal is great for things like voting because after you tally up all the votes, you'll still have a number that is reasonably small.

Paillier is additively homomorphic as well, and can support a proper decryption of any sized message. Dispite this, many voting schemes still use exponential Elgamal because it is faster, easier to do distributed key generation, and not patented.

share|improve this answer
    
I'm curious on your remark that exponential Elgamal is faster. Do you know of any published benchmarks or results of tests that I can get numbers from? Also, do you know how traditional Elgamal compares to the elliptic curve variant when it comes to speed? –  mikeazo Oct 4 '12 at 13:53
    
I don't know of any publications that directly compare Paillier with Elgamal in Gq or with ECC; although I haven't look too hard either. It is just accepted as folk wisdom I guess. –  PulpSpy Oct 16 '12 at 19:55
    
Can i use elgamal for both additions and multiplication of ciphertexts?I.e: Whenever i want to multiply i compute my message $x$ as $g^x$ and whenever i want to add i compute conventional Elgamal. My plaintext would be small integers in a range of $0 \ldots 2^{32} or 2^{64}$ –  curious Mar 22 '13 at 11:22
1  
Reading between the lines of what you are asking, the answer is no. Elgamal can handle both multiplication and addition, but you cannot mix the two operations on any given ciphertexts. You must decide when you encrypt to lock the ciphertext into only doing addition or only doing multiplication. The ability to do both is a "fully homomorphic" cryptosystem, of which there are some, but they are mainly theoretical and too slow to be practical. One efficient scheme, BGN, allows a single multiplication and as many additions as you want. –  PulpSpy Mar 25 '13 at 13:11
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.