Slashdot is powered by your submissions, so send in your scoop

 



Forgot your password?
typodupeerror
×
Cloud Encryption Math Microsoft Privacy The Internet Science

Microsoft Demonstrates Practical Homomorphic Computing 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."
This discussion has been archived. No new comments can be posted.

Microsoft Demonstrates Practical Homomorphic Computing

Comments Filter:
  • by rbrausse ( 1319883 ) on Tuesday August 09, 2011 @07:14AM (#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)

    • (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 (Score:4, Informative)

        by gweihir ( 88907 ) on Tuesday August 09, 2011 @07:30AM (#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.

        • Microsoft gets a lot of crap but many of their products recently have been great, especially with regard to the GUI. Windows 7 is the best version of Windows ever. It has been very stable (on proper hardware) and runs pretty quickly. Windows Home Server 2011 allows a home operator to backup the computers of his entire network onto his servers without much of a hassle.

          • by skids ( 119237 )

            Windows Home Server 2011 allows a home operator to backup the computers of his entire network onto his servers without much of a hassle.

            The only time I want my software to "allow" me to do something is when I'm crossing authentication domains. The rest of the time I would like it to "help" or "enable" me to do things.

          • I bluescreened a win7 packard bell netbook by trying to do something esoteric as... tethering an android phone (an ideos).
            I had to try with a linux machine to understand what was going on, that is tethering worked - got the ip - but the phone wasn't on the network. Just an episode of course, but not very promising given the little time i spend on win.

            Anyway... I'd take a linux desktop that crashes twice a day instead of reverting to the old days of windows in my workplace - type the license key, download th

      • Re: (Score:3, Interesting)

        by ailnlv ( 1291644 )

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

      • by gmhowell ( 26755 )

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

        So it's not as if it was on display in the bottom of a locked filing cabinet stuck in a disused lavatory with a sign on the door saying 'Beware of the Leopard'.

    • by Zouden ( 232738 )

      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

      • by jpapon ( 1877296 )

        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.

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

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

    • 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 t

  • 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?

    • by ledow ( 319597 )

      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)

      • by Threni ( 635302 )

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

          • 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

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

              • 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), th

                • 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 wil
      • by PopeRatzo ( 965947 ) * on Tuesday August 09, 2011 @08:14AM (#37031792) Journal

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

        • by ledow ( 319597 )

          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 attack

    • by gweihir ( 88907 )

      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.

      • 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
    • by vlm ( 69642 )

      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 pla

    • by smallfries ( 601545 ) on Tuesday August 09, 2011 @07:33AM (#37031436) Homepage

      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.

    • by elsurexiste ( 1758620 ) on Tuesday August 09, 2011 @07:35AM (#37031444) Journal

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

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

    • by Eivind ( 15695 ) <eivindorama@gmail.com> on Tuesday August 09, 2011 @08:18AM (#37031854) Homepage

      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.

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

    • by gweihir ( 88907 )

      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: (Score:2, Funny)

      by MightyYar ( 622222 )

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

    • by vlm ( 69642 )

      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.

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

    • by plover ( 150551 ) *

      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 cl

  • I thought it said "Microsoft Demonstrated Homophobic Computing'.
  • 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

    • by Eivind ( 15695 )

      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 ?

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

      • by mwvdlee ( 775178 )

        Or both x and y are 0.

      • Re: (Score:3, Insightful)

        by Scumbumbo ( 521718 )
        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.
        • by Eivind ( 15695 )

          Guilty as charged !

          Nevertheless, if the encryption isn't one-to-one, then by nessecity, encrypting the input must expand it. For example, if you want to encode 256 possible integers in a single byte, then your encoding MUST be one-to-one.

          And the higher the possible count, the larger the expansion. If you want each of your integers to map to one of 256 possible encrypted values, you've now doubled the size of your cleartext to get your ciphertext.

          Not that that's nessecarily a deal-killer, but it doesn't soun

  • by erroneus ( 253617 ) on Tuesday August 09, 2011 @07:37AM (#37031454) Homepage

    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 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.
    • by vlm ( 69642 )

      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 simp

    • 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, yo

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

  • by bigsexyjoe ( 581721 ) on Tuesday August 09, 2011 @07:37AM (#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.
  • 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.
  • If i only has some money to invest, stocks will be going up for the next year because of this tech.

  • 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 b

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

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

  • 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 ->
    H

    • I am just hoping that Homoerotic Encryption doesn't catch on.

  • Next they'll be wanting computers to get married!
  • OMG Microsoft actually did some basic research and with results to boot!
  • by Anonymous Coward

    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 theoretica

    • When you add and multiply encrypted data, do the different data values have to be encrypted with the same key? Or can this technique combine numbers sourced from different people each with their own encryption key?

  • 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 mon

"The following is not for the weak of heart or Fundamentalists." -- Dave Barry

Working...