12 ms·

Machine Learning on Encrypted Data Without Decrypting It

421 points by KenoFischer 7y ago

rehasu 7y ago
Think about what encryption should do. Think about what Machine Learning should do. The only thing you can do with ML on encrypted data is show where encryption needs to be improved. Or maybe there is a way to create ML models that produces output which only someone with the correct (private) key can understand.
- KenoFischer 7y ago
  > Or maybe there is a way to create ML models that produces output which only someone with the correct (private) key can understand. Yes, that's what the blog post describes how to do.
- yati 7y ago
  > Nowhere was the user data decrypted and in particular the cloud provider does not have access to either the orignal image nor is it able to decrypt the prediction it computed. That's from the post. Is that what you meant by creating a model whose results only the owner of the data can understand?
- zionic 7y ago
  Precisely. Any encryption that allows an attacker to significantly reason about its underlying plaintext is broken.
falcolas 7y ago
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.
- KenoFischer 7y ago
  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.
  - marviel 7y ago
    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.
    - DougBTX 7y ago
      Good starting point: https://en.wikipedia.org/wiki/Homomorphic_encryption https://en.wikipedia.org/wiki/Homomorphic_encryption
      - marviel 7y ago
        yeah I appreciate it! I usually check wikipedia first, but nonetheless a good place to start
    - KenoFischer 7y ago
      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 https://eprint.iacr.org/2016/421.pdf [2] https://eprint.iacr.org/2011/277.pdf https://eprint.iacr.org/2011/277.pdf [3] https://juliacomputing.github.io/ToyFHE.jl/dev/man/background/rlwe/ https://juliacomputing.github.io/ToyFHE.jl/dev/man/backgroun... [4] https://juliacomputing.github.io/ToyFHE.jl/dev/man/ckks/ https://juliacomputing.github.io/ToyFHE.jl/dev/man/ckks/
brenden2 7y ago
If you can infer information from encrypted data then it's not properly encrypted. Generally you would use a salt that would render this type of analyses useless.
- theschwa 7y ago
  The person who runs the model won’t be able to infer anything. The result of the model is itself encrypted, and would need to be decrypted using the original encryption key.
  - garganzol 7y ago
    >would need to be decrypted using the original encryption key A small correction. Decryption is performed with a decryption (private) key which is kept in secret and only known to the data owner. In contast, encryption key is public and known to both data owner and "the person who runs the model".
- LeanderK 7y ago
  Maybe i misunderstood something, but they are not really inferring information. The model is still encrypted, the outsider doesn't know what's going on. Wouldn't salt destroy the homomorphic property?
  - brenden2 7y ago
    Homomorphic encryption is malleable[1] in that it can, with enough information, be decrypted without knowing the private keys in some cases. For example, if you can correlate with other data it may be possible to effectively undo the encryption. This is more like anonymization (effectively a one-way hash) than encryption. If you encrypt 2 different values with the same algorithm and key, you will get the same ciphertext which reveals information about the original value (i.e., that they are the same). [1]: https://en.wikipedia.org/wiki/Malleability_(cryptography) https://en.wikipedia.org/wiki/Malleability_(cryptography)
    - 7y ago
mlthoughts2018 7y ago
What are the runtimes?
- KenoFischer 7y ago
  About a minute or so for the batch of 64, but I haven't tuned the implementation yet (I just did enough work to get it down to a comfortable range of experimentation). The paper I linked (https://eprint.iacr.org/2018/1041.pdf https://eprint.iacr.org/2018/1041.pdf) which uses the same model, but with a more optimized implementation cites 26ms amortized per image (in a batch of 64), so I would suspect I can get down to that with a day or two of optimization work if I wanted to (or just plug in their backend - but where's the fun in that).
- deleted 7y ago
  [deleted]
- osaariki 7y ago
  I'm a researcher at Microsoft who's worked a lot on this problem (neural network inference on encrypted data). Take a look at this paper we published at PLDI [1] on our CHET compiler. The speed of the inference depends a lot on the depth of the network. A small 2 convolutional layer model takes a couple of seconds, while a 10 convolutional layer SqueezeNet takes 164 seconds. The reason is that you have to select encryption parameters according to the depth of the computation. Since this paper was published we've by the way improved these numbers ~5X. That was optimizing for latency and throughput is a something you can separately optimize for. This landmark paper (also from Microsoft) [2] showed inferencing on 2 convolutional layer network at a throughput of 58k images per hour. [1]: https://www.cs.utexas.edu/~roshan/CHET.pdf https://www.cs.utexas.edu/~roshan/CHET.pdf [2]: http://proceedings.mlr.press/v48/gilad-bachrach16.pdf http://proceedings.mlr.press/v48/gilad-bachrach16.pdf
ChrisRackauckas 7y ago
This blog post reminds me of the "Machine Learning Systems are Stuck in a Rut" paper [1], where they mentioned: > It is hard to experiment with front end features like named dimensions, because it is painful to match them to back ends that expect calls to monolithic kernels with fixed layout. On the other hand, there is little incentive to build high quality back ends that support other features, because all the front ends currently work in terms of monolithic operators. An end-to-end tool chain for machine learning requires solutions from many specialist disciplines. This is a fantastic example of getting around this problem using Flux.jl's interaction with the full Julia language. Here the author does some exceedingly cool stuff (doing machine learning on encrypted data!), and in order to get there he needed to write what many would think of as lower-level kernels that should be "provided by the library" (encrypted matrix multiplication, encrypted convolutions). To make the interface useful, he needed to use a mature interface that people are already using and make it something that can automatically switch over to encrypted implementations. And, because of the nature of fully homeomorphic encryption, the implementation has to be fast, otherwise it's dead in the water since FHE is expensive! To me, this example showcases one way how Flux.jl's is helping machine learning get out of that "rut". The author adds dispatches to standard kernels which allow for his encrypted data types, which then allows standard Julia Flux.jl machine learning models to act on encrpyted data, and it uses type-inference + JIT compilation to make it fast enough to work. Not only that, but it's also not tied to some "sub-language" defined by a machine learning framework. That means the FHE framework not only works nicely with machine learning, it can be used by any other package in the Julia language (differential equation solvers, nonlinear optimization, macroeconomics models?). This allows composibility of tools and community: all tools from all fields can now use this same FHE implementation, so authors collaborate and mature this to a very good one. These knock-on effects give people doing research in Julia a lot of competitive advantages over other researchers, and it will be interesting to see how this effects not just the ML research community, but also everyone else! https://dl.acm.org/citation.cfm?id=3321441 https://dl.acm.org/citation.cfm?id=3321441 (Repost from the previous thread on this!)
- yowlingcat 7y ago
  Thanks for this provocative comment -- if you don't mind me asking, what do you think the tradeoffs are between using Julia and Python for ML in production? I get the idea of right tool for the right job and all, and I know that Python has a fantastic ecosystem. But, how close is Julia? How developed is the ecosystem right now, and how fast is it developing?
Stasis5001 7y ago
As somebody with some ML background but no expertise in crypto, is the following ELI~20 summary correct? We take an ML model trained on unencrypted data, use a 'homomorphic evaluation' technique (let's just leave that as magic here) to convert the model operation-by-operation to a model that runs on encrypted data, do a little more crypto magic, and we've solved the business problem described at the beginning of the article. (In particular, if you train a model on encrypted data you get a really bad model, right?)
- KenoFischer 7y ago
  Yep, that's correct. With the minor caveat that we choose an ML model that's "easy" to evaluate using homomorphic encryption.
  - Analog24 7y ago
    As someone who is not a cryptography expert, is there any hope of using similar logic to train on encrypted data? Naively it seems like you could perform the same operations on the back propagation steps (or any other update algorithm you're using for non NN models) to arrive at the encrypted version of the parameter updates, which you could then decrypt to get the updated model. Am I missing something here?
    - KenoFischer 7y ago
      Training is a lot tougher. Just doing one gradient update step isn't all that bad (although you may have to play with the loss function a bit, e.g. logit cross entropy is probably tough to evaluate). However, then you need to go and actually do all the steps and gradient updates, so you probably need some form of bootstrapping to be able to evaluate computations of that depth. Also, the use case is slightly less compelling. For training, you can probably get all the parties who have data to coordinate and evaluate an MPC more cheaply than you could with HE alone. I think it'll require a very compelling use case for somebody to go and think through what the best way to do it is and it'll probably depend on the specifics of the application (who has what data, and what are we willing to leak as we go along - e.g. it's a lot easier if you don't care about keeping the weights secret).
zcw100 7y ago
This sounds like what Microsoft research did with SEAL to produce CryptoNets https://www.microsoft.com/en-us/research/publication/cryptonets-applying-neural-networks-to-encrypted-data-with-high-throughput-and-accuracy/ https://www.microsoft.com/en-us/research/publication/crypton...
- KenoFischer 7y ago
  Yep, same research setting, though a different network. I don't at the moment remember all the details of CryptoNets, but IIRC they were doing batch size 8192 evaluations (i.e. just using each slot as an independent value and evaluating the code as if on scalars), which allows you to get away without the fancy ciphertext encoding magic that's described in the blog post (at the cost of high latency of course).
  - osaariki 7y ago
    You're right, CryptoNets used a data layout optimized for throughput with a batch size 4096. Since then we've done a lot of work on low latency inference with our CHET compiler [1] and my colleagues with LoLa [2]. It all comes down to the data layouts you use. [1]: https://www.cs.utexas.edu/~roshan/CHET.pdf https://www.cs.utexas.edu/~roshan/CHET.pdf [2]: https://arxiv.org/pdf/1812.10659.pdf https://arxiv.org/pdf/1812.10659.pdf
kylek 7y ago
Not sure I totally grok this, but this has been around for a while to use tensorflow on encrypted data [0] [0] https://github.com/tf-encrypted/tf-encrypted https://github.com/tf-encrypted/tf-encrypted
- osaariki 7y ago
  TF Encrypted has focused more on MPC [1]. At least that's what their arXiv paper [2] talks about. It does seem they are also working to integrate Microsoft SEAL for HE. [1]: https://en.wikipedia.org/wiki/Secure_multi-party_computation https://en.wikipedia.org/wiki/Secure_multi-party_computation [2]: https://arxiv.org/abs/1810.08130 https://arxiv.org/abs/1810.08130
abd1 7y ago
very nice machine learning releted post amazing share information thanks by @KenoFischer
spencerp 7y ago
There’s a PyTorch-style library for that: https://github.com/facebookresearch/CrypTen https://github.com/facebookresearch/CrypTen
winrid 7y ago
I'm assuming this uses similar encryption algorithms that you can use to do queries on encrypted data?
- KenoFischer 7y ago
  I'm assuming you're referring to private information retrieval (https://en.wikipedia.org/wiki/Private_information_retrieval https://en.wikipedia.org/wiki/Private_information_retrieval), which is from the same field of research, but may or may not use the same techniques.
  - winrid 7y ago
    Never looked into it. Just heard about it recently. Very cool.
EGreg 7y ago
You know what’s interesting? Aren’t hashes etc. done by some nonlinear functions? Doesn’t ML kind of try to fit your model using linear functions all the way down? Or not only linear? Point being — can ML techniques be used to reverse hashes or find collissions? Immovable object vs irresistible force? Anyone got actual INFO on how this plays out?
- garganzol 7y ago
  > Point being — can ML techniques be used to reverse hashes or find collissions? Immovable object vs irresistible force? That's actually a good philosophical observation. And there is an answer for that. If you try to use ML on an encrypted data set then it will blow up and won't converge. The encrypted data contain a lot of randomness while the ML would assume the presence of a not insignificant amount of continuity, linearity and correlation. Trying to train a network on encrypted data would blow it up as it would not be able to find a convergence point in any observable time. The effort would be equivalent to trying to bruteforce the encryption. But if you have a few million years, a few PBs of storage and some extravagant network training algorithm based on mutations, who knows.
personjerry 7y ago
This technique is deeply flawed. You can't do this effectively without outside knowledge they should not have. They are in fact using outside knowledge, specifically that the encrypted data is in the form of images. Without that knowledge, you wouldn't know which ML techniques to use! Additionally, remember that feature engineering is a big part of what makes ML effective at all, and that certainly cannot be done on encrypted data (the feature engineering you need to do depends on what the data looks like).
- sthatipamala 7y ago
  If I don't even know what data type my input is, what meaningful output can the system give? I wouldn't consider that cheating. Also, you can do feature engineering on a training set that you collect, as long as that is similar to the distribution of end user inputs. That's a pretty standard ML workflow.
  - personjerry 7y ago
    The entire point of encrypted data is you don't know what's in there. What they're claiming is they've worked around this problem, but they haven't, because they're subtly incorporating outside information: specifically that they know what the data looks like already. From a true third-party looking at encrypted data, you would have no idea. What does your statement about feature engineering have to do with encrypted data? Maybe I can clarify with an example: You can't transform a waveform into more usable features with a fourier transform if the waveform is encrypted.
    - karpierz 7y ago
      You seem to be misunderstanding the value proposition. Suppose that I have some of my personal medical data, and I'd like to use it to try and detect early symptoms of HIV. But because there's a stigma against HIV and I don't trust medical providers to handle my data correctly, I refuse to hand over my data to a third party service unencrypted. Without homomorphic encryption, I'd be out of luck; I couldn't use a third-party service to analyze my data and return a prediction. With homomorphic encryption: - I encrypt my data locally - Send the encrypted bits over to the third-party - The third-party uses their ML algorithm to compute a prediction - They send back an encrypted prediction - I decrypt the prediction locally and get my results. At no point in this process can anyone, aside from me, see either the input data or the output.
littlestymaar 7y ago
With Homomorphic Encryption, the data owner encrypt data X, and give C(X) it to the owner of the function f applies it to C(X), which gives f(C(X)), which equals to C(f(X)) and return it to the data owner, which can decipher it to f(X). The owner of the function know neither the initial data nor the result, and the owner of the data doesn't know f. There is also Functional Encryption, a different technique solving a similar (but different) goal. With F.E., the owner of the data must know the function f, but the party performing the calculation get directly the result f(X).
t_mann 7y ago
How is this new in 2019, as the article states? Fully homomorphic encryption has been around for at least a decade. There’s even a hedge fund (numerai) that crowdsources its quantitative modeling based on an implementation of FHE since 2015.
StefanKarpinski 7y ago
Since there seems to be a lot of confusion throughout this thread, perhaps I can attempt to clarify what's going on at a very high level. The setting is that the user sends their data to a service and wants the service to do useful work on their data without knowing what their data is. In this case, the work that the service does is apply a pre-trained, non-secret ML vision model to the secret, encrypted data. The result is an encrypted answer that is sent back to the user, who can decrypt it and get a useful result. The service is none the wiser about what the user's data was, nor what the answer was. Does this seem like impossible magic? Yes. Everyone was pretty surprised when the first theoretical fully homomorphic encryption schemes were found. For a while people believed that it might never be efficient enough to be practical. But now it's actually feasible to do limited but real useful computations on behalf of a user without the service learning anything about what it is computing for the user. There is ongoing work to expand what kinds of computations can be done efficiently.
- k__ 7y ago
  Sounds strange. Does this mean that the model has to be trained on encrypted data?
  - StefanKarpinski 7y ago
    Yes, it’s rather surprising that it can be done at all. And no, you train the model normally and then express the application of the model in terms of the set of primitive operations that the encryption scheme supports. Broadening the set of operations supported by the encryption scheme is an active area of research since having a better “instruction set” allows more computations to be done efficiently. It is also possible for the model to be provided by the user and encrypted along with the data rather than being fixed and public. That way the service can apply a model that it doesn't know to data that it also doesn't know. This allows a fairly general service in theory, but it remains a challenge to express more than fairly simple models in a way that can be computed efficiently.
    - pishpash 7y ago
mikedilger 7y ago
"True homomorphic encryption isn't possible, and my guess is that it will never be feasible for most applications. But limited application tricks like this have been around for decades, and sometimes they're useful" - Bruce Schneier https://www.schneier.com/blog/archives/2019/07/google_releases_1.html https://www.schneier.com/blog/archives/2019/07/google_releas...
- StefanKarpinski 7y ago
  I don't understand what Bruce Schneier means by this quote. Several fully homomorphic encryption schemes have been proposed and implemented. "True" doesn't have a technical meaning in this context, so it's unclear what's he means by that phrase. Perhaps that he believes it will never be fast enough for general computations? Or perhaps he's referring to the fact that schemes don’t allow conditionals?
webew 7y ago
Wow! Does this mean translating a program from one language to another using ML will be possible?
nightsd01 7y ago
I wonder if you could apply the same homomorphic encryption to ML model training as well, so that you can fully train an algorithm without ever being able to actually “see” the training data.

421 points by KenoFischer 7y ago

Think about what encryption should do. Think about what Machine Learning should do. The only thing you can do with ML on encrypted data is show where encryption needs to be improved. Or maybe there is a way to create ML models that produces output which only someone with the correct (private) key can understand.

KenoFischer 7y ago
> Or maybe there is a way to create ML models that produces output which only someone with the correct (private) key can understand. Yes, that's what the blog post describes how to do.
yati 7y ago
> Nowhere was the user data decrypted and in particular the cloud provider does not have access to either the orignal image nor is it able to decrypt the prediction it computed. That's from the post. Is that what you meant by creating a model whose results only the owner of the data can understand?
zionic 7y ago
Precisely. Any encryption that allows an attacker to significantly reason about its underlying plaintext is broken.

falcolas 7y ago

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.

KenoFischer 7y ago
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.
- marviel 7y ago
  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.
  - DougBTX 7y ago
    Good starting point: https://en.wikipedia.org/wiki/Homomorphic_encryption https://en.wikipedia.org/wiki/Homomorphic_encryption
    - marviel 7y ago
      yeah I appreciate it! I usually check wikipedia first, but nonetheless a good place to start
  - KenoFischer 7y ago
    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 https://eprint.iacr.org/2016/421.pdf [2] https://eprint.iacr.org/2011/277.pdf https://eprint.iacr.org/2011/277.pdf [3] https://juliacomputing.github.io/ToyFHE.jl/dev/man/background/rlwe/ https://juliacomputing.github.io/ToyFHE.jl/dev/man/backgroun... [4] https://juliacomputing.github.io/ToyFHE.jl/dev/man/ckks/ https://juliacomputing.github.io/ToyFHE.jl/dev/man/ckks/

brenden2 7y ago

If you can infer information from encrypted data then it's not properly encrypted. Generally you would use a salt that would render this type of analyses useless.

theschwa 7y ago
The person who runs the model won’t be able to infer anything. The result of the model is itself encrypted, and would need to be decrypted using the original encryption key.
- garganzol 7y ago
  >would need to be decrypted using the original encryption key A small correction. Decryption is performed with a decryption (private) key which is kept in secret and only known to the data owner. In contast, encryption key is public and known to both data owner and "the person who runs the model".
LeanderK 7y ago
Maybe i misunderstood something, but they are not really inferring information. The model is still encrypted, the outsider doesn't know what's going on. Wouldn't salt destroy the homomorphic property?
- brenden2 7y ago
  Homomorphic encryption is malleable[1] in that it can, with enough information, be decrypted without knowing the private keys in some cases. For example, if you can correlate with other data it may be possible to effectively undo the encryption. This is more like anonymization (effectively a one-way hash) than encryption. If you encrypt 2 different values with the same algorithm and key, you will get the same ciphertext which reveals information about the original value (i.e., that they are the same). [1]: https://en.wikipedia.org/wiki/Malleability_(cryptography) https://en.wikipedia.org/wiki/Malleability_(cryptography)
  - 7y ago

mlthoughts2018 7y ago

What are the runtimes?

KenoFischer 7y ago
About a minute or so for the batch of 64, but I haven't tuned the implementation yet (I just did enough work to get it down to a comfortable range of experimentation). The paper I linked (https://eprint.iacr.org/2018/1041.pdf https://eprint.iacr.org/2018/1041.pdf) which uses the same model, but with a more optimized implementation cites 26ms amortized per image (in a batch of 64), so I would suspect I can get down to that with a day or two of optimization work if I wanted to (or just plug in their backend - but where's the fun in that).
deleted 7y ago
[deleted]
osaariki 7y ago
I'm a researcher at Microsoft who's worked a lot on this problem (neural network inference on encrypted data). Take a look at this paper we published at PLDI [1] on our CHET compiler. The speed of the inference depends a lot on the depth of the network. A small 2 convolutional layer model takes a couple of seconds, while a 10 convolutional layer SqueezeNet takes 164 seconds. The reason is that you have to select encryption parameters according to the depth of the computation. Since this paper was published we've by the way improved these numbers ~5X. That was optimizing for latency and throughput is a something you can separately optimize for. This landmark paper (also from Microsoft) [2] showed inferencing on 2 convolutional layer network at a throughput of 58k images per hour. [1]: https://www.cs.utexas.edu/~roshan/CHET.pdf https://www.cs.utexas.edu/~roshan/CHET.pdf [2]: http://proceedings.mlr.press/v48/gilad-bachrach16.pdf http://proceedings.mlr.press/v48/gilad-bachrach16.pdf

ChrisRackauckas 7y ago

This blog post reminds me of the "Machine Learning Systems are Stuck in a Rut" paper [1], where they mentioned: > It is hard to experiment with front end features like named dimensions, because it is painful to match them to back ends that expect calls to monolithic kernels with fixed layout. On the other hand, there is little incentive to build high quality back ends that support other features, because all the front ends currently work in terms of monolithic operators. An end-to-end tool chain for machine learning requires solutions from many specialist disciplines. This is a fantastic example of getting around this problem using Flux.jl's interaction with the full Julia language. Here the author does some exceedingly cool stuff (doing machine learning on encrypted data!), and in order to get there he needed to write what many would think of as lower-level kernels that should be "provided by the library" (encrypted matrix multiplication, encrypted convolutions). To make the interface useful, he needed to use a mature interface that people are already using and make it something that can automatically switch over to encrypted implementations. And, because of the nature of fully homeomorphic encryption, the implementation has to be fast, otherwise it's dead in the water since FHE is expensive! To me, this example showcases one way how Flux.jl's is helping machine learning get out of that "rut". The author adds dispatches to standard kernels which allow for his encrypted data types, which then allows standard Julia Flux.jl machine learning models to act on encrpyted data, and it uses type-inference + JIT compilation to make it fast enough to work. Not only that, but it's also not tied to some "sub-language" defined by a machine learning framework. That means the FHE framework not only works nicely with machine learning, it can be used by any other package in the Julia language (differential equation solvers, nonlinear optimization, macroeconomics models?). This allows composibility of tools and community: all tools from all fields can now use this same FHE implementation, so authors collaborate and mature this to a very good one. These knock-on effects give people doing research in Julia a lot of competitive advantages over other researchers, and it will be interesting to see how this effects not just the ML research community, but also everyone else! https://dl.acm.org/citation.cfm?id=3321441 https://dl.acm.org/citation.cfm?id=3321441 (Repost from the previous thread on this!)

yowlingcat 7y ago
Thanks for this provocative comment -- if you don't mind me asking, what do you think the tradeoffs are between using Julia and Python for ML in production? I get the idea of right tool for the right job and all, and I know that Python has a fantastic ecosystem. But, how close is Julia? How developed is the ecosystem right now, and how fast is it developing?

Stasis5001 7y ago

As somebody with some ML background but no expertise in crypto, is the following ELI~20 summary correct? We take an ML model trained on unencrypted data, use a 'homomorphic evaluation' technique (let's just leave that as magic here) to convert the model operation-by-operation to a model that runs on encrypted data, do a little more crypto magic, and we've solved the business problem described at the beginning of the article. (In particular, if you train a model on encrypted data you get a really bad model, right?)

KenoFischer 7y ago
Yep, that's correct. With the minor caveat that we choose an ML model that's "easy" to evaluate using homomorphic encryption.
- Analog24 7y ago
  As someone who is not a cryptography expert, is there any hope of using similar logic to train on encrypted data? Naively it seems like you could perform the same operations on the back propagation steps (or any other update algorithm you're using for non NN models) to arrive at the encrypted version of the parameter updates, which you could then decrypt to get the updated model. Am I missing something here?
  - KenoFischer 7y ago
    Training is a lot tougher. Just doing one gradient update step isn't all that bad (although you may have to play with the loss function a bit, e.g. logit cross entropy is probably tough to evaluate). However, then you need to go and actually do all the steps and gradient updates, so you probably need some form of bootstrapping to be able to evaluate computations of that depth. Also, the use case is slightly less compelling. For training, you can probably get all the parties who have data to coordinate and evaluate an MPC more cheaply than you could with HE alone. I think it'll require a very compelling use case for somebody to go and think through what the best way to do it is and it'll probably depend on the specifics of the application (who has what data, and what are we willing to leak as we go along - e.g. it's a lot easier if you don't care about keeping the weights secret).

zcw100 7y ago

This sounds like what Microsoft research did with SEAL to produce CryptoNets https://www.microsoft.com/en-us/research/publication/cryptonets-applying-neural-networks-to-encrypted-data-with-high-throughput-and-accuracy/ https://www.microsoft.com/en-us/research/publication/crypton...

KenoFischer 7y ago
Yep, same research setting, though a different network. I don't at the moment remember all the details of CryptoNets, but IIRC they were doing batch size 8192 evaluations (i.e. just using each slot as an independent value and evaluating the code as if on scalars), which allows you to get away without the fancy ciphertext encoding magic that's described in the blog post (at the cost of high latency of course).
- osaariki 7y ago
  You're right, CryptoNets used a data layout optimized for throughput with a batch size 4096. Since then we've done a lot of work on low latency inference with our CHET compiler [1] and my colleagues with LoLa [2]. It all comes down to the data layouts you use. [1]: https://www.cs.utexas.edu/~roshan/CHET.pdf https://www.cs.utexas.edu/~roshan/CHET.pdf [2]: https://arxiv.org/pdf/1812.10659.pdf https://arxiv.org/pdf/1812.10659.pdf

kylek 7y ago

Not sure I totally grok this, but this has been around for a while to use tensorflow on encrypted data [0] [0] https://github.com/tf-encrypted/tf-encrypted https://github.com/tf-encrypted/tf-encrypted

osaariki 7y ago
TF Encrypted has focused more on MPC [1]. At least that's what their arXiv paper [2] talks about. It does seem they are also working to integrate Microsoft SEAL for HE. [1]: https://en.wikipedia.org/wiki/Secure_multi-party_computation https://en.wikipedia.org/wiki/Secure_multi-party_computation [2]: https://arxiv.org/abs/1810.08130 https://arxiv.org/abs/1810.08130

abd1 7y ago

very nice machine learning releted post amazing share information thanks by @KenoFischer

spencerp 7y ago

There’s a PyTorch-style library for that: https://github.com/facebookresearch/CrypTen https://github.com/facebookresearch/CrypTen

winrid 7y ago

I'm assuming this uses similar encryption algorithms that you can use to do queries on encrypted data?

KenoFischer 7y ago
I'm assuming you're referring to private information retrieval (https://en.wikipedia.org/wiki/Private_information_retrieval https://en.wikipedia.org/wiki/Private_information_retrieval), which is from the same field of research, but may or may not use the same techniques.
- winrid 7y ago
  Never looked into it. Just heard about it recently. Very cool.

EGreg 7y ago

You know what’s interesting? Aren’t hashes etc. done by some nonlinear functions? Doesn’t ML kind of try to fit your model using linear functions all the way down? Or not only linear? Point being — can ML techniques be used to reverse hashes or find collissions? Immovable object vs irresistible force? Anyone got actual INFO on how this plays out?

garganzol 7y ago
> Point being — can ML techniques be used to reverse hashes or find collissions? Immovable object vs irresistible force? That's actually a good philosophical observation. And there is an answer for that. If you try to use ML on an encrypted data set then it will blow up and won't converge. The encrypted data contain a lot of randomness while the ML would assume the presence of a not insignificant amount of continuity, linearity and correlation. Trying to train a network on encrypted data would blow it up as it would not be able to find a convergence point in any observable time. The effort would be equivalent to trying to bruteforce the encryption. But if you have a few million years, a few PBs of storage and some extravagant network training algorithm based on mutations, who knows.

personjerry 7y ago

This technique is deeply flawed. You can't do this effectively without outside knowledge they should not have. They are in fact using outside knowledge, specifically that the encrypted data is in the form of images. Without that knowledge, you wouldn't know which ML techniques to use! Additionally, remember that feature engineering is a big part of what makes ML effective at all, and that certainly cannot be done on encrypted data (the feature engineering you need to do depends on what the data looks like).

sthatipamala 7y ago
If I don't even know what data type my input is, what meaningful output can the system give? I wouldn't consider that cheating. Also, you can do feature engineering on a training set that you collect, as long as that is similar to the distribution of end user inputs. That's a pretty standard ML workflow.
- personjerry 7y ago
  The entire point of encrypted data is you don't know what's in there. What they're claiming is they've worked around this problem, but they haven't, because they're subtly incorporating outside information: specifically that they know what the data looks like already. From a true third-party looking at encrypted data, you would have no idea. What does your statement about feature engineering have to do with encrypted data? Maybe I can clarify with an example: You can't transform a waveform into more usable features with a fourier transform if the waveform is encrypted.
  - karpierz 7y ago
    You seem to be misunderstanding the value proposition. Suppose that I have some of my personal medical data, and I'd like to use it to try and detect early symptoms of HIV. But because there's a stigma against HIV and I don't trust medical providers to handle my data correctly, I refuse to hand over my data to a third party service unencrypted. Without homomorphic encryption, I'd be out of luck; I couldn't use a third-party service to analyze my data and return a prediction. With homomorphic encryption: - I encrypt my data locally - Send the encrypted bits over to the third-party - The third-party uses their ML algorithm to compute a prediction - They send back an encrypted prediction - I decrypt the prediction locally and get my results. At no point in this process can anyone, aside from me, see either the input data or the output.

littlestymaar 7y ago

With Homomorphic Encryption, the data owner encrypt data X, and give C(X) it to the owner of the function f applies it to C(X), which gives f(C(X)), which equals to C(f(X)) and return it to the data owner, which can decipher it to f(X). The owner of the function know neither the initial data nor the result, and the owner of the data doesn't know f. There is also Functional Encryption, a different technique solving a similar (but different) goal. With F.E., the owner of the data must know the function f, but the party performing the calculation get directly the result f(X).

t_mann 7y ago

How is this new in 2019, as the article states? Fully homomorphic encryption has been around for at least a decade. There’s even a hedge fund (numerai) that crowdsources its quantitative modeling based on an implementation of FHE since 2015.

StefanKarpinski 7y ago

Since there seems to be a lot of confusion throughout this thread, perhaps I can attempt to clarify what's going on at a very high level. The setting is that the user sends their data to a service and wants the service to do useful work on their data without knowing what their data is. In this case, the work that the service does is apply a pre-trained, non-secret ML vision model to the secret, encrypted data. The result is an encrypted answer that is sent back to the user, who can decrypt it and get a useful result. The service is none the wiser about what the user's data was, nor what the answer was. Does this seem like impossible magic? Yes. Everyone was pretty surprised when the first theoretical fully homomorphic encryption schemes were found. For a while people believed that it might never be efficient enough to be practical. But now it's actually feasible to do limited but real useful computations on behalf of a user without the service learning anything about what it is computing for the user. There is ongoing work to expand what kinds of computations can be done efficiently.

k__ 7y ago
Sounds strange. Does this mean that the model has to be trained on encrypted data?
- StefanKarpinski 7y ago
  Yes, it’s rather surprising that it can be done at all. And no, you train the model normally and then express the application of the model in terms of the set of primitive operations that the encryption scheme supports. Broadening the set of operations supported by the encryption scheme is an active area of research since having a better “instruction set” allows more computations to be done efficiently. It is also possible for the model to be provided by the user and encrypted along with the data rather than being fixed and public. That way the service can apply a model that it doesn't know to data that it also doesn't know. This allows a fairly general service in theory, but it remains a challenge to express more than fairly simple models in a way that can be computed efficiently.
  - pishpash 7y ago

mikedilger 7y ago

"True homomorphic encryption isn't possible, and my guess is that it will never be feasible for most applications. But limited application tricks like this have been around for decades, and sometimes they're useful" - Bruce Schneier https://www.schneier.com/blog/archives/2019/07/google_releases_1.html https://www.schneier.com/blog/archives/2019/07/google_releas...

StefanKarpinski 7y ago
I don't understand what Bruce Schneier means by this quote. Several fully homomorphic encryption schemes have been proposed and implemented. "True" doesn't have a technical meaning in this context, so it's unclear what's he means by that phrase. Perhaps that he believes it will never be fast enough for general computations? Or perhaps he's referring to the fact that schemes don’t allow conditionals?

webew 7y ago

Wow! Does this mean translating a program from one language to another using ML will be possible?

nightsd01 7y ago

I wonder if you could apply the same homomorphic encryption to ML model training as well, so that you can fully train an algorithm without ever being able to actually “see” the training data.