Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Homomorphic encryption

en.wikipedia.org

Post reply on HN
Print view View original

31–40 of 86 posts

Re: Homomorphic encryption

#31

Post by weberc2 »

crdrost wrote: post #10

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…

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.

Re: Homomorphic encryption

#32

Post by crdrost »

jayd16 wrote: post #29
crdrost wrote: post #10

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…

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

Re: Homomorphic encryption

#33

Post by k__ »

rfugger wrote: post #14
Iv wrote: post #3

Seriously one of the most important area of mathematics for democracies in an online world. Homomorphic encryption promises a hidden and verifiable online voting system that does not rely on trusting third party.

Any political voting system will need a trusted third party to run the voter registration/identity system, so I doubt the lack of practical homomorphic encryption is blocking this. There are other voter-verifiable systems that don't rely on HE for trustworthy counting: https://www.chaum.com/publications/AccessibleVoterVerifiabil... The major problem with online voting is that people can be coerced into voting against…

How does online voting differ from mail voting?

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.

Re: Homomorphic encryption

#34

Post by buzzdenver »

For a layman like me it sounds really cool, almost like magic. Consider a trivial operation like finding a maximum value in a list. How is that supposed to work on encrypted values while simultaneously providing strong encryption? So something like adding N to everything in the list is not an acceptable encryption.

Re: Homomorphic encryption

#35

Post by motohagiography »

rch wrote: post #2

I've run into a few people working on this over the last five years or so, but they've been a bit cagey about discussing their use cases and customers. Any public applications outside of blockchain?

When I encountered FHE as a potential solution, it was in designing authentication and payment tokens.

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.

Re: Homomorphic encryption

#37

Post by UncleMeat »

doctorpangloss wrote: post #5

The technology for all this progress was a huge discovery in 2009. But what if it is a dead end, that nothing originating from that discovery will ever be practical? 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?"

FHE isn't the only option. Somewhat Homomorphic Encryption can be fast and stupendously valuable for a lot of statistical operations where you can figure out how to compute your function off only a small number of multiplications.

Re: Homomorphic encryption

#38

Post by mhh__ »

Iv wrote: post #3

Seriously one of the most important area of mathematics for democracies in an online world. Homomorphic encryption promises a hidden and verifiable online voting system that does not rely on trusting third party.

I still think paper voting is the only way no matter the algorithm i.e. no matter how good the system is it's still just a black box at the end of the day.

Imagine trying to hack the British general election, it would be impossible without hiring millions.

Re: Homomorphic encryption

#39

Post by jcoffland »

rfugger wrote: post #14
Iv wrote: post #3

Seriously one of the most important area of mathematics for democracies in an online world. Homomorphic encryption promises a hidden and verifiable online voting system that does not rely on trusting third party.

Any political voting system will need a trusted third party to run the voter registration/identity system, so I doubt the lack of practical homomorphic encryption is blocking this. There are other voter-verifiable systems that don't rely on HE for trustworthy counting: https://www.chaum.com/publications/AccessibleVoterVerifiabil... The major problem with online voting is that people can be coerced into voting against…

> The major problem with online voting is that people can be coerced into voting against their wishes

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.

Re: Homomorphic encryption

#40

Post by jcoffland »

k__ wrote: post #33
rfugger wrote: post #14

Earlier quoted context omitted.

Any political voting system will need a trusted third party to run the voter registration/identity system, so I doubt the lack of practical homomorphic encryption is blocking this. There are other voter-verifiable systems that don't rely on HE for trustworthy counting: https://www.chaum.com/publications/AccessibleVoterVerifiabil... The major problem with online voting is that people can be coerced into voting against…

How does online voting differ from mail voting? 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.

> How does online voting differ from mail voting?

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.

Post reply on HN