Hacker News Reader

Comment by dataexp | Hacker News Reader

I wonder is there is some restricted kind of homomorphic encryption so that the encryption is tailored to be used for certain kind of programs. For example if the program is to compute the average of a list of numbers then some simple encryption could be done just to compute the average and nothing more. Is there some related concept to this idea of the encryption restricted to a concrete computation?

View on HN

One related concept is “partially homomorphic encryption” (https://en.wikipedia.org/wiki/Homomorphic_encryption#Partial...). These are encryption schemes that are homomorphic under one operation such as addition or multiplication.

For example, you could use an additively homomorphic scheme to compute a sum of encrypted values. This could then be converted into an average assuming you knew the number of values.

You're looking for functional encryption (https://en.wikipedia.org/wiki/Functional_encryption). It lets you compute exactly an encryption of a pre-specified function of the input message and nothing else.

I think functional encryption is even less well developed than FHE. Most problems can't be expressed in functional encryption, and the security model is really iffy.

This is basically what people do with problems like Private Information Retrieval and Private Set Intersection. They use some lightly applied FHE as a subroutine, but otherwise hand-develop a cryptographic protocol for the specific program at hand.

As it turns out, these applications are much more widely used than FHE.

I think there are special cases, like Yao's millionaire problem, where you compute a simple predicate to compare two numbers. I do not know whether such a notion will save you much, though. Because as soon as you can compute a simple instruction like SUBLEQ you have a Turing complete scheme.

Reply on news.ycombinator.com