Hacker News Reader

Comment by hossbeast | Hacker News Reader

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

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

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.

Reply on news.ycombinator.com