4 ms·

Someone please correct me if I'm wrong, wouldn't this still be vulnerable to side channel or pattern analysis attacks? Also, how can all operations on a DB lik

Someone please correct me if I'm wrong, wouldn't this still be vulnerable to side channel or pattern analysis attacks? Also, how can all operations on a DB like projection, and equality be represented by addition and multiplication? Are we in the peano arithmetic space here? Can somebody break it down from me?

kmeisthax 6y ago
You answered your own question accidentally: side-channel attacks are not possible in this model of computation because everything is represented as addition and multiplication. The homomorphic ciphertext doesn't tell you when it's done, you sort of just do all the operations you're told and hand back the answer gaining no knowledge about the computation you just did. That's not to say that a badly-designed usage of homomorphic computation can't introduce a timing channel, though. If there's a point in time where the result is handed back to the client, they inspect it, and then conditionally send more computations, you might be able to infer something with either the client's timing or if they happened to send back more computations or not. However, that assumes that we'd be able to trace multiple API requests associated with the same data set (as opposed to unrelated computations), and that we know enough about the computations we're being told to do to infer a timing channel from them. That's why I use the qualifying term "badly-designed", which in practice will probably be most uses of this technology.
- bfuclusion 6y ago
  So basically I tell you to do a bunch of stuff and give it back, and you have no idea if the computation is a partial application/full application etc. Neat. Next question: if my previous statement is correct it seems that it may push a lot of the work back onto the client, otherwise I don't get how a server couldn't figure out relationships from access patterns on blocks. This would limit the utility of the server right?
  - dodobirdlord 6y ago
    Yea, fully homomorphic querying of a database necessarily requires reading all of the data, or you could glean information from the access pattern.
    - josh2600 6y ago
      You can get a lot of the benefit of a linear scan using a technique like oblivious RAM but I’m not convinced it’s possible to build such a system without using a Secure Enclave. There are some papers that purport to implement this but once you’re dancing in the realm of Secure Enclave’s you’re out on a different limb. I don’t think it’s possible for a circuit to operate over a large set quickly and use a fully homomorphic pure software design.
      - Ar-Curunir 6y ago
        With some minor interaction between client and server, you can use ORAM in conjunction with FHE to enable sub linear database scans. It’s not practical for deployments, but is probably feasible for implementations
        josh2600 6y ago
        I’m not convinced you can do ORAM without a Secure Enclave. If you’re already using an enclave, you don’t need FHE.
indolering 6y ago
That's a lot of questions, but AFAIK it is not vulnerable to side channel analysis. That's why the author spent time on the database search use case; you must visit every row because you don't want an attacker to be able to segment your data at all. It would be possible to make trade-offs in that specific case, but cryptographic engineers are loathe to give the common programmer such a foot-gun.
- bfuclusion 6y ago
  Yeah, this stuff is cool so I'm trying to wrap my head around it. It sounds from what you're saying that you're trading a lot of efficiency for protection, but I can't see any way around it.
moonchild 6y ago
There can always be side channels. Side channel means some information channel that your model doesn't account for. By definition, it's not possible to be sure an implementation of a model doesn't have any side channels. The best known class of side channels is timing attacks, where the amount of time that an operation takes leaks some information about its content. This is a well-known area of research, and most modern implementations of cryptographical algorithms do take it into account; I expect this one does, too. If you can model the time an operation takes, you can prove that a given implementation has no timing channel. But any number of other side channels could potentially exist in this (or any other) implementation.
- bfuclusion 6y ago
  Got it. I took another pass through the article and was able to understand it a bit better with everyone's comments. Thanks all.

kmeisthax 6y ago

You answered your own question accidentally: side-channel attacks are not possible in this model of computation because everything is represented as addition and multiplication. The homomorphic ciphertext doesn't tell you when it's done, you sort of just do all the operations you're told and hand back the answer gaining no knowledge about the computation you just did. That's not to say that a badly-designed usage of homomorphic computation can't introduce a timing channel, though. If there's a point in time where the result is handed back to the client, they inspect it, and then conditionally send more computations, you might be able to infer something with either the client's timing or if they happened to send back more computations or not. However, that assumes that we'd be able to trace multiple API requests associated with the same data set (as opposed to unrelated computations), and that we know enough about the computations we're being told to do to infer a timing channel from them. That's why I use the qualifying term "badly-designed", which in practice will probably be most uses of this technology.

bfuclusion 6y ago
So basically I tell you to do a bunch of stuff and give it back, and you have no idea if the computation is a partial application/full application etc. Neat. Next question: if my previous statement is correct it seems that it may push a lot of the work back onto the client, otherwise I don't get how a server couldn't figure out relationships from access patterns on blocks. This would limit the utility of the server right?
- dodobirdlord 6y ago
  Yea, fully homomorphic querying of a database necessarily requires reading all of the data, or you could glean information from the access pattern.
  - josh2600 6y ago
    You can get a lot of the benefit of a linear scan using a technique like oblivious RAM but I’m not convinced it’s possible to build such a system without using a Secure Enclave. There are some papers that purport to implement this but once you’re dancing in the realm of Secure Enclave’s you’re out on a different limb. I don’t think it’s possible for a circuit to operate over a large set quickly and use a fully homomorphic pure software design.
    - Ar-Curunir 6y ago
      With some minor interaction between client and server, you can use ORAM in conjunction with FHE to enable sub linear database scans. It’s not practical for deployments, but is probably feasible for implementations
      - josh2600 6y ago
        I’m not convinced you can do ORAM without a Secure Enclave. If you’re already using an enclave, you don’t need FHE.

indolering 6y ago

That's a lot of questions, but AFAIK it is not vulnerable to side channel analysis. That's why the author spent time on the database search use case; you must visit every row because you don't want an attacker to be able to segment your data at all. It would be possible to make trade-offs in that specific case, but cryptographic engineers are loathe to give the common programmer such a foot-gun.

bfuclusion 6y ago
Yeah, this stuff is cool so I'm trying to wrap my head around it. It sounds from what you're saying that you're trading a lot of efficiency for protection, but I can't see any way around it.

moonchild 6y ago

There can always be side channels. Side channel means some information channel that your model doesn't account for. By definition, it's not possible to be sure an implementation of a model doesn't have any side channels. The best known class of side channels is timing attacks, where the amount of time that an operation takes leaks some information about its content. This is a well-known area of research, and most modern implementations of cryptographical algorithms do take it into account; I expect this one does, too. If you can model the time an operation takes, you can prove that a given implementation has no timing channel. But any number of other side channels could potentially exist in this (or any other) implementation.

bfuclusion 6y ago
Got it. I took another pass through the article and was able to understand it a bit better with everyone's comments. Thanks all.