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.
Machine Learning. Apply neural networks to encrypted data and avoid privacy issues.
That's the big one.
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.
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.
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...