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)
Blind Microsoft hate is sooooo 2001.
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?
And the people shall be oppressed, every one by another, and every one by his neighbour Isaiah 3:5
Did anyone else read the headline as "Microsoft Says Homophobic Computing Is Practical" ..?
Georgia Schools voted to not allow teachers to include this in their Computer Science programs.
See my journal for slashdot ID's by year. Mine created in 2005. http://slashdot.org/journal/289875/slashdot-ids-by-year
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.
Most ACs are not even worth the keystrokes to insult them. Be generically insulted by this and ignored otherwise.
I thought it said "Microsoft Demonstrated Homophobic Computing'.
Can I light a sig ?
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?
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.
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
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.
I'm an American. I love this country and the freedoms that we used to have.
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.
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,
If i only has some money to invest, stocks will be going up for the next year because of this tech.
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.
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.
"Science flies us to the moon. Religion flies us into buildings." - Victor Stenger
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...
'When the Going gets Weird, the Weird turn Pro.' - Hunter S. Thompson
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.
My God, it's Full of Source!
OUTSIDE_IP=$(dig +short my.ip @outsideip.net)
And this is what happens when people learn Greek from afternoon sentai shows...
I bet you know very well how to pronounce it.
After all, you've been hearing the word since the third grade.
You are welcome on my lawn.
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.
XML is like violence. If it doesn't solve the problem, use more.
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.
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.
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?
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.
...
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
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.
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.
God said, "div D = rho, div B = 0, curl E = -@B/@t, curl H = J + @D/@t," and there was light.
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.
You are welcome on my lawn.
Your backdoor paranoia is entirely justified given your purty face.
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.
Seriously, 94 posts and no one has made the requisite car analogy for the rest of us?
> 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 is discovered, your sentence is unprovable until the Polynomial Hierarchy collapses.
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.
Next they'll be wanting computers to get married!
I hate to break this to you, but you know that money in your pocket? It was printed by the US Government.
But the US government doesn't print money. The twelve Federal Reserve Banks do, and they are private.
*Not really...
The algorithm you described is a known, at least to me, polynomial attack on a well-known NP-complete problem (Graph Isomorphism). Likelihood of it working on a contrived pair of graphs high. Likelihood of it working on all graphs, next to 0. The simplest class of problems that it is ambiguous on is matching up elements in a 1,000 node 3-regular graph. Everyone has 3 friends, all of them have 3 friends, all of their friends have 3 friends, ad infitum. I say ambiguous and not disproven because the number of distinct friends of friends is not necessarily 6
It probably has to do with cloud computing. Encrypted data can be sent to remote data centers for processing with the encrypted results sent back to the client.
A NYC lawyer blogs. http://www.chuangblog.com/
Bzzzt!
The Bureau of Engraving and Printing handles the paper stuff, and the United States Mint produces coinage. Your statement is not entirely incorrect, but for the purposes of this discussion and as written, you are wrong.
TFP, HAND
OMG Microsoft actually did some basic research and with results to boot!
I'm a cryptographer, I saw and understood the talk on this, and it is a very interesting development out of MSR. There's a lot of marketing spin, and this won't do what the marketing department claims, but it's impressive nonetheless.
Fully homomorphic encryption (FHE) is designed so that you can add and multiply numbers (bits or small integers, anyway) under the encryption -- that is, given an encryption of X and of Y, you can create an encryption of X+Y or XY, and using these operations, you can theoretically run any program on the encrypted data. You can't see the result of the program (it's still encrypted), but you could in theory do useful processing on data without compromising its secrecy. In practice, FHE is still far too slow for general programs, especially since you can't have random access memory under the encryption, but for certain specific programs it could be useful.
IBM's solution to this problem (the first solution ever, even in theory) is both highly convoluted and extremely slow, at least for multiplication -- I've heard numbers on the order of minutes for a single AND gate. Microsoft's solution is conceptually simpler, and much faster if you only want to multiply a few times, but as you spec it for more sequential multiplications it becomes exponentially more expensive up to some limit. Last I heard, that limit was well into the realm of the impossible ("we didn't actually compute this but it's probably more than 2^100"), so in practice you can only multiply a few times. Theoretically, it's still polynomial time even for general programs, but in practice that polynomial is far too big. IBM's solution, in contrast, starts at the "completely impractical but still possible if you really want to" level and stays there.
As far as I can tell, Microsoft has gotten around this problem by only adding numbers for their demo. For adding numbers the design is quite efficient, but there are other known solutions that work just as well or better, including classical results (RSA, Diffie Hellman and ECC all support this to some degree, and Pailler encryption supports it better). If there is any practical relevance to this design, it's that it's relatively fast and simple to do lots of additions and a few multiplications, which wasn't possible before.
It should be pointed out that there are other solutions besides FHE for encrypting on computed data, some of which border on practical. Unlike FHE, though, they require some cooperation from the party that owns the data. FHE is completely offline, so once the data is encrypted and stored, anyone can compute on it (but can't read the results).
There are several people on this thread saying that such encryption is doomed to be insecure. This is not (known to be) true. Being able to compute on encrypted data doesn't necessarily make the encryption weaker, just less efficient. You can't just "collect statistics" on the ciphertext. The encryption procedure is randomized, which prevents the most obvious attacks (anything based on testing if something is the encryption of zero). The actual algorithms used are structured around well-known and well-studied statistical/AI problems ("learning with errors"), and the parameters are set far beyond the reach of any currently-known approaches to these problems. It might be possible to break the encryption without solving LWE in full generality, but nobody knows how to do that either.
When Microsoft patents this tech, the monopoly the patent grants will kill this fundamental technology. No one else will be able to develop it. MS will not grant any license, because MS wants to own the brand of anything successful. MS will not develop it, because it's too esoteric and will take too long to become a profitable brand.
There will be no homomorphic computing. An essential component of the rest of the future of the Internet will be dead. Its corpse will be the poster child for the tyranny of monopolies.
--
make install -not war
I shake my head and wonder at you.
Homomorphic operations do not require decryption of the data. What research can you point to that demonstrates that encryption schemes used with homomorphic algorithms are ' weak enough to be cracked within reasonable execution time' ?
Your point about people being security holes is well taken, however.