Elgamal is a cryptosystem that is homomorphic over multiplication.
- How can I convert it to an additive homomorphic cryptosystem?
- How can I use this additive homomorphic Elgamal cryptosystem for E-voting purpose?
Please explain with examples.
$\begingroup$
$\endgroup$
1
-
$\begingroup$ The Coconut paper implements a voting system exploiting the homomorphic capabilities in ElGamal, among other features. $\endgroup$– user73105Dec 24, 2019 at 11:55
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
5
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.
-
$\begingroup$ 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? $\endgroup$– mikeazoOct 4, 2012 at 13:53
-
$\begingroup$ 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. $\endgroup$– PulpSpyOct 16, 2012 at 19:55
-
$\begingroup$ 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}$ $\endgroup$– curiousMar 22, 2013 at 11:22
-
1$\begingroup$ 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. $\endgroup$– PulpSpyMar 25, 2013 at 13:11
-
$\begingroup$ Wait... Is Paillier cryptosystem patented? $\endgroup$– bazzilicJan 19, 2023 at 5:39