6 ms·

Just to clarify, homomorphic encryption does not expose patterns. At every point in the computation the ciphertexts are computationally indistinguishable from r

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/
  - marviel 7y ago
    this is great, thank you.
- throwawaymath 7y ago
  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).
  - jeltz 7y ago
    What about side effects? Does eg timing of the computations leak data?
    - jrockway 7y ago
      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.)
      - rhindi 7y ago
        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.
- voxic11 7y ago
  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 https://eprint.iacr.org/2016/421.pdf
- garganzol 7y ago
  You can get a sense of it just by looking at the classic: https://en.wikipedia.org/wiki/Block_cipher_mode_of_operation#Electronic_Codebook_(ECB) 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.
peteradio 7y ago
That seems nontrivial that the same key would be used to decrypt the result. Does this only work for some subset of ML models?
- KenoFischer 7y ago
  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.
  - peteradio 7y ago
    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)
- ummonk 7y ago
  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.
falcolas 7y ago
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.
- thefifthsetpin 7y ago
  > 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?
  - falcolas 7y ago
    https://csrc.nist.gov/publications/detail/sp/800-111/final 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.
mikorym 7y ago
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.
- ummonk 7y ago
  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).
  - ct520 7y ago
    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.
    - deleted 7y ago
      [deleted]
  - xvector 7y ago
    You might want to clarify that “C-1” is actually C^-1 because otherwise I was wondering where subtraction comes into play.
    - ummonk 7y ago
      Whoops, too late to edit; thanks for posting the clarification.
  - mikorym 7y ago
    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?

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/
- marviel 7y ago
  this is great, thank you.
throwawaymath 7y ago
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).
- jeltz 7y ago
  What about side effects? Does eg timing of the computations leak data?
  - jrockway 7y ago
    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.)
    - rhindi 7y ago
      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.
voxic11 7y ago
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 https://eprint.iacr.org/2016/421.pdf
garganzol 7y ago
You can get a sense of it just by looking at the classic: https://en.wikipedia.org/wiki/Block_cipher_mode_of_operation#Electronic_Codebook_(ECB) 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.

peteradio 7y ago

That seems nontrivial that the same key would be used to decrypt the result. Does this only work for some subset of ML models?

KenoFischer 7y ago
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.
- peteradio 7y ago
  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)
ummonk 7y ago
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.

falcolas 7y ago

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.

thefifthsetpin 7y ago
> 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?
- falcolas 7y ago
  https://csrc.nist.gov/publications/detail/sp/800-111/final 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.

mikorym 7y ago

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.

ummonk 7y ago
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).
- ct520 7y ago
  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.
  - deleted 7y ago
    [deleted]
- xvector 7y ago
  You might want to clarify that “C-1” is actually C^-1 because otherwise I was wondering where subtraction comes into play.
  - ummonk 7y ago
    Whoops, too late to edit; thanks for posting the clarification.
- mikorym 7y ago
  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?