Slashdot Mirror
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."
Well, MS research publishes pretty regularly. The problem is just that MS proper does not listen to them at all. MS research has time and again demonstrated that something was stupid, only to have MS proper do it later or continue to do it.
Most ACs are not even worth the keystrokes to insult them. Be generically insulted by this and ignored otherwise.
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.
Slashdot: where don knuth is an idiot because he cant grasp the awesome power of php
That's the point of homomorphic computing: to add two encrypted numbers, you need to take that operation and transform it into another one (let's say, for instance, multiplication) that when performed on two encrypted numbers, it will provide the answer, also encrypted.
This is not new. IBM has already done this. The problem is not homomorphic computing, which is easy to accomplish; having HC performed in reasonable time with a strong encryption scheme is...
I rarely respond to comments. Also, don't ask for clarifications: a brain and Google are faster, believe me!
The problem isn't potential leaks in data by sniffing the machine's data as it flows, it's invariably the machine's data as it's stored... especially on flash drives at a bar.
Any encryption weak enough to be processed with any amount of reasonable execution time would also be weak enough to be cracked within reasonable execution time.
I find it amazing that people continue to seek out technological solutions to problems that are not generally technological. The real holes are the people and the stupid things they do. Those holes are the ones that most often get exploited and the ones that are not being closed effectively.
I just have to shake my head and wonder why... I have a company executive where I work who maintains more than 200GB of email history on his laptop. It's frikken ridiculous. It's against company policy but no one will call him out on it. So you want to see where the REAL holes in security lie? Look no further than a company's leadership.
The father of Computer Science, Alan Turing, was gay. And now people actually want to engage in homophobic computing? I find this kind of hatred shameful.
Democracy Now! - your daily, uncensored, corporate-free
You're questioning the validity of academic research based on the transgressions of a company?
If it's research, who cares where it comes from if it is valid? Do you really think Microsoft software engineers and the researchers are the same pople?
Slashdot needs Geekcode | Can anyone recommend any good SCIFI? My tastes: Foundation, Startide Rising, CITY, Ringworld,
not really, microsoft research is pretty big and they publish basically everything. Google on the other hand keeps its research to itself.
Aren't you the guy who complained that the Wright Brothers were crap because they still needed an airplane to fly? Or that Watson and Crick weren't shit because they didn't cure baldness?
Jaysus man, give 'em a break. That's why they call it "research" and not "products ready for the marketplace".
You are welcome on my lawn.
http://research.google.com/pubs/papers.html
That's some serious hording going on there.
Every time I start to have faith in humanity, I ruin it by driving to work between 7 and 8 am.
It's not voodoo, but math.
Trivial example ? The xor-function. If you encrypt two different numbers with certain (weak, but this is a trivial example!) cryptosystems, then run xor on the encrypted numbers, you get the same answer as you would've if you'd run xor on the original number.
Yeah, that example is indeed *trivial*, but the real examples are math-heavy.
I'm not convinced that practical applications exist though. Most heavy lifting on numbers involve large sets of numbers that are connected somehow. Encrypting those numbers is insufficient to anonymize the data, because the connections themselves give away information.
For example, given a network-graph of Facebook with every single column encrypted, but the connections still visible, and you'd be able to find out which record corresponds to which person.
How many users on facebook have precisely 19871 friends ? How many of those 19871 friends have *precisely* 561 friends ? Basically, even the connections themselves, contain enough information to recognize someone.
It's most trivial for those with many friends, but even for those with a handful, it should be very well doable.
How large a fraction of Facebooks users have *precisely* 7 friends, and those friends again have *precisely* 173, 40, 3, 19, 21 and 4563 friends ? And if that's not enough to nail someone, you can go one step further. Pretty soon it's obvious that the anonymous graph can be mapped onto the non-anonymous one in only precisely *one* way.
I think the same problem is likely for any actually interesting dataset.
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.)
AJ Henderson
You're assuming that the encryption is one-to-one, which is not necessarily true. For instance, it could be that x+x yields y and x*x yields z, but either y or z decrypts as 4.