Forgot your password?
typodupeerror
Encryption IBM Math Security

IBM Claims Breakthrough In Analysis of Encrypted Data 199

Posted by timothy
from the scrambled-in-the-shell dept.
An anonymous reader writes "An IBM researcher has solved a thorny mathematical problem that has confounded scientists since the invention of public-key encryption several decades ago. The breakthrough, called 'privacy homomorphism,' or 'fully homomorphic encryption,' makes possible the deep and unlimited analysis of encrypted information — data that has been intentionally scrambled — without sacrificing confidentiality." Reader ElasticVapor writes that the solution IBM claims "might better enable a cloud computing vendor to perform computations on clients' data at their request, such as analyzing sales patterns, without exposing the original data. Other potential applications include enabling filters to identify spam, even in encrypted email, or protecting information contained in electronic medical records."
This discussion has been archived. No new comments can be posted.

IBM Claims Breakthrough In Analysis of Encrypted Data

Comments Filter:
  • First post! (Score:5, Funny)

    by fenring (1582541) on Thursday June 25, 2009 @02:16PM (#28469471)
    Have you seen the new neighbours. I think they're homomorphic.
  • Yeah (Score:3, Insightful)

    by rodrigoandrade (713371) on Thursday June 25, 2009 @02:18PM (#28469507)
    "might better enable a cloud computing vendor to perform computations on clients' data at their request, such as analyzing sales patterns, without exposing the original data. Other potential applications include enabling filters to identify spam, even in encrypted email, or protecting information contained in electronic medical records."

    Right, because we've already figured out everything about cloud computing and it's a totally stable environment ready to be deployed in every company around the globe. Time to take it to the next step.
    • Yeah, you can perform calculations on encrypted data without unencrypting it. But it's just a LITTLE slow. The first step is just showing it can be done, but it's a very long way from useful.

      • by SiliconEntity (448450) on Thursday June 25, 2009 @05:54PM (#28473133)

        I read the paper and my guess is that a TRILLION is actually an understatement. It looks to me like it might be almost INFINITELY slower. In other words, completely impractical and only of theoretical value.

        However, now that the first step has been taken, it's possible that someone will come up with an improvement that makes the idea practical someday.

        • Actually, the presentation (http://www.fields.utoronto.ca/audio/08-09/crypto/gentry/index.html) claims that evaluating one logic gate takes in the order of k to the 7th operations, where k is the size of the key. For 128-bit keys that's around 10 to the 15th power. Which is most definitely not infinitely slower (whatever this "informative" sentence is supposed to mean), but also not exactly practical.
  • No More Privacy (Score:5, Insightful)

    by basementman (1475159) on Thursday June 25, 2009 @02:22PM (#28469563) Homepage

    "perform computations on clients' data at their request, such as analyzing sales patterns"

    Or without their request.

    • by Magic5Ball (188725) on Thursday June 25, 2009 @02:25PM (#28469615)

      IBM researcher solves longstanding cryptographic challenge
      Posted on 25 June 2009.
      An IBM researcher has solved a thorny mathematical problem that has confounded scientists since the invention of public-key encryption several decades ago. The breakthrough, called "privacy homomorphism," or "fully homomorphic encryption," makes possible the deep and unlimited analysis of encrypted information - data that has been intentionally scrambled - without sacrificing confidentiality.

      IBM's solution, formulated by IBM Researcher Craig Gentry, uses a mathematical object called an "ideal lattice," and allows people to fully interact with encrypted data in ways previously thought impossible. With the breakthrough, computer vendors storing the confidential, electronic data of others will be able to fully analyze data on their clients' behalf without expensive interaction with the client, and without seeing any of the private data. With Gentry's technique, the analysis of encrypted information can yield the same detailed results as if the original data was fully visible to all.

      Using the solution could help strengthen the business model of "cloud computing," where a computer vendor is entrusted to host the confidential data of others in a ubiquitous Internet presence. It might better enable a cloud computing vendor to perform computations on clients' data at their request, such as analyzing sales patterns, without exposing the original data.

      Other potential applications include enabling filters to identify spam, even in encrypted email, or protecting information contained in electronic medical records. The breakthrough might also one day enable computer users to retrieve information from a search engine with more confidentiality.

      "At IBM, as we aim to help businesses and governments operate in more intelligent ways, we are also pursuing the future of privacy and security," said Charles Lickel, vice president of Software Research at IBM. "Fully homomorphic encryption is a bit like enabling a layperson to perform flawless neurosurgery while blindfolded, and without later remembering the episode. We believe this breakthrough will enable businesses to make more informed decisions, based on more studied analysis, without compromising privacy. We also think that the lattice approach holds potential for helping to solve additional cryptography challenges in the future."

      Two fathers of modern encryption - Ron Rivest and Leonard Adleman - together with Michael Dertouzos, introduced and struggled with the notion of fully homomorphic encryption approximately 30 years ago. Although advances through the years offered partial solutions to this problem, a full solution that achieves all the desired properties of homomorphic encryption did not exist until now.

      IBM enjoys a tradition of making major cryptography breakthroughs, such as the design of the Data Encryption Standard (DES); Hash Message Authentication Code (HMAC); the first lattice-based encryption with a rigorous proof-of-security; and numerous other solutions that have helped advance Internet security.

      Craig Gentry conducted research on privacy homomorphism while he was a summer student at IBM Research and while working on his PhD at Stanford University.

    • Re: (Score:3, Insightful)

      by megamerican (1073936)

      Or without their request.

      The NSA figured that out a long time ago.

    • Re: (Score:3, Informative)

      by Anonymous Coward

      Or without their request.

      If they really figured it out, then sure they can analyze without your request, but they can't decrypt the results without your key. So you still have the same privacy. BTW, this is the entire point of this process.

      • I wonder if this would make possible the following:

        Here is Encrypt(www.slashdot.org), please compute Encrypt(DNSLookup(www.slashdot.org)) so that I can then Decrypt(Encrypt(DNSLookup(www.slashdot.org))) to produce 216.34.181.48.

    • Re:No More Privacy (Score:4, Interesting)

      by mea37 (1201159) on Thursday June 25, 2009 @02:53PM (#28470073)

      TFA doesn't seem clear on this point, but what the name of the technique implies is that you can perform the operation, but neither the inputs nor the outputs are ever decrypted. So if you can't see the question, and you can't see the answer, then why would you perform the operation other than at the request of someone who can (i.e. the client)?

      That said, I'd like to know a lot more about this before I'd want to trust it. For this to work, I'd think a lot of the data's structure must be preserved. Maybe you can't detect that structure from the encrypted data, but you can probably infer a lot about it by analyzing the algorithms your clients ask you to apply (especially if they're your algorithms - i.e. software-as-a-service type stuff). I'm impressed if this doesn't create vulnerabilities.

      Also I suspect this is fundamentally divorced from public key techniques. If I'm able to encrypt values of my choosing and perform operations of my choosing on encrypted values, I'm pretty sure I can work backward to extract the cleartext from the encrypted data the client provides...

      • TFA doesn't seem clear on this point, but what the name of the technique implies is that you can perform the operation, but neither the inputs nor the outputs are ever decrypted. So if you can't see the question, and you can't see the answer, then why would you perform the operation other than at the request of someone who can (i.e. the client)?

        Example, I want the total sales figures for all the left handed employees. I cobble together the appropriate SQL processing request send it to my cloud server which rummages throught the data base summing up the figures for some subset of the fields. It sends me back just the sum, encypted. It never knows which employees it was selecting nor any of their sales figures or even the sum. It just has the encrypted result that it sends to me all processed.

        otherwise I'd have to pull every encrypted record of

        • by TheLink (130905)
          Why would you encrypt ballots?

          You should allow observers and party representatives to watch the counting of the votes.

          Requirement #0 of democratic elections: elections do not just have to be fair, they have to be seen as fair.

          Electronic voting systems fail that requirement.

          You can have simple scalable solutions like paper based voting that are easily understandable (esp on how easy and hard it is to cheat) and thus satisfy requirement #0.

          So it makes no sense to me to use electronic voting systems unless you
    • Re:No More Privacy (Score:5, Informative)

      by John Hasler (414242) on Thursday June 25, 2009 @02:56PM (#28470133) Homepage

      Everything remains encrypted throughout the process, including the output. Only the client can read the results. That is the point.

    • Re: (Score:3, Informative)

      by Mashiara (5631)

      TFA is skimp on this but after bit of Googling around I understand a little more, see also http://en.wikipedia.org/wiki/Homomorphic_encryption [wikipedia.org].

      The point being that those who provide the encrypted data must encrypt it in a special way to allow the homomorphic properties to be taken advantage of.

    • No, the Slashdot headline is, as usual, misleading. The article didn't really help explain the distinction either. This breakthrough doesn't help anybody break otherwise secure, non homomorphic cryptosystems and suddenly make them insecure. What the researcher did was be the first to create a fully homomorphic cryptosystem that allows the types of things described in the article, while still keeping certain desired information secure. This Wikipedia article [wikipedia.org] gives a much better description of the issue, and
    • Doesn't matter, you'll need to decrypt the output anyway so the analyzer won't be able to benefit from the analysis result, only the client can:
      http://en.wikipedia.org/wiki/Homomorphic_encryption [wikipedia.org]
      Using such a scheme, one could homomorphically evaluate any circuit, effectively allowing the construction of programs which may be run on encryptions of their inputs to produce an encryption of their output. Since such a program never decrypts its input, it could be run by an untrusted party without revealing it
    • But the output is encrypted. So basically you give them your sales data ( encrypted ) and they compute the results ( encrypted ). They can't understand the results they produce. Only you can decrypt the results and make use of them.
  • by grshutt (985889) on Thursday June 25, 2009 @02:22PM (#28469575) Homepage
    The abstract for Gentry's article can be found at: http://doi.acm.org/10.1145/1536414.1536440 [acm.org]
  • then that form of encryption is useless for highly sensitive information.

    It's as simple as that.

    • BAD summary (Score:5, Informative)

      by spun (1352) <loverevolutionar ... m ['o.c' in gap]> on Thursday June 25, 2009 @02:43PM (#28469889) Journal

      You can not analyze the data. You can perform calculations on it without knowing what it is. So, for instance, you could encrypt all your tax info, send it to a company that processes the encrypted data without decrypting it, and sends you back your encrypted tax return, without ever having seen any of your financial detail.

      • by master_p (608214)

        How is it possible for them to calculate the tax return if they do not analyze the data?

        • by spun (1352)

          That's the breakthrough. They add (as a made up example) E47F109A and FA619B05, coming up with 191AA7FC. They have no idea that, when decrypted with your key, those values are 51, 49, and 100 respectively. How is that possible? You'll have to read the paper, because I can't explain it :)

    • Re: (Score:2, Interesting)

      by Isarian (929683)
      So I may have missed something from the article, but are all forms of public-key encryption vulnerable or just certain algorithms?
      • Re: (Score:3, Informative)

        by Magic5Ball (188725)

        This isn't a vulnerability with existing encryption systems, it's a scheme for a different way to structure and encrypt the data to explicitly allow calculations on the data without exposing the original values.

    • then that form of encryption is useless for highly sensitive information.

      Unless the analysis is also encrypted.

    • Re: (Score:2, Interesting)

      by Anonymous Coward

      They can perform computations on the data, but the answer is still encrypted.

    • Re: (Score:3, Informative)

      by John Hasler (414242)
      All the data and all the results remain encrypted so that only the client can read the results. That is the point. Read about homomorphic encryption here [wikipedia.org]
  • Wait, what? (Score:2, Interesting)

    Okay, maybe I'm a noob when it comes to encryption, but I was under the impression that if you were able to read the encrypted email, you were probably able to read the encrypted recipient address too. Is there something I'm missing here?
    • Re:Wait, what? (Score:5, Informative)

      by moogied (1175879) on Thursday June 25, 2009 @02:37PM (#28469809)
      Yes, yes you are.

      The point is not to read the content, but to enable a computer to analyze the content in such a way that they can deduce statistics and patterns from it. FTFA:

      computer vendors storing the confidential, electronic data of others will be able to fully analyze data on their clients' behalf without expensive interaction with the client, and without seeing any of the private data

      I don't need to know that you love apples to know you definitely love the same thing as 14 other people. Lets assume that we have 20 encrypted sets of data. Lets also assume the 20 sets say basically the same thing but because of the encyrption method look nothing a like from the raw data perspective. If you go ahead and find a way to analyze the encryption enough to know that the 20 emails all contain a similar message, but not enough to actually know what the message is... well then! You could go ahead and store all of ebay's customer information and do massive amounts of data crunching for them, without ever actually seeing any data.

      This is a huge problem in IT, where admins need access to the databases in order to see how the data is being stored, how the tables are working, etc etc.. but can't actually have access to the database because then they might see customer information. So you either let joe-bob admin in there and let him see all the data, or you don't. Now you can let the admin in there, they can determine anything they might want to know, but they never actually see any exact data.

      No, I don't know anything about the math portion.. but thats basically what they are trying to say in the article. I think. :)

      • Yes, yes you are.

        The point is not to read the content, but to enable a computer to analyze the content in such a way that they can deduce statistics and patterns from it.

        I'm not crypto-geek, but aren't patterns generally the bane of encryption?

      • by Cyberax (705495)

        Implausible. Changing just one bit results in an 'avalanche effect' in good ciphers, so quite a lot of bits will be changed.

        You won't be able to derive any useful information from that.

      • Fair enough, but how is that better than just "anonymizing" data from a database through a one-way hash and then removing all directly identifiable info (client ID, etc)?
      • by e-scetic (1003976)
        If I encrypt my data, and I like apples, and I can now use this new technique to determine that 20 other people like apples too, don't I have an essential piece of information I can use to decrypt the encrypted data of those 20 other people?
        • Homomorphic encryption does not give you any such ability.

          • Okay... So what if I like apples. And I have a username that starts with S. Now we've already established that I can see how many other people like apples. Can I see how many other people like apples that have usernames that start with S? And then can I see how many other people like apples, and have usernames that start with 'Sp'? I'm sure you see where I'm going with this. I may just be a cynical bastard with a math education insufficient to understand the technique by which this works, but it soun
            • by mhall119 (1035984)

              You can only see if 20 other people like apples if that plaintext data was encrypted with the same key as the plaintext data that says you like apples.

              Suppose Coca-Cola and Pepsi Cola both use the same Market Research firm, which we'll call StatisticsInc. Now, companies are very jealous of market insight data, most will not work with a firm that also works with a competitor, lest someone get bribed into sharing trade secrets. What this allows if for Coca-Cola to sent a bunch of demographic data to Statist

      • Now you can let the admin in there, they can determine anything they might want to know, but they never actually see any exact data.

        If they can determine "anything they might want to know" about the data, that is exactly equivalent to having full access to the data. So if that's what this offers, for a 12 order of magnitude performance hit, I'm not impressed.

  • by Anonymous Coward on Thursday June 25, 2009 @02:31PM (#28469701)

    Just FYI this site is whole sale cut and paste ripping IBM press off.

    http://www-03.ibm.com/press/us/en/pressrelease/27840.wss

    • Re: (Score:2, Informative)

      Uhh... I'm not sure how to break this to you, but WHOLE POINT of a PRESS RELEASE is that it gets sent out to the press, in the hopes that websites and newspapers will reprint it. That's why IBM published it in the first place. So, yeah, it's not plagiarism, sorry.
      • Yeah, but it's kind of nice to hope that the news vendor will add some of their own analysis rather than simply regurgitating a press release. Foolishly optimistic, in most cases, but nice nonetheless.

  • I bet multi-modal reflection sorting can determine what the confidential info is.

  • by Dr. Manhattan (29720) <sorceror171@gmaiSTRAWl.com minus berry> on Thursday June 25, 2009 @02:41PM (#28469871) Homepage
    With fully homomorphic encryption [wikipedia.org], you can perform operations on the encrypted data, in encrypted form, that produces encrypted output. Sort of like doing a database query on encrypted data, that produces an encrypted result. So you could store your data somewhere in encrypted form, ask the host to perform some operations using their CPU cycles, and send you the result. You decrypt the result yourself, the host never sees unencrypted data at any point.

    Cool, but I'm half-convinced that holes will be found. The first time a new encryption scheme is put to the test, it usually fails. Still, hopefully, it'll lead to a truly secure scheme.

    • by SUB7IME (604466)
      Yes, you may, until 1==0.
    • f(x) = x

      No. The operations you get are addition and multiplication, that's it. Given E(x) and E(y), you can compute E(x + y) or E(xy), nothing else. And you do this without ever learning x or y. RTFWA [wikipedia.org].

      The reason for the terminology is that the encryption function E is a ring homomorphism [wikipedia.org] between plaintext and ciphertext. Some operation of addition is defined on both plaintext and ciphertext such that if x and y are plaintext, f(x + y) = f(x) + f(y). (The "+" on the left is addition of plaintext, the "+" on the right is addition of ciphertext: two totally different operations.) Multiplication is similar. You don't get to apply arbitrary homomorphisms to the data, it's the (predetermined) encryption function that's the homomorphism.

      Actually, I don't see any mention of subtraction -- so maybe it's really a semiring homomorphism. With an actual ring homomorphism you'd also have f(x - y) = f(x) - f(y), and some 0 element with f(0) = 0. And maybe f(1) = 1, depending on definition.

  • simple explanation (Score:5, Informative)

    by Anonymous Coward on Thursday June 25, 2009 @02:54PM (#28470091)

    OK, it looks like a lot of people are missing the point.

    What Gentry figured out was a scheme for carrying out arbitrary computations on encrypted data, producing an encrypted result. That way, you can do your computation on encrypted data in the "cloud", but only you can view the results.

    If E() is your encryption function, x is your data, and f() is the function you'd like to compute, homomorphic encryption gives you a function f'() such that f'(E(x)) = E(f(x)). But at no point does it actually decrypt your data.

    This could be huge for secure computing.

    • by TypoNAM (695420)

      If E() is your encryption function, x is your data, and f() is the function you'd like to compute, homomorphic encryption gives you a function f'() such that f'(E(x)) = E(f(x)). But at no point does it actually decrypt your data.

      Got an example in C language instead?

      • by Lunzo (1065904)

        Replace the = with ==. You now have it in C.

        Joking aside GP was talking mathematical functions, which is quite appropriate given the context - theory underpinning cryptography.

    • by cenc (1310167)

      Perhaps I am a bit slow and stupid, but is this not like running an encrypted virtual machine or at least could be done in some sort of encrypted virtual machine? Something where the underlying hardware and OS does not know what the processes and data are at the higher level.

    • What Gentry figured out was a scheme for carrying out arbitrary computations on encrypted data, producing an encrypted result. That way, you can do your computation on encrypted data in the "cloud", but only you can view the results

      The other direction--letting the server do secure computation on the client, is also very interesting. Consider an MMORPG. One of the problems in MMORPG is cheat programs. These can be particularly troublesome in a PvP game. For example, there were programs for Dark Age of Camelot that would show you every enemy player in a large bubble around you, regardless of any obstacles blocking line of sight or the use of stealth abilities.

      The obvious solution for this is that the server should only send player posit

    • Isn't there some restriction on your "f" function? For example, it might be nice to compute a diff between two encrypted files, but the resulting size of the diff could reveal a lot of information and thus make the system insecure.

  • At first... (Score:4, Funny)

    by curtix7 (1429475) on Thursday June 25, 2009 @03:00PM (#28470195)
    I thought I was being childish when i thought to myself "tehee homo-morphic,"
    but after RTFA my suspicions may be justified:

    Two fathers of modern encryption...

  • Basically, IBM has created a set of cryptographic algorithms that allow fully homomorphic encryption. If you don't want your data to be analyzed, all you have to do is use an algorithm that doesn't support it. You'd want to do that anyway, since you'd want to use algorithms that are already considered strong, such as RSA and AES. Although RSA is homomorphic in theory, in practice it is not, since padding is used to prevent other weaknesses.

  • Fully homomorphic encryption is a bit like enabling a layperson to perform flawless neurosurgery while blindfolded, and without later remembering the episode.

    Oh, I get it! It's like when Dr. McCoy reinstalled Spock's brain. McCoy was an idiot before, got the 1337 skillz, and then forgot it all.

    • Fully homomorphic encryption is a bit like enabling a layperson to perform flawless neurosurgery while blindfolded, and without later remembering the episode.

      I remember the episode: Spock's Brain [memory-alpha.org].

  • I don't suppose the researcher's name was Janik?

  • Homomorphism (Score:5, Insightful)

    by NAR8789 (894504) on Thursday June 25, 2009 @03:51PM (#28470903)

    This article needs some clarification. In particular, a lot of the worried comments here show a lack of understanding of the word "homomorphic".

    Here's a very simplified example of a homomorphism. I define a function
    f(x) = 3x
    This function is a homomorphism on numbers under addition. Its image "preserves" the addition operation. What I mean more precisely is
    f(a) + f(b) = f(a + b)
    That's pretty easy to verify for the function I've given.

    Homomorphic encryption is interested in an encryption function f() that preserves useful computational operations. If we take my example as a very very simplified encryption then, say I have two numbers, 6, and 15, and I lack the computational power to do addtion, but I can encrypt my data with my key--3. (I'm generalizing my function to be multiplication by a key. And yes, for some reason I have the computational power to do multiplication. Humor me). I can encrypt my data, f(6) = 18 and f(15) = 45, and pass these to you, and ask you do do addtion for me. You'll do the addition, get 63, and pass this result to me, which I can then decrypt, which yields 21.

    Now, my encryption here is very simple and very, very weak, but if you're willing to suspend disbelief, you'll note that the information I've allowed you to handle does not reveal either my inputs or my outputs. (In fact, with the particular numbers I've chosen, you might guess that my key is 9 instead of 3, (though relying on lucky choices or constraining myself to choices which have this property make my scheme rather useless))

    If you generalize this to strong encryption and more useful computational operations, you begin to see how homomorphic encryption can be useful. One should note that, no, homomorphic encryption will not be a drop-in replacement for other forms of encryption. (Sending encrypted emails with homormorphic encryption would be unwise. An attacker can modify the data (though, if my understanding is correct, only with other data encrypted with the same key)) Homomorphic encryption simply fills a need that the other forms do not serve.

    Hopefully you now also see how the article's use of the word "analysis" can be rather misleading. In particular, one of the earlier comments notes that it might be useful in allowing you to determine if different people's encrypted information is identical. By my understanding, homomorphic encryption would not allow this.

    In any case, if my explanation is not enough, here [wikipedia.org]'s the wikipedia article.

    • Re:Homomorphism (Score:4, Informative)

      by Simetrical (1047518) <Simetrical+sd@gmail.com> on Thursday June 25, 2009 @09:50PM (#28476175) Homepage

      Here's a very simplified example of a homomorphism. I define a function

      f(x) = 3x

      This function is a homomorphism on numbers under addition. Its image "preserves" the addition operation. What I mean more precisely is

      f(a) + f(b) = f(a + b)

      That's pretty easy to verify for the function I've given.

      But examples like you gave (semigroup homomorphisms) have existed for a long time. Basic RSA has that property. The key advance here is that you have a semiring homomorphism, where it preserves two operations, one of which distributes over the other. Like multiplication and addition, or bitwise and and xor. (For those who don't follow: x*(y + z) = x*y + x*z, x & (y ^ z) = (x & y) ^ (x & z). If you don't believe the second identity, try all possibilities.)

      An example of a semiring homomorphism on the reals is f(x) = -x. Then f(x + y) = -(x + y) = f(x) + f(y), and f(xy) = (-x)(-y) = xy = f(x)f(y). (Unless you believe in Time Cube.)

      It seems distributivity is enough to do complicated calculations. You could simulate and and xor gates, I guess. Then you could get ~x = x ^ -1, x | y = ~(~x & ~y), etc.: all possible binary operations. That's enough to build a virtual computer right there, all operating on encrypted data.

      Of course, the one running the code would be able to figure out exactly what algorithm you're using. So it's not perfect. But it's pretty cool regardless.

    • by master_p (608214)

      Thank you for the explanation. Here is a shorter explanation: using homomorphic encryption, mathematical operations on encrypted data can produce results which are themselves encrypted by the same encryption code.

  • What are the operations for which this is homomorphic?

    It has to be quite limited. Otherwise for example, lets suppose I have an integer (encrypted of course) and I have comparison and addition/subtraction and multiply/divide.

    I can very easily find the encrypted values of both 0 (a-a for any a) and 1 (a/a)

    I can now decrypt the data with repeated additions (or subtractions) of 1 and equality comparisons.

    And, I don't see how you can prevent equality tests in the encrypted domain. You might have to calc

    • Re: (Score:3, Informative)

      by SiliconEntity (448450)

      What are the operations for which this is homomorphic?
      It has to be quite limited. Otherwise for example, lets suppose I have an integer (encrypted of course) and I have comparison and addition/subtraction and multiply/divide.

      I can very easily find the encrypted values of both 0 (a-a for any a) and 1 (a/a)

      The article neglected to mention that the underlying encryption system is randomized public key encryption. This means (A) you can easily discover encryptions of 0, encryptions of 1, and encryptions of anyt

    • So I don't see how the operations available can be as much as the usual operators on reals.

      The idea seems to make the operations map to something like & and ^, so that you can recover all logical operators and make a virtual computer using them. & and ^ on the integers may not seem as powerful as * and + on integers/floating points/etc., but you can easily encode the latter as the former.

  • by rlseaman (1420667) on Thursday June 25, 2009 @05:05PM (#28472339)

    A lot of respondents seem to have seized on a spurious notion of what this is all about. That isn't surprising since the Slashdot article and the press release and even the abstract are rather obscure. No sign of a preprint, but the same abstract shows up for a number of colloquiums in the last couple of months. The paper is from a proceedings, so it may itself not be especially profound.

    The abstract says: "We propose a fully homomorphic encryption scheme -- i.e., a scheme that allows one to evaluate circuits over encrypted data without being able to decrypt. Our solution comes in three steps. First, we provide a general result -- that, to construct an encryption scheme that permits evaluation of arbitrary circuits, it suffices to construct an encryption scheme that can evaluate (slightly augmented versions of) its own decryption circuit; we call a scheme that can evaluate its (augmented) decryption circuit bootstrappable."

    The encryption and compression literature tends to use the word "scheme" where others might say algorithm or transform. "Circuits" here is a term of art (maybe arising originally from actual physical circuits, as in the Enigma machine?)

    "An encryption scheme that permits evaluation of arbitrary circuits" suggests only that the possessor of the private key can generate these arbitrary queries, not that anybody and their brother can scavenge the encrypted data. It isn't stated whether such a query also requires the plaintext. It would be pretty cool if one feature were to be able to discard the plaintext post-encryption.

    The gimmick appears to be that the arbitrary circuit can include the decryption itself (the bootstrap part). Note that this feature is far more cool (assuming it works) than all the nonsense about cloud computing. Somehow the data are *arbitrarily* available to properly encoded queries without ever being exposed - even to the CPU performing the operations. This processor could be on the same machine, on some remote server, in the cloud or across the galaxy. How cool is that?

  • makes possible the deep and unlimited analysis of encrypted information -- data that has been intentionally scrambled -- without sacrificing confidentiality."

    This is nonsense: unlimited analysis being possible is the same thing as confidentiality being sacrificed.

    Maybe there is something significant and important here, but TFA doesn't provide a clue as to what it is.

  • I downloaded the PDF paper and it says "We omit full details due to lack of space...". Doh!!!

    What use is an ACM account when white papers "omit full details"?

    Well I suppose they don't have to kill me as they omitted the full details... that's something at least.

  • Wouldn't this sort of analysis of the encrypted data potentially provide clues of its nature that would help in the decryption of the data? Seems to me that this new analysis method weakens ALL POSSIBLE encryption techniques...
  • by SiliconEntity (448450) on Thursday June 25, 2009 @07:47PM (#28474789)

    A few misconceptions continue to circulate here; let me try to shed some light.

    First, the encryption system is apparently not practical in its current form. Maybe improvements will occur some day to make it practical, maybe not. It is still a major theoretical breakthrough because fully homomorphic encryption had often been thought to be impossible in the past. It has been a long sought goal in cryptography and it is remarkable to see it finally achieved. So in practice nobody is going to be doing spam filtering, income tax returns, or anonymous google searches any time soon.

    Second, several people have gotten tripped up over an apparent weakness: if you can calculate E(X-Y) you can get an encryption of 0; if you can calculate E(X/Y) you can get an encryption of 1; and from these you could get other encryptions and potentially break the system. This idea fails for two reasons: first, it is a public-key system, so you don't need to go through all this rigamarole to get encryptions of 0, 1, or anything. In public key cryptography, anyone can encrypt data under a given key, without knowing any secrets. So it is already possible to get encryptions of known values, even without the special homomorphic properties. Second, in order for public key systems to be secure, they need to have a randomization property. In randomized encryption, there are multiple ciphertext values that encrypt the same plaintext. Basically, the encryption algorithm takes both the plaintext and a random value, and produces the ciphertext. Each different possible random value causes the same plaintext to go to a different ciphertext. The decryption algorithm nevertheless can take any of these different ciphertext values and produce the same plaintext.

    This may be confusing because the most well known public key encryption system, RSA is not randomized. At the time it was invented, this aspect was not well understood. Shortly afterwards it became clear how important randomization is. Other encryption systems like ElGamal do use randomization, and RSA was adapted to allow randomization via what is called a "random padding" layer, known by the technical name PKCS-1. This adds the randomness which allows RSA to be used securely.

    One other point is that people are getting hung up about what "fully" homomorphic encryption covers. Exactly what operations can you do? I think the best way to think of it is to go down to the binary level. We know that in our computers, at the lowest level everything is 1's and 0's. These get combined with elementary logical operations like AND, OR, NOT, XOR, and so on. Using these primitive operations, all the complexity of modern programs can be built up.

    In the case of the homomorphic encryption, it is probably best to think of the values being encrypted in binary form, as encryptions of 1's and 0's. Keep in mind the point above about randomized encryption: all the encryptions of 1 look different, as do all the encryptions of 0. You can't tell whether a given value encrypts a 1 or a 0. Given these encrypted values, you can compute AND, OR, XOR, NOT and so on with these values, and get new encrypted values as the answers. You don't know the value of the outputs, they are encrypted. Only the holder of the private key, who originally encrypted the data, could decrypt the output. But you can continue to work with these output values, do more calculations with them, and so on.

    Let me give an example of how you could do an equality comparison. Suppose you have two encrypted values and want to determine if they are the same. Recall that we are working in binary, so you actually have two sequences of encrypted bits; some are encrypted 1's and some are encrypted 0's, but you can't tell which. So the first thing you compute is the XOR of corresponding bits in the two values: XOR the 1st bits of each value; XOR the 2nd bits of each value, and so on. Now if the values are equal, the results are all encryptions of 0's. If the values are different, some of the results will be encryptions of 1's. But aga

I tell them to turn to the study of mathematics, for it is only there that they might escape the lusts of the flesh. -- Thomas Mann, "The Magic Mountain"

Working...