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

Practical homomorphic encryption over integers (2017)

arxiv.org

Post reply on HN
Print view View original

51–57 of 57 posts

Re: Practical homomorphic encryption over integers (2017)

#51

Post by heavenlyblue »

betterunix2 wrote: post #31
mcbits wrote: post #12

Earlier quoted context omitted.

Potentially a search engine could provide results without knowing the actual query, although that would make it difficult to identify new trends or determine which results are/aren't being clicked, so it probably wouldn't be competitive as a general purpose search engine.

It would also be completely impractical, since the search engine would necessarily have to perform some sort of scan of its entire database to respond to every query (otherwise it would, in fact, learn something about the query).

Unless the database is also encrypted and provides the same homomorphism against reverse index queries.

Re: Practical homomorphic encryption over integers (2017)

#52

Post by jkabrg »

betterunix2 wrote: post #32
jldugger wrote: post #27

Earlier quoted context omitted.

To the extent that computations are feasible, yes. There was a pretty big paper like a decade ago proposing a fully homomorphic system. It was pretty much impractical, running like a million times slower than native instructions. I assume without reading that this post's paper reduces that multiplier to hundreds of thousands. edit: reading the abstract, it looks like they don't have a faster fully homomorphic system,…

Actually the paper presents nothing; their security proofs make no sense at all and the rest of the paper is not much better.

Wow. Explain?

Re: Practical homomorphic encryption over integers (2017)

#53

Post by soberhoff »

heavenlyblue wrote: post #51
betterunix2 wrote: post #31

Earlier quoted context omitted.

It would also be completely impractical, since the search engine would necessarily have to perform some sort of scan of its entire database to respond to every query (otherwise it would, in fact, learn something about the query).

Unless the database is also encrypted and provides the same homomorphism against reverse index queries.

If the database was encrypted, you would need a different encrypted database for every user - again impractical.

Re: Practical homomorphic encryption over integers (2017)

#54

Post by betterunix2 »

jkabrg wrote: post #52
betterunix2 wrote: post #32

Earlier quoted context omitted.

Actually the paper presents nothing; their security proofs make no sense at all and the rest of the paper is not much better.

Wow. Explain?

Theorem 1 fails to specify what it means to "attack" the cryptosystem; it seems to deal only with complete plaintext recovery. It is possible that an attack can only recover a single bit of the plaintext, something which is not handled by the proof.

Definition 1 is not really a definition; in particular it would not be useful in a proof or logical argument. Likewise with Definition 2.

The authors claim that chosen plaintext attacks are not relevant; then they claim in Theorem 3 that their system is secure against CPA. Over and over in this paper the authors refer to the need to be CPA secure when the plaintext has "insufficient entropy" so it is hard to understand why they would claim CPA security is irrelevant.

The vector version of their scheme appears to be a lattice problem, but the authors do not discuss lattice attacks that might be used against their scheme. The authors state that it is "clear" that the security of the vector version follows from the same arguments used for the integer version.

In the "FHE" section the authors do not actually construct an FHE scheme; instead they have constructed some kind of garbled circuit scheme that uses the encryption schemes proposed in the paper. No proof of security is given for that garbling scheme.

For what it's worth, this is more or less what I would have written if I had to review this for a conference and I would give this paper a "strong reject" score.

Re: Practical homomorphic encryption over integers (2017)

#55

Post by betterunix2 »

heavenlyblue wrote: post #51
betterunix2 wrote: post #31

Earlier quoted context omitted.

It would also be completely impractical, since the search engine would necessarily have to perform some sort of scan of its entire database to respond to every query (otherwise it would, in fact, learn something about the query).

Unless the database is also encrypted and provides the same homomorphism against reverse index queries.

In which case you are no longer talking about FHE. With FHE the server receives a ciphertext query and produces a ciphertext output, without ever seeing any plaintexts (not even the result of a reverse index query).

Re: Practical homomorphic encryption over integers (2017)

#56

Post by betterunix2 »

chaboud wrote: post #40
betterunix2 wrote: post #34

Earlier quoted context omitted.

You need more than FHE for that; just because I cannot see what I am computing does not mean I will compute the answer correctly. There are ways this can be resolved but it pushes practicality even further back.

Is it not practical to just saddle the dataset and compute request with a canary payload that is easily computable by the requestor? If one can spoof the canary payload effectively, one would have broken the FHE scheme, probabilistically, right? Unless I'm thinking about this wrong, the FH part of FHE makes this a pretty solvable problem. Is this not already fundamental to any FHE scheme?

Maybe in some cases that is possible, but it is also possible that your function requires as much time to verify as the FHE evaluator would spend on (honestly) computing the result. In other words it would make outsourcing pointless; this is briefly discussed in the related work section of this paper:

https://eprint.iacr.org/2014/202.pdf

You also have to be careful to ensure that the canary cannot be identified in the plaintext; otherwise the evaluator can homomorphically identify the canary (i.e. it can compute the canary values honestly and cheat everywhere else).

Re: Practical homomorphic encryption over integers (2017)

#57

Post by strstr »

tdullien wrote: post #45
strstr wrote: post #42

Earlier quoted context omitted.

Enclaves (e.g. SGX) get you there without the need for fancy math. And you get to maintain normal computation (i.e. x86). Enclaves have the downside of being a bit of a pain to use. But hell, FHE isn’t any easier.

It is somewhat doubtful, though, that SGX achieves what it was supposed to achieve. While you get full-RAM encryption & integrity, the trouble is that CPUs tend to only work-as-defined for a narrow range of environmental parameters. In all likelihood, a malicious cloud provider can take a CPU out of spec, at which point pretty much all security guarantees go out of the window...

My understanding was that if you take the CPU out of spec (e.g. voltage) while in an enclave, you’ll get MCEs and the CPU either nukes your enclave or forcibly reboots (idr which).

That said you can still shave it down and start FIBing if you have the $$$.

Post reply on HN