3 ms·

Can someone explain how FHE can make data useable e.g. for a database application without also leaking lots of information? Like when I select count(*) from dat

Can someone explain how FHE can make data useable e.g. for a database application without also leaking lots of information? Like when I select count(*) from data where name = 'Bob' and SSN = 123, can't I use that to find out Bob's social security number with little effort despite FHE?

Dylan16807 6y ago
The database server won't have any idea what the query is, and doesn't know how to create encrypted queries either. It also won't know the size of the result, only seeing a fixed-size buffer.
- xyzzy123 6y ago
  I think what OP meant is that this logically implies every query must touch all the data (or else you could infer information from data access patterns) at which point is it really a database anymore as we know it?
  - Dylan16807 6y ago
    If that's the question, then the answer is "if you make it usable for a database application then it's not FHE, sorry"
    - adrianN 6y ago
      Interesting, so FHE is essentially useless for cloud applications? What would be a good use case where FHE can be applied?
      - Dylan16807 6y ago
        Many types of processing on small data sets are fine. Or lots of small data sets in parallel. You could run statistics on data or do a grid-based simulation. Running a neural net would be almost trivial. General purpose code is extremely difficult to adapt, since it loves to branch based on data.
        adrianN 6y ago
        Neural nets are a very convincing use case. Thanks!
        haggy 6y ago
        No offense but just "running a neural net" is rarely trivial
        Dylan16807 6y ago
        What do you mean? I'm not talking about design or tuning or anything, just shoving raw data through. All you have to do is multiply each weight and add up each node. Pure bulk arithmetic is both simple and a perfect match for FHE.
        fingerlocks 6y ago
        “Trivial” is relative, and in the context of this forum post and the audience that is reading it, running a basic neural net is unlikely a large hurdle for most here. Hell, I’m not an ML practitioner and I almost never use python, and yet it took me maybe a day or two learn enough about covnet training to detect my dog on a home security camera.
      - numpad0 6y ago
        Probably good for batch jobs? Updating billing information, device location registry, etc., for 10k users each day or each hour etc.
      - bawolff 6y ago
        "Cloud applications" cover a big range. If you mean is it useless as a replacement for the mysql backend of your php app, the answer is yes.
threeseed 6y ago
I'm confused what your plan of attack is. Because simply querying the database a billion times and replacing SSN with 1, 2 etc. is never going to work in any reasonably secure environment. Queries are logged and people will know if you're trying to brute force a table.
- comex 6y ago
  The whole point of homomorphic encryption is that you don’t trust the server doing the computation.
  - threeseed 6y ago
    Is it ? I thought the whole point was that your data remains encrypted during computation. Especially for data lakes where the act of manipulating data can sometimes involve moving actual files around a distributed cluster in a potentially insecure environment e.g. cloud.
KenoFischer 6y ago
For practical applications you can do better if you allow some information leakage or multiple rounds of communication. People play various tricks. What kind of leakage is acceptable depends on the application.
doomrobo 6y ago
You're right. This isn't a good use case for FHE. Instead, FHE is really useful when the query itself is private, and the data is not private. One example is a private OCSP. Every time you open a TLS-secured webpage, your browser has to check whether or not the TLS certificate has been revoked (I'm leaving out some complications but bear with me). In order to do that, you browser has to contact the certificate authority (CA) and ask "has anyone revoked this cert?". But in doing that, the browser is revealing your browsing patterns to the CA! It would be nice, instead, to use Private Information Retrieval to ask the CA "please process this encrypted query and return the result". Then the CA knows nothing about your browsing patterns, and you still get your data. Well, (computational) Private Information Retrieval is super inefficient today, and the best asymptotic solution we have is based on FHE (https://eprint.iacr.org/2017/1142 https://eprint.iacr.org/2017/1142). So getting efficient FHE would hopefully make something like this a lot more reasonable for moderately sized databases. For the record, this is only a toy example. We actually have really good solutions for private OCSP that don't require FHE. We can side-step the difficult of Private Information Retrieval in this case because OCSP databases are small enough for anyone to download. If this interests you, check out CRLite https://blog.mozilla.org/security/2020/01/09/crlite-part-1-all-web-pki-revocations-compressed/ https://blog.mozilla.org/security/2020/01/09/crlite-part-1-a...
- totetsu 6y ago
  - Does -my time/location- match any time/location where we know corona case was. - Does -my dna- match known predistortions for diseases that kind of thing.

Dylan16807 6y ago

The database server won't have any idea what the query is, and doesn't know how to create encrypted queries either. It also won't know the size of the result, only seeing a fixed-size buffer.

xyzzy123 6y ago
I think what OP meant is that this logically implies every query must touch all the data (or else you could infer information from data access patterns) at which point is it really a database anymore as we know it?
- Dylan16807 6y ago
  If that's the question, then the answer is "if you make it usable for a database application then it's not FHE, sorry"
  - adrianN 6y ago
    Interesting, so FHE is essentially useless for cloud applications? What would be a good use case where FHE can be applied?
    - Dylan16807 6y ago
      Many types of processing on small data sets are fine. Or lots of small data sets in parallel. You could run statistics on data or do a grid-based simulation. Running a neural net would be almost trivial. General purpose code is extremely difficult to adapt, since it loves to branch based on data.
      - adrianN 6y ago
        Neural nets are a very convincing use case. Thanks!
      - haggy 6y ago
        No offense but just "running a neural net" is rarely trivial
        Dylan16807 6y ago
        What do you mean? I'm not talking about design or tuning or anything, just shoving raw data through. All you have to do is multiply each weight and add up each node. Pure bulk arithmetic is both simple and a perfect match for FHE.
        fingerlocks 6y ago
        “Trivial” is relative, and in the context of this forum post and the audience that is reading it, running a basic neural net is unlikely a large hurdle for most here. Hell, I’m not an ML practitioner and I almost never use python, and yet it took me maybe a day or two learn enough about covnet training to detect my dog on a home security camera.
    - numpad0 6y ago
      Probably good for batch jobs? Updating billing information, device location registry, etc., for 10k users each day or each hour etc.
    - bawolff 6y ago
      "Cloud applications" cover a big range. If you mean is it useless as a replacement for the mysql backend of your php app, the answer is yes.

threeseed 6y ago

I'm confused what your plan of attack is. Because simply querying the database a billion times and replacing SSN with 1, 2 etc. is never going to work in any reasonably secure environment. Queries are logged and people will know if you're trying to brute force a table.

comex 6y ago
The whole point of homomorphic encryption is that you don’t trust the server doing the computation.
- threeseed 6y ago
  Is it ? I thought the whole point was that your data remains encrypted during computation. Especially for data lakes where the act of manipulating data can sometimes involve moving actual files around a distributed cluster in a potentially insecure environment e.g. cloud.

KenoFischer 6y ago

For practical applications you can do better if you allow some information leakage or multiple rounds of communication. People play various tricks. What kind of leakage is acceptable depends on the application.

doomrobo 6y ago

You're right. This isn't a good use case for FHE. Instead, FHE is really useful when the query itself is private, and the data is not private. One example is a private OCSP. Every time you open a TLS-secured webpage, your browser has to check whether or not the TLS certificate has been revoked (I'm leaving out some complications but bear with me). In order to do that, you browser has to contact the certificate authority (CA) and ask "has anyone revoked this cert?". But in doing that, the browser is revealing your browsing patterns to the CA! It would be nice, instead, to use Private Information Retrieval to ask the CA "please process this encrypted query and return the result". Then the CA knows nothing about your browsing patterns, and you still get your data. Well, (computational) Private Information Retrieval is super inefficient today, and the best asymptotic solution we have is based on FHE (https://eprint.iacr.org/2017/1142 https://eprint.iacr.org/2017/1142). So getting efficient FHE would hopefully make something like this a lot more reasonable for moderately sized databases. For the record, this is only a toy example. We actually have really good solutions for private OCSP that don't require FHE. We can side-step the difficult of Private Information Retrieval in this case because OCSP databases are small enough for anyone to download. If this interests you, check out CRLite https://blog.mozilla.org/security/2020/01/09/crlite-part-1-all-web-pki-revocations-compressed/ https://blog.mozilla.org/security/2020/01/09/crlite-part-1-a...

totetsu 6y ago
- Does -my time/location- match any time/location where we know corona case was. - Does -my dna- match known predistortions for diseases that kind of thing.