Microsoft Demonstrates Practical Homomorphic Computing

holy_calamity writes "Homomorphic computing makes it possible to compute with encrypted data and get an encrypted result, something that could make cloud services more secure. Such systems have so far been mathematical proofs, but researchers at Microsoft now say that stripped down versions able to only compute certain mathematical functions are efficient enough to be used today. They built prototype software capable of calculating statistical functions using encrypted data and say it could be used for processing medical data while protecting privacy."

Comments

Re:How does this voodoo work?

[smallfries]

Here is a simple example (leaks way more information than the real system). Let's say that the two numbers that you want are elements on a ring (or in CS terms they are numbers modulo some N). You have two numbers, x mod N and y mod N. You want me to perform the modulo addition without learning x and y.
1. You pick two random numbers, p mod N and q mod N.
2. You send me (x+p) mod N and (y+q) mod N. As long as your selections were really random this provides no information about x or y.
3. I compute (x+p) + (y+q) mod N and send you the result. This leaks nothing about the sum.
4. You then compute r - (q+p) mod N to recover the real sum.

There are two problems with this simple scheme (which is why the real scheme took many years to discover and is quite hard to implement). The first problem is that you do as much work blinding and unblinding the numbers as you would computing the real sum. The second problem is that this scheme leaks some information (can't remember what, it's been quite a while).

A Somewhat Homomorphic encryption scheme will solve both of these issues for addition (for some value of solve and some value of efficiency), while a Fully Homomorphic will also allow you to perform multiplications in the ring.

Re:performance

[nschubach]

http://research.google.com/pubs/papers.html

That's some serious hording going on there.

Re:Microsoft?

[AJH16]

This is Microsoft Research we are talking about. They are probably one of the best computational research centers around. I'd trust their security research quite a bit. These are the same people that made a managed code kernel with a native code compiler for .Net just to study how to make OSes in a different, more secure way. It actually did a lot of process isolation in a similar way to how Android does it, but actually predated Android development. As far as I know, that project is still ongoing (it's called Singularity if you are interested and it is quite interesting imho.)

They have many other very innovative and ground breaking research credits to their name, but as other people have mentioned, they are unfortunately more think tank than product development so a lot of times what they come up with isn't really used, at least not by Microsoft. (Note they were also doing multi-touch interaction with their "Surface" research a long time ago too. Some of that actually appears to be getting worked in to Windows 8.)