4 ms·

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.

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.