News for hackers. Stuff that matters.
Re:Machine Learning on Encrypted Data Without Decrypting It by falcolas on Tuesday November 26, 2019 @10:27AM (#21639060)
Before reading: "I bet they're using homomorphic encryption to expose patterns in the encrypted data"

After reading: Yup. It makes sense, so long as your resulting model is run against similarly encrypted data, the same patterns will be there for the ML to identify.

Which is, of course, one of the issues with homomorphic encryption.

Re:Machine Learning on Encrypted Data Without Decrypting It by KenoFischer on Tuesday November 26, 2019 @10:31AM (#21639098)
Just to clarify, homomorphic encryption does not expose patterns. At every point in the computation the ciphertexts are computationally indistinguishable from random. The result of evaluating the ML model will be an encrypted prediction that you then need to send back to whoever encrypted the data (or more precisely whoever has the key - doesn't need to be the same person) so they can decrypt and use the prediction.
Re:Machine Learning on Encrypted Data Without Decrypting It by marviel on Tuesday November 26, 2019 @10:40AM (#21639195)
Do you have a reference somewhere that backs up your assertions, where I can read more on this topic? I'm super curious about it.
Re:Machine Learning on Encrypted Data Without Decrypting It by KenoFischer on Tuesday November 26, 2019 @10:48AM (#21639270)
The CKKS paper that describes the crypto scheme I'm using is described here: [1]. The paper is decently readable, but frankly I feel that it doesn't really convey much intuition and it's a bit hard to follow if you don't have an algebraic number theory background. Probably the correct thing to do is to read the original BGV paper [2], which is still quite technical of course, but at least doesn't implicitly assume all the development that has happened since then. Once you've gotten the basics, I have an overview that focuses more on the practical aspects of how it works in the documentation [3]. I've also written an overview of how CKKS works, in which I've tried to highlight what the two main ideas of CKKS are compared to earlier schemes [4]. Let me know if you were looking for something else.

[1] https://eprint.iacr.org/2016/421.pdf

[2] https://eprint.iacr.org/2011/277.pdf

[3] https://juliacomputing.github.io/ToyFHE.jl/dev/man/backgroun...

[4] https://juliacomputing.github.io/ToyFHE.jl/dev/man/ckks/

Re:Machine Learning on Encrypted Data Without Decrypting It by marviel on Tuesday November 26, 2019 @10:49AM (#21639284)
this is great, thank you.
Re:Machine Learning on Encrypted Data Without Decrypting It by throwawaymath on Tuesday November 26, 2019 @10:51AM (#21639301)
Read Craig Gentry's PhD thesis, which was the first working fully homomorphic encryption scheme. It's no longer state of the art, but it contains a lot of accessible background on the core problem (which was then open) and why it's important.

The person you're responding to is correct. It's an explicit design goal that a fully homomorphic encryption system would not expose any distinguishable oracle about the underlying data. Otherwise there would be no point to it whatsoever, because you'd just be performing the same computations on the data dramatically less efficiently and without any benefit.

This follows the general imperative of cryptography, which is that the outputs of cryptographically secure primitives (hash functions, pseudorandom generators, pseudorandom permutations, etc) should be computationally indistinguishable from random up to 2^n queries, for some large n (such as 128).

Re:Machine Learning on Encrypted Data Without Decrypting It by jeltz on Tuesday November 26, 2019 @02:17PM (#21641614)
What about side effects? Does eg timing of the computations leak data?
Re:Machine Learning on Encrypted Data Without Decrypting It by jrockway on Tuesday November 26, 2019 @04:28PM (#21642929)
I would expect that all data processing by default leaks information via computation time. Some algorithms are intentionally designed to resist this; people that have gone to this effort will mention them. (A similar thing: assume something is not thread-safe unless the documentation mentions it's thread-safe.)
Re:Machine Learning on Encrypted Data Without Decrypting It by rhindi on Tuesday November 26, 2019 @06:35PM (#21643848)
Actually homomorphic encryption always ends up running as slow as the worse case, so you can’t do a sidechannel attack by looking at the computation time.
Re:Machine Learning on Encrypted Data Without Decrypting It by voxic11 on Tuesday November 26, 2019 @11:24AM (#21639684)
He is just stating the definition of homomorphic encryption. There are lots of papers on the topic. The one mentioned in the article is a good starting point. "Homomorphic Encryption for Arithmetic of Approximate Numbers" https://eprint.iacr.org/2016/421.pdf
Re:Machine Learning on Encrypted Data Without Decrypting It by DougBTX on Tuesday November 26, 2019 @10:48AM (#21639269)
Re:Machine Learning on Encrypted Data Without Decrypting It by marviel on Tuesday November 26, 2019 @10:50AM (#21639287)
yeah I appreciate it! I usually check wikipedia first, but nonetheless a good place to start
Re:Machine Learning on Encrypted Data Without Decrypting It by garganzol on Tuesday November 26, 2019 @01:43PM (#21641291)
You can get a sense of it just by looking at the classic: https://en.wikipedia.org/wiki/Block_cipher_mode_of_operation...

Look for penguin image in ECB mode. Encryption without randomness reveals the patterns! That image is highly educational and makes you think.

Re:Machine Learning on Encrypted Data Without Decrypting It by peteradio on Tuesday November 26, 2019 @10:44AM (#21639229)
That seems nontrivial that the same key would be used to decrypt the result. Does this only work for some subset of ML models?
Re:Machine Learning on Encrypted Data Without Decrypting It by KenoFischer on Tuesday November 26, 2019 @10:54AM (#21639338)
I may be missing the question, so let me know if I do, but the point here is just that the crypto system is asymmetric. There's three kinds of keys, public, private and evaluation (as usual you can derive the others from the private key). Whoever has the public key can encrypt, whoever has the private key can decrypt and evaluation may or may not need the evaluation keys depending on what you're computing. As for which ML models it works for, they theoretical answer is all of them, because you can do arbitrary computation. The practical answer is that currently models of this complexity are probably the best you can do, because everything else would take years to run. It's being worked on though, both in theory land and in the implementation.
Re:Machine Learning on Encrypted Data Without Decrypting It by peteradio on Tuesday November 26, 2019 @11:20AM (#21639626)
Ok, I think you answered my question, basically I was missing the public key. So you send an encrypted picture of a cat to the encryption trained model and it returns an answer which is encrypted using the public key. (as a super simple example)
Re:Machine Learning on Encrypted Data Without Decrypting It by ummonk on Tuesday November 26, 2019 @11:09AM (#21639493)
The ML model has to use certain operations (which are homomorphic to the encryption) as its building blocks, but with fully homomorphic encryption you can put an arbitrary number of the building blocks together so you can build complex ML models out of those.
Re:Machine Learning on Encrypted Data Without Decrypting It by mikorym on Tuesday November 26, 2019 @03:53PM (#21642558)
It would be good to see a proof why the homomorphism property is sufficient for doing ML (or a specific type of ML) on encrypted data.

Intuitively it may or may not make sense to people, but a proof would also clarify whether there are any caveats, limitations or other particuliarities.

Re:Machine Learning on Encrypted Data Without Decrypting It by ummonk on Tuesday November 26, 2019 @05:34PM (#21643459)
It is really straightforward. The currently top voted comment basically explains it. If you take data x and encrypt it with encryption function C to get C(x), and then apply your machine learning model f to that to get f(C(x)), homomorphism means that f(C(x)) = C(f(x)) (because f and C commute), so the client can then apply the decryption to the result to get C-1(f(C(x)) = C-1(C(f(x)) = f(x).
Re:Machine Learning on Encrypted Data Without Decrypting It by xvector on Tuesday November 26, 2019 @07:25PM (#21644166)
You might want to clarify that “C-1” is actually C^-1 because otherwise I was wondering where subtraction comes into play.
Re:Machine Learning on Encrypted Data Without Decrypting It by ummonk on Tuesday November 26, 2019 @11:37PM (#21645285)
Whoops, too late to edit; thanks for posting the clarification.
Re:Machine Learning on Encrypted Data Without Decrypting It by ct520 on Tuesday November 26, 2019 @07:14PM (#21644093)
more like really straight forward over my head. I appreciate you taking the time to explain it - still can't grasp the concept. Back to framework connecting.
Re:Machine Learning on Encrypted Data Without Decrypting It by mikorym on Wednesday November 27, 2019 @12:29AM (#21645502)
But are you saying that a ML model is just a function? The function C is clear, but what is f?

What is the domain and what is the codomain? If f and C commute, then x in X is just your "data" and both the domain and codomain.

Edit:

> the top voted comment

Ah, I see that the top comment says that you use a pre-trained model. Intuitively that I think makes sense. Bot how about training the model itself?

Re:Machine Learning on Encrypted Data Without Decrypting It by falcolas on Tuesday November 26, 2019 @03:10PM (#21642166)
So, you're training a statistical model - teaching it to recognize certain patterns - on data that is somehow wholly without patterns? Even with a certain amount of noise in the individual data points, if you're given enough data to train a statistical model to identify traits in the ciphertext you also probably have enough data to break the encryption.

Also, something can be statistically random and still have patterns (see PRNGs, which are statically random (you can't identify the next value from previous values), but there's still a pattern if you know the algorithm and seed).

I'll admit, the promise of homomorphic encryption is pretty amazing, but this particular combination of data and ML seems like a fairly obvious way to leak data. I believe there's a reason that homomorphic encryption has not been broadly accepted as an allowed standard.

EDIT: So, I think I'm missing a practical example. I have a model which I want to train on data homomorphically encrypted with key X, and that model is a very simple "is this a cat". I'm given a whole set of data encrypted with key X that's tagged with "cat" and "not a cat".

Once the model is trained, I can run this on any data encrypted with key X and find out if the data contains a cat (with some degree of accuracy). I have no way of telling information outside the tags provided on the training data, but it still gives me, a person without the encryption key, the ability to identify any feature that's tagged in the training set on any un-tagged production set.

Having seen a large quantity of ML training sets, the tag sets are rarely so limited. There's also often "elephant", "ball", and "dog" tags, even if I'm only being asked to train on cats.

Re:Machine Learning on Encrypted Data Without Decrypting It by KenoFischer on Tuesday November 26, 2019 @03:28PM (#21642347)
> Once the model is trained, I can run this on any data encrypted with key X and find out if the data contains a cat (with some degree of accuracy). I have no way of telling information outside the tags provided on the training data, but it still gives me, a person without the encryption key, the ability to identify any feature that's tagged in the training set on any un-tagged production set.

I think you're missing the fact that the predictions come back encrypted, so you don't learn anything unless you know the key. Also, in this particular example the model was trained on unencrypted data, but as discussed below, you can do either.

Re:Machine Learning on Encrypted Data Without Decrypting It by falcolas on Tuesday November 26, 2019 @03:49PM (#21642523)
Predictions are a tag, and a separate confidence value. A fairly finite set. Cat. Not a Cat.

Large quantities of small finite sets are anathema to encryption.

Re:Machine Learning on Encrypted Data Without Decrypting It by KenoFischer on Tuesday November 26, 2019 @03:58PM (#21642616)
I'm still only guessing at the objection, but if it helps, the encryptions are randomized, so two different encryptions of the same value do not have the same ciphertext.
Re:Machine Learning on Encrypted Data Without Decrypting It by heavenlyblue on Tuesday November 26, 2019 @05:30PM (#21643433)
Not all encryption algorithms are susceptible to known-cyphertext attacks.
Re:Machine Learning on Encrypted Data Without Decrypting It by heavenlyblue on Tuesday November 26, 2019 @05:16PM (#21643317)
If you map a binary variable into a, let's say, 128-bit number (non-linearly) where a mapping is unique for every encryption key used, there's nothing making it an anathema for encryption.

I am not sure whether this is achievable practically though.

Re:Machine Learning on Encrypted Data Without Decrypting It by ReidZB on Tuesday November 26, 2019 @04:54PM (#21643141)
> I believe there's a reason that homomorphic encryption has not been broadly accepted as an allowed standard.

Well, yes... Practical homomorphic encryption is cutting-edge research, and standards bodies like NIST aren't going to deal with an area like this until it's much closer to "solved" (by which I mean much more efficient, with more practical applications, widely used and scrutinized schemes, etc.)

Re:Machine Learning on Encrypted Data Without Decrypting It by thefifthsetpin on Tuesday November 26, 2019 @03:20PM (#21642261)
> homomorphic encryption has not been broadly accepted as an allowed standard.

I get that a lack of broad acceptance is a hard thing to source, but do you have one?

Re:Machine Learning on Encrypted Data Without Decrypting It by falcolas on Tuesday November 26, 2019 @03:37PM (#21642434)
https://csrc.nist.gov/publications/detail/sp/800-111/final is a good starting point (and used by HIPPA, as an aside).

It leads to block cipher standards, AES standards, and so on.

I think it's not unreasonable to say that if it should ever appear as a recommended cipher by NIST, then it can be considered to be broadly accepted.

Re:Machine Learning on Encrypted Data Without Decrypting It by madrafi on Wednesday November 27, 2019 @10:55AM (#21648898)
Last year a group of companies and institutions created a working standard. https://homomorphicencryption.org/standard/
Re:Machine Learning on Encrypted Data Without Decrypting It by osaariki on Tuesday November 26, 2019 @12:00PM (#21640131)
This is not how this works. Homomorphic encryption (HE) is best thought of as a software CPU that gives you ways to mutate data (but not read it without the secret key of course). Any computation you run has to be using the instruction set offered by HE: addition, multiplication or rotation. When you do an operation on two ciphertexts, you get a new ciphertext back, but no information on its contents.

Now the way you do machine learning here is by translating your model to use the instructions offered by HE. You've effectively recompiled the model to a new architecture.

If you'd like to read more about machine learning with homomorphic encryption, we published a paper on our CHET compiler [1]. I also talk about this space on a high level in this MSR podcast episode [2].

[1]: https://www.cs.utexas.edu/~roshan/CHET.pdf [2]: https://www.microsoft.com/en-us/research/blog/he-compilers-f...

Re:Machine Learning on Encrypted Data Without Decrypting It by mcguire on Tuesday November 26, 2019 @12:54PM (#21640733)
Quick question: If you have control of the computation instructions (the software for your HE CPU), can arrange for a leak of information from the encrypted data?
Re:Machine Learning on Encrypted Data Without Decrypting It by KenoFischer on Tuesday November 26, 2019 @01:06PM (#21640872)
In a properly functioning HE scheme, the party doing the evaluation cannot obtain information about the encrypted data, even if they do the operation incorrectly. Without further measures, they can of course compute an incorrect value, which depending on the larger protocol can sometimes be an issue (e.g. consider the scenario where after decryption the client shares the prediction with the server for some reason - in that case, if the server sends the original image ciphertexts, instead of predictions, they can trick the client into decrypting the original image). There is also always the risk that whoever is choosing the instantiation of the cryptoscheme knows something you don't and picks weak parameters, but that's just all the usual attack modes on cryptographic schemes.
Re:Machine Learning on Encrypted Data Without Decrypting It by osaariki on Tuesday November 26, 2019 @01:37PM (#21641220)
As other posters already mentioned, there's no control flow in the HE instruction set. This is actually one of the reasons neural networks are a great fit for HE, as they often have fixed data access patterns and no control flow.
Re:Machine Learning on Encrypted Data Without Decrypting It by Dylan16807 on Tuesday November 26, 2019 @01:04PM (#21640848)
The software can only do arithmetic in a fixed pattern, no "if" statements or while loops or anything. Any conditionals have to be faked with arithmetic.

So, since the arithmetic is secure (otherwise it wouldn't be HE), and the entire runtime pattern is fixed up front and made of nothing but arithmetic, there's no way to leak anything.

Re:Machine Learning on Encrypted Data Without Decrypting It by garganzol on Tuesday November 26, 2019 @02:49PM (#21641953)
This gives a whole new look to lambda calculus and Lisp concepts that promote to represent everything as a (preferably pure) function.

If the whole logic can be expressed as a pure function without conditionals then it would fully fit into HE.

But what if we want conditionals?

Comparison operators like (a < b), (a > b), etc go out of the question immediately as they would allow to guess the values by a simple binary search.

Equality operation (a == b) seems plausible from the security standpoint as it would not reveal the encrypted value. But there is a challenge in performing that operation because both of its arguments may be encrypted with different randomization. To overcome this, probably some neat trick could be performed but... this is the question of the future.

EDIT: Here is an idea. Some FHE engines have pre-encoded values for some magic numbers like 0, 1 and -1.

What if the equality operation p(a, b) = (a == b) is performed like this:

p(a, b) = (a + (b * -1)) == 0

Does anyone have an intuition regarding the feasibility of the proposed trick in something like Microsoft SEAL? Do both left and right parts of the comparison would have the canonicalized randomness making the equality operation possible?

P.S. On a side note, the sheer existence of an equivalence operation in FHE scheme would decimate its security by allowing to plant bruteforce attacks with a lower guesswork. Not a catastrophe by any means, and some systems would prefer that as a small price to pay for having conditionals in a program.

Re:Machine Learning on Encrypted Data Without Decrypting It by kortex on Tuesday November 26, 2019 @11:03PM (#21645140)
Have you looked at reversible computing? The ideas are only vague in my mind at the moment, but the fragments are there. Disclaimer: out of my wheelhouse. Any conditional statement will throw some information away, "knowing" a==b means provably you have less complexity. Not a good look for encryption.

But instead let's say you have some register which gets rotated/xor'd in some way based on the relationship of a to b.

I don't think you can do branching logic though.

Re:Machine Learning on Encrypted Data Without Decrypting It by garganzol on Wednesday November 27, 2019 @10:31AM (#21648661)
Good suggestions, thank you.

> I don't think you can do branching logic though.

You can. If we would be able to introduce a special equality operator, let's call it SEQ that works like so:

SEQ(a, b) = 1 when a == b; SEQ(a, b) = 0 when a != b

Then we would be able to do conditionals by discarding the result of unmatched branch by multiplying it by 0.

Thanks to the fact that all HE calculations are pure, no observable side effects would be produced.

For example, here is a simple program with a conditional statement:

P(x) = x == 10 ? 42 : sin(x)

This is how it may look in HE domain:

P(x) = SEQ(x, 10) * 42 + (1 - SEQ(x, 10)) * sin(x)

No branching is involved here but the result is equivalent to a program with branching. Eureka!

Once again, thank you for the fruitful suggestions.

EDIT: by the way, it paves the way for implementing > and < operators as well due to the fact that operator result remains in encrypted domain. This is a serious wow moment.

Re:Machine Learning on Encrypted Data Without Decrypting It by garganzol on Tuesday November 26, 2019 @01:35PM (#21641199)
The encryption done right mixes a random noise to the encrypted data exactly to avoid pattern recognition. Homomorphic encryption does it too.

Otherwise it would be trivial to analyze and eventually crack the scheme. This is especially true for homomorphic encryption where an attacker can employ math operations to solve equations in order to reveal as much data as he/she humanly can.