Implement Condorcet method

[remixtj]

A nice idea on the platform can be implementing the Condorcet Method for the result of the election. In this case the platform will be very interesting for some communities that are using this kind of methods.

Ref: http://en.wikipedia.org/wiki/Condorcet_method

[coorasse]

I agree. Integrating Schulze Method would be great!

[benadida]

This would be cool, but it's not doable with the existing verifiability of Helios, unfortunately.

[rhertzog]

@benadida Can you expand on what's the problem?

I'm looking into trustable vote software implementing condorcet. If you know alternatives, let me know.

[rhertzog]

If the issue is representing ballot as integers, here's a solution: https://blog.agoravoting.org/index.php/2014/07/20/integer-encoding-of-multiple-choice-ballots/

Feel free to reopen if that was the problematic issue :-)

[benadida]

No, that blog post doesn't solve the core of the problem.

It's hard to expand on this in a github issue, since it's a whole topic of research :) But I'll try.

Roughly: to tally Condorcet or similar style ballots, there are two approaches: tricky homomorphic schemes (see work by Teague and others, https://www.usenix.org/legacy/event/evt08/tech/full_papers/teague/teague_html/NaishTeague2_0.html), which are quite complex to implement and require a lot more computation. I don't have any plans to implement these, given the complexity.

The other approach is to use mixnets, which allow for free-form ballots that you can tally any way you want, only with identity removed. The tricky part with mixnets, beyond their implementation which is relatively complex in practice, is that if the ballots encode a lot of information (which ranked ballots often do), there is usually a coercion problem, sometimes called the Italian attack (see https://books.google.com/books?id=loQpPWGGezEC&pg=PA144&lpg=PA144&dq=italian+attack+voting&source=bl&ots=mQHHVuN88B&sig=P4Nr2eZlfW4VPQGOon0bDGwKG2c&hl=en&sa=X&ei=vRPhVJTnFoqyogTi7IGgCQ&ved=0CB4Q6AEwAA#v=onepage&q=italian%20attack%20voting&f=false).

In other words, there is a lot of complexity and risk to either approach, and so I've chosen so far to steer clear of ranked voting, especially since I'm not convinced most voters understand how to express their choices efficiently in ranked voting: http://www.electology.org/#!approval-voting-versus-irv/c1mmu

Hope this helps!

[RunasSudo]

@benadida, Doesn't this method allow for the tallying of Condorcet elections with no changes to Helios's architecture?

Single-winner Ranked Pairs and Schulze rely only on the total number of votes that prefer A over B, B over C, etc. (See, for example, page 11 of the linked PDF, which specifies that the input of the Schulze method is ‘the number of voters who strictly prefer’ one alternative to another.)

The Usenix page you linked to doesn't talk about Condorcet methods, but about STV (a multi-winner system which does require more information than Helios's current architecture can easily provide), so I don't think it's relevant to this particular discussion.

[benadida]

@RunasSudo interesting, I see how this might be possible, though there are possible problems already mentioned in that post (circular ballots), and how do you prove that they're not circular? Could be promising, but not a small amount of work.

[mukeshtiwari]

@benadida I am the lead author of homomorphic Schulze method [1, 2]. The idea is that a voter, at the front end, would encode her choices in form encrypted binary matrix, e.g., if her vote is A > B > C, then the ballot will be: A | B | C A | E(0), E(1), E(1) B | E(-1), E(0), E(1) C | E(-1), E(-1), E(0)

Now, the problem is she can encode all kind values in her ballot, so we need some mechanism to distinguish valid ballots and invalid ballots in a verifiable way. Our solution, that we presented in our paper [1] and very much inspired by [3], is that we commit to a permutation and use this permutation to shuffle each row of the original ballot to get a new row-shuffled ballot, and zero-knowledge-proof for the shuffle verifiability. In the next step, we shuffle every column of row-shuffled ballot to get a column-row-shuffled ballot, and zero-knowledge-proof for the shuffle verifiability. Finally, we decrypt the column-row-shuffled ballot, with honest decryption zero-knowledge-proof. You can see that if a ballot is valid, i.e., contains only -1, 0, and 1 and contains no cycle, then it will still be valid after going through the transform, I described above. The downside is if a user ranks every candidate same, or prefers one candidate and ranks every other candidate same, then it will leak her ballot [4].

Btw, you are right, it was not a small amount of work, specially it involved the formalisation in Coq :)

[1] https://ntnuopen.ntnu.no/ntnu-xmlui/bitstream/handle/11250/2726543/homomorphic-schulze.pdf?sequence=2 [2] https://github.com/mukeshtiwari/EncryptionSchulze/blob/master/code/Workingcode/EncryptionSchulze.v [3] https://eprint.iacr.org/2011/168.pdf [4] https://eprint.iacr.org/2021/491.pdf

[BenSmyth]

I am the lead author of homomorphic Schulze method [1, 2]. The idea is that a voter, at the front end, would encode her choices in form encrypted binary matrix

You might like to take a look at: https://bensmyth.com/files/Smyth17-FPTP-for-ranked-voting.pdf, where I consider using first-past-the-post voting systems for ranked voting.