3
$\begingroup$

I'd need a crypto system allowing online yes/no votes but without revealing who voted what. Is a "partial" homomorphic crypto system what I'm after? Would, for example, Damgård-Jurik work in my case?

In my scheme there would be a server getting the votes and the server shouldn't see who voted what. However we can consider that the server shall not cheat: he won't modify the voting results. But the votes should still be anonymous.

If I need homomorphism, how does it work? Does each voter need to get the encryption from the previous voter? Or can the centralized server receive all the encrypted votes and then "mix" them himself and, once mixed, get the result?

How does it work it there are say, four voters: does the scheme break if only three people vote?

For example I played with the nice simulator here, which expects 8 voters. You can't put seven voters on that page: is this just an implementation detail of that site or is Damgård-Jurik expecting all the votes from a number of voters known beforehand?

Also the page shows who voted what, but it's not clear to me if it's for instructional purposes or if, when the vote counts happens, the votes aren't anonymous anymore.

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ Are you aware that there is tons of work on secure voting schemes? Probably hundreds of papers. Have you done a search on this site and a literature search in the literature? Are you familiar with E2E (end-to-end) cryptographic voting systems? For instance, Helios and VoteBox? That would be a good starting point for you. $\endgroup$
    – D.W.
    Commented Feb 21, 2014 at 1:52
  • $\begingroup$ @D.W.: I wasn't aware of Helios and VoteBox (thanks a lot for the pointers), nor that there were hundreds of paper (if there are hundreds, that's even more reason to ask a question here: I'd need to know where to look). I've heard about homomorphic encryption because it's something programmers start to talk about but that's about it. Basically I know what my needs are but I don't know which scheme I need to choose from... $\endgroup$
    – bitcoinNeverSleeps
    Commented Feb 21, 2014 at 5:01

1 Answer 1

Reset to default
2
$\begingroup$

A homomorphic cryptosystem has some operation $*$ on ciphertexts that correspond to some other operation $\circ$ on plaintexts, that is $$\mathcal{D}(c_1 * c_2) = \mathcal{D}(c_1) \circ \mathcal{D}(c_2).$$ Typically, the ciphertexts you get by applying $*$ look like ciphertexts that are produced by the encryption algorithm. For Damgård-Jurik, $*$ is multiplication modulo $n^{s+1}$ and $\circ$ is addition modulo $n^s$.

A cryptosystem is secure if the ciphertext does not help you to say anything about the message encrypted.

Suppose you encode "yes" as $1$ and "no" as $0$. The voter will encrypt his encoded vote and send it to the server. Suppose the server receives ciphertexts $c_1, c_2, \dots, c_L$ that are all encryptions of $0$ or $1$. The server can now multiply the ciphertexts to get a single ciphertext, which by the above requirement will satisfy $$\mathcal{D}\left(\prod_i c_i\right) \equiv \sum_i \mathcal{D}(c_i) = \text{number of "yes" votes.}$$ The server can therefore find the correct election result by decrypting the product ciphertext.

It does not really matter how many ciphertexts are submitted.

If the server is passive (honest-but-curious, will try to break confidentiality without deviating from instructions), the voters are honest and the cryptosystem is secure, the server cannot deduce anything about the votes from the ciphertexts (except the result, of course, since he decrypted a ciphertext containing the result). Damgård-Jurik is generally believed to be secure.

The interesting question is of course what happens when the voters aren't honest or the server tries to cheat. There's a lot of nice cryptography in the answers to those questions.

Improve this answer
$\endgroup$
6
  • $\begingroup$ Thanks a lot for your answer, things are a bit clearer now. Regarding cheating and leaving aside the issue of server-side cheating, doesn't Damgard-Jurik use ZKP to verify that each participant voted once and only once? $\endgroup$
    – bitcoinNeverSleeps
    Commented Feb 19, 2014 at 14:46
  • $\begingroup$ also, in case the server is curious, couldn't the server simply not multiply the ciphertexts and instead take each ciphertext individually and count the number of "yes" vote (hence getting 0 or 1, and knowing what each participant voted?) Or does the server need to multiply at least two ciphertexts before being able to decrypt the product ciphertext? (and if so, couldn't the server simply sneakily multiply with a fake vote of its own, just to be able to decipher?) $\endgroup$
    – bitcoinNeverSleeps
    Commented Feb 19, 2014 at 14:49
  • $\begingroup$ I don't know about the particular case of the Damgård-Jurik e-voting system, but ZKP are generally used in this context not only to make the voter prove that he voted only once, but also to prove that his vote is valid (for example, he only voted "0" or "1"). $\endgroup$
    – LRM
    Commented Feb 20, 2014 at 10:39
  • $\begingroup$ As for whether the server can simply decrypt each ciphertext individually instead of decrypting the ciphertext containing the overall result of the election, yes, in principle this can happen. But in order to avoid this, e-voting systems usually use what is known as threshold cryptography: the decryption key is shared among a set of trustees, in such a way that only when a certain subset (threshold) of them collaborate, they can decrypt anything. $\endgroup$
    – LRM
    Commented Feb 20, 2014 at 10:43
  • 2
    $\begingroup$ You would not use zero knowledge proofs to prevent voters from voting more than once. You would instead record the voter identities along with the ciphertext they submit, which would allow you to do what you want (reject all ballots, reject all but the first, discard all but the final, etc.). Obviously, you need to authenticate somehow before accepting the ballot. $\endgroup$
    – K.G.
    Commented Feb 20, 2014 at 14:00

Your Answer

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

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