Live data from Hacker News

Homomorphic encryption

en.wikipedia.org

81–86 of 86 posts

Re: Homomorphic encryption

#81
post #32
post #29

Earlier quoted context omitted.

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)

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…

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.

Re: Homomorphic encryption

#82
post #66

Earlier quoted context omitted.

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 Pa…

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.

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.

Re: Homomorphic encryption

#83
post #82

Earlier quoted context omitted.

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.

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…

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.

Re: Homomorphic encryption

#84
post #82

Earlier quoted context omitted.

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…

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"…

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.)

Re: Homomorphic encryption

#85
post #84

Earlier quoted context omitted.

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"…

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…

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)

Re: Homomorphic encryption

#86
post #84

Earlier quoted context omitted.

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…

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 th…

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.

Post reply on HN