5 ms·

Wait, so they're doing computation on encrypted data and inferring some information about the relationships between data in the encrypted set? How is that even

Wait, so they're doing computation on encrypted data and inferring some information about the relationships between data in the encrypted set? How is that even possible? That seems to defeat the purpose of encryption, or at least show that our encryption is severely flawed. This is the first time I've heard of this and it's kind of blowing my mind

fiddlerwoaroof 3y ago
The idea is the result is encrypted too such that, when the person that holds the key gets it back they can decrypt it and see the result. So you can run an inference algorithm on data without ever having to decrypt it and see what the data actually is. It seems to me that this intrinsically is vulnerable to side-channel attacks, but it will be interesting to see if we can avoid those with constant-time algorithms or something.
- l33t7332273 3y ago
  What about this seems vulnerable to side channels?
  - fiddlerwoaroof 3y ago
    Because, if you have a mechanism to run arbitrary computations on encrypted data, I’d be a bit concerned about an attacker running carefully crafted computations on the data and deducing information about the encrypted data based on how the ciphertext changes or the time/memory usage of the computation. This isn’t really a particularly well-informed suspicion: it’s partly based on a sense that FHE is a “have your cake and eat it too” sort of technology that’s too good to be true and partly based on the recent discoveries that fairly well-understood things like speculative execution in CPUswere vulnerable to serious side-channel attacks.
    - HeadsUpHigh 3y ago
      zk proofs are used in public blockchains to transmit millions in value so I would assume they aren't vulnerable to side channel attacks at least not on a superficial level.
    - l33t7332273 3y ago
      If running computations on encrypted data is enough to compromise the integrity of the encryption then that encryption algorithm is not even EAV secure, and EAV secure is a pretty low bar.
    - jkhdigital 3y ago
      There is no side-channel because FHE effectively considers the computational hardware itself to be the adversary.
- PeterisP 3y ago
  No, FHE is not intrinsically vulnerable to any side-channel attacks, by definition; the properties hold no matter how the "executor" executes the operations and they include the assumption that obviously they can see (or change!) everything that happens during the execution. However, that effectively means that any FHE approach has to be "anti-optimized", always touching all the data that might get touched, always taking all the conditional paths, not just the worst case path as in constant time algorithms, since the execution must return the correct result for any encrypted input data. It's not that you can "see if we can avoid those with constant-time algorithms or something", the basic table stakes (which all FHE methods actually implement) is the constant-time algorithm approach taken to the extreme and then squared. It does have "some" unavoidable performance impact because of that.
  - fiddlerwoaroof 3y ago
    I suspect that you’re right, but my concern is more about unknown unknowns here: new tech like this often has failure modes we can’t imagine until the tech itself becomes commonplace.
l33t7332273 3y ago
A homomorphism is a function so that f(ab) = f(a) f(b). So you can imagine the cloud customer wants to compute ab, but the use a homomorphic encryption function, f, to ask the cloud provider to computer f(ab) given f(a) and f(b). Then the customer decrypts f(ab). This doesn’t imply any weakness in encryption. FHE is a bit stronger than what I’ve described, but that’s the idea.
noman-land 3y ago
It's pretty damn insane. I implemented the simplest form of this in Javascript as a sort of test a while back and it's just so cool. https://en.wikipedia.org/wiki/Paillier_cryptosystem https://en.wikipedia.org/wiki/Paillier_cryptosystem https://gist.github.com/noman-land/a65520aa4f2ce7ba3bf9f13d20016346 https://gist.github.com/noman-land/a65520aa4f2ce7ba3bf9f13d2...

fiddlerwoaroof 3y ago

The idea is the result is encrypted too such that, when the person that holds the key gets it back they can decrypt it and see the result. So you can run an inference algorithm on data without ever having to decrypt it and see what the data actually is. It seems to me that this intrinsically is vulnerable to side-channel attacks, but it will be interesting to see if we can avoid those with constant-time algorithms or something.

l33t7332273 3y ago
What about this seems vulnerable to side channels?
- fiddlerwoaroof 3y ago
  Because, if you have a mechanism to run arbitrary computations on encrypted data, I’d be a bit concerned about an attacker running carefully crafted computations on the data and deducing information about the encrypted data based on how the ciphertext changes or the time/memory usage of the computation. This isn’t really a particularly well-informed suspicion: it’s partly based on a sense that FHE is a “have your cake and eat it too” sort of technology that’s too good to be true and partly based on the recent discoveries that fairly well-understood things like speculative execution in CPUswere vulnerable to serious side-channel attacks.
  - HeadsUpHigh 3y ago
    zk proofs are used in public blockchains to transmit millions in value so I would assume they aren't vulnerable to side channel attacks at least not on a superficial level.
  - l33t7332273 3y ago
    If running computations on encrypted data is enough to compromise the integrity of the encryption then that encryption algorithm is not even EAV secure, and EAV secure is a pretty low bar.
  - jkhdigital 3y ago
    There is no side-channel because FHE effectively considers the computational hardware itself to be the adversary.
PeterisP 3y ago
No, FHE is not intrinsically vulnerable to any side-channel attacks, by definition; the properties hold no matter how the "executor" executes the operations and they include the assumption that obviously they can see (or change!) everything that happens during the execution. However, that effectively means that any FHE approach has to be "anti-optimized", always touching all the data that might get touched, always taking all the conditional paths, not just the worst case path as in constant time algorithms, since the execution must return the correct result for any encrypted input data. It's not that you can "see if we can avoid those with constant-time algorithms or something", the basic table stakes (which all FHE methods actually implement) is the constant-time algorithm approach taken to the extreme and then squared. It does have "some" unavoidable performance impact because of that.
- fiddlerwoaroof 3y ago
  I suspect that you’re right, but my concern is more about unknown unknowns here: new tech like this often has failure modes we can’t imagine until the tech itself becomes commonplace.

l33t7332273 3y ago

A homomorphism is a function so that f(ab) = f(a) f(b). So you can imagine the cloud customer wants to compute ab, but the use a homomorphic encryption function, f, to ask the cloud provider to computer f(ab) given f(a) and f(b). Then the customer decrypts f(ab). This doesn’t imply any weakness in encryption. FHE is a bit stronger than what I’ve described, but that’s the idea.

noman-land 3y ago

It's pretty damn insane. I implemented the simplest form of this in Javascript as a sort of test a while back and it's just so cool. https://en.wikipedia.org/wiki/Paillier_cryptosystem https://en.wikipedia.org/wiki/Paillier_cryptosystem https://gist.github.com/noman-land/a65520aa4f2ce7ba3bf9f13d20016346 https://gist.github.com/noman-land/a65520aa4f2ce7ba3bf9f13d2...