News for hackers. Stuff that matters.
Re:Fully Homomorphic Encryption Without Bootstrapping [pdf] by sweis on Wednesday June 17, 2015 @02:03PM (#9733959)
This Yagisawa paper is of poor quality and lacks adequate proofs. It unfortunately uses the exact title as a 2011 paper by Brakerski, Gentry, and Vaikuntanathan: https://eprint.iacr.org/2011/277.pdf

The BGV paper is the real deal.

Re:Fully Homomorphic Encryption Without Bootstrapping [pdf] by smohare on Wednesday June 17, 2015 @07:38PM (#9735944)
Even the typesetting is atrocious in the Yagisawa paper.
Re:Fully Homomorphic Encryption Without Bootstrapping [pdf] by pbsd on Wednesday June 17, 2015 @03:12PM (#9734512)
Broken a few weeks later: https://eprint.iacr.org/2015/519
Re:Fully Homomorphic Encryption Without Bootstrapping [pdf] by themeek on Wednesday June 17, 2015 @02:10PM (#9734019)
The paper suggests that it would take on order 2^27 bit operations for encryption/decryption for securely parameterized instances of this scheme, small ciphertexts and keys, and a simple multiplication and addition formula. If true, this would be an incredible leap - a breakthrough in efficiency. And efficient FHE would be a game changer for the Internet and the world.

Evaluating the claim thus requires skepticism and care. The quality of the paper is suspect as are its proofs. But, as is the case with science, heuristics like this count for little.

They do seem to have selected a hard worst-case problem to base the system on. Obviously this means very little if secure keys and setting in this complexity space can not be found in practice - or if the details of the cryptosystem, for one of many many reasons, lead to its easy compromise.

Looking forward to a proper peer review of the scheme.

Edit: Looks like it's already broken!

https://news.ycombinator.com/item?id=9734512

Re:Fully Homomorphic Encryption Without Bootstrapping [pdf] by deegles on Wednesday June 17, 2015 @02:32PM (#9734242)
How many bit operations do non-FHE tasks need in comparison?
Re:Fully Homomorphic Encryption Without Bootstrapping [pdf] by themeek on Wednesday June 17, 2015 @02:38PM (#9734287)
Admittedly much fewer (on the order of 'a few'). It's also hard to compare, as constants are hidden in big-O. Real performance comparisons between cryptosystems are comparisons of real-world engineering implementations: especially since side channel blinding, exception and case handling, etc need to be taken into effect.

The take away is that this would still be nowhere near as efficient as 'traditional', especially symmetric, encryption. What would be a breakthrough is that presumably the scheme would be orders of magnitude more efficient than current existing theoretical FHE schemes.

Re:Fully Homomorphic Encryption Without Bootstrapping [pdf] by noahtkoch on Wednesday June 17, 2015 @03:12PM (#9734523)
Totally clicked on it because I wanted to know what "Homophobic Encryption" was.