Comment by bo1024 | Hacker News Reader

Comment by bo1024 | Hacker News Reader

Parent Full thread

You encrypt some data and send it to Bob.

Bob does some computations on the encrypted data and sends you the (still-encrypted) results.

You decrypt the results to get the answer of your computation. Bob never learns what your data is or what the results are.

The term "homomorphic" roughly refers to the fact that the encrypt/decrypt functions go "outside" the computation. That is, if Bob is applying the function f, we have f(Encrypt(data)) = Encrypt(f(data)). The left side is what Bob does, the right side is what you want to get (because you can decrypt it).

EDIT. To see how cool this is, think about this: I have two numbers, I encrypt them to form long strings of gibberish. Then I have Bob perform the "multiplication" function on the gibberish and send me the result, and I am able to decrypt that to get the result of multiplying the original two numbers. If that doesn't impress you, I send Bob my database of encrypted emails, then ask him to do a string lookup for "chocolate", he sends me back the set of matching emails without ever knowing what they say or what string I looked for.

Does it generalize? Can you in theory perform any computation in this way?

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, just some better results in the partial homomorphic domains.

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.

It does generalize, but not all the way. You can't perform while loops (or anything with unbounded runtime) or operate on anything with unbounded (secret) size, so it isn't Turing complete.

You can do anything expressible as a bounded-depth (non-cyclic) circut of eg NAND gates. You can also do something like [a][+ b][+ c][+ d], where each [] is a new homomorphic operation, which gets around the bounded-size problem somewhat, but the attacker can obviously see how many chunks you're working on, just not the content, which provides some traffic analysis vulnerabilities.

All in all, it's a very useful tool but I don't really like the way people keep presenting it a silver bullet, like "yay, once we get this working we won't have to care that the cloud is full of phantom trolleys armed with hammers!".

Even with partially homomorphic encryption and additional "privacy preserving protocols" you can carry out pretty general computation tasks such as machine learning. Have a look at this blog post using the Paillier cryptosystem for a federated linear regression - https://blog.n1analytics.com/distributed-machine-learning-an...

Reply on news.ycombinator.com