Homomorphic encryption(en.wikipedia.org) |
Homomorphic encryption(en.wikipedia.org) |
Let me know what you think! :)
Homomorphic encryption promises a hidden and verifiable online voting system that does not rely on trusting third party.
https://www.chaum.com/publications/AccessibleVoterVerifiabil...
The major problem with online voting is that people can be coerced into voting against their wishes outside the watchful eye of election authorities. This may be worth the increase in voting ease, but it's where the real debate is.
The only difference I see, is, the mail is sent via the postal service and the online vote is sent via my personal computer and internet connection.
To get around this, the government could issue verified voting tablets that are locked down and use secured connections.
Otherwise, people can force me to vote different without the authorities noticing already.
The main problem is guaranteeing one vote per eligible voter.
Coercion is a related but smaller problem. It's much harder to coerce most of the people most of the time than it is to stuff the ballot.
Imagine trying to hack the British general election, it would be impossible without hiring millions.
Helios [1], for instance uses an homomorphic scheme.
There are alternatives to it though which preserve voter privacy but allow vote tallying. Shuffling is one of them. Cothority [2] implements an e-voting scheme based on Neff Shuffles
1. https://heliosvoting.org/ 2. https://github.com/dedis/cothority/tree/master/evoting
P.S. I contributed to the latter
Like wouldn't it be preposterous if someone said, "Here Craig Gentry, take $1 billion to run enough computers for the current FHE schemes. What is the snazziest demo you can run?"
Does it work, though?
It will join the graveyard of technologies was that rhetorical?
I referenced NuFHE in a comment, but you should give it a try and see if it will do what you're wanting. See https://github.com/nucypher/nufhe/. We also have a discord channel where you can ask questions on using it in the #nufhe channel -- https://discord.gg/rmSafk
Do you mind sending me an email with your use case and needs? I'd love to have a chat with you.
john@nucypher.com
i'm not sure how this helps e2e encrypted collaborative editing though. why not just use asymmetric encryption? what am i missing?
I guess your concern is that the output is "one of the encrypted input" values and hence identified, although not decrypted. Subsequently, all the input values would be fed into the "max" module and their complete order can be determined by the one running the homeomorphic server.
In that case we will need to have an output where all inputs are returned. Perhaps a map with indices and values (all encrypted) as input and as output would be sufficient.
I guess one brute force way to do it is making encryption unnecessary. For an input of N bits, have the results calculated/returned for all 2^N possibilities. Does not sound very practical.
Any public applications outside of blockchain?
Use case was you need to be able to verify that the output of a program was also a proof of the integrity of that program.
E.g. I receive a payment token from you, and I can verify that this token was produced by a program I could verify as being the "real," program, personalized to your identity, on a device also personalized to your identity, that you physically hold and verify yourself to.
Pretty good* with a chip/pin combination, but on a mobile general purpose computer with lots of other code on it, Hard problem. With some handwaving, FHE would ostensibly have enabled the secure personalization of the program and the signing of those token outputs. It was a variation on: https://en.wikipedia.org/wiki/Direct_Anonymous_Attestation as well.
FHE was the DRM holy grail where suddenly you can "tokenize," information. Other applications are in selling and metering software use.
In the case of health information, the ability to open up data sets to researchers to query and analyze without the risk of losing control of the data is huge. We know that de-identification of data is (information theoretically) impossible, but an ideal FHE scheme would facilitate queries against data that would mitigate much of the risk associated with it.
The other use case is in highly regulated environments where there are legal firewalls between lines of business. Basically wherever there is a use case for de-identification, FHE is a potential solution in that domain. In that regulatory case, it's sort of ironic that it's a solution for, "ok, we won't commit a crime, but we need the hypothetical output of that crime, so let's use cryptography to facilitate that outcome without explicitly breaking the law whose effect is to prevent this outcome."
Perhaps that's why people working in it seem so cagey.
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.
IE: You have a value that you need to do `if <condition> then <statement> else <other statement>`
Problematically, if that condition could work, then it would violate the confidentiality of the encrypted value, thus breaking the CPA security. Now there are some workarounds and methods to getting around this problem sometimes, but in many cases it's not possible.
> A cryptosystem that supports arbitrary computation on ciphertexts is known as fully homomorphic encryption (FHE). Such a scheme enables the construction of programs for any desirable functionality, which can be run on encrypted inputs to produce an encryption of the result
I thought that meant the program itself could be fully encrypted, but after a second look it seems that it is just the inputs that are encrypted. Still, other areas of the wiki talk about support for boolean gates and even arbitrary gates. I don't know what to think, but it is motivating me to revisit coding theory :-)
[1] https://en.m.wikipedia.org/wiki/Homomorphic_encryption#Fully...
Machine Learning. Apply neural networks to encrypted data and avoid privacy issues.
That's the big one.
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)
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.
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)
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.
did you want to transform within words or something?
You cannot easily encrypt your voting information when sent by regular mail. If you have a unique unforgeable id, like a private key, and a secure voting device then your vote can be submitted and counted securely online. Granted, you could print your encrypted vote and mail it in.
> We demonstrate CryptoNets on the MNIST optical character recognition tasks. CryptoNets achieve 99% accuracy and can make more than 51000 predictions per hour on a single PC. Therefore, they allow high throughput, accurate, and private predictions.
Do you just mean the ballots are filled out at home where a government authority is not looking over my shoulder? Because everything else is controlled by the government. The ballots and booklets are printed by the government (who authorize what can be on the ballot and in the booklet), are mailed by a government agency, are checked by a government authority, etc.
Imagine constructing a system that can thwart a abusive, tyrannical father who insists that his wife and children vote for a particular candidate (to make it concrete.) If you can get past him, your voting system passes the first test. Now imagine someone is offering $50 if you vote in a particular way. If there's no way to figure out how someone would claim it, it passes the second test.
The abusive father can literally just fill out all of his family's ballots, and the $50 could be claimed by filling out the ballot in front of the buyer. You could thwart this with allowing multiple votes but only accepting the first, but then the father or buyer could just have the ballots filled out immediately at the first legal moment.
I don't know that it's a thing that can be done without totally private environment around the voter and the record; meaning that the actions of the voter cannot be observed.
I don't think this is currently happening, so I don't think it is a major issue.
As I understand it (perhaps incorrectly), the primary thing that makes vote buying financially difficult is the fact that a person's vote can't be verified. how does homomorphic encryption enable me to verify my own vote but prevent anyone else from using the info I'd give them that I'd use myself to verify my vote.
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 |
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.)
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.
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.
There are also countries where turnout is consistently above 70% and there is no mail voting. In the US the obstacles to voting are not having to go to a polling station: voter registration due to not having a federal ID, voting on a Tuesday rather than during the weekend, gerrymandering due to political bodies bring able to affect the redistricting process, and so on.
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.
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.
UPDATE ballots
SET status = "burned"
WHERE contents = :ballot AND status = "unused"
UPDATE ballots
SET status = "used"
, voter_id = :voter
, choice = :choice
WHERE contents = :ballot
AND status = "unused"
AND region = :region
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.)
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)
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.