Beta
×

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

Thank you!

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

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

IBM Researchers Open Source Homomorphic Crypto Library

timothy posted about a year ago | from the z-plus-n-equals-of-course-q dept.

Encryption 130

mikejuk writes with news of an advancement for homomorphic encryption and open source: "To be fully homomorphic the code has to be such that a third party can add and multiply numbers that it contains without needing to decrypt it. In other words they can change the data by working with just the encrypted version. This may sound like magic but a fully homomorphic scheme was invented in 2009 by Craig Gentry. This was a step in the right direction but the problem was that it is very inefficient and computationally intensive. Since then there have been a number of improvements that make the scheme practical in the right situations Now Victor Shoup and Shai Halevi of the IBM T J Watson Research Center have released an open source (GPL) C++ library, HElib, as a Github project. The code is said to incorporate many optimizations to make the encryption run faster. Homomorphic encryption has the potential to revolutionize security by allowing operations on data without the need to decrypt it."

cancel ×

130 comments

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

Marriage equality (5, Funny)

Anonymous Coward | about a year ago | (#43612235)

All cryptos should be able to marry any other crypto. Anyone that is homomorphic should really broaden their horizons.

Re:Marriage equality (0, Offtopic)

Jeremiah Cornelius (137) | about a year ago | (#43612349)

Next, they'll want the right to encrypt dogs... and children.

Re:Marriage equality (0, Offtopic)

fustakrakich (1673220) | about a year ago | (#43612389)

No no, it's horses [buzzfed.com]

Re:Marriage equality (0)

Anonymous Coward | about a year ago | (#43612773)

So you are a bigot as well as a spammer? Nice.

Re:Marriage equality (0, Offtopic)

davester666 (731373) | about a year ago | (#43613223)

or dogs with children.

or terrorists!

Re:Marriage equality (1, Interesting)

lgw (121541) | about a year ago | (#43612475)

Since the first 5 posts are all "homo" jokes, I'm gonna squat here for my on-topic post (heh ... heh ... he said squat).

The main problem I see with the whole idea of homomorphic encryption is it's necessary limitations. If I can get the plaintext results of the difference (subtraction) of the plaintext of two encrypted strings, I can trivially decrypt both if they're English text. (Obviously if I know one of the strings, but less obviously adding, subtracting, or XORing two strings is a trivial cypher these days, more of a compression algorithm really.)

If I can compare two strings, or sort a set of strings in plaintext order, that leaks a lot. If I can compare substrings, and have a large set of strings to work with, that's probably enough to decrypt all the strings in the set (again assuming English or some natural language text, not arbitrary GUIDs).

In order to preserve encryption, the set of operations you can perform on an encrypted DB table without decrypting has to be kept small. Most of the stuff you'd really want to do, like alerting when the value in a column exceeds a bound, or any sort of aggregation of results, must be disallowed. Sure, you can blindly increment or decrement a value, but you can't test the result in any way.

As much as it would be cool for me to be able to stick data in the cloud, encrypted so the provided can't read it, but still have the provider do data grooming for me - you just can't have both.

Re:Marriage equality (5, Informative)

cryptizard (2629853) | about a year ago | (#43612543)

I think you are misunderstanding. What homomorphic encryption allows is for you to obtain the encrypted sum or product of two ciphertexts. That is, there exists some efficient operation o such that E(a) o E(b) = E(a+b) and another operation u such that E(a) u E(b) = E(a*b). What you are describing is closer to functional encryption, in which case the function which you are allowed to evaluate over the ciphertexts is severely limited and must be explicitly granted by the owner of private key.

Re:Marriage equality (4, Interesting)

Samantha Wright (1324923) | about a year ago | (#43612579)

...and from there, you can go on to implement just about any mathematical operation, as long as you encrypt all of your operands first and don't mind an ungodly number of steps just to do a simple division. The algorithm implementer has to be more trusted than the hardware provider, though, to get arbitrary operations done.

Re:Marriage equality (1)

cryptizard (2629853) | about a year ago | (#43612667)

Correct, but how does this relate to the above comment?

Re:Marriage equality (1)

Samantha Wright (1324923) | about a year ago | (#43612793)

I was explaining for the layperson how you would actually put such a scheme to use, as not everything can be directly reduced to the addition and multiplication of matrices. Imagine there is a post between yours and mine asking "what good is that?"

Re:Marriage equality (1)

cryptizard (2629853) | about a year ago | (#43612839)

Gotcha :D It is actually not that bad to do division though, depending on your definition of division. Usually these schemes operate over a finite field, where division is just multiplication by an inverse element. If you mean floating point division, then yeah that would be a mess I suppose.

Re:Marriage equality (0)

Anonymous Coward | about a year ago | (#43612913)

...as long as you encrypt all of your operands first ...

And therein lies the problem I can't get over. They can't do anything without you providing all the numbers they need, your encryption key, or the encrypted value of "1" (from which the can compute any other number's encrypted value - though also determine the value of any other encrypted number you've given them.

They couldn't even give you the average of a stream of numbers without you providing the encrypted count value.

Unless this also works with public key crypto, then the public key would be enough to get an encrypted operand. Does it?

Re:Marriage equality (2)

cryptizard (2629853) | about a year ago | (#43613955)

It can be made public key. It is also semantically secure, so knowing the plaintext value of any one ciphertext gives you no information about the value of other ciphertexts.

Re:Marriage equality (1)

Samantha Wright (1324923) | about a year ago | (#43613991)

Honestly, I hope it doesn't work with a public key, because then you could just brute-force all integers, and for a hundred times the same computational effort, all currency values. Public-key crypto makes the exposure problem worse.

Re:Marriage equality (3, Interesting)

cryptizard (2629853) | about a year ago | (#43614335)

Nah because it is also semantically secure [wikipedia.org] . For every plaintext value, there are lots and lots of different ciphertext values (it is a one-to-many mapping). So many, in fact, that knowing the plaintext value of any particular ciphertext doesn't give you any good information.

You do have the problem that anyone can come up with any valid ciphertext and jam it into your computation wherever they want, but we have some other cool stuff for verifying that only authenticated ciphertexts were used and that the function the guy evaluated was the one he was supposed to do. Lots of very cool stuff :-)

Re:Marriage equality (2)

DuckDodgers (541817) | about a year ago | (#43613217)

Steve Gibson did a podcast in which he tried to put homomorphic encryption in layman's terms ( here, about 25 minutes in is the meat of the discussion: http://twit.tv/show/security-now/376 [twit.tv] ). What he said was possible, but didn't explain even in general terms, would be a distributed encrypted search engine in which you could send search request into it and get results, and the company hosting the service would not even know what you searched for.

I don't understand how you get from encrypted inputs and a mathematical operation that occurs without decrypting the inputs to a distributed search.

Re:Marriage equality (1)

Samantha Wright (1324923) | about a year ago | (#43613895)

I think it would depend on not knowing what the search index itself contained. You could deduce patterns ("this person keeps searching for x, the query keeps returning these pages") but not directly infer the content. Page hits would be ranked by multiplying topic relevance scores. It would be a much simpler algorithm than PageRank, but still feasible for keyword search.

Re:Marriage equality (5, Interesting)

cryptizard (2629853) | about a year ago | (#43614091)

Sure, that's pretty easy. We can even do it without homomorphic encryption (do a google scholar search for encrypted keyword search, there is lots of stuff with varying levels of security and utility). A quick explanation, which might convince you, is that you can actually run any program you can think of using fully homomorphic encryption.

First, suppose that any program can be written down as a circuit (it can). Now, we know from boolean theory that AND gates and XOR gates are functionally complete, that is any circuit you can write with other gates, you can rewrite with only AND and XOR gates. You might know it with AND and NOT gates, but it is easy to show that XOR can actually implement NOT so that also works. Now, with two bits, AND is really just multiplying the bits (1 AND 1 = 1, any other combo has at least one zero and is 0). XOR, on the other hand is just adding the bits, with the weird case that 1 + 1 = 0, which actually is bitwise addition ignoring the carry (mod 2). So, now we can implement any program as a circuit, any circuit with only AND and XOR gates, and we can do those AND and XOR gates with addition and multiplication. Therefore, we can do anything we want over homomorphically encrypted ciphertexts, with a suitable compiler that will translate our program into those operations!

Now that is a very general construction, so it might not be particularly interesting to your problem, but what it does show is that we can really do anything over the encrypted inputs that we could do with unencrypted inputs. Since Google can run their search algorithm over your unencrypted query, they would also be able to do it over your encrypted query.

Re:Marriage equality (1)

goombah99 (560566) | about a year ago | (#43614331)

I don't understand how you get from encrypted inputs and a mathematical operation that occurs without decrypting the inputs to a distributed search.

There's a lot of gotcha's here but let me give you the gist. When you do a search something like this happens (encrypted or not), your query gets hashed into some feature vector of ones and zero. You can imagine the bits of this feature vectors like 20 questions (first bit: is it alive...) etc. The search company then AND this feature vector against every feature vector of the web pages it has scanned. The ones with a good match are returned to you. That's of course a naive version of searching.

If we could do that encoding operation on the client or by a trusted third party then encrypt the feature vector, you can send this to the data base holder to do all the AND operations for you and return all the scores. You could then decrypt that and pick the records you want to fetch.

Naively that works. But it has a lot of holes in it. For example, you'd have to have the database encrypted differently for every client and not tell the server company the key to do that. But that's a detail that can be fixed in other ways that are not so hard.

The point is you can search your data stored in the cloud without the server knowing what you searched for in the database.

Re:Marriage equality (1)

lgw (121541) | about a year ago | (#43613853)

What homomorphic encryption allows is for you to obtain the encrypted sum or product of two ciphertexts

Right, but what good is that? The only scenario in which this stuff is going to come up is hosted/cloud data stores, where the tenant has the keys and the host doesn't (or the moral equivalent thereof in purely internal datacenters where one team must keep data secret from the IT department).

So, as the owner of the data, I have the keys and can already do everything I need. Clever encryption could I theory allow the owner of the hardware to offer various bulk data grooming services, where my data could be processed in some useful way without needing to reveal my key. But in practice I can't think of any such services that could be valuable without access to operations that would necessarily leak information.

Re:Marriage equality (2)

Rich0 (548339) | about a year ago | (#43614213)

Well, I imagine they might be useful for solving some esoteric encryption problems. Imagine I have a document that is digitally signed by somebody you trust, but I don't want to share the whole thing with you. I want to redact the document, and then have the non-redacted parts still be signed. Maybe functions like these might let me derive a new signature for the redacted content in a way that tells the recipient that the unredacted part is valid, but that it wasn't the original either.

I don't know that anybody has come up with a way to solve that particular problem - I just use it as an example of the sort of case where being able to manipulate encrypted data without a key could be useful. There are lots of cases where you want groups of people to be able to work with data where no individual has all the keys, but some group of individuals can still read it, and this falls into the same sort of category of interesting techniques that might solve very particular problems.

Re:Marriage equality (4, Informative)

cryptizard (2629853) | about a year ago | (#43614277)

So, let me first say that the main selling point for this technology is that it allows you to outsource your computation. You can use a low powered device like a cell phone and take advantage of more powerful computation in the cloud, while maintaining data privacy. You are correct that certain things will be leaked, like if I am storing encrypted email and I search for all emails sent by so-and-so then the server would learn how many emails I have from that guy. This is still a huge advantage over what we have now.

Now, I can outline a cool use that you probably have not thought of which is a little different. Imagine that a server is storing some really sensitive stuff for me. Obviously I don't trust the server so I am encrypting all my files. If he is really sneaky, however, he can learn something about the contents of those files by watching when, where and how often I access them. We call this the access pattern, and usually people just write this off as a cost of doing business. However, with homomorphic encryption we can hide even that!

Since I can evaluate any program homomorphically over my data, I write a program that says "return file number x" and give it an encrypted value, say 50, for x. The server now evaluates this program, with my encrypted 50, over the entire set of files. What he gives back to me is my file that I wanted, but from his point of view he can't actually tell which file he gave me! All he knows is he ran a circuit over all the files in the database, with my input that specifies which one I want, but he can't tell what my input is because it is encrypted.

Re:Marriage equality (0)

Anonymous Coward | about a year ago | (#43613301)

If I can get the plaintext results of the difference (subtraction) of the plaintext of two encrypted strings, I can trivially decrypt both if they're English text.

But what if they're both Chinglish text? Can you decrypt that? Can anyone?

MOD PARENT DOWN (2)

kumanopuusan (698669) | about a year ago | (#43614069)

You obviously haven't even read the wikipedia article on homomorphic encryption, much less any of the relevant papers. Every single thing you said was wrong.

Re:MOD PARENT DOWN (1, Interesting)

lgw (121541) | about a year ago | (#43614187)

You obviously haven't even read the wikipedia article on homomorphic encryption, much less any of the relevant papers. Every single thing you said was wrong.

Care to actually add something to the discussion. I listed a few things one couldn't do with homomorphic encryption, but would be needed do do anything useful with the encrypted data. Yes, I know full well you can't do those things (e.g., you can't get the plaintext difference between two encrypted strings), which is precisely what I'm complaining about.

Since there's no way for me to tell is a value if greater than X (since that would leak in ways that homomorphic encryption doesn't), I can't send alerts when encrypted data passes an alarm threshold X, or delete email older than X (assuming that metadata is encrypted).

So, anyone, please give some examples of useful processing that someone without the key could do with the data? What is this actually useful for?

Re:MOD PARENT DOWN (3, Insightful)

chihowa (366380) | about a year ago | (#43614499)

Your understanding of what homomorphic encryption is is fundamentally incorrect. If you apply an operator to an encrypted value in a homomorphic system, the result is also encrypted. So, since the initial values and the results are both encrypted, no information is leaked.

Your entire missive above was predicated on the fact that the results of the function would be plaintext, so as the GP so eloquently put it, "Every single thing you said was wrong." Seriously, the first sentence of the wikipedia page [wikipedia.org] makes it fairly clear:

Homomorphic encryption is a form of encryption which allows specific types of computations to be carried out on ciphertext and obtain an encrypted result which decrypted matches the result of operations performed on the plaintext.

Re:MOD PARENT DOWN (4, Informative)

cryptizard (2629853) | about a year ago | (#43614503)

Nobody said these things weren't possible, just that homomorphic encryption out of the box does not do them. There are recent techniques for functional encryption, which use FHE as a component, that allow these exact scenarios. As you pointed out though, you have to be very careful if you don't want to ruin security. The way they work now, you can supply a server with a specific token which allows him to evaluate one very specific function on your encrypted data and get the plaintext result of that function. For instance, you could give your email server a token which allows him to run spam filtering over your incoming emails and output a plaintext bit which is '1' if it is spam and '0' if it is not. The security property of these schemes is that you cannot learn any information other than the output of this function run over encrypted data. It is veeery tricky at this point because you could leak some dangerous information unknowingly, but the techniques do exist.

Re:Marriage equality (4, Insightful)

goombah99 (560566) | about a year ago | (#43614207)

Since the first 5 posts are all "homo" jokes, I'm gonna squat here for my on-topic post (heh ... heh ... he said squat).

The main problem I see with the whole idea of homomorphic encryption is it's necessary limitations. If I can get the plaintext results of the difference (subtraction) of the plaintext of two encrypted strings, I can trivially decrypt both if they're English text.

Well no.
here's just one possible way to deal with that. For each string you form two different strings by XOR the string with a random string and the complement of that random string. Now You encrypt each String in the pair with a different key in a homomorphic way.

A third party can now do whatever albelian operations they want on either of these strings but they have no way to combine the two results since the keys are different.

However you are able to do this by doing the operations on both strings then at the very end decrypting them and Xoring the result.

Voila.

Works for voting systems where one person gets to have the keys, and one person gets to maintain the database of encrypted votes. As long as they don't collude, then the data base holder can sum all the ballots up but not know what any ballot is. The key holder can determine the sum but never get access to the individual ballots.

MOD parent UP (0)

Anonymous Coward | about a year ago | (#43614487)

good explanation!

Re:Marriage equality (0)

Anonymous Coward | about a year ago | (#43613077)

that is very funny!

Say what? (-1)

frovingslosh (582462) | about a year ago | (#43612259)

Who you callin' homomorphic?

Re:Say what? (0, Offtopic)

Anonymous Coward | about a year ago | (#43612325)

Your cryptographic orientation is your own business.

well... (-1)

Anonymous Coward | about a year ago | (#43612285)

Homo works for Rob Malda...

Re:well... (0)

Anonymous Coward | about a year ago | (#43612829)

Reminds me of the joke...

Q: Is CmdrTaco gay?

A: He mos' certainly is!

This is not going to (-1)

Anonymous Coward | about a year ago | (#43612323)

end well

I dunno.. (-1, Offtopic)

ComputerPhreak (1057874) | about a year ago | (#43612337)

this release sounds pretty homo to me

Good news ciphercloud! (2)

GameboyRMH (1153867) | about a year ago | (#43612401)

Now you can start offering non-jokey encryption!

Sounds impractical (1, Informative)

mark-t (151149) | about a year ago | (#43612423)

How the heck can you know what operations you needed to perform on the data in the first place if you don't actually know what the data was?

Re:Sounds impractical (1)

X0563511 (793323) | about a year ago | (#43612459)

Easy - you write the algorithm with unencrypted data. That's the fun part about your computer being deterministic and all...

Re:Sounds impractical (1)

fahrbot-bot (874524) | about a year ago | (#43612647)

That's the fun part about your computer being deterministic and all...

Well... your computer anyway, not mine [wikipedia.org] . :-)

Re:Sounds impractical (1)

betterunixthanunix (980855) | about a year ago | (#43612701)

Interestingly, there is some evidence that today's FHE systems are secure against quantum computing attacks.

Re:Sounds impractical (1)

Anonymous Coward | about a year ago | (#43612517)

If you're just storing ERP data for customers you can manipulate it without knowing what the data is, only people with passwords would have access to what the data actually is.

Re:Sounds impractical (1)

Em Adespoton (792954) | about a year ago | (#43612529)

How the heck can you know what operations you needed to perform on the data in the first place if you don't actually know what the data was?

The summary doesn't really explain this that well... the benefits here (if I'm reading this correctly) are that someone with a HUGE block of ciphertext and the encryption key can modify slices in situ without having to decrypt the large block and re-encrypt. They can just swap out the old data for the new, based on the index.

This begins to have significant benefits when applied to hosted computing (called Cloud Computing this decade), where, say, all your email is stored encrypted, as is the email index, and you just want to add/remove something without decrypting the entire blob. It also means that cloud hashing becomes significantly easier, as does filesystem-level encryption (since we no longer need to depend on block ciphers, but can use a homomorphic stream cipher and then chop it up after the fact).

The big stumbling block to this point has been that the speed gains achieved by homomorphism have been offset by the overhead in implementing the homomorphic algorithms in the first place -- meaning that it's faster to decrypt, modify, re-encrypt.

The other benefit of course is security; with homomorphic crypto, there's never a decrypted version of the data stored, and never needs to be a decrypt/encrypt loop in memory for someone to patch for their own purposes. This means that you can have a database that is handling live data, but never knows anything about the contents. So you can securely offload data management to a third party, and minimize the data transfer to your local server for decryption/manipulation.

Re:Sounds impractical (2)

cryptizard (2629853) | about a year ago | (#43612581)

All it means for an encryption to be fully-homorphic is that there exists some efficient operation o such that E(a) o E(b) = E(a+b) and another operation u such that E(a) u E(b) = E(a*b). The benefit of this is that you can arithmetize any program into a circuit containing only addition and multiplication gates, meaning you can run any program you want over the encrypted data. I'm not sure what you mean by your second paragraph. Blocks are already very very small in existing ciphers so you are never required to download a whole thing and reencrypt it (if you are using an appropriate mode of operation, CBC obviously would not work for this).

Re:Sounds impractical (3, Interesting)

SLi (132609) | about a year ago | (#43612741)

The summary doesn't really explain this that well... the benefits here (if I'm reading this correctly) are that someone with a HUGE block of ciphertext and the encryption key can modify slices in situ without having to decrypt the large block and re-encrypt. They can just swap out the old data for the new, based on the index.

This begins to have significant benefits when applied to hosted computing (called Cloud Computing this decade), where, say, all your email is stored encrypted, as is the email index, and you just want to add/remove something without decrypting the entire blob. It also means that cloud hashing becomes significantly easier, as does filesystem-level encryption (since we no longer need to depend on block ciphers, but can use a homomorphic stream cipher and then chop it up after the fact).

Err, no, you are actually reading it completely wrong.

The point is actually that you can give encrypted data, say, some of your company's vital statistics, to an outsider (for example, a consulting agency); that agency can do a computation on that encrypted data (say, their super-secret algorithm that analyzes your company and tells you how to get rich fast) and get an encrypted result, which it then gives back to you. Only you can then decrypt the result.

You get to keep your data secret, and the company doing the computation gets to keep the function they compute secret; the only thing revealed to you is the function applied to your data, and nothing is revealed to the consulting agency.

The big stumbling block to this point has been that the speed gains achieved by homomorphism have been offset by the overhead in implementing the homomorphic algorithms in the first place -- meaning that it's faster to decrypt, modify, re-encrypt.

Homomorphic encryption most certainly is not about speed gains.

Re:Sounds impractical (1)

interval1066 (668936) | about a year ago | (#43614005)

The point is actually that you can give encrypted data, say, some of your company's vital statistics, to an outsider (for example, a consulting agency); that agency can do a computation on that encrypted data (say, their super-secret algorithm that analyzes your company and tells you how to get rich fast) and get an encrypted result, which it then gives back to you. Only you can then decrypt the result.

1) You have a bunch of encrpyted data. 2) A third party wants the results of a operation on your data. 3) You're too busy to be bothered with it so you say to a middle man "Wave this magic wand over my data and give me the results." 4) You decrpyt those results and send them to the third party. This will open up a completely new business model; the "data broker", a sort of clearing house or processor of encrypted data that the owning company can safely pass off to these middle men without comprimising the data.

Re:Sounds impractical (1)

betterunixthanunix (980855) | about a year ago | (#43612557)

You are not actually operating on the data; rather, you are operating on some input ciphertext to compute an output ciphertext. The idea is that the output ciphertext can be decrypted to get the results.

A good example of what this means and why anyone cares is the problem of spam filtering on encrypted messages. Suppose a spammer decided to encrypt spam using your public key; how might your mail server perform a spam check (something which is generally considered to be desirable)? The solution with FHE is that the server will use the homomorphic operations to compute a ciphertext that encrypts a "spam or not spam" bit, which will be sent to you with the encrypted message. In theory, even Google's spam filtering approach, which is based on aggregating the spam classifications they receive from many users, would work: your email client would encrypt a "right or wrong" bit, and FHE would be used to train a classifier.

There are also some odd thing that happen with FHE. Suppose, for example, that you had a symmetric FHE system i.e. one that had no public encryption key. It turns out you can create a public key encryption system without any additional secure assumption, by creating two secret keys, using one to encrypt the other, and then publishing the encrypted secret key and an encryption of "0" and an encryption of "1." The public encryption process would amount to encoding the plaintext using the encrypted "0" and "1" as "bits," then homomorphically evaluating the decryption algorithm using the encrypted secret key -- this would output ciphertext that must decrypt the to plaintext under the second key.

FHE can also be used for function privacy e.g. if you have a function and I have input, you can compute the function on my input without me revealing the input to you and with a cryptographic guarantee that I cannot learn more about your function from the ciphertext you give me than I can from the plaintext I decrypt (remember that the ciphertext will have more information than the message itself; it also contains the randomness from encryption; it is possible that the randomness will be combined in some way by your function that would allow me to learn what your function is). The construction is somewhat technical, but in simple terms it involves homomorphically adding encryptions of "0" to the output ciphertext (which will not affect the output value).

Correction (1)

betterunixthanunix (980855) | about a year ago | (#43612627)

The process for turning symmetric FHE input public-key FHE involves encoding the plaintext using the encrypted "0" and "1", then using FHE to evaluate the symmetric encryption algorithm using the encrypted key. Decryption requires two symmetric decryption operations, using both keys.

Re:Correction (2)

cryptizard (2629853) | about a year ago | (#43612713)

Nah, this wouldn't work because the encryption would be deterministic. If I wanted to test whether you had encrypted a certain bitstring I could recreate the process you used and compare the results. The actual way they do it in the Gentry paper is to publish an encryption of 1 and a whole bunch of encryptions of 0. Then your encryption process is to pick a random subset of those zeroes, add them together to get a new encryption of zero and then add the one if you are encrypting a 1. If the sparse subset sum assumption is true, then it will be hard to determine whether this ciphertext is the result of summing a bunch of zeroes and a one or just a bunch of zeroes.

Re:Correction (1)

betterunixthanunix (980855) | about a year ago | (#43612879)

this wouldn't work because the encryption would be deterministic

How is that? Wherever the encryption algorithm samples random numbers, the FHE evaluator would sample a random number and encode it using the encrypted "0" and "1".

The only tricky part to this is that it might not work if the FHE system does not have function privacy, though I am not sure that requirement is truly necessary.

Re:Correction (1)

cryptizard (2629853) | about a year ago | (#43612973)

Gotcha that makes sense. A lot less efficient but it doesn't require any additional assumptions. It doesn't seem to me that it would require function privacy, the encryption function should be public anyway. Also you have to be sure that your encryption homomorphically supports its own Eval function, which I don't think is guaranteed. Otherwise, you would not be able to do any homomorphic operations on your double-encrypted ciphertexts.

Re:Correction (1)

betterunixthanunix (980855) | about a year ago | (#43613031)

My point about function privacy was that the randomness might be "lost" in a sense. For example, in plaintext, 0 might be "0 xor 0" or "1 xor 1", and there is no additional information that can be used to distinguish those two cases. On the other hand, you might be able to distinguish the two cases if it was "A xor A" versus "B xor B," where A and B are ciphertexts for some FHE system. If I remember correctly, function privacy in FHE will guarantee that these two cases are indistinguishable.

Re:Correction (1)

cryptizard (2629853) | about a year ago | (#43613265)

I think you should be covered in this case just by IND-CPA security of your encryption, but I'm not 100% on that. The randomness is an input to your function, and the inputs should be hidden no matter what. I'll ponder it when I get a chance and see if I can't come up with a proof. What paper did you get this technique from by the way?

Re:Correction (1)

betterunixthanunix (980855) | about a year ago | (#43613479)

Earlier in my career as a PhD student I wrote a short paper about FHE and homomorphically evaluating block ciphers, and I wrote about that construction there. We tried to publish it but there was not really enough material, and since then I have been more focused on garbled circuits.

Re:Sounds impractical (1)

cryptizard (2629853) | about a year ago | (#43612561)

Any program you can write can be translated into an arithmetic circuit containing only addition and multiplication gates. Using that fact, you can apply any program you want on encrypted data using fully homomorphic encryption.

Re:Sounds impractical (0)

Anonymous Coward | about a year ago | (#43612569)

It can be useful for processing a class of data. adding salt to all encrypted passwords stored in a table.

Re:Sounds impractical (0)

Anonymous Coward | about a year ago | (#43612783)

I think the same way an individual transistor in a CPU doesn't care at all about the operation of the overall chip. It's just input to output over and over even if it's not doing anything functional.

Re:Sounds impractical (0)

Anonymous Coward | about a year ago | (#43613025)

I was thinking that too. OTOH, let's say you have an encrypted volume on your drive, or in the cloud.

Without this technology, you decrypt, operate, encrypt. During the operation phase, you have plaintext which is potentially insecure.

This obviously doesn't work for something like an Office document, where you need to view the letter while you type it. The letter has to be plaintext while you edit it, otherwise this makes no sense.

It makes more sense for an operation like, "query the encrypted medical records of patient A, and send his EKG to the doctor over a secure channel". The doctor doesn't have to know the key that decrypts your entire database, and the record isn't decrypted until it hits his monitor.

this could be useful (1)

lister king of smeg (2481612) | about a year ago | (#43612445)

This would be great for manipulating encrypted data on hosted servers you could upload your encrypted database never decrypt it so you will not have to worry about your data beings stolen. while you may have to pay more as you are using more resources i can see this being useful in many environments where business are hesitant to move to cloud based servers for fear of privacy breaches of customer data.

Re:this could be useful (1)

cryptizard (2629853) | about a year ago | (#43612777)

Yes, unfortunately the size of the key is measured in gigabytes and it takes several seconds to compute one multiplication.

The ultimate DRM? (3, Interesting)

MobyDisk (75490) | about a year ago | (#43612531)

Can homomophic encryption be used to create near-perfect DRM?

Current DRM chain:
Raw video stream -> Compress to MPEG -> Encrypt -> Send to customer's player -> Decrypt -> Decompress MPEG -> Cracker grabs video stream here -> Re-encrypt HDCP -> Send to television -> Television decrypts HDCP

Homomorphic DRM chain:
Raw video stream -> Compress to MPEG -> Encrypt -> Send to customer's player -> Decompress without decrypting -> Send to television -> Television decrypts

But this assumes it is possible to perform an immensely complex transformation on the encrypted data. Is that even theoretically possible? Multiplying encrypted numbers is a long way from performing an MPEG decompression on an encrypted string.

Re:The ultimate DRM? (1)

betterunixthanunix (980855) | about a year ago | (#43612575)

Television decrypts

I see a possible flaw in your DRM...

Every DRM scheme is vulnerable (0)

Anonymous Coward | about a year ago | (#43612637)

The content has to be displayed eventually.

If needed you can tap it from the LCD panel circuitry. There are actually patents for technology trying to prevent this. All that means tapping the signal gets a bit more involved, you have to sample every cell instead of the signal coming from the driver chip. Still, doable, if you really want to get the content.

Re:Every DRM scheme is vulnerable (3, Interesting)

Kookus (653170) | about a year ago | (#43613033)

I dunno, I found a device that pretty easily/cheaply rips the content from the tv screen.
I just point my phone at the tv and hit record.

In the old days I used a vhs recorder.

True (0)

Anonymous Coward | about a year ago | (#43613385)

Your method will defeat any and all DRM, with some loss of quality.

But as you so insightfully referred to, people used to watch VHS tapes without problem so perhaps quality isn't as important as content. I think good content is more important than shiny pixels. Sure, I would like good content in glorious 2160p, but I don't particularly need it to enjoy a movie.

Re:True (1)

SuricouRaven (1897204) | about a year ago | (#43613685)

It's always possible to get the audio un-DRMed with almost no loss of quality by just hooking a recorder up to the speaker cables and doing some basic electronics fiddling.

Video is much harder though.

Re:The ultimate DRM? (1)

cryptizard (2629853) | about a year ago | (#43612605)

Couldn't the television just decompress as well in that case? I am not saying this has no use in DRM, but I have been doing my PhD work on homomorphic encryption and I personally cannot see it if it exists.

Re:The ultimate DRM? (1)

omnichad (1198475) | about a year ago | (#43612731)

If you didn't want the ability to FF or Rewind. You can't even just skip ahead by B-Frame if the frame boundaries are unknown without decrypting. This could be solved by sending a piggyback unencrypted stream of frame sizes. But it would just be redundant data.

Re:The ultimate DRM? (1)

betterunixthanunix (980855) | about a year ago | (#43612891)

Can I contact you off site? I am doing work in a related field.

Re:The ultimate DRM? (0)

Anonymous Coward | about a year ago | (#43612935)

And to your point could I not just encrypt it then use standard compression?

I am really trying to figure out a use case for this. I am failing (must be having a brain fart today). Because for data to be useful at some point it has to be decrypted. If you are not going to decrypt it then why bother with the data at all.

Re:The ultimate DRM? (2)

pipatron (966506) | about a year ago | (#43613249)

You can generally not compress an encrypted stream of data.

Good encryption masks all the structure/redundancy from the data, which the compressor needs in order to remove useless bits.

Re:The ultimate DRM? (0)

Anonymous Coward | about a year ago | (#43613911)

Good point but then wouldnt the compression be in the weeds anyway with this setup? So you would want decompression to happen after the decrypt step for you to realize any gains out of it?

ITYM (0)

Anonymous Coward | about a year ago | (#43612691)

Homomorphic DRM chain:
Raw video stream -> Compress to MPEG -> Encrypt -> Send to customer's player -> Decompress without decrypting -> Send to television -> Television decrypts -> Cracker grabs video stream here

The only reason it's done at the player level is players are easy to crack and load software on, being basically general-purpose computers in a fancy little box. With the advent of "smart TVs" that could soon be the TV. At the point they can afford the computing power to do this on-chip on a special board before it hits the screen, that will be easy to program too, unless the entire chip runs encrypted code, which may be possible. Then you just intercept on the wire as it leaves that board.

Also that will require everyone buy new special TVs and not everyone even has an HDTV yet and this would only work if all the studios demanded everyone buy a new (expensive!) TV just because they're intentionally breaking their content. Time to keep an eye on the 4K BS.

Re:The ultimate DRM? (2)

steelfood (895457) | about a year ago | (#43613283)

No. And it illustrates just how useless DRM and activities around developing DRM actually are. There's always one place where the information has to come out decrypted. That place typically sits right in front of your sensory organs.

Re:The ultimate DRM? (5, Funny)

Rich0 (548339) | about a year ago | (#43614257)

They're working on neurological DRM. Pretty soon you'll go to the movies and leave talking about how much you enjoyed it, without actually knowing what the story was about or who the actors were, but with a general desire to buy products made by Coca Cola.

Wait... what? (0)

Anonymous Coward | about a year ago | (#43612553)

Okay... so you can add and multiply without knowing the decrypted version?

So... multiply by zero. You now know the hidden value is zero. Repeatedly add one, and you'll know what the 'encrypted' version of every possible value looks like... you now have a dictionary.

What am I missing here?

Re:Wait... what? (2)

cryptizard (2629853) | about a year ago | (#43612623)

It is a probabilistic encryption. That is, there are many different encryptions of the same value, to the point that knowing the plaintext that corresponds to a particular ciphertext does not give you any information. All modern encryption schemes are like this in order to prevent the attack you describe (or a similar one).

Re:Wait... what? (1)

femtobyte (710429) | about a year ago | (#43612635)

What you're missing is knowing the key to encrypt 0 and 1. If you already have the key to encrypt/decrypt the data, then you're already set. Without the encryption keys, how do you know whether 0 is represented by '852ee92374f0527bf7499161c' or '6dba27a49b5e0fc6979' (or whatever else)?

Re:Wait... what? (0)

Anonymous Coward | about a year ago | (#43612677)

So... multiply by zero. You now know the hidden value is zero

In order to multiply by zero, you would need to already know the encrypted value of zero.

Re:Wait... what? (0)

Anonymous Coward | about a year ago | (#43613065)

So... multiply by zero. You now know the hidden value is zero

In order to multiply by zero, you would need to already know the encrypted value of zero.

If you can do E(a) + E(b) = E(c), it is probably trivial to perform E(a) - E(b) = E(c') - in which case, E(a) - E(a) = E(0).

OTOH, the E(0) you get is only *one* possible representation of a zero, as has been pointed out in other posts.

Re:Wait... what? (1)

cryptizard (2629853) | about a year ago | (#43614193)

If your scheme is over a finite field, then E(a) - E(a) will just be a literal zero. Technically this is an encryption of zero, but it has not security as it is an encryption of zero under every possible key. Knowing it doesn't really give anything to an adversary.

zero (1)

goombah99 (560566) | about a year ago | (#43614409)

So... multiply by zero. You now know the hidden value is zero

In order to multiply by zero, you would need to already know the encrypted value of zero.

Zero is obtained by homomorhopically subtracting a record form itself.

Re:Wait... what? (2)

betterunixthanunix (980855) | about a year ago | (#43612681)

https://en.wikipedia.org/wiki/Semantic_security [wikipedia.org]

Let's put it this way: you could do the same with any public key cryptosystem by using the public key to encrypt the dictionary you described. The reason that does not work is that there are many (exponentially many in the security parameter) possible encryptions of each plaintext.

As someone who has to deal with HIPAA Requirements (4, Informative)

jforr (15487) | about a year ago | (#43612577)

This will be revolutionary for the healthcare industry.

Let me explain for those of you who have never dealt with HIPAA. HIPAA requires that an entity possessing protected healthcare information(PHI) keep that data safe and secure. Additionally, any outside entity coming in contact with PHI must sign a business associates agreement also agreeing to keep any PHI in their possession safe. None of the major cloud players will sign such agreements, which means any PHI can't go into the cloud. This means any practical deployment of say a hadoop cluster to reduce the process time of a large ETL job isn't feasible.

Now there is a tiny loophole in that encrypted PHI isn't treated as PHI at all. This means we can pass data through cloud services to backup for example, but doing any manipulating of the data is impossible due to the fact that as soon as you decrypt it, it's PHI and that's a big no-no. And this is where we lead back to homomorphic cryptography being revolutionary for the world of healthcare data.

Re:As someone who has to deal with HIPAA Requireme (1)

cryptizard (2629853) | about a year ago | (#43612649)

This is interesting for me as I am doing my PhD dissertation on homomorphic encryption. The problem we have, as a community, is that the computational assumptions used in these schemes are very new and we cannot come to a consensus as to whether the encryption schemes that result from them are going to remain secure 5, 10 or 20 years from now. For instance, NSA recommends that you only use AES, El Gamal, elliptic curve Diffie Hellman, and SHA-256. The community has butt loads of awesome and interesting protocols and techniques which use things not on this list. NSA is obviously being conservative because they have very important secrets to hide, but it leads to a problem where nothing can new can be "certified" to be secure. How do you even judge that something is "encrypted" if you are using a scheme that some grad student made up like a month ago?

Re:As someone who has to deal with HIPAA Requireme (1)

pipatron (966506) | about a year ago | (#43613361)

How do you even judge that something is "encrypted" if you are using a scheme that some grad student made up like a month ago?

This is a problem that has already been solved. The answer is: You treat it like it's simply "security by obscurity" and assume it will be broken any day soon. The sad fact is that this is true for most of the encryption schemes thought up over the years.

And honestly, if homomorphic encryption can't work with a well tested and analyzed encryption algorithm, I'm not sure I'm very impressed about it..

Re:As someone who has to deal with HIPAA Requireme (3, Interesting)

cryptizard (2629853) | about a year ago | (#43614177)

It is not that the algorithms have not been well tested. Actually the "algorithms" do not really need to be tested as we have security proofs that reduce to hardness assumptions. The problem is that the hardness assumptions simply have not been around long enough to be thoroughly vetted. RSA is based on the hardness of the RSA assumption (related to the hardness of factoring) which has had 40 years to be broken. These new homomorphic encryption schemes have been around for at most 4 years, which is NOTHING in the scheme of things.

Re:As someone who has to deal with HIPAA Requireme (1)

dmbasso (1052166) | about a year ago | (#43613711)

Can I ask you what are the algorithms behind this secure voting method [youtube.com] ? When I watched this presentation I thought he was talking about homomorphic encryption, but after I read about it I realized it couldn't be, since the computation required for processing millions of ballots would be far too much.

Re:As someone who has to deal with HIPAA Requireme (1)

cryptizard (2629853) | about a year ago | (#43613929)

I can't say for sure, I am not familiar with that guy's work. There are many other systems that provide verifiable end-to-end voting (Punchscan and Scantegrity for example, which I have personall worked on) which do not require anything more than a secure symmetric key encryption scheme.

There is a famous voting system by Rivest which does use homomorphic encryption though, and I can explain to you why it still remains efficient. This article is specifically about fully homomorphic encryption schemes, which are universally very very slow. For a long time now, however, we have had singularly homomorphic encryption schemes, under which you can calculate either sums or products of ciphertexts, but not both. For instance, RSA is actually homomorphic under multiplication (c1^e * c2^e = (c1*c2)^e). There is another encryption called Paillier which is very well understood and is homomorphic under addition. Using that, we can have secure elections which require only homomorphic addition.

To see why this suffices, you have to know how such a system would actually work. In it's most basic form, the voters could encrypt a one for the candidate they want to vote for and a zero for the candidates they don't want to vote for. The judge then adds up all the ciphertexts to obtain an encrypted sum of the votes for each candidate. There are some subtleties to deal with, like how do you prevent someone from encrypting a 10 and getting more votes for their guy, but we can deal with these too. The point is, for election purposes we can get by with just a single homomorphism and it can actually be pretty fast.

Re:As someone who has to deal with HIPAA Requireme (0)

Anonymous Coward | about a year ago | (#43613835)

Without knowing NSA's 'Suite A' algorithms, I'd take any of their recommendations with a grain of salt. If they're relying on security through obscurity, it brings a lot of assumptions into question.

Re:As someone who has to deal with HIPAA Requireme (1)

genghisjahn (1344927) | about a year ago | (#43612683)

Re:As someone who has to deal with HIPAA Requireme (1)

jforr (15487) | about a year ago | (#43612845)

Thank you. I was aware that they were in technical compliance, but I was not aware that Azure had started offering the business associate agreement. The link below seems to indicate that AWS is still "looking into" the matter, but I haven't found anything conclusive that says they will offer it. Needless to say, I'm starting a project immediately to begin an Azure deployment for my organization.

https://forums.aws.amazon.com/thread.jspa?messageID=444933 [amazon.com]

Opensource cryptography... (0)

Anonymous Coward | about a year ago | (#43612617)

this is a bit offtopic, but I can't resist linking another interesting release
https://github.com/exaexa/codecrypt [github.com]

Scary stuff (1)

Plazmid (1132467) | about a year ago | (#43612727)

Homomorphic encryption is scary stuff, one could use it to make malware or drm schemes that would be, for all practical intents and purposes, impossible to reverse engineer:
http://www.kuro5hin.org/story/2010/12/15/151617/78/ [kuro5hin.org]

Re:Scary stuff (1)

cryptizard (2629853) | about a year ago | (#43612821)

Fortunately we are way far off from that kind of reality. It takes on the order of seconds, at least, to do a homomorphic multiplication. To emulate an entire instruction set would be, conservatively, trillions of times slower than running it unencrypted.

Examples? (1)

steamraven (2428480) | about a year ago | (#43613047)

The documentation is mostly reference material and very dense. Anybody have some examples on how to actually use the library?

Re:Examples? (1)

cryptizard (2629853) | about a year ago | (#43613173)

I don't think this release is targeted at general developers or people who just want to toy around with it. FHE is not anywhere near that level of maturity. It is mostly for researchers who are trying to make this stuff faster and want to try out some new theoretical twist that they came up with, but not have to code this whole mess of a thing from scratch. I haven't looked too deeply at the code, but it seems you need a good understanding of the ciphertext representation at least (which is very different from traditional ciphers) in order to make use of it.

Numerical Porn (2)

nanospook (521118) | about a year ago | (#43613131)

With the erection of homomorphic data centers, we should be able to pound our data injections directly and deeply into encrypted data mounds using a direct boaring method without worrying about compromising data health.

Really? (0)

Anonymous Coward | about a year ago | (#43613651)

Have a look at the (lack of) quality of this code, compared to real-world cryptographic requirements. Aside from choosing a C++ implementation, it's just appalling. Consider the vulnerability to timing attacks: branching, data-dependent execution, etc. I guess these 'experts' will wait for serious crypto developers to fill the gap between theory and practice, as usual. I'm sure it has merit, but these number theoretic libraries should be regarded as nothing more than reference implementations until academics accept the often ugly requirements of cryptographically blind execution in software.

I don't believe that timing attacks and simple power analysis can ever be completely countered in a software implementation; but this just isn't good enough for people who should be taking the lead on best practices.

Re:Really? (2)

cryptizard (2629853) | about a year ago | (#43614139)

You're missing the point, this is not being released so that people can actually use it. Keys in this system measure in the gigabytes, and single multiplications take seconds. It is so researchers can apply their new ideas on how to make it more efficient without having to code this whole thing from scratch. It is a great help for research.
Load More Comments
Slashdot Login

Need an Account?

Forgot your password?