Beta
×

Welcome to the Slashdot Beta site -- learn more here. Use the link in the footer or click here to return to the Classic version of Slashdot.

Thank you!

Before you choose to head back to the Classic look of the site, we'd appreciate it if you share your thoughts on the Beta; your feedback is what drives our ongoing development.

Beta is different and we value you taking the time to try it out. Please take a look at the changes we've made in Beta and  learn more about it. Thanks for reading, and for making the site better!

Microsoft Demonstrates Practical Homomorphic Computing

timothy posted more than 3 years ago | from the garbage-looking-in-garbage-looking-out dept.

Cloud 141

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

cancel ×

141 comments

Sorry! There are no comments related to the filter you selected.

Homo's? (-1)

Anonymous Coward | more than 3 years ago | (#37031260)

Who you calling a homo?

I Don't Like The Sound Of This (-1)

Anonymous Coward | more than 3 years ago | (#37031276)

Homomorphic? Let's break that down, shall we?
Homo = Manly
Morphic = Changing

Homomorphic computing is going to change our manliness - it's going to be like getting married.

Re:I Don't Like The Sound Of This (1)

geminidomino (614729) | more than 3 years ago | (#37031888)

And this is what happens when people learn Greek from afternoon sentai shows...

Re:I Don't Like The Sound Of This (2)

maxwell demon (590494) | more than 3 years ago | (#37031974)

Homomorphic? Let's break that down, shall we?

Ok.

Homo = Manly

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

Morphic = Changing

Right.

Homomorphic computing is going to change our manliness - it's going to be like getting married.

No, homomorphic means "changing the same way". It's going to be like mass hysteria.

performance (2)

rbrausse (1319883) | more than 3 years ago | (#37031294)

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)

Re:performance (2)

Robert Zenz (1680268) | more than 3 years ago | (#37031350)

(otoh, it is nice to see that MS still invests in basic research)

They do a lot of research...unfortunately most of it ends up in a coffin buried deep underground.

Re:performance (3, Informative)

gweihir (88907) | more than 3 years ago | (#37031412)

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.

Re:performance (3, Interesting)

ailnlv (1291644) | more than 3 years ago | (#37031554)

not really, microsoft research is pretty big and they publish basically everything. Google on the other hand keeps its research to itself.

Re:performance (0)

Anonymous Coward | more than 3 years ago | (#37032026)

Why bring Google into this? Some serious insecurity you have going on there.

Re:performance (2)

Zouden (232738) | more than 3 years ago | (#37031472)

In the article a researcher says, "You can still do a lot of statistical functions and perform analysis like logistical regression, which is used to do things like predict how likely a person is to have a heart attack."
Okay, but statistical analysis like that isn't particularly computationally-intensive. At some point, an authorised person is going to look at the data (of course), and they can perform the statistical analysis then. That's the way it's done now.

I just don't see how valuable any analysis will be if the system doesn't have an understanding about what the data represents. If it's all just numbers, then all you can do is perform arithmetic, which doesn't exactly require a server in the cloud.

Re:performance (1)

jpapon (1877296) | more than 3 years ago | (#37031532)

the system doesn't have an understanding about what the data represents

Isn't the point that the system knows what the data represents, just not what the actual values are? So, for instance (as a trivial example), it could take your encrypted blood pressure, age, and weight and output an encrypted number corresponding to your risk of heart attack, without ever actually knowing the real value of the input or the output.

Re:performance (0)

Anonymous Coward | more than 3 years ago | (#37031592)

Indeed. It's a perfect example of a case where you'd use less than 100 numbers and still be able to create end-user value. Nobody would complain if it took 20 milliseconds per patient.

The whole reason for such encyprtion is because you'd like to deploy such applications to the Cloud; i.e. host it on environments that you'd really not trust with your data. However, you'd still require a secure client, so you cannot trivially rely on browser-delivered Javascript.

The point being... (1)

Junta (36770) | more than 3 years ago | (#37031970)

This brings us back to:

Okay, but statistical analysis like that isn't particularly computationally-intensive.

You might as well decrypt the data on the client device and calculate it there. Even javascript execution of the associated arithmetic on a 3-year old iphone is going to be sufficient for the given use cases. The volume of data to transfer all the data versus just the results could be interesting in some problems, but in general I just think the horrible inefficiency and inherent limitations make this an academic-only exercise at this point.

Re:performance (1)

nedlohs (1335013) | more than 3 years ago | (#37032056)

Sure that might be a use. The bigger reason though is you can implement your DRM so that the DRM logic and the decryption keys that need to be on the end user device are encrypted and never decrypted on the end user device, instead they run via this. But for that it needs to be faster, since you are effectively building boolean logic with it and running on that.

Re:performance (1)

FhnuZoag (875558) | more than 3 years ago | (#37032292)

It's generally dangerous to do statistical analyses without looking at the data. You never know if the data turns out to be something you've never envisioned as possible.

Re:performance (1)

marcello_dl (667940) | more than 3 years ago | (#37031720)

But crappy performance is actually a selling point for more performing hardware, I guess some guys are already rubbing their hands and waiting for this tech to be a lil more feasible, so that they can have it mandated by law in some sectors that suddenly will require much more computing power to do the same old things.

Re:performance (1)

flappinbooger (574405) | more than 3 years ago | (#37032094)

Step 1: Invent some plausibly useful technology applicable to a given sector
Step 2: Bribe ... I mean "lobby" .... for the tech to be mandated by law in the given sector
Step 3: ????
Step 4: Profit

I think step 3 may be optional.

Re:performance (1)

WrongSizeGlass (838941) | more than 3 years ago | (#37031958)

It works, but at this speed not production-ready. a proof of concept, not much more.

Next, let's see how fast it works using GPU's.

Re:performance (0)

Anonymous Coward | more than 3 years ago | (#37032190)

"wow. just wow" = Loser message board speak

Re:performance (1)

insertwackynamehere (891357) | more than 3 years ago | (#37032352)

Actually this troll is right. It's up there with extended ellipses after every statement...................

Re:performance (1)

DarthVain (724186) | more than 3 years ago | (#37032908)

Crypo is pretty slow anyway. Over a network where the work is being done and there is communication latency, it is less a big deal than local. What I mean is over the network is going to be slower than say local to a computer anyway. So if it is a bit slow on one end, that will be lessened by the fact of what is expected over a network to begin with. I know for giggles I try to encrypt a 500GB dive using truecrypt, and got a progress bar that was 7 or 8 hours long, and that was locally.

So it isn't a cloud thing, encryption of more data than handshake keys and the like take time. Besides, having non-crypto cloud is no less secure, than all the commercial sites out there storing passwords in plain text files and the like, or on outdated software.

Microsoft? (-1, Troll)

tessellated (265314) | more than 3 years ago | (#37031296)

Not exactly the company I'm going to take my security advice from.

Re:Microsoft? (0)

Anonymous Coward | more than 3 years ago | (#37031308)

Blind Microsoft hate is sooooo 2001.

Re:Microsoft? (0)

geekmux (1040042) | more than 3 years ago | (#37031502)

Blind Microsoft hate is sooooo 2001.

Yeah. And in the meantime, Microsoft security attacks are sooooo 2011.

Don't sit here and bathe in ignorance thinking the OP isn't justified in his comments here. He's certainly not the only one seeing the irony of Microsoft being involved in this, casting questionable doubt as to the overall integrity of this solution.

Re:Microsoft? (3, Insightful)

improfane (855034) | more than 3 years ago | (#37031536)

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:Microsoft? (1)

tessellated (265314) | more than 3 years ago | (#37031722)

Just beeing cautious, after all they've got the same signature on their paychecks.

But GP may be right, it's probably just my backdoor paranoia...

Re:Microsoft? (0)

Anonymous Coward | more than 3 years ago | (#37032906)

Your backdoor paranoia is entirely justified given your purty face.

Re:Microsoft? (1)

geekmux (1040042) | more than 3 years ago | (#37031984)

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?

No, I do not question the validity of academic research, when done properly. What concerns me is when anyone hands over their research to a company that is as deeply embedded in our culture (read Government) as Microsoft is, and they are tasked with taking said research and developing a product sans any questions of integrity, especially when addressing a solution involving encryption for the implied purpose of securing sensitive data in a cloud infrastructure design.

Let's just say Microsoft would likely be slightly more influenced than other companies to create master keys or a backdoor, at the request (read demand) of certain very large customers.

Re:Microsoft? (-1, Flamebait)

PopeRatzo (965947) | more than 3 years ago | (#37031756)

Don't sit here and bathe in ignorance thinking the OP isn't justified in his comments here. He's certainly not the only one seeing the irony of Microsoft being involved in this, casting questionable doubt as to the overall integrity of this solution.

Just a hint: "Bathe in ignorance" is one of those highfalutin' phrases that ends up making you sound stupid. Not that your original comment didn't do that well enough, but "bathe in ignorance" removed all doubt.

Re:Microsoft? (-1)

Anonymous Coward | more than 3 years ago | (#37031870)

Yeehaw! You tell 'im Jeb! There be none of that highfalutin lingo 'round these parts.

Re:Microsoft? (0)

geekmux (1040042) | more than 3 years ago | (#37032086)

Don't sit here and bathe in ignorance thinking the OP isn't justified in his comments here. He's certainly not the only one seeing the irony of Microsoft being involved in this, casting questionable doubt as to the overall integrity of this solution.

Just a hint: "Bathe in ignorance" is one of those highfalutin' phrases that ends up making you sound stupid. Not that your original comment didn't do that well enough, but "bathe in ignorance" removed all doubt.

And your tenacity to attack a particular phrase that has little to do with my overall point of my post says what about the depth of your ability? If you wish for me to be a bit more guttural here to appease the lowbrow masses, I certainly can be. Given the fact that Microsoft has the US Government as one of their largest customers, there ain't no way in fuckin' hell I'm gonna trust those asshats to create a encryption solution, especially for the purposes of securing sensitive data in a cloud infrastructure design, without questioning where the back door or master key is. It's pretty much a given.

There, that better for ya?

Re:Microsoft? (1)

PopeRatzo (965947) | more than 3 years ago | (#37032710)

Given the fact that Microsoft has the US Government as one of their largest customers, there ain't no way in fuckin' hell I'm gonna trust those asshats to create a encryption solution,

I hate to break this to you, but you know that money in your pocket? It was printed by the US Government. I suppose that upon learning that fact, you feel inclined to burn the little wad of ones and fives in your wallet and strictly do business using shiny stones as a medium of barter.

You should stop digging, geekmux. Pretty soon I won't be able to see the top of your head.

Re:Microsoft? (1)

Anonymous Coward | more than 3 years ago | (#37031446)

Not exactly the company I'm going to take my security advice from.

Nobody is giving you advice in this article--security related or otherwise. Plus, you do realize that people like Ron Rivest of MIT, and his proteges, like Susan Hohenberger work with Microsoft--the latter being a research fellow for MSFT? Oh, no, you probably don't.

Re:Microsoft? (5, Informative)

AJH16 (940784) | more than 3 years ago | (#37032340)

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

How does this voodoo work? (0)

CProgrammer98 (240351) | more than 3 years ago | (#37031328)

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?

Re:How does this voodoo work? (2)

ledow (319597) | more than 3 years ago | (#37031360)

http://en.wikipedia.org/wiki/Homomorphic_encryption [wikipedia.org]

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)

Re:How does this voodoo work? (1)

Threni (635302) | more than 3 years ago | (#37031566)

Isn't there a risk that attackers will also be able to process the data whilst it's encrypted, though. Aren't you just removing the requirement for the data to be decrypted first? How does that make anything more secure? The overhead is what makes it secure - I'd have thought that you'd consider the ability to do this as proof that you need to reconsider your encryption system.

Re:How does this voodoo work? (1)

mattpalmer1086 (707360) | more than 3 years ago | (#37031732)

The whole point is that, without the decryption key, you don't know what the result of any processing is. Even were an attacker be able to process the data in some way, they would not know what the result meant. Remember that encryption only deals with confidentiality, not integrity. If you want to be sure that an attacker has not processed the data in some way, you would need to add integrity protection of some sort to your data in addition.

Anyway, since you don't have to decrypt the data first in order to perform operations on it, you can do most of your processing without ever having the data in the clear. Only when you want to learn a result do you need to decrypt. I'm really not sure why you don't see the potential security benefits of such a scheme. The overhead has no bearing on the security, other than its slowness preventing it from being used in the first place.

Re:How does this voodoo work? (2)

maxwell demon (590494) | more than 3 years ago | (#37032390)

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.

Re:How does this voodoo work? (1)

mattpalmer1086 (707360) | more than 3 years ago | (#37032850)

I don't think homomorphic encryption provides values for true and false or provides comparison operators - only one operation (e.g. addition) or two operations (e.g. addition & multiplication over a ring).

I do like the idea of arriving at known values through some basic arithmetic though - I'm just not sure the operations provided permit this.

Re:How does this voodoo work? (1)

maxwell demon (590494) | more than 3 years ago | (#37033786)

Well, for n-bit integers using standard two's complement addition throwing away overflow (i.e. calculating mod 2^n, the standard way modern computers hndle it), it is possible to recover zero using only addition: Take an arbitrary number. Add to itself; this multiplies by 2, thus shifts it one bit left, the lowest bit is zero. Repeat n times, now all bits are zero.

As soon as you know zero, you can easily test the lowest bit of any given number: Double it n-1 times; if the result is zero (which you know), the bit was zero. If it was non-zero, that bit was one.

Furthermore, as soon as you found a single odd number, you additionally know the representation of INT_MIN (sign bit 1, all other bits 0) for signed resp. 2^(n-1) for unsigned values.

Now you are ready to discover bit 1. Shift a number left (i.e. double it) n-2 times. Now the two most significant bits contain the previously two least significant ones. Two of the possible values you already know (from now on, for simplicity I'll assume unsigned numbers): 0 and 2^(n-1). For the other two, you can have one of two yet unknown encrypted values, corresponding to 01 and 11. So you now know how to distinguish 0 and 1 for the next-to-last bit, although for odd numbers you don't know yet which is which if the last bit is 1. However, if you have multiplication in addition to addition, you can use the fact that multiplying an odd number with itself always gives a number ending in 01. That is, if you have addition and multiplication, you can also discover the next to last bit.

I'd not be surprised if that scheme could be extended to discover all bits of an unknown number (note that with addition and multiplication you can calculate an arbitrary polynomial with zero constant term of a given integer).

Re:How does this voodoo work? (3, Insightful)

PopeRatzo (965947) | more than 3 years ago | (#37031792)

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? (0)

Anonymous Coward | more than 3 years ago | (#37031370)

This is how it works: http://signallake.com/innovation/HomomorphicEncryption062509.pdf

Good luck understanding it. :)

Re:How does this voodoo work? (1)

gweihir (88907) | more than 3 years ago | (#37031418)

Actually very old. Relevant research papers were published 20-30 years ago. It is just that CPUs have gotten fast enough that you can actually demonstrate something.

Re:How does this voodoo work? (1)

vlm (69642) | more than 3 years ago | (#37031426)

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?

The key is probably how incredibly slow it operates. I could implement something as slow as their solution... What if you did BCD encoding of all numbers and had a lookup table that turned "7 aka binary 0111" into "1024 bit encrypted/hash". Then a big IBM 1620-ish table of hashes such that "this 1024 bit enum" plus "that 1024 bit enum" equals "another 1024 bit enum". It would of course be incredibly slow, much as reported...

Followed in about 6 months by a 2600 article RE-discovering the joy of known plaintext attacks, statistical analysis.

Re:How does this voodoo work? (0)

Anonymous Coward | more than 3 years ago | (#37031698)

lol, what? That would be a table of size 2^1024 * 2^1024 = 2^2048, almost a hundred googols.

Re:How does this voodoo work? (1)

vlm (69642) | more than 3 years ago | (#37032446)

lol, what? That would be a table of size 2^1024 * 2^1024 = 2^2048, almost a hundred googols.

Sparse table. Almost like a one time pad, except probably not as good.

Imagine salting each digit with a 16 bit number... that table size is somewhat more reasonable.

Now a 16 bit salt means fundamentally you're only got 16 bit security, sorta, but...

Re:How does this voodoo work? (4, Informative)

smallfries (601545) | more than 3 years ago | (#37031436)

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:How does this voodoo work? (3, Insightful)

elsurexiste (1758620) | more than 3 years ago | (#37031444)

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:How does this voodoo work? (2)

thedonger (1317951) | more than 3 years ago | (#37031654)

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

Re:How does this voodoo work? (1)

Paxinum (1204260) | more than 3 years ago | (#37031832)

Encryption is essentially a function, f(x), that sends plaintext, x, to encrypted text, f(x). The public key is the recipy on how to perform f, and the private key is essentially the inverse of f. Note, the only assumption so far on f, is that it has an inverse, which is hard to find given only f.
Ok, now, a homeomorphic crypto algorithm f has the following additional properties:
f(x+y) = f(x) (+) f(y),
f(x*y) = f(x) (*) f(y),
where (+) and (*) are some mathematical binary operators, that are known. Thus, if I know f(x), f(y), I just perform (+) on these two, and arrive at f(x+y). Notice, I did not need to know x or y, the plaintext data!
The trouble is, finding a crypto with good strength with both (+) and (*) is hard. (Finding only (*) is easy for RSA-like cryptos). Now, for this to be useful, (+) and (*) should not be too slow to perform in practice.
Now, why both + and * ? Well, these operators alone can, when composed together, give any other function:
Wikipedia:

Using such a scheme, any circuit can be homomorphically evaluated, effectively allowing the construction of programs which may be run on encryptions of their inputs to produce an encryption of their output.

Re:How does this voodoo work? (2)

FhnuZoag (875558) | more than 3 years ago | (#37032358)

"Now, why both + and * ? Well, these operators alone can, when composed together, give any other function."

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?

Re:How does this voodoo work? (3, Insightful)

Eivind (15695) | more than 3 years ago | (#37031854)

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:How does this voodoo work? (0)

Anonymous Coward | more than 3 years ago | (#37033064)

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.

"We call it Eivind's Axiom. Nobody really knows why. All we know is that it works, and you're under arrest."

HOMO (-1)

Anonymous Coward | more than 3 years ago | (#37031340)

sorry just trying to sound out how to pronounce it.

Re:HOMO (1)

PopeRatzo (965947) | more than 3 years ago | (#37031936)

sorry just trying to sound out how to pronounce it.

I bet you know very well how to pronounce it.

After all, you've been hearing the word since the third grade.

What the hell is wrong with me?! (0)

lostsoulz (1631651) | more than 3 years ago | (#37031346)

Did anyone else read the headline as "Microsoft Says Homophobic Computing Is Practical" ..?

Re:What the hell is wrong with me?! (2)

vlm (69642) | more than 3 years ago | (#37031384)

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.

Georgia School (1, Funny)

MyLongNickName (822545) | more than 3 years ago | (#37031352)

Georgia Schools voted to not allow teachers to include this in their Computer Science programs.

Re:Georgia School (1)

gweihir (88907) | more than 3 years ago | (#37031440)

Georgia Schools voted to not allow teachers to include this in their Computer Science programs.

Homomorphic computation has maybe a place in a selected crypto topics lecture for grad students. Even there it is questionable. This stuff does is not practical beyond toy examples. And it has been known for > 20 years.

Re:Georgia School (1)

jpapon (1877296) | more than 3 years ago | (#37031556)

Woosh!

Re:Georgia School (1, Funny)

MightyYar (622222) | more than 3 years ago | (#37031518)

It was banned in the same bill that mandated intelligent computation.

Re:Georgia School (2)

vlm (69642) | more than 3 years ago | (#37031580)

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.

Yes, but there are to few "certain functions" (0)

gweihir (88907) | more than 3 years ago | (#37031388)

Some functions have worked for ages and efficiently. However they are not enough except for a few demo cases. I expect that is exactly the same here. And if you need more than the simplistic demo cases, you are straight out of luck. For example, multiplication has been infeasible so far and you cannot simulate it. As far as I remember, relative comparison does not work either.

To sum up: This is a publicity stunt. Once again.

Re:Yes, but there are to few "certain functions" (1)

plover (150551) | more than 3 years ago | (#37031590)

It's still an interesting concept, and while not of widespread utility, it could be valuable in certain applications.

Perhaps there is some accounting, banking, auction, or currency escrow function, where you want some untrusted party to deposit funds into an account, but not be able to access the balance. Or voting, where you want to see proof that your vote was tallied without revealing who you voted for.

Sure, these are probably the "simplistic demo" cases you were mentioning, but there could be a real class of problems that nobody's yet identified. That's kind of the thing with research like this. Novel things are created, then knock around for a bit until someone figures out that they solve their problem. Or not.

Re:Yes, but there are to few "certain functions" (0)

Anonymous Coward | more than 3 years ago | (#37031662)

If you use RSA then multiplication is easy. It's addition that becomes hard then.

Re:Yes, but there are to few "certain functions" (0)

Anonymous Coward | more than 3 years ago | (#37031834)

Indeed. If you read the paper, the encryption scheme allows calculating a mean, calculating a standard deviation and logistical regression. It notably does not allow calculating division or square roots. Microsoft Research (pet peeve, I wish people would stop attributing this to Microsoft, as if Microsoft and Microsoft Research had much of anything to do with one another) have picked what they thought were key domains (medical applications, financial applications and advertising and pricing) and tailored the encryption scheme specifically to those applications. It's not a general-purpose computational framework but it certainly offers more than just a few demo cases.

Zen moment (1)

equex (747231) | more than 3 years ago | (#37031428)

I thought it said "Microsoft Demonstrated Homophobic Computing'.

Re:Zen moment (0)

Anonymous Coward | more than 3 years ago | (#37031512)

I thought it said "Homeopathic" at first myself.

Why should I trust this? (-1)

Anonymous Coward | more than 3 years ago | (#37031432)

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

Re:Why should I trust this? (2)

Voyager529 (1363959) | more than 3 years ago | (#37033312)

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.

Homomorphic encryption... (1)

shic (309152) | more than 3 years ago | (#37031442)

From the "Homomorphic Encryption" page linked from the article:
"Only in 2009 did Craig Gentry of IBM publish a mathematical proof showing fully homomorphic encryption was possible."

In the past (in a very hand-wavy kind of way) I've argued that it should be possible to "prove" that homomorphic encryption isn't feasible... because, in order to implement multiplication and addition of integers, I need a total-ordering over my data... and if I have a total ordering, my data is (effectively) decrypted. This, of course, doesn't preclude obfuscation and scrambling - but I (used to) believe strong homomorphic encryption was not worth investigation.

Does anyone have a reference to this proof? Has anyone read it? Can anyone summarise what Gentry concludes?

Re:Homomorphic encryption... (2)

Eivind (15695) | more than 3 years ago | (#37031908)

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 ?

Re:Homomorphic encryption... (1)

CAPSLOCK2000 (27149) | more than 3 years ago | (#37032100)

This only works for a limited number of variables and equations. If it works there may be many solutions.
It doesn't even work for your example:

0 + 0 = 0
0 * 0 = 0

If the number of equations growth it quickly becomes infeasible to solve it, especially if the formulas are a bit more complicated (e.g. non-linear).

Re:Homomorphic encryption... (1)

mwvdlee (775178) | more than 3 years ago | (#37032260)

Or both x and y are 0.

Re:Homomorphic encryption... (3, Insightful)

Scumbumbo (521718) | more than 3 years ago | (#37032860)

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.

I hope no one believes this makes it more secure (3, Informative)

erroneus (253617) | more than 3 years ago | (#37031454)

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.

Re:I hope no one believes this makes it more secur (1)

cavreader (1903280) | more than 3 years ago | (#37031578)

The thing is getting rid of the stupid people doing stupid things is impossible so you are left with trying to limit the amount of damage with technology.

Re:I hope no one believes this makes it more secur (1)

vlm (69642) | more than 3 years ago | (#37031680)

Good, but, I think the main application will be DRM not data protection.

You get to checkmark "security" and checkmark "encryption" for the PHBs at sales meetings. Also the PHBs think "stronger" encryption helps, because they don't understand how the internet works (as soon as one person in the world breaks it / leaks it / steals it, its as if the whole world knows)

Its easy for R+D to test, just call a function name "drm_add_two_nums(a,b)" where before the testing servers are implemented, that function simply returns a+b. This also makes it easy to hack later on, just replace the baroque crypto subroutine with the testing subroutine that simply returns the sum.

Maybe you can convince the legal system that breaking an encrypted DRM system is somehow more heinous of a crime than murder, or at least worse than breaking an unencrypted DRM scheme.

You can't patent addition itself (well, actually, you can) ... But you could patent a ridiculously complicated and inefficient way to implement addition. So its useful in patent wars, both offensively as a brick to hit others over the head with, and defensively as a way out to re-implement tired old DRM systems, now "all new", and also avoid patents and licensing fees on existing crazy patents involving addition.

Re:I hope no one believes this makes it more secur (0)

Anonymous Coward | more than 3 years ago | (#37032536)

If I give you encrypted data to process and I don't give you the key, then you can't leak the key to someone else or run away with my data. My data cannot be stored unencrypted on a flash drive at a bar by you, because you can't decrypt it as you don't have the key. So even if you do stupid things and you've got my data, my data isn't at risk because it's encrypted. This technology fixes some of the stupid things people do. Making it fast enough is a research problem that's being worked on. If attackers are targeting people because technology is too hard (which isn't always true btw), then we should replace people by technology as much as possible since, by your own reasoning, that removes some of the weak elements. My car may have a risk of killing me even if we install safety features, but the safety features still help.

Re:I hope no one believes this makes it more secur (1)

locofungus (179280) | more than 3 years ago | (#37032566)

I haven't read TFA but I don't think that's the idea here.

You have spare computer processing going that I'm prepared to pay for.

I have a dataset 'x' and an algorithm 'A' I want to run on it. I want A(x) but I don't want to give you x.

What I can do (in theory) is encrypt the data to give me E(x), then give that to you where you run A'(E(x)). I then run D(A'(E(x))) and I get back to A(x) that I wanted all along.

The problems are finding secure E such that A' and D can easily be derived from A and, usually, you want E and D to be cheap calculations in comparison with A' or A.

Tim.

Re:I hope no one believes this makes it more secur (0)

Anonymous Coward | more than 3 years ago | (#37033468)

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

This sentence is unprovable until P = NP is proven. If an asymmetric encryption scheme build upon matrix permanent [wikipedia.org] is discovered, your sentence is unprovable until the Polynomial Hierarchy collapses.

I think this is shameful (3, Funny)

bigsexyjoe (581721) | more than 3 years ago | (#37031456)

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.

Re:I think this is shameful (0)

Anonymous Coward | more than 3 years ago | (#37031826)

Haha, good to see I wasn't the only one that misread the title as such.

Re:I think this is shameful (0)

Anonymous Coward | more than 3 years ago | (#37032028)

Would Alan be impressed by a computer passing the Turing test, even if the result was a bigot?

Re:I think this is shameful (0)

Anonymous Coward | more than 3 years ago | (#37032610)

I, for one, thought it said "Homoerotic Computing". Guess I'll break out the joystick for this one...

Re:I think this is shameful (0)

Anonymous Coward | more than 3 years ago | (#37032624)

it must be the people who can't do recursion

disgusting (1)

frovingslosh (582462) | more than 3 years ago | (#37031474)

Disgusting. I'll stick with heteromorphic computing. Sure looks like another scam to try to get you to put data that you should be keeping secure into the "cloud" bullshit. Use an OS that doesn't squander all of the computing power of the computer on the OS and there will be no need to put the data into someone else's hands.

But... (-1)

Anonymous Coward | more than 3 years ago | (#37031488)

The GLBT community is all Apple Fanboys (and girls and whatever) They wouldn't touch a MS product

stocks will rise (1)

hesaigo999ca (786966) | more than 3 years ago | (#37031558)

If i only has some money to invest, stocks will be going up for the next year because of this tech.

I am 12 (-1)

Anonymous Coward | more than 3 years ago | (#37031568)

I have no idea what the article is talking about, but it sounds gay.

First marriage... (-1)

Anonymous Coward | more than 3 years ago | (#37031634)

and now this? When will it end?

Massively Distributed Cloud Computing (1)

bill_mcgonigle (4333) | more than 3 years ago | (#37031836)

This is the tech that will make massively distributed cloud computing possible. I did a startup about 5 years ago that involved home computing devices that were paid for by the distributed computing that ran on them. Among the things that made it unsuccessful was that we knew we needed this kind of technology but didn't have the resources to develop it.

Microsoft and others have previously proposed domestic heating with distributed computing, and once this kind of data protection becomes possible it will be a really enticing option. The computing user will submit jobs to a broker, who will distribute the jobs to the 'cloud'. The data will be crunched on these distributed units, and then returned to the broker, and to the user (sufficient mapping rules can cut out the middle man of the data transfer, just signed control packets need to run that way).

Probably you'll have the option to get a free hot water heater (provided by the computing company) and your electric bill to run it will be lower than your current domestic hot water heater. You save money, the user saves money, the middle man makes money, the planet is warmed less. We need IPv6 and FTTH to make it very feasible, but those things should show up this decade.

Re:Massively Distributed Cloud Computing (2)

nedlohs (1335013) | more than 3 years ago | (#37032114)

I did a startup about 5 years ago that involved home computing devices that were paid for by the distributed computing that ran on them. Among the things that made it unsuccessful was that we knew we needed this kind of technology but didn't have the resources to develop it.

That's an understatement. This is cutting edge cryptography. IBM and Microsoft didn't have the resources to develop this 5 years ago.

Re:Massively Distributed Cloud Computing (1)

bill_mcgonigle (4333) | more than 3 years ago | (#37032454)

True that. I've been following the research since then - last year there was a breakthrough academic paper. Perhaps if that had existed we could have reduced it to practice. Lack of funding was also a small problem. ;)

At this point I've got young kids and will be happy to see somebody else get it to market. I'll get back in the game once they're older.

Doesn't seem secure... (1)

GargamelSpaceman (992546) | more than 3 years ago | (#37032204)

After a quick look at the wikipedia entries for Homomorphism and Homomorphic Encryption, this scheme seems roughly equivalent to other homomorphisms such as ROT-13.

If you know the algebraic structure ( which you might guess looking at the encrypted data ) then you can use statistics about data pertaining to that structure to tell what encrypted value corresponds to what real value. ( similarly to how you can tell which letter is E if you 'encrypt' by letter substitution eg:

ABCDEFGHIJKLMNOPQRSTUVWXYZ ->
HLGVDAQZMIKWTYENBJUXPCSFOR

This is the way we encrypt the sentence ->
XZMU MU XZD SHO SD DYGJONX XZD UDYXDYGD

Maybe I misunderstood something but this is what it seems like at first glance.

Where's the car analogy (0)

Anonymous Coward | more than 3 years ago | (#37033390)

Seriously, 94 posts and no one has made the requisite car analogy for the rest of us?

DNA (0)

Anonymous Coward | more than 3 years ago | (#37033586)

Right now DNA is theory based. While the math is correct no one knows if there are unknown variables that influence results and some unknown variables have been identified since the theory was accepted as "fact". There have been some pretty interesting developments in DNA including people with multiple DNA and DNA results that predicted two people were "brothers" but were separated by distance, race and where research showed that the fathers DNA was very similar even though they were of different races. These developments are being used in court to question the accuracy of DNA evidence and there are no actual DNA studies large enough to counter the arguments. Some defense lawyers are claiming the use of DNA as evidence is akin to giving FDA approval for a drug based on chemical analysis and without doing actual drug trials. The FBI has the largest database of DNA information including phenotypes and that database is not accessible for research purposes to prove the theories behind DNA identification because of privacy issues. By creating a process where specific data can be entered into a statistical analysis without endangering the privacy of those involved it may be possible to eliminate the developing mountain of evidence that questions the accuracy of DNA technology. This is a huge deal to law enforcement.

Homomorphic computing? (1, Troll)

TheGoodNamesWereGone (1844118) | more than 3 years ago | (#37033746)

Next they'll be wanting computers to get married!
Load More Comments
Slashdot Login

Need an Account?

Forgot your password?

Submission Text Formatting Tips

We support a small subset of HTML, namely these tags:

  • b
  • i
  • p
  • br
  • a
  • ol
  • ul
  • li
  • dl
  • dt
  • dd
  • em
  • strong
  • tt
  • blockquote
  • div
  • quote
  • ecode

"ecode" can be used for code snippets, for example:

<ecode>    while(1) { do_something(); } </ecode>