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

Re:How does this voodoo work?

[elsurexiste]

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 [slashdot.org]. The problem is not homomorphic computing, which is easy to accomplish; having HC performed in reasonable time with a strong encryption scheme is...

Re:Microsoft?

[improfane]

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?

Re:How does this voodoo work?

[PopeRatzo]

Basically, you have a crap cryptosystem that lets you do it - nobody's yet figured out how to do this without possibly compromising the encryption and you have to start all your maths from scratch - which in encryption security terms is a bit of a nightmare

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

Re:How does this voodoo work?

[Eivind]

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.

Re:Homomorphic encryption...

[Scumbumbo]

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.