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)
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
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
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.
Most ACs are not even worth the keystrokes to insult them. Be generically insulted by this and ignored otherwise.
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.
"Science flies us to the moon. Religion flies us into buildings." - Victor Stenger
I thought it said "Microsoft Demonstrated Homophobic Computing'.
Can I light a sig ?
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
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?
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!
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.
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.
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.
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.
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.
John
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.
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
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.
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.
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)
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.
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.
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
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.
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...
"Science flies us to the moon. Religion flies us into buildings." - Victor Stenger
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.
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.
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.
Next they'll be wanting computers to get married!
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).
The Tao of math: The numbers you can count are not the real numbers.
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.
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/
If they didn't do it 25 years ago it was only because no one could have been bothered; it could have been done in 2- 20 seconds then
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.
Offcourse it doesn't work on all graphs. I never claimed it would. I said I consider it likely that it'll work on interesting datasets, and gave one example of a interesting dataset - the social graph of Facebook.
It'll work on most random graphs too, but not, offcourse, graphs that are regular, such as the one you describe where every node is connected in an identical way. (another trivial example is that it won't work on the fully connected graph)
Even on a graph like facebooks, it'll not work on all nodes.
Imagine there's 2 facebook-users who have only one friend: me.
There'll be no way to tell them apart only by looking at the graph. Similar situations can arise for anyone with few friends, but it gets progressively less likely the larger your network is.
Research is all well and good, but this is a press release that basically say "we're nearly able to let you buy this", which means more scrutiny.
And my general point, in the line you quoted, is that you don't trust any form of encryption whatsoever until it's been under attack for several years by experienced cryptographers. And even then, it won't last the decade.
So claiming that you can do work on fully encrypted data safely is nothing more than a pipedream until you put out a product, and have it attacked for about a decade. Any claim of "security" before that is worthless and actually works against you (literally - the more someone insists something is "secure" before it's tested properly, the more chance it will be broken, and vice versa).
If this is research, where's the peer review? If this is a product, where's the testing by established cryptographers? If this is merely an idea, where's the document that lists potential weaknesses and exploits? The fact is, they are pushing it as a done deal - they've "achieved" this. Until dozens of people can replicate this and confirm it, it is neither computer science, nor a practical product. It is, in fact, a Microsoft claim to have a secure product. Which is worth about as much as a car salesman's promise.
A lot of this was my first thought when I read this. Math is surprisingly magical when it comes to predicting the outcome of a basic two operand operation. Given that a small amount of tinkering could provide you with the encrypted representations of known values it becomes trivial to slowly expand your dictionary and eventually reverse engineer that dictionary to discover the key for the entire data set.
Sounds to me like Microsoft has a long way to go before this is even close to being ready for the wild. Hell, the basic concept alone sounds broken from square one.
Cool post bro, highfive \o
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
Note that my suggested attack does nowhere assume that I'm encrypting a number myself. I'm taking encrypted numbers (whoever uses the service will submit such numbers), and do all my calculations with them. If all numbers used within a single calculation have the same random key (which I expect to be necessary in order to combine them without decoding), I'll likely find the two(!) numbers I need.
Of course the decrypted results will tell me nothing about the encoding used for the next submitted calculation. But that only means that I'll have to repeat the attack for each calculation separately. If I know that in this calculation, 0 is encoded by 0x12345678, it likely won't be in the next calculation. However, it doesn't need to be, I'll just take a number from the next calculation and subtract it from itself to get the new representation of zero.
The Tao of math: The numbers you can count are not the real numbers.