4 ms·

To address the inevitable “what is this useful for” questions, my go-to example is cryptographic voting mechanisms. The idea is that you segment a large intege

To address the inevitable “what is this useful for” questions, my go-to example is cryptographic voting mechanisms. The idea is that you segment a large integer into a couple of different bins by its bitwise representation. So you have a 60-bit integer and you segment it into four 15-bit bins. You use one of those to randomize what the encrypted versions are going to be, and you use the other three for different vote tallies of three candidates for some office. You can then hand people three numbers each corresponding to a different candidate, and ask them to commit to one as their vote. Public authorities can then aggregate votes which they cannot actually see, and we don't decrypt until we get to some large enough context where your vote has been anonymized among ten thousand others, and you can check that the random seeds have been properly added, or other such things. This also allows you to create a big online database where anybody can see their vote was counted, but nobody can figure out who someone else voted for. There is a slight difficulty in that you cannot see directly what your numbers are actually voting for, so that the machines you are using to vote with need to be able to decrypt a ballot for you and then immediately destroy it, to verify that it was what you thought it was, so that you can trust that your three numbers do not all happen to vote for the same person because if someone tried that on any scale that could affect an election, even if they only poison 1% of ballots in a 500 person district, if everyone burns one to test the system then the fraud gets discovered at least once with 99.3% certainty. But the point is that all of these other issues can be handled “out-of-band” once you protect the important stuff.

compsciphd 7y ago
I'd think there's a simpler way to accomplish what you said above (though in both cases, any voting mechanism that lets the voter verify their vote after the fact also runs into the problem of people complaining about encouraging vote buying). i.e. imagine every polling place would output to you (after you voted) a random number in the 128 bit space. the votes are recorded with this random number. we can verify after polls closed that the voting machine has an appropriate number of votes (i.e. not more or less than people who came through the booths) all these vote data is aggregated into public record. you can look up after the fact your random number and see that it matched who you voted for. No encryption needed (beyond the technology that goes into making a secure rng)
- monocasa 7y ago
  You open yourself to vote buying and voter cohersion attacks, historically the most common voting fraud mechanism in the states.
  - compsciphd 7y ago
    any verifiable voting mechanism opens oneself up to vote buying. if I can use homomorphic encryption to verify my vote I can give the same info needed (say this 128 bit number) to someone else.
    - monocasa 7y ago
      Define "verifiable". There are absolutely schemes where I can't verify what my vote was after the fact, but can verify that it was counted.
      - compsciphd 7y ago
        verify that my vote was counted correctly. i.e. that my vote wasn't changed or fraudelently presented to me.
        monocasa 7y ago
        You can do that with quite a few pen and paper systems today, without being to verify what you voted for after the fact.
- crdrost 7y ago
  Well, no, if you do it cryptographically, at least with the proper mechanism, you can prevent votes from being buyable. In your case, if someone wants to buy your vote, they can ask you to text the number to them before it has appeared as a matter of public record—and if you voted for the Right Person they will pay you. The 128-bit number makes this very hard to forge, whereas to destroy vote-buying you want to make something very easy to forge. Suppose that you receive a ballot from a machine which tears it down the middle: on the right hand side are bar codes containing the voting numbers; on the left-hand-side are candidates' metadata—names, parties, etc. So from the very moment I hand you the ballot, you can see that there is a connection between these numbers and those names, but as long as I provide a supply of other left-hand-sides in other orders, it becomes very easy for you to fake it when displaying it to someone else. That ease-of-forgery is the key to making it impossible to buy votes.
jayd16 7y ago
So conceptually, I get sent a locked voting box, I slip my vote in, return the box. No one can open the box until the election and nothing is identifiable about the tallies at the end. Ok... What is stopping me from putting in multiple votes? Whats stopping someone from checking my single vote difference? (ie, skipping the anonymization through aggregation part)
- crdrost 7y ago
  1. The box only fits one ballot. This is easier to do with bits than with real boxes, of course. "This is box number 12345" and that number is present also within the homomorphically-encrypted payload and we can confirm that the sum of the box numbers in the public database is the same as the sum of the decrypted box numbers. And of course I can tie you-the-person with the box number that you voted with publicly, to prevent you from sending multiple boxes to be counted. 2. The tallies are added without opening the boxes, so anyone can confirm that computations to add together the tallies for a region were all done properly. But we don't give everyone the ability to decrypt ballots ad-hoc. The only big question here is about key compromise at the end; that is a matter of properly destroying the decryption key at the end of the decryption of the tallies, so that this key cannot be leaked out to someone to try and decrypt individual votes. There are some options for making this part more robust—open-source software and secret sharing schemes—but I mean there can be very fundamental issues of trust at the highest level and if those issues are sufficiently pervasive then no amount of cryptography can protect the election; you just have a dictator who is prepared to fix it at all costs or so.
  - jayd16 7y ago
    If any such decryption key exists that can decrypt single votes, it's already a failure. Not only can we not trust that it will stay secret, we also must ensure its secret from the vote counter themselves.
weberc2 7y ago
This could allow us to build a universal distributed network of compute resources and a real-time auction system that allows agents to bid for time on. No need to worry that the hardware owners are snooping on your computation. Of course, economics rarely favor distributed networks, and and the "no need to worry" is really just "diminished need to worry", but it's an interesting thought nevertheless.

compsciphd 7y ago

I'd think there's a simpler way to accomplish what you said above (though in both cases, any voting mechanism that lets the voter verify their vote after the fact also runs into the problem of people complaining about encouraging vote buying). i.e. imagine every polling place would output to you (after you voted) a random number in the 128 bit space. the votes are recorded with this random number. we can verify after polls closed that the voting machine has an appropriate number of votes (i.e. not more or less than people who came through the booths) all these vote data is aggregated into public record. you can look up after the fact your random number and see that it matched who you voted for. No encryption needed (beyond the technology that goes into making a secure rng)

monocasa 7y ago
You open yourself to vote buying and voter cohersion attacks, historically the most common voting fraud mechanism in the states.
- compsciphd 7y ago
  any verifiable voting mechanism opens oneself up to vote buying. if I can use homomorphic encryption to verify my vote I can give the same info needed (say this 128 bit number) to someone else.
  - monocasa 7y ago
    Define "verifiable". There are absolutely schemes where I can't verify what my vote was after the fact, but can verify that it was counted.
    - compsciphd 7y ago
      verify that my vote was counted correctly. i.e. that my vote wasn't changed or fraudelently presented to me.
      - monocasa 7y ago
        You can do that with quite a few pen and paper systems today, without being to verify what you voted for after the fact.
crdrost 7y ago
Well, no, if you do it cryptographically, at least with the proper mechanism, you can prevent votes from being buyable. In your case, if someone wants to buy your vote, they can ask you to text the number to them before it has appeared as a matter of public record—and if you voted for the Right Person they will pay you. The 128-bit number makes this very hard to forge, whereas to destroy vote-buying you want to make something very easy to forge. Suppose that you receive a ballot from a machine which tears it down the middle: on the right hand side are bar codes containing the voting numbers; on the left-hand-side are candidates' metadata—names, parties, etc. So from the very moment I hand you the ballot, you can see that there is a connection between these numbers and those names, but as long as I provide a supply of other left-hand-sides in other orders, it becomes very easy for you to fake it when displaying it to someone else. That ease-of-forgery is the key to making it impossible to buy votes.

jayd16 7y ago

So conceptually, I get sent a locked voting box, I slip my vote in, return the box. No one can open the box until the election and nothing is identifiable about the tallies at the end. Ok... What is stopping me from putting in multiple votes? Whats stopping someone from checking my single vote difference? (ie, skipping the anonymization through aggregation part)

crdrost 7y ago
1. The box only fits one ballot. This is easier to do with bits than with real boxes, of course. "This is box number 12345" and that number is present also within the homomorphically-encrypted payload and we can confirm that the sum of the box numbers in the public database is the same as the sum of the decrypted box numbers. And of course I can tie you-the-person with the box number that you voted with publicly, to prevent you from sending multiple boxes to be counted. 2. The tallies are added without opening the boxes, so anyone can confirm that computations to add together the tallies for a region were all done properly. But we don't give everyone the ability to decrypt ballots ad-hoc. The only big question here is about key compromise at the end; that is a matter of properly destroying the decryption key at the end of the decryption of the tallies, so that this key cannot be leaked out to someone to try and decrypt individual votes. There are some options for making this part more robust—open-source software and secret sharing schemes—but I mean there can be very fundamental issues of trust at the highest level and if those issues are sufficiently pervasive then no amount of cryptography can protect the election; you just have a dictator who is prepared to fix it at all costs or so.
- jayd16 7y ago
  If any such decryption key exists that can decrypt single votes, it's already a failure. Not only can we not trust that it will stay secret, we also must ensure its secret from the vote counter themselves.

weberc2 7y ago

This could allow us to build a universal distributed network of compute resources and a real-time auction system that allows agents to bid for time on. No need to worry that the hardware owners are snooping on your computation. Of course, economics rarely favor distributed networks, and and the "no need to worry" is really just "diminished need to worry", but it's an interesting thought nevertheless.