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."
FTFA: "It added together 100 numbers, each 128 binary digits long, in 20 milliseconds."
wow. just wow.
It works, but at this speed not production-ready. a proof of concept, not much more.
(otoh, it is nice to see that MS still invests in basic research)
http://en.wikipedia.org/wiki/Homomorphic_encryption
You're welcome.
(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)
Did anyone else read the headline as "Microsoft Says Homophobic Computing Is Practical" ..?
Nah I saw it as "homeopathic" which given the MS/PC rep, seemed quite believable.
Homeopathic computing is basically buying a new bloatware stuffed PC, and discovering that the more you dilute the hard drive by deleting bloatware, the better the PC runs. Needless to say, I stick to Debian or macs to avoid the bloat.
"Science flies us to the moon. Religion flies us into buildings." - Victor Stenger
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,
You're confusing this with homeopathic computing, where the more you "dilute" the hard drive of a new PC by removing bloatware, the more effective the PC becomes.
"Science flies us to the moon. Religion flies us into buildings." - Victor Stenger
So let's get this straight... You take a bunch of encrypted numbers, never ever decrypt them but somehow still add them together to get the right encrypted answer.
WTF???
No details in TFA but HOW does this voodoo work?
More importantly, when will we get lazy enough that the encrypted version of our medical stats becomes commonplace? E.g.,
"Hey, what's your cholesterol?"
"9E024B9D7G129F8A7D084HF0241746GAE98364FA9295HA82754834H9328747FA 8907A089F004375G73649E746D92850F872892B398D93095738A74674F943834B3."
Help fight poverty: Punch a poor person.
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.
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.
Indeed. I never quite got that part either.
x + x = y
x * x = y
Implies that x is 2 and y is 4. It doesn't matter how the numbers are encrypted, if those are the inputs and those are the outputs, then that's what they by mathemathical nessecity -must- mean.
Do more math, and every one gives you a new equation, pretty soon you can solve for any unknown.
What am I missing ?
Does homomorphic computation make special assumption such as the operations must all be mod N or something of that nature ?
Ok.
No. This is the Greek "homo", meaning "same" (which BTW also is the "homo" appearing in "homosexual": same sex). But even the Latin "homo" doesn't mean "man" in the sense of "man/woman", but in the sense of "human being", used e.g. in "homo sapiens" (which actually means "wise human" -- whoever gave our species that name must have had a very strange humour).
Right.
No, homomorphic means "changing the same way". It's going to be like mass hysteria.
The Tao of math: The numbers you can count are not the real numbers.
That's an understatement. This is cutting edge cryptography. IBM and Microsoft didn't have the resources to develop this 5 years ago.
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
Eh. Any smooth function, maybe.
But 'any function' seems pretty contradictory. If you can apply functions like 'is this number >1, return 1 if yes, 0 if no' you'd be able to find out what the answer is pretty quickly without decrypting it. Actually, really, isn't homomorphic computer inherently contradictory this way?
But you could run tests. For example, assume that the only operations you have are addition, subtraction, multiplication and comparison operators. You start by determining the encrypted values for true and false, by choosing a random encrypted number (you have no idea what it is, but you know it's an encrypted number) and comparing it to itself. Testing for equality gives the encrypted value for true and testing for inequality gives the encrypted value for false. Next, you determine the encrypted value for zero (assuming zero and false might have different encrypted representations) by simply subtracting that encrypted number from itself. Given that the list above doesn't include division, getting at the 1 is harder. However you can easily compare a number against 1 by simply comparing it against with its square (you actually have to test first whether it's positive, but that's easy -- you already have the representations of 0, true and false, and the comparison operators are provided). If you manage to find a number that's smaller than one, you can repeatedly double it until you get something larger than one (or equal to one, if you are very lucky). Note that doubling means just adding the number to itself (no representation of 2 required). As soon as you get to a number larger than 1 this way, you can do nested intervals to find the 1. Now you have 0, 1 and a number between 0.5 and 1, and that is enough to determine the value of any encrypted number sent to the network.
The Tao of math: The numbers you can count are not the real numbers.
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.
We haven't even gotten encryption right yet. Certainly they had to "cut corners" on encryption to make it computationally feasible. When they get this working with 65000 bit encryption (not 256 or 1024) THEN I'll take them seriously. Until that day I can't trust encryption and I won't trust people who claim it is "secure".
Because the alternative is trusting unencrypted data. None of us are under the delusion that anything, digital or physical, is 100% secure and completely impenetrable. However, properly encrypted data is MORE secure than unencrypted data. Then, there's also the "outrunning the bear" aspect. If you and I both have data sets of equal value to a data thief, mine is encrypted and yours is not, my database doesn't have to be 65,000 bit encrypted in order to be the less desirable target.