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

Show HN: Distributed Homomorphic Encryption Adder (Weekend Project)

9ac345a5509a.github.io

Post reply on HN
Print view View original

11–20 of 25 posts

Re: Show HN: Distributed Homomorphic Encryption Adder (Weekend Project)

#11

Post by davidw »

Here's a hypothetical use case for homomorphic encryption, although I think it needs to do a lot more than the linked example if it's actually going to work in this case:

There's a bunch of data on a server, including, say, encrypted names. Users accessing the server have a key to decrypt those names, but they also need to be able to search for and sort names. Decrypting all the names and searching/sorting would be one option, but with enough names, it becomes very, very slow. Another option is having a big index that you decrypt for searching/sorting. This is kind of unwieldy as well, even if it's faster than decrypting everything piece by piece.

Perhaps the right homomorphic encryption techniques could also be used, although you'd have to account for substring searching in the case of names: finding "David" searching for "Dav".

Re: Show HN: Distributed Homomorphic Encryption Adder (Weekend Project)

#12

Post by ReidZB »

Honestly, I think the potential advent of efficient fully-homomorphic encryption is potentially one of the largest effects we could ever see on privacy-related computing. The possibilities are absolutely staggering. Imagine, for example, a search engine that returns useful results but does not know what the user is searching for. And so on; the possibilities are well-covered in the literature.

As of right now, the current-day state-of-the-art fully-homomorphic schemes impose roughly a billion-factor overhead on operations, but this is quickly decreasing (in the past 4 years, we've already knocked off three orders of magnitude). But I am personally convinced that an efficient scheme would likely revolutionize privacy in computing. Exciting stuff, especially with recent events.

Unfortunately, I don't expect an efficient scheme to be widely-used for at least 15-25 years. For one, even if a super-efficient FHE scheme was published tomorrow, it'd probably take at least 6-10 years of powerful, sustained cryptanalysis for the community to trust it. Add the time to discover such a scheme (if even possible...) and you have quite a while. But still, the potential is amazing.

Re: Show HN: Distributed Homomorphic Encryption Adder (Weekend Project)

#13

Post by cabalamat »

ReidZB wrote: post #12

Honestly, I think the potential advent of efficient fully-homomorphic encryption is potentially one of the largest effects we could ever see on privacy-related computing. The possibilities are absolutely staggering. Imagine, for example, a search engine that returns useful results but does not know what the user is searching for. And so on; the possibilities are well-covered in the literature. As of right now, the cu…

By fully-homomorphic do you mean Turing-complete?

Re: Show HN: Distributed Homomorphic Encryption Adder (Weekend Project)

#14

Post by joshuak »

This reminds me of the average salary tool. If you are not allowed, or it is bad form, to ask your peers' salaries you can create a list of people add a random number to your own salary give it to the first person on the list that person had their salary and gives it to the next continuing through the list. The last person give you the final number. You subtract your random number and divide by the total number of people and bingo you have the average salary of the group.

I actually did this once at a company I worked for. Both the management and the employees ended up unhappy.

(the typical, and more secure, version of this includes public key encryption between each participant)

Re: Show HN: Distributed Homomorphic Encryption Adder (Weekend Project)

#15

Post by xyzzyz »

cabalamat wrote: post #13
ReidZB wrote: post #12

Honestly, I think the potential advent of efficient fully-homomorphic encryption is potentially one of the largest effects we could ever see on privacy-related computing. The possibilities are absolutely staggering. Imagine, for example, a search engine that returns useful results but does not know what the user is searching for. And so on; the possibilities are well-covered in the literature. As of right now, the cu…

By fully-homomorphic do you mean Turing-complete?

No, by fully homomorphic he means the usual meaning of this phrase: http://en.wikipedia.org/wiki/Homomorphic_encryption#Fully_ho...

Re: Show HN: Distributed Homomorphic Encryption Adder (Weekend Project)

#16

Post by mjn »

xyzzyz wrote: post #15
cabalamat wrote: post #13

Earlier quoted context omitted.

By fully-homomorphic do you mean Turing-complete?

No, by fully homomorphic he means the usual meaning of this phrase: http://en.wikipedia.org/wiki/Homomorphic_encryption#Fully_ho...

I suppose it depends on which you consider more fundamental to the definition. The reason this particular ring and set of operations is interesting is because it implies being able to compute any Turing-computable function of the data. Hence Gentry's high-level overview paper was entitled "Computing arbitrary functions of encrypted data" [1].

[1] http://ece.gmu.edu/coursewebpages/ECE/ECE646/F10/project/F10...

Re: Show HN: Distributed Homomorphic Encryption Adder (Weekend Project)

#17

Post by swordswinger12 »

geal wrote: post #9

Homomorphic encryption is interesting from a business standpoint (think: manipulating credit card numbers without being able to read them). For anonymization systems, care must be taken: being able to manipulate encrypted data could very well create information leaks. There have been some interesting theoretical uses of the Pallier cryptosystem in private information retrieval systems, though.

What kind of arithmetic operations would you ever need to do on a credit card number? Other than maybe verifying the checksum digit.

Re: Show HN: Distributed Homomorphic Encryption Adder (Weekend Project)

#18

Post by aaronmerriam »

joshuak wrote: post #14

This reminds me of the average salary tool. If you are not allowed, or it is bad form, to ask your peers' salaries you can create a list of people add a random number to your own salary give it to the first person on the list that person had their salary and gives it to the next continuing through the list. The last person give you the final number. You subtract your random number and divide by the total number of pe…

Can you expand a little on why the result of this made people unhappy? At a guess, something relating to significant differences in salary for similar jobs?

Re: Show HN: Distributed Homomorphic Encryption Adder (Weekend Project)

#19

Post by carb »

aaronmerriam wrote: post #18
joshuak wrote: post #14

This reminds me of the average salary tool. If you are not allowed, or it is bad form, to ask your peers' salaries you can create a list of people add a random number to your own salary give it to the first person on the list that person had their salary and gives it to the next continuing through the list. The last person give you the final number. You subtract your random number and divide by the total number of pe…

Can you expand a little on why the result of this made people unhappy? At a guess, something relating to significant differences in salary for similar jobs?

I assume he has three groups:

1. Employees paid less than the average 2. Employees paid equal to or more than the average 3. Management.

Reactions are:

1. Unhappy: Being paid less than average 2. Happy: Being paid more than average 3. Unhappy: Half of their employees now know they are being paid less and are unhappy.

Re: Show HN: Distributed Homomorphic Encryption Adder (Weekend Project)

#20

Post by baddox »

ReidZB wrote: post #12

Honestly, I think the potential advent of efficient fully-homomorphic encryption is potentially one of the largest effects we could ever see on privacy-related computing. The possibilities are absolutely staggering. Imagine, for example, a search engine that returns useful results but does not know what the user is searching for. And so on; the possibilities are well-covered in the literature. As of right now, the cu…

Not to mention cloud computing platforms that have no idea what computation their clients are performing.
Post reply on HN