5 ms·

You can use tricks to reduce this requirement. For example, you access a random subset, and at the same time you randomly rearrange a portion of the data. Viewe

by Taek 6y ago

You can use tricks to reduce this requirement. For example, you access a random subset, and at the same time you randomly rearrange a portion of the data. Viewer can't narrow anything down because you are shuffling fast enough to invalidate anything they learn from your access patterns.

heavenlyblue 6y ago
You should be able to relax even that assumption: if the executor doesn’t know the contents of the database itself, then it may not even matter to you that they can correlate your query with the row in the database (they can build a book of correlations but they still would not be able to see the contents). It should be even more feasible if the query contains some random nonce too?
- Someone 6y ago
  If they can correlate you with rows in the database, and they can correlate me with rows in the database, they can correlate you with me. Given enough queries and perseverance in unraveling things, a surprising amount of information can leak, for example whether you and me live in the same country, frequently travel together (indicating a relationship), etc.
  - heavenlyblue 6y ago
    I said “relax the condition” and also said “they know nothing about the information stored in the database”. I am trying to see whether I am missing something and you’re adding things I removed back into the equation.
    - sukilot 6y ago
      I think what you are missing is yet your assumptions are unreasonable and unrealistic. If we could just keep our data secret, we wouldn't need encryption at all.
- Taek 6y ago
  Working on privacy tech has taught me that zero knowledge is absolutely critical if you want true privacy. Statistical correlation is stupidly powerful. Identifying someone uniquely in the world requires about 33 bits of entropy. Which means you have have some statistical analysis that reveals 0.01 bits of information per sample, you only need 3300 samples to uniquely identify the person performing the activity. It's a bit tough to explain without having actual examples, but the same math that allows a javascript library running in a web browser to extract the private key being computed in a VM elsewhere on the machine can also be used to identify which individual people have diabetes from looking at a stack of "anonymized" health reports, or which individual people are watching porn from looking at an aggregated history of request sizes going through a VPN.
  - heavenlyblue 6y ago
    > the same math that allows a javascript library running in a web browser to extract the private key being computed in a VM elsewhere on the machine I am not entirely certain whether I was clear about the point I made in my message, however I have asked a very specific technical question and you are making some generalised sweeping statement about privacy in the most widely used case. We could not decrypt any ancient languages, for example; if we didn’t have an equivalent of a Rosetta Stone for them. Thus you should not be able to do the same for the encrypted database I assume.
    - sukilot 6y ago
      "hiding the database" is security-through-obscurity, which is not security.
  - disabled 6y ago
    > 33 bits of entropy For the clueless (including myself--I just looked this up), if doing a brute-force search to identify or reidentify someone using "anonymized" data (which is what this poster is referring to), it only takes 2^33 attempts, or 8,589,934,592 attempts (on a bit scale--binary--0 or 1), to exhaust all other possibilities (such as other people--when reidentifying people via health data that was "anonymized"), when tracing to find a person via data in general. Obviously some data is more sensitive than others, but that has little relevance: it requires nearly no data (especially in terms of what is being hoarded about each and every one of us) and virtually no effort or computing power, to be found. This also means that even the most mundane (and always sensitive, too--although some data is more sensitive!) data that has been hoarded about you will be used against you, in ways you would have never imagined. It will be used for processing and inferences (which you are unaware of) will be made on you. You are already probably part of several unhealthy social experiments that you are unaware of, via correlations from mundane data, using things that are pervasive such as AI.
- SilasX 6y ago
  Right but I would think you'd also need to avoid the executor learning that you were accessing the same record at different times. Merely encrypting the records wouldn't prevent this, so your query (to be homomorphically encrypted) would need to be executed in such a way that you look at more than one record. You'd need that to stop the risk that, say, an attacker learns (from a side channel) you were looking for person A's details at time T1, and thereby unmasks which other queries/times were about A.
wsxcde 6y ago
You're trying to come up with a homemade ORAM. All I'll say is that this problem is harder than it seems.

by Taek 6y ago

heavenlyblue 6y ago

You should be able to relax even that assumption: if the executor doesn’t know the contents of the database itself, then it may not even matter to you that they can correlate your query with the row in the database (they can build a book of correlations but they still would not be able to see the contents). It should be even more feasible if the query contains some random nonce too?

Someone 6y ago
If they can correlate you with rows in the database, and they can correlate me with rows in the database, they can correlate you with me. Given enough queries and perseverance in unraveling things, a surprising amount of information can leak, for example whether you and me live in the same country, frequently travel together (indicating a relationship), etc.
- heavenlyblue 6y ago
  I said “relax the condition” and also said “they know nothing about the information stored in the database”. I am trying to see whether I am missing something and you’re adding things I removed back into the equation.
  - sukilot 6y ago
    I think what you are missing is yet your assumptions are unreasonable and unrealistic. If we could just keep our data secret, we wouldn't need encryption at all.
Taek 6y ago
Working on privacy tech has taught me that zero knowledge is absolutely critical if you want true privacy. Statistical correlation is stupidly powerful. Identifying someone uniquely in the world requires about 33 bits of entropy. Which means you have have some statistical analysis that reveals 0.01 bits of information per sample, you only need 3300 samples to uniquely identify the person performing the activity. It's a bit tough to explain without having actual examples, but the same math that allows a javascript library running in a web browser to extract the private key being computed in a VM elsewhere on the machine can also be used to identify which individual people have diabetes from looking at a stack of "anonymized" health reports, or which individual people are watching porn from looking at an aggregated history of request sizes going through a VPN.
- heavenlyblue 6y ago
  > the same math that allows a javascript library running in a web browser to extract the private key being computed in a VM elsewhere on the machine I am not entirely certain whether I was clear about the point I made in my message, however I have asked a very specific technical question and you are making some generalised sweeping statement about privacy in the most widely used case. We could not decrypt any ancient languages, for example; if we didn’t have an equivalent of a Rosetta Stone for them. Thus you should not be able to do the same for the encrypted database I assume.
  - sukilot 6y ago
    "hiding the database" is security-through-obscurity, which is not security.
- disabled 6y ago
  > 33 bits of entropy For the clueless (including myself--I just looked this up), if doing a brute-force search to identify or reidentify someone using "anonymized" data (which is what this poster is referring to), it only takes 2^33 attempts, or 8,589,934,592 attempts (on a bit scale--binary--0 or 1), to exhaust all other possibilities (such as other people--when reidentifying people via health data that was "anonymized"), when tracing to find a person via data in general. Obviously some data is more sensitive than others, but that has little relevance: it requires nearly no data (especially in terms of what is being hoarded about each and every one of us) and virtually no effort or computing power, to be found. This also means that even the most mundane (and always sensitive, too--although some data is more sensitive!) data that has been hoarded about you will be used against you, in ways you would have never imagined. It will be used for processing and inferences (which you are unaware of) will be made on you. You are already probably part of several unhealthy social experiments that you are unaware of, via correlations from mundane data, using things that are pervasive such as AI.
SilasX 6y ago
Right but I would think you'd also need to avoid the executor learning that you were accessing the same record at different times. Merely encrypting the records wouldn't prevent this, so your query (to be homomorphically encrypted) would need to be executed in such a way that you look at more than one record. You'd need that to stop the risk that, say, an attacker learns (from a side channel) you were looking for person A's details at time T1, and thereby unmasks which other queries/times were about A.

wsxcde 6y ago

You're trying to come up with a homemade ORAM. All I'll say is that this problem is harder than it seems.