4 ms·

Homomorphic encryption (HE) is NOT what people would understand as "on-chip cryptography", i.e., secure enclaves. HE is a form of encryption that allows arithme

Homomorphic encryption (HE) is NOT what people would understand as "on-chip cryptography", i.e., secure enclaves. HE is a form of encryption that allows arithmetic operations on encrypted numbers without any access to the decryption key. Secure enclaves on the other hand do decrypt data on-chip and are thus vulnerable to side channel attacks. You can use HE to implement things like encrypted database lookups that don't reveal what is being queried (even to the database server) and the security of the encrypted query does not depend on any hardware properties of the server providing the service.

Dylan16807 6y ago
While noting that "database lookup" is a painful scenario for HE because you have to read through the entire thing just to find a single row.
- Misdicorl 6y ago
  Wouldn't a normal db btree index work just fine? Scans certainly seem problematic though
  - Dylan16807 6y ago
    A tree would require the ability to have control flow based on data, or using data as an index. You can't do that while keeping the data secret. Just to select a single row you have to do something like sum(row_meets_criteria() * row). With row_meets_criteria returning 0 or 1.
    - trhway 6y ago
      for equality predicate you can just use hash based index, for range search the situation is of course worse, yet you can have a somewhat like a partially/probabilistically preserving order hash so that you can produce a number of candidates orders of magnitude less than the whole table scan.
      - bawolff 6y ago
        But then you are not using FHE, but something with much weaker security properties.
      - RobLach 6y ago
        The mere fact that you did not need to scan the entire db means the data was not securely encrypted in the first place.
  - dodobirdlord 6y ago
    If every query didn’t walk the entire dataset then the server could figure out what was queried based on what data was loaded and what data was not loaded.
    - mikepurvis 6y ago
      Does that matter if the indexes, the data, and the query are all encrypted?
      - im3w1l 6y ago
        Possibly? It could leak data in a lot of ways. For instance you might see that a particular IP is accessing particular rows. Or you might see that certain rows are accessed together. For instance if rows represent users, you could look at the "shape" of accesses and try to match that to the shape of a social network you know from elsewhere. As an unrealistic reduced example: Maybe you know that Alice is friends with Bob and Charlie and Dennis. Bob is friends with Charlie. Now you see that W has 3 friends X, Y, Z, of which X and Z are friends with each other. Then W might be Alice, the X and Z might be Bob and Charlie (but we don't know which is which), and the Y Dennis. . ABCD A xxx B x x C xx D x . XYZW X xx Y x Z x x W xxxx
        mikepurvis 6y ago
        Fair. I suppose it really depends what the motivating use cases are for this kind of thing— in my head, the killer app would be a mail server where I decrypt (from GPG) my email in my local client, and then re-encrypt (with HE) and prepare indexing information which is sent to a cloud service for long-term archival. The cloud service allows me to search on and retrieve my email without ever seeing the contents or knowing any of the metadata other than when you uploaded them and the message lengths (and even that could be scrambled up a bunch by adding arbitrary padding and periodically re-uploading old messages). In this scenario there isn't really the "known from elsewhere" info— knowing that certain groups of messages are returned together in response to sets of queries is unlikely to be meaningful if you don't have anything else to map that info to. And thinking about it further, the client could do other shenanigans to further protect the user, like arranging for every query to return 20% "false" results that are filtered out before display, or storing duplicate instances in the database so that the server thinks query X leads to result A and query Y leads to result B, without knowing the A and B are in fact the same thing.

Dylan16807 6y ago

While noting that "database lookup" is a painful scenario for HE because you have to read through the entire thing just to find a single row.

Misdicorl 6y ago
Wouldn't a normal db btree index work just fine? Scans certainly seem problematic though
- Dylan16807 6y ago
  A tree would require the ability to have control flow based on data, or using data as an index. You can't do that while keeping the data secret. Just to select a single row you have to do something like sum(row_meets_criteria() * row). With row_meets_criteria returning 0 or 1.
  - trhway 6y ago
    for equality predicate you can just use hash based index, for range search the situation is of course worse, yet you can have a somewhat like a partially/probabilistically preserving order hash so that you can produce a number of candidates orders of magnitude less than the whole table scan.
    - bawolff 6y ago
      But then you are not using FHE, but something with much weaker security properties.
    - RobLach 6y ago
      The mere fact that you did not need to scan the entire db means the data was not securely encrypted in the first place.
- dodobirdlord 6y ago
  If every query didn’t walk the entire dataset then the server could figure out what was queried based on what data was loaded and what data was not loaded.
  - mikepurvis 6y ago
    Does that matter if the indexes, the data, and the query are all encrypted?
    - im3w1l 6y ago
      Possibly? It could leak data in a lot of ways. For instance you might see that a particular IP is accessing particular rows. Or you might see that certain rows are accessed together. For instance if rows represent users, you could look at the "shape" of accesses and try to match that to the shape of a social network you know from elsewhere. As an unrealistic reduced example: Maybe you know that Alice is friends with Bob and Charlie and Dennis. Bob is friends with Charlie. Now you see that W has 3 friends X, Y, Z, of which X and Z are friends with each other. Then W might be Alice, the X and Z might be Bob and Charlie (but we don't know which is which), and the Y Dennis. . ABCD A xxx B x x C xx D x . XYZW X xx Y x Z x x W xxxx
      - mikepurvis 6y ago
        Fair. I suppose it really depends what the motivating use cases are for this kind of thing— in my head, the killer app would be a mail server where I decrypt (from GPG) my email in my local client, and then re-encrypt (with HE) and prepare indexing information which is sent to a cloud service for long-term archival. The cloud service allows me to search on and retrieve my email without ever seeing the contents or knowing any of the metadata other than when you uploaded them and the message lengths (and even that could be scrambled up a bunch by adding arbitrary padding and periodically re-uploading old messages). In this scenario there isn't really the "known from elsewhere" info— knowing that certain groups of messages are returned together in response to sets of queries is unlikely to be meaningful if you don't have anything else to map that info to. And thinking about it further, the client could do other shenanigans to further protect the user, like arranging for every query to return 20% "false" results that are filtered out before display, or storing duplicate instances in the database so that the server thinks query X leads to result A and query Y leads to result B, without knowing the A and B are in fact the same thing.