[crdrost]

Just the way I said in the comment you are replying to. Well, actually, I know two ways, that is just one of them.

Let me put it a different way. Let us suppose that you are in New York State in 2016, voting for the US president, and let's ignore the strange things that can happen with write-ins. After a random shuffle your ballot might look like this:

                         | BALLOT #5846
                         |
    1. Hillary Clinton   |  [  ]  [barcode]
       Democratic Party  |
    2. Jill Stein        |  [  ]  [barcode]
       Green Party       |
    3. Gary Johnson      |  [  ]  [barcode]
       Libertarian Party |
    4. Donald Trump      |  [  ]  [barcode]
       Republican Party  |

As this ballot is being presented to you, it is being cut by a sharp blade along that line through the center. So you have these two halves, and you know that they once belonged to the same piece of paper.

The right hand side is scanned and it is what we make public. Everyone can confirm that you voted in this past election, and you punched the third (say) square in your ballot. But we also make it really easy for you to take, outside of the voting booth, any of a number of other left-hand sides in other random permutations. So if you wanted a left-hand side that said "Trump, Johnson, Stein, Clinton" that is easily available for you to take out of the booth.

Now after the election you can keep either or both papers and go to a government-run website and confirm that that right-hand side corresponds to who you voted for, and you can start a political watchdog group to make sure that the homomorphic operations were properly done on all of these peoples' right-hand-sides-of-ballots. But that web site is not saying "Oh hi it's you, you voted for Gary Johnson," it's saying "Oh hi it's you, you voted for the third person on your ballot." You know that the left-hand side you have says that candidate #3 was Gary Johnson, you saw the paper cut with your own eyes. But to everyone else, that left-hand-side is just a piece of paper.

So: we have made it very easy for you to forge any other vote, as far as any other party would be able to verify. Nobody else can confirm the connection between the piece of paper you hold in your hand and the piece of paper that has been scanned and appears in the public database. And since this is very easy to forge it is very valueless as a piece of information for vote-buying purposes.

So that stuff is all really straightforward. The only dodgy thing is, what if I were to hand you a ballot like this where every vote on the right hand side happened to be a bar code for Jill Stein? Since the number is encrypted, that is not something you would otherwise have access to.

And the solution there is burning ballots on-demand. You can make requests to the election authority asking to decrypt a ballot during the election; indeed we print a lot of extra ballots expecting folks to do this and we declare it their civic duty. When you do so, you get to reveal the "true" left-hand-side for a given right-hand-side and confirm that they are the same—but that ballot is thereafter invalidated and cannot participate in the election. As more and more people do this, it becomes more and more costly to do less and less vote-rigging in this way. So you get an implicit assurance that no tampering has happened in the process of getting this ballot to you, if you can trust that your communication pipeline to the decryption authority is secure and they are not compromised. (And if they are compromised there is very little you can do in any case.)

(The other mechanism just has a ballot which is two pieces of paper attached above each other with labels on the one piece of paper and holes that let you punch out the other piece of paper -- you can go online after the election and verify that the hole which was punched was the one you punched, but your ability to get other front-sheets at the voting booth makes it very easy for you to forge a ballot for say your employer where you appear to have publicly voted for their preferred candidate but secretly you voted for another one.)

[compsciphd]

re burning ballots.

If it's possible to burn a ballot (i.e. associate the set of bar codes to actual candidates), shouldn't it be possible to "burn" a ballot after the fact as well?

i.e. we have 4 barcodes, I need a way to associate each barcode with a candidate to burn it, so why couldn't this happen after the fact as well?

I assume homomorphic encryption might help here, I just am missing it.

[crdrost]

Homomorphic encryption does not affect that problem... It's just down to policy. If the decryption authority “stays open” after the election and no longer insists on checking ballots to see if they have already been cast, then yeah, you can abuse the system to decrypt placed ballots.

If the keys are destroyed after a valid election, as one would expect, then there is no possibility for that.

One way to better ensure the keys are destroyed is to use secret-sharing schemes so that multiple parties that are adversaries would have to lie similarly about destroying the keys, then conspire to work together to decrypt ballots after the fact. But I hope you see that this is all chasing social problems that must be solved as a precondition to have fair elections in the first place.

[compsciphd]

well, you would have to someone "close" the ability to "decrypt" the used ballot instantly, otherwise while the election is ongoing someone could "decrypt" it.

Though I tend to agree, its more of a social issue that technology can't really solve and hence why I'm more concerned about a user (and hence others) being able to verify that their vote was recorded correctly than doing out utmost to discourage "vote buying" schemes as at the end of the day, I don't think technology can really solve that problem but having more faith in the electoral system as a whole by being individually verifiable has more value (even if it can make vote buying more common). but I understand I might be in the minority on that.

[crdrost]

Right, the protocol is essentially that you have a central server which supports in essence two SQL queries,

    UPDATE ballots 
    SET status = "burned" 
    WHERE contents = :ballot AND status = "unused"

which, if it succeeds, then sends the ballot to the decryption oracle with the private key, to be decrypted and sent back to the user; and

    UPDATE ballots
    SET status = "used"
      , voter_id = :voter
      , choice = :choice
    WHERE contents = :ballot 
      AND status = "unused"
      AND region = :region

which, if it succeeds, then sends back a confirmation that this user has been logged with that ballot and made that choice for that ballot.

If you allow people to access the decryption oracle without going through that first pathway, which simultaneously checks if the ballot was not spent and immediately spends it into the "burning" pathway, then either of those opens up the space to attacks which decrypt individual ballots. With that said, just about any auditing mechanism applied to the decryption oracle would be revealing the existence of those attacks anyway so you can still get a measure of security without this.

You can potentially even distribute the database (e.g. over a blockchain among several political parties), but as far as I can tell the decryption authority would still need to be centralized and could be a single-point of failure. (In this case it would be a program which is watching that blockchain and interacting with it via some “I publish a burned ballot onto the ledger after I think the blockchain has passed N blocks ahead of the ledger request to burn that ballot” algorithm, and nodes in the network need to reject requests to cast ballots that they think have been requested to be burnt.)

[compsciphd]

at the end of the day, this still relies on a heavy level of trust (i.e. on the infrastructure itself to do the right thing and that no one has a copy of the db).

As discussed, I'd prefer a system that increases trust without relying on trusted components (by making the vote verifiable after the fact) even if that can incentivize vote buying (but that's mostly because I view trusting the infrastructure as a bigger threat than being worried about vote buying, but I might be wrong about that)

[crdrost]

I don’t understand why you think these things are necessary or opposite.

You can have a system where everyone has a copy of the database. That is not hard, it just requires the separation of what a ballot means, from what is stored in the database. That is just these two-sided ballots with encrypted values on the right-hand-sides: so that the fact that I voted for #1 on my ballot does not tell those who hold the database who I voted for.

You can have a system where encrypted ballots are known by the people to have the values that they say they have. That is not hard, it just requires a challenge-response scheme. If I give you a box and claim there is a pony figurine inside, you can be suspicious: if I give you twenty thousand boxes and claim that they all have pony figurines inside of them, and you ask me to open ten thousand of them which you choose randomly, then for me to omit one pony I am facing a 50% detection rate, for two I am facing a 25% detection rate; to disenfranchise even 10 people from their ponies I will be caught in the act 99.9% of the time, and even then I can only disenfranchise 0.1% of the boxes.

So I can have great confidence that my vote was recorded for the first person on my ballot (I can see the database), and I can have great confidence that the first person on my ballot was Alice and not Bob or Carol (because they passed my challenge/response test).

You can also have a system where nobody can pay substantial sums of money for votes. That is also not hard, it just requires the things that users take home with them out of the voting booth to be easily forged, so that they cannot prove that they did not forge the thing.

Absolutely none of this requires homomorphic encryption; homomorphic encryption just streamlines some of the process around the decryption oracle: with HE tallying and anonymization happen outside of it, so that its internal structure simplifies drastically.