8 ms·

How do you provide anonymized ballots while at the same time guaranteeing that fraudulant voting is not taking place? It seems that being able to verify that a

How do you provide anonymized ballots while at the same time guaranteeing that fraudulant voting is not taking place? It seems that being able to verify that a ballot came from an actual person authorized to vote (and not some bot) is key, but I'm not sure how to satisfy both.

mvid 9y ago
Perhaps with asymmetric key encryption? So someone can validate that a vote was theirs, but you can't pin a vote to a person without them doing so. It would require that everyone understood key management, which is probably untenable
- GeneralMayhem 9y ago
  That doesn't guard against the lead pipe decryption strategy. The point is that you need a way to prove that a vote was yours, without any possible way to prove which vote was yours, whether you want to or not. I'm not a cryptography expert, but that sounds difficult if not logically impossible.
  - colordrops 9y ago
    How is lead pipe coercion currently handled?
    - Infernal 9y ago
      There is no way to prove you voted one way or another with anonymous ballots, so there is no incentive to bribing or threatening violence to influence your vote. The desired outcome is to prove that each vote came from a valid voter, while being impossible to prove which vote came from whom.
      - amitbr 9y ago
        There is a cryptographic primitive that does just this allowing of plausible deniability whilst ensuring that only persons able to vote voted: Using Linked Ring Signatures.
      - Mediterraneo10 9y ago
        > There is no way to prove you voted one way or another with anonymous ballots. The coercing party can insist that you take a mobile phone picture of your ballot. This kind of coercion is common in some regions of Russia where civil servants and teachers are told by their superiors that they must vote for the preferred party “or else”, and a mobile phone picture is demanded as proof.
        KMag 9y ago
        The way around this is to give each person 1 ballot for each of N candidates. 1 ballot goes into an envelope and into the vote box. N-1 ballots go into envelopes and into the discard box. It's trivial to show a photo of your ballot for Dr. Evil, but it would take a video of you going into the voting booth, closely following your hands to prevent three-card-monty, and continuing to follow you into the public lobby containing the vote and discard boxes. If you strictly enforce no recording in the public lobby, then there's no way for you to prove to your boss which box got your ballot for Dr. Evil in the end. Edit: Perhaps I wasn't clear. Each of the N ballots is already filled out for a different candidate. The envelopes are all identical and sealed by you inside the voting booth. That way an existence proof of a ballot for the given candidate leaks absolutely no information. There are no empty paper ballots, and none of the paper ballots can leave the polling station. Ballots need to be counted both from the "vote" and from the "discard" boxes. Ballots missing from the discard box prove vote tampering.
        tschwimmer 9y ago
        I suspect the envelope with the good ballot is sealed in some way. All they would have to do in that case is force you to take a picture of the sealed ballot with the non-desired ballots next to it.
        KMag 9y ago
        All of the envelopes are identical. Absolutely the only difference is which envelope goes into which ballot box. Taking a photo of N-1 ballots for non-Dr. Evil next to one sealed envelope only discloses that the Dr. Evil ballot was put into an envelope first. It gives no information as to which box that envelope was placed into later, and therefore leaks no information about how the vote was cast.
      - colordrops 9y ago
        Why is that any different from being anonymous on a blockchain?
        Armisael16 9y ago
        It isn’t unless you have some way to verify your vote. Lots of blockchain ideas offer that, though.
  - meeton 9y ago
    How about this: when you get into the booth you're given an ID. You then cast your vote for Ms A and you can see on the block chain that it was recorded for A. After you cast, the system shows you a bunch of ids on the chain which voted for other candidates and you can memorise the id shown that voted for Mr B. When people come round, you tell them that other id. When they look it up they see that it voted for B and leave you alone. That doesn't solve the potential problem of vote stuffing... Still thinking about that one.
    - snakeboy 9y ago
      However in this setup, anyone can bring a smartphone in and take a picture of the screen when it displays anything that separates your id from a fake one. Sounds like you might be on the right track if you can get over that hurdle somehow.
      - kybernetikos 9y ago
        The smartphone problem exists currently with paper ballots. You're not supposed to be allowed to bring a camera into the voting booth, but this is not enforced particularly well. One approach to this problem is to make it easy to cancel a previous ballot and submit a new one, so you can get your evidence that you voted the way e.g. your employer wanted you to, but then you can cancel it and vote with your conscience.
        rjmunro 9y ago
        As far as I can remember from the instructions last time I voted, in Britain you can do this, just return the ballot to the person handing them out and say that you made a mistake, and they should issue you a replacement.
        feborges 9y ago
        In the Brazilian voting machine this is often done. You type the numbers and it loads the candidate info in the screen. Once you click [Confirm] the screen gets blank with the message of success. Therefore the only way to take a picture is before the vote is actually processed. You have a [Reset] button to re-enter the numbers.
darawk 9y ago
Presumably you'd want a deniable system. So, something where you have a private key 'k', some function 'f', and the public chain 'p'. So, you compute: r = f(k, p) Suppose r may be 1 or 0. The meaning of 1/0 will be randomly distributed among the population, and will be made known to you when you place your vote, but at no other time. So, later on, you understand that a value of 1 means your vote counted for candidate A, but if someone tries to coerce you, you can realistically claim the opposite.
- geofft 9y ago
  How do you know that the people tallying the vote have the same meaning for r? (That is, how do you prevent a butterfly-ballot-style situation where people think they're voting for Gore, accurately cast a ballot that appears to them to be a vote for Gore, and actually end up casting an objectively valid vote for Buchanan?)
  - darawk 9y ago
    Presumably you could generate some proof that the vote was correctly cast at the moment you cast it, and that 1 corresponds to A and 0 corresponds to B. But that proof would not be accessible after you leave the polling booth (because it'd require some ephemeral value that you could retain or throw away).
  - breatheoften 9y ago
    Maybe you could do a block tallying with verification scheme. 1. Enter your vote and receive an identifier 2. Group n identifiers into a batch ensuring not all votes in the batch are for the same candidate. Record the n identifiers into a block then randomly order the identifiers but don’t record the randomized sort order. Display the index of their identifier to each user but don’t record it. Record the actual vote in this (random) order to the block. Allow each voter to see all votes recorded in the block at each location (including the one only they know represents their vote). Allow the voter to manually tally the block to ensure the sum of symbols reflects their vote intent. Present to each voter cryptographic proof of the existence of the block and the net affect the block as a whole has on the vote tally for each candidate. Each voter leaves with: 1. cryptographic proof of having voted 2. Cryptographic verification of the effect their vote had on vote tally 3. Ability to claim having voted for any candidate represented in their voting block/inability to prove to others who they voted for while being sure of how their vote was counted themselves.
deleted 9y ago
[deleted]
offbytwo 9y ago
Would zero knowledge proofs work for this?
jinpan 9y ago
Rivest invented the 3-ballot voting protocol (see https://en.wikipedia.org/wiki/ThreeBallot https://en.wikipedia.org/wiki/ThreeBallot) The trick to the 3-ballot voting protocol is that not everyone can validate their vote. However, when a group of voters band together, they should be able to validate that a subset of their votes (1/3) were registered with high probability. With a sufficiently large group of voters checking results, the law of large numbers comes into play and they can statistically detect the presence of voting fraud.
- googlryas 9y ago
  I like how the example ballot on that wikipedia page has Alex Jones running for president.
  - fareesh 9y ago
    One can dream
- littlestymaar 9y ago
  Zero-knowledge \o/
- notahacker 9y ago
  It's an interesting idea whose utility depends on whether you think turning casting a valid vote for the intended candidate into a logic puzzle is a good thing
deleted 9y ago
[deleted]
ihm 9y ago
One simple way (basically using Zerocoin/ZCash) is the following. Every voter is issued one "vote coin" at registration time. There are special addresses for each candidate. Each voter sends their "vote coin" using a zero-knowledge/private transaction to the candidate of their choice. It's totally auditable, not possible to vote more than once, etc. The main issue is in making it potentially easy to sell your vote, which as the OP was getting at is at the heart of the tension.
- clintonb 9y ago
  Voters can sell their votes now. While unethical, it's not illegal and probably not worth combatting since, technically, that is the will of the voter.
  - vincnetas 9y ago
    So this basically reduces democracy to "moneycrasy". Whoever has/can promise most money, wins. And then when they in power guess from where (whom) they will get back all the money that they spent? It's like saying, well it's your kidney, it should not be illegal to sell it...
    - thaumasiotes 9y ago
      > So this basically reduces democracy to "moneycrasy". "Plutocracy".
  - brianberns 9y ago
    In the U.S., I believe it's illegal to buy or sell votes. http://www.slate.com/articles/news_and_politics/net_election/2000/10/want_to_sell_your_vote_not_so_fast.html http://www.slate.com/articles/news_and_politics/net_election...
  - KMag 9y ago
    But if properly implemented (use metal detectors to keep cameras and phones out of the voting booths), it's difficult to prove how you voted using paper ballots / old fashioned mechanical voting machines. I don't see much problem in selling your vote if there's no way to verify that you're not ripping off the person buying the vote.
KMag 9y ago
Preventing non-registered voters is the easy problem. Some signature systems allow blind signatures: I can create a ballot and encrypt the ballot. The government can sign the ballot, and then knowing my secret encryption key, I can decrypt the ballot and transform the government signature so that it matches the decrypted ballot. The signed but decrypted ballots can then be published using mixnets, Tor, or some other anonymous publishing mechanism. As I remember, it's still an open problem to set things up (without requiring trusted hardware or trusting the government to destroy a private homomorphic encryption key) so that I can't later prove to Dr. Evil's jackbooted thugs that I voted for Dr. Evil. Though, maybe there's some mechanism where I actually generate ballots for all candidates and only submit one of the ballots and it's impossible for me to prove which one I actually submitted, and I could cheat by submitting more than one ballot but there's a zero-knowledge proof that my ballots were for all of the N candidates, so in an American-style first-past-the-post voting system, submitting all of my ballots has the same effect as submitting none of my ballots.
em3rgent0rdr 9y ago
Also could use "homomorphic encryption" [1] which allows you to perform arithmetic on encrypted data without decrypting it. [1] https://en.wikipedia.org/wiki/Homomorphic_encryption https://en.wikipedia.org/wiki/Homomorphic_encryption
em3rgent0rdr 9y ago
https://en.wikipedia.org/wiki/End-to-end_auditable_voting_systems https://en.wikipedia.org/wiki/End-to-end_auditable_voting_sy...
tlrobinson 9y ago
There was a relevant discussion on the Bitcoin mailing list recently: https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-March/015812.html https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018...
deleted 9y ago
[deleted]

mvid 9y ago

Perhaps with asymmetric key encryption? So someone can validate that a vote was theirs, but you can't pin a vote to a person without them doing so. It would require that everyone understood key management, which is probably untenable

GeneralMayhem 9y ago
That doesn't guard against the lead pipe decryption strategy. The point is that you need a way to prove that a vote was yours, without any possible way to prove which vote was yours, whether you want to or not. I'm not a cryptography expert, but that sounds difficult if not logically impossible.
- colordrops 9y ago
  How is lead pipe coercion currently handled?
  - Infernal 9y ago
    There is no way to prove you voted one way or another with anonymous ballots, so there is no incentive to bribing or threatening violence to influence your vote. The desired outcome is to prove that each vote came from a valid voter, while being impossible to prove which vote came from whom.
    - amitbr 9y ago
      There is a cryptographic primitive that does just this allowing of plausible deniability whilst ensuring that only persons able to vote voted: Using Linked Ring Signatures.
    - Mediterraneo10 9y ago
      > There is no way to prove you voted one way or another with anonymous ballots. The coercing party can insist that you take a mobile phone picture of your ballot. This kind of coercion is common in some regions of Russia where civil servants and teachers are told by their superiors that they must vote for the preferred party “or else”, and a mobile phone picture is demanded as proof.
      - KMag 9y ago
        The way around this is to give each person 1 ballot for each of N candidates. 1 ballot goes into an envelope and into the vote box. N-1 ballots go into envelopes and into the discard box. It's trivial to show a photo of your ballot for Dr. Evil, but it would take a video of you going into the voting booth, closely following your hands to prevent three-card-monty, and continuing to follow you into the public lobby containing the vote and discard boxes. If you strictly enforce no recording in the public lobby, then there's no way for you to prove to your boss which box got your ballot for Dr. Evil in the end. Edit: Perhaps I wasn't clear. Each of the N ballots is already filled out for a different candidate. The envelopes are all identical and sealed by you inside the voting booth. That way an existence proof of a ballot for the given candidate leaks absolutely no information. There are no empty paper ballots, and none of the paper ballots can leave the polling station. Ballots need to be counted both from the "vote" and from the "discard" boxes. Ballots missing from the discard box prove vote tampering.
        tschwimmer 9y ago
        I suspect the envelope with the good ballot is sealed in some way. All they would have to do in that case is force you to take a picture of the sealed ballot with the non-desired ballots next to it.
        KMag 9y ago
        All of the envelopes are identical. Absolutely the only difference is which envelope goes into which ballot box. Taking a photo of N-1 ballots for non-Dr. Evil next to one sealed envelope only discloses that the Dr. Evil ballot was put into an envelope first. It gives no information as to which box that envelope was placed into later, and therefore leaks no information about how the vote was cast.
    - colordrops 9y ago
      Why is that any different from being anonymous on a blockchain?
      - Armisael16 9y ago
        It isn’t unless you have some way to verify your vote. Lots of blockchain ideas offer that, though.
- meeton 9y ago
  How about this: when you get into the booth you're given an ID. You then cast your vote for Ms A and you can see on the block chain that it was recorded for A. After you cast, the system shows you a bunch of ids on the chain which voted for other candidates and you can memorise the id shown that voted for Mr B. When people come round, you tell them that other id. When they look it up they see that it voted for B and leave you alone. That doesn't solve the potential problem of vote stuffing... Still thinking about that one.
  - snakeboy 9y ago
    However in this setup, anyone can bring a smartphone in and take a picture of the screen when it displays anything that separates your id from a fake one. Sounds like you might be on the right track if you can get over that hurdle somehow.
    - kybernetikos 9y ago
      The smartphone problem exists currently with paper ballots. You're not supposed to be allowed to bring a camera into the voting booth, but this is not enforced particularly well. One approach to this problem is to make it easy to cancel a previous ballot and submit a new one, so you can get your evidence that you voted the way e.g. your employer wanted you to, but then you can cancel it and vote with your conscience.
      - rjmunro 9y ago
        As far as I can remember from the instructions last time I voted, in Britain you can do this, just return the ballot to the person handing them out and say that you made a mistake, and they should issue you a replacement.
      - feborges 9y ago
        In the Brazilian voting machine this is often done. You type the numbers and it loads the candidate info in the screen. Once you click [Confirm] the screen gets blank with the message of success. Therefore the only way to take a picture is before the vote is actually processed. You have a [Reset] button to re-enter the numbers.

darawk 9y ago

Presumably you'd want a deniable system. So, something where you have a private key 'k', some function 'f', and the public chain 'p'. So, you compute: r = f(k, p) Suppose r may be 1 or 0. The meaning of 1/0 will be randomly distributed among the population, and will be made known to you when you place your vote, but at no other time. So, later on, you understand that a value of 1 means your vote counted for candidate A, but if someone tries to coerce you, you can realistically claim the opposite.

geofft 9y ago
How do you know that the people tallying the vote have the same meaning for r? (That is, how do you prevent a butterfly-ballot-style situation where people think they're voting for Gore, accurately cast a ballot that appears to them to be a vote for Gore, and actually end up casting an objectively valid vote for Buchanan?)
- darawk 9y ago
  Presumably you could generate some proof that the vote was correctly cast at the moment you cast it, and that 1 corresponds to A and 0 corresponds to B. But that proof would not be accessible after you leave the polling booth (because it'd require some ephemeral value that you could retain or throw away).
- breatheoften 9y ago
  Maybe you could do a block tallying with verification scheme. 1. Enter your vote and receive an identifier 2. Group n identifiers into a batch ensuring not all votes in the batch are for the same candidate. Record the n identifiers into a block then randomly order the identifiers but don’t record the randomized sort order. Display the index of their identifier to each user but don’t record it. Record the actual vote in this (random) order to the block. Allow each voter to see all votes recorded in the block at each location (including the one only they know represents their vote). Allow the voter to manually tally the block to ensure the sum of symbols reflects their vote intent. Present to each voter cryptographic proof of the existence of the block and the net affect the block as a whole has on the vote tally for each candidate. Each voter leaves with: 1. cryptographic proof of having voted 2. Cryptographic verification of the effect their vote had on vote tally 3. Ability to claim having voted for any candidate represented in their voting block/inability to prove to others who they voted for while being sure of how their vote was counted themselves.

deleted 9y ago

[deleted]

offbytwo 9y ago

Would zero knowledge proofs work for this?

jinpan 9y ago

Rivest invented the 3-ballot voting protocol (see https://en.wikipedia.org/wiki/ThreeBallot https://en.wikipedia.org/wiki/ThreeBallot) The trick to the 3-ballot voting protocol is that not everyone can validate their vote. However, when a group of voters band together, they should be able to validate that a subset of their votes (1/3) were registered with high probability. With a sufficiently large group of voters checking results, the law of large numbers comes into play and they can statistically detect the presence of voting fraud.

googlryas 9y ago
I like how the example ballot on that wikipedia page has Alex Jones running for president.
- fareesh 9y ago
  One can dream
littlestymaar 9y ago
Zero-knowledge \o/
notahacker 9y ago
It's an interesting idea whose utility depends on whether you think turning casting a valid vote for the intended candidate into a logic puzzle is a good thing

deleted 9y ago

[deleted]

ihm 9y ago

One simple way (basically using Zerocoin/ZCash) is the following. Every voter is issued one "vote coin" at registration time. There are special addresses for each candidate. Each voter sends their "vote coin" using a zero-knowledge/private transaction to the candidate of their choice. It's totally auditable, not possible to vote more than once, etc. The main issue is in making it potentially easy to sell your vote, which as the OP was getting at is at the heart of the tension.

clintonb 9y ago
Voters can sell their votes now. While unethical, it's not illegal and probably not worth combatting since, technically, that is the will of the voter.
- vincnetas 9y ago
  So this basically reduces democracy to "moneycrasy". Whoever has/can promise most money, wins. And then when they in power guess from where (whom) they will get back all the money that they spent? It's like saying, well it's your kidney, it should not be illegal to sell it...
  - thaumasiotes 9y ago
    > So this basically reduces democracy to "moneycrasy". "Plutocracy".
- brianberns 9y ago
  In the U.S., I believe it's illegal to buy or sell votes. http://www.slate.com/articles/news_and_politics/net_election/2000/10/want_to_sell_your_vote_not_so_fast.html http://www.slate.com/articles/news_and_politics/net_election...
- KMag 9y ago
  But if properly implemented (use metal detectors to keep cameras and phones out of the voting booths), it's difficult to prove how you voted using paper ballots / old fashioned mechanical voting machines. I don't see much problem in selling your vote if there's no way to verify that you're not ripping off the person buying the vote.

KMag 9y ago

Preventing non-registered voters is the easy problem. Some signature systems allow blind signatures: I can create a ballot and encrypt the ballot. The government can sign the ballot, and then knowing my secret encryption key, I can decrypt the ballot and transform the government signature so that it matches the decrypted ballot. The signed but decrypted ballots can then be published using mixnets, Tor, or some other anonymous publishing mechanism. As I remember, it's still an open problem to set things up (without requiring trusted hardware or trusting the government to destroy a private homomorphic encryption key) so that I can't later prove to Dr. Evil's jackbooted thugs that I voted for Dr. Evil. Though, maybe there's some mechanism where I actually generate ballots for all candidates and only submit one of the ballots and it's impossible for me to prove which one I actually submitted, and I could cheat by submitting more than one ballot but there's a zero-knowledge proof that my ballots were for all of the N candidates, so in an American-style first-past-the-post voting system, submitting all of my ballots has the same effect as submitting none of my ballots.

em3rgent0rdr 9y ago

Also could use "homomorphic encryption" [1] which allows you to perform arithmetic on encrypted data without decrypting it. [1] https://en.wikipedia.org/wiki/Homomorphic_encryption https://en.wikipedia.org/wiki/Homomorphic_encryption

em3rgent0rdr 9y ago

https://en.wikipedia.org/wiki/End-to-end_auditable_voting_systems https://en.wikipedia.org/wiki/End-to-end_auditable_voting_sy...

tlrobinson 9y ago

There was a relevant discussion on the Bitcoin mailing list recently: https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-March/015812.html https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018...

deleted 9y ago

[deleted]