4 ms·

> Eventually, it will be obvious that running shared workloads on a single piece of physical hardware has fundamentally unremediatable security implications. I

> Eventually, it will be obvious that running shared workloads on a single piece of physical hardware has fundamentally unremediatable security implications. If I understand correctly, Homomorphic Encryption aims to solve for these kinds of attacks (although presumably the computations are more expensive and programs must be restructured to use HE primitives?). https://en.wikipedia.org/wiki/Homomorphic_encryption https://en.wikipedia.org/wiki/Homomorphic_encryption EDIT: Why the downvotes? Am I mistaken?

pbronez 5y ago
Yeah HE is a totally different security model. It moves all the trust out of the hardware. You ship encrypted workloads to an untrusted party, who computes on the encrypted data and returns an encrypted result. Then you decrypt the result to use it. And yeah, this is just as inefficient as you'd think.
- rocqua 5y ago
  I'd say its much more inefficient as you'd think. Firstly the computations on encrypted data just take a LOT longer, especially for Fully Homomorphic encryption. With a single 64 bit addition taking microseconds. Secondly, the FHE code cannot branch based on data. If it could, it would know something about the data, and it wouldn't be proper encryption. This means an if statement becomes "calculate both branches, and throw away the result you don't need". Similarly, a for loop becomes "give me an upper bound of how long this will run", then "loop for exactly the upper bound number of times, if the loop is 'done' early, just throw away the result of the remaining operations". FHE is really cool, and has its uses in situations where you want to cooperate without needing to trust, but it is stupidly inefficient. (Things get really cool if two parties want to cooperate and the computing party can e.g. branch based on their local unencrypted data)
teddyh 5y ago
HE is stupidly inefficient, and is entirely an academic oddity, and there is every indication that it will always remain that way. Bringing up HE in a context of real problems needing real solutions is unproductive.
- ghaff 5y ago
  If solving a problem in a stupidly inefficient way is the only way of mitigating said problem, you may not have much choice--at least for some use cases. Saying something can't be answer because it isn't an efficient answer (today) is also unproductive.
  - PeterisP 5y ago
    There's a simple way of mitigating said problem - don't use shared hardware, and run each thing on aseparate, isolated chip. That's also inefficient, but compared to the immense overhead of HE it's quite reasonable.
simiones 5y ago
HE is incredibly slow, and unlikely to ever be fast enough for common workflows. As in, an HE implementation of an algorithm that runs in seconds in Python on a regular machine might run in minutes or tens of minutes. Not to mention, to avoid side-channel attacks, an HE scheme still needs to always run the longest possible sequence of operations regardless of input (otherwise, information about the input data is leaked through timing). So an HE version of a quick-sort scheme would always run in O(n^2), otherwise it would leak details about the contents of the list. In some cases it would even have to run in the same amount of time regardless of the size of the list, to avoid leaking information about that.
- astrange 5y ago
  Is HE any different from taking the encrypted input data, sticking the program you want to run on the end, and returning that? If anything, it sounds less efficient than that.
  - tsimionescu 5y ago
    HE is designed for running a secret algorithm with secret input data and obtaining secret output data, all on an untrusted computer. It works a little bit like this: you write your algorithm using only HE computing primitives, then you encrypt it and the input data and send those to the HE runtime, who you don't trust, and who DOESN'T have any way to decrypt your message. The HE runtime executes your encrypted program and sends back the still encrypted output. Once you receive your output, you decrypt it using the key you have kept secret.
    - astrange 5y ago
      That's not how it works, that's what it does. I provided an example of how it could work, but it had better be more efficient than that or it's a silly idea.
      - tsimionescu 5y ago
        One note, first of all: I made one mistake, the algorithm is not secret in HE (the HE runtime has to know it). Only the input data is guaranteed to be secret. I'm not sure what you mean. This is how HE works, at a high level. The whole point is that you're doing public operations on secret data on a machine that can never know what the data was, nor what response it gave you. Furthermore, the point of HE is also that you know that your data remained secret regardless of how the HE runtime was implemented, as you just send it encrypted information. Making it more efficient by giving it access to the decrypted data would defeat the whole point. Making it more efficient by optimizing based on the actual data would allow your data to leak through timing side-channels, again defeating the whole point. Basically, HE refers to computing schemes where DECRYPT(ALGORITHM(ENCRYPT(X)) == ALGORITHM(X). You send [ALGORITHM, ENCRYPT(X)] to the runtime, and it gives you Y. DECRYPT(Y) is then the result of your computation. As far as we know, this is indeed hopelessly slow, and there is no guarantee that we will ever find fast secure HE primitives.

pbronez 5y ago

Yeah HE is a totally different security model. It moves all the trust out of the hardware. You ship encrypted workloads to an untrusted party, who computes on the encrypted data and returns an encrypted result. Then you decrypt the result to use it. And yeah, this is just as inefficient as you'd think.

rocqua 5y ago
I'd say its much more inefficient as you'd think. Firstly the computations on encrypted data just take a LOT longer, especially for Fully Homomorphic encryption. With a single 64 bit addition taking microseconds. Secondly, the FHE code cannot branch based on data. If it could, it would know something about the data, and it wouldn't be proper encryption. This means an if statement becomes "calculate both branches, and throw away the result you don't need". Similarly, a for loop becomes "give me an upper bound of how long this will run", then "loop for exactly the upper bound number of times, if the loop is 'done' early, just throw away the result of the remaining operations". FHE is really cool, and has its uses in situations where you want to cooperate without needing to trust, but it is stupidly inefficient. (Things get really cool if two parties want to cooperate and the computing party can e.g. branch based on their local unencrypted data)

teddyh 5y ago

HE is stupidly inefficient, and is entirely an academic oddity, and there is every indication that it will always remain that way. Bringing up HE in a context of real problems needing real solutions is unproductive.

ghaff 5y ago
If solving a problem in a stupidly inefficient way is the only way of mitigating said problem, you may not have much choice--at least for some use cases. Saying something can't be answer because it isn't an efficient answer (today) is also unproductive.
- PeterisP 5y ago
  There's a simple way of mitigating said problem - don't use shared hardware, and run each thing on aseparate, isolated chip. That's also inefficient, but compared to the immense overhead of HE it's quite reasonable.

simiones 5y ago

HE is incredibly slow, and unlikely to ever be fast enough for common workflows. As in, an HE implementation of an algorithm that runs in seconds in Python on a regular machine might run in minutes or tens of minutes. Not to mention, to avoid side-channel attacks, an HE scheme still needs to always run the longest possible sequence of operations regardless of input (otherwise, information about the input data is leaked through timing). So an HE version of a quick-sort scheme would always run in O(n^2), otherwise it would leak details about the contents of the list. In some cases it would even have to run in the same amount of time regardless of the size of the list, to avoid leaking information about that.

astrange 5y ago
Is HE any different from taking the encrypted input data, sticking the program you want to run on the end, and returning that? If anything, it sounds less efficient than that.
- tsimionescu 5y ago
  HE is designed for running a secret algorithm with secret input data and obtaining secret output data, all on an untrusted computer. It works a little bit like this: you write your algorithm using only HE computing primitives, then you encrypt it and the input data and send those to the HE runtime, who you don't trust, and who DOESN'T have any way to decrypt your message. The HE runtime executes your encrypted program and sends back the still encrypted output. Once you receive your output, you decrypt it using the key you have kept secret.
  - astrange 5y ago
    That's not how it works, that's what it does. I provided an example of how it could work, but it had better be more efficient than that or it's a silly idea.
    - tsimionescu 5y ago
      One note, first of all: I made one mistake, the algorithm is not secret in HE (the HE runtime has to know it). Only the input data is guaranteed to be secret. I'm not sure what you mean. This is how HE works, at a high level. The whole point is that you're doing public operations on secret data on a machine that can never know what the data was, nor what response it gave you. Furthermore, the point of HE is also that you know that your data remained secret regardless of how the HE runtime was implemented, as you just send it encrypted information. Making it more efficient by giving it access to the decrypted data would defeat the whole point. Making it more efficient by optimizing based on the actual data would allow your data to leak through timing side-channels, again defeating the whole point. Basically, HE refers to computing schemes where DECRYPT(ALGORITHM(ENCRYPT(X)) == ALGORITHM(X). You send [ALGORITHM, ENCRYPT(X)] to the runtime, and it gives you Y. DECRYPT(Y) is then the result of your computation. As far as we know, this is indeed hopelessly slow, and there is no guarantee that we will ever find fast secure HE primitives.