7
$\begingroup$

Whenever I look at online voting schemes, the idea of homomorphic encryption being a key concept, specially in the form of homomorphic tallying, appears to be universally accepted. The accepted answer for this question, for instance, suggests that it is one of the two most important technical approaches to online voting (the other one being mixnets).

The general approach for homomorphic tallying that I have found so far (supported on different additively homomorphic encryption schemes) is to define the tally as a single number, assigning some bits to the part of the tally corresponding to each voter. For instance, assuming that we have 4 voters and 3 candidates, the tally can be represented by the bit string ABCDEF, such that the candidate 1 has AB votes, the candidate 2 CD votes and the candidate 3 EF votes. In the general case, getting the values for each candidate given the integer representing the tally should be a trivial set of bit operations.

The problem is that it doesn't seem to scale: if I had 50 candidates and 256 voters, I'd need a tally of size 8*50=400 bits. It is my understanding that homomorphic schemes and big integers are not a very efficient combination. However, I cannot find a scenario that addresses this problem and shows that it is feasible in a country wide scenario (where voters can be hundreds of thousands, or even millions, and candidates can get up to a few hundreds), or, quite the opposite, clearly states the practical limits of homomorphic tallying.

Am I missing something? Is homomorphic tallying as restricted as it seems? If so, why is it regarded so highly as a building block for online voting?

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
4
$\begingroup$

I am not sure why you think that "homomorphic schemes and big integers are not a very efficient combination". In most homomorphic public-key cryptosystem, the message space is very large. For example, the Paillier cryptosystem (probably one of the most used for secure voting) has a plaintext space size of $2^{2048}$ with current security parameters. This allows for elections with a million voters and a hundred candidates. Moreover, the plaintext space of Paillier can be increased if necessary (interestingly, it can even be increased "on-the-fly" if the plaintext space size seems too short, without having to ask the voters to re-vote). With $4096$ bits, you can support twice more candidates, or a billion of voters.

Improve this answer
$\endgroup$
2
  • $\begingroup$ But is it efficient? Is there a scheme for which I could homomorphically add 100k encryptions of 2048-bit numbers within an hour or two of very efficient computation? $\endgroup$
    – Sergio A. Figueroa
    Apr 6, 2016 at 8:26
  • $\begingroup$ Well, I've never implemented it, only used it a lot in theoretical works, but although it involves some expensive operations (exponentiations with large integers), it seems to me that it's still reasonable for voting applications. In particular, homomorphic addition is just multiplication of ciphertexts; This paper indicates around 50 000 clock cycles for optimized 2048 bit multiplication, and modern CPU can do billions of clock cycles / second. $\endgroup$
    – Geoffroy Couteau
    Apr 6, 2016 at 8:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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