5 ms·

As a key:value store this makes sense. However modern data stores need to do more than just store values with known keys. The most popular stores support some

As a key:value store this makes sense. However modern data stores need to do more than just store values with known keys. The most popular stores support some sort of query system that implies the database itself can make sense of the data. However when the data is encrypted this is no longer possible as the data store cannot make any sense if the stored information. I’d love to see something that could support queries on encrypted data without comprising privacy. I just don’t know how that would be possible.

withinboredom 4y ago
If you know what you are indexing by, you can use a bloom filter. However, this gives an attacker information they otherwise wouldn’t have. It’s trade offs, as usual.
- bognition 4y ago
  How can you do range queries with a bloom filter? Ie show me all records created between two specific dates
  - withinboredom 4y ago
    Hash the dates you are looking for and do a binary OR. It becomes unreasonable to search beyond n-dates, so arbitrary searches are probably out of the question. It also depends on how you are storing the filter (I’m thinking of a scheme I worked on for work in GDPR anonymization which suffers the same sort of problems)
    - deleted 4y ago
      [deleted]
    - bognition 4y ago
      Sure you can do a binary OR but you need to examine all of the data in the table which effectively becomes a full table scan. The beauty of indices is that you only need to scan a subset of the data to find the information you're looking for.
      - withinboredom 4y ago
        You can store columns for each bit in the filter, so a binary OR wasn’t a full table scan, just an index lookup for certain columns.
  - deleted 4y ago
    [deleted]
a1369209993 4y ago
> something that could support queries on encrypted data Assuming you're talking about client-specified queries (database-specified are impossible by definition of "encrypted"), the keyword you want is "fully homomorphic encryption". AFAIK, there aren't any fully working systems yet, although they're pretty close and should be available Real Soon Now. The main restriction is that for any given query you have a response of a fixed (and known-to-the-attacker) size, so you can't do open-ended queries like "all records between 2021-01-01 and 2021-12-31". Instead you'd get something like a fixed-size mapreduce/foldMap interface, and queries would look something like "total number of records (modulo UINT_MAX+1) matching predicate x and first N such records according to ordering y", where N, sizeof x, and sizeof y - but not x and y themselves - are known by the database/attacker.
- withinboredom 4y ago
  This is not necessarily true. It depends on your security model. You can use a bloom filter on each row. When the client does the encryption it encodes properties about the encrypted value into a bloom filter. The filter’s construction can be scrambled according to the user (salted) using regular means (xor). An attacker would need to unsalt the filter and know how to query the filter in order to derive any useful information. Arbitrary querying of all users data is computationally impossible. The client can even do the salting and pass the salt to the server to support server-side querying, thus allowing a user to consent to a server to know information it otherwise wouldn’t know.
MattPalmer1086 4y ago
There are things like cryptdb: https://m-cacm.acm.org/magazines/2012/9/154574-cryptdb-processing-queries-on-an-encrypted-database/fulltext https://m-cacm.acm.org/magazines/2012/9/154574-cryptdb-proce... Update: It's been a while since I've looked into encrypted databases. They do a reasonable job, but they are limited in various ways. Private Information Retrieval is also interesting. https://en.m.wikipedia.org/wiki/Private_information_retrieval https://en.m.wikipedia.org/wiki/Private_information_retrieva...
Comevius 4y ago
I spent a long time trying to build a privacy-preserving database. The challenge is that a persistent attacker (a honest, but curious server hosting your data) can defeat the encryption by observing the access pattern. This happens because issuing the same query twice will access the same encrypted data, and the same amount of encrypted data. Naively one would think that this is of no use, and such patterns can be trivially obfuscated, but any statistical correlation can be fatal, and ensuing that they do not occur is costly. If you would download the entire database for each query that would be private, but also have a linear communication overhead. You could rewrite data to a new location after you read it, which is what ORAM does, and it has at least a logarithmic communication overhead. This is where the buck stops, logarithmic is a theoretical minimum cost even for the weakest computational access pattern privacy guarantees. With differential privacy guarantees a double logarithmic overhead is possible, but it is not clear when such guarantees are useful. Fully homomorphic encryption would only allow to push the overhead from communication to computation. On the practical side there are symmetric searchable encryption schemes with forward and backward privacy. They are reasonably functional, with reasonable leakage, without any guarantees. They tend to be vulnerable to sophisticated adversaries with knowledge about the queries or the documents. These schemes often have to deal with more than just access pattern privacy, because they not all passive (where the server is only a storage device, the client selects the documents to access). They have to worry about the search tokens presented to the server, which is now running code. Some of these schemes have to deal with a malicious server breaking protocol.

withinboredom 4y ago

If you know what you are indexing by, you can use a bloom filter. However, this gives an attacker information they otherwise wouldn’t have. It’s trade offs, as usual.

bognition 4y ago
How can you do range queries with a bloom filter? Ie show me all records created between two specific dates
- withinboredom 4y ago
  Hash the dates you are looking for and do a binary OR. It becomes unreasonable to search beyond n-dates, so arbitrary searches are probably out of the question. It also depends on how you are storing the filter (I’m thinking of a scheme I worked on for work in GDPR anonymization which suffers the same sort of problems)
  - deleted 4y ago
    [deleted]
  - bognition 4y ago
    Sure you can do a binary OR but you need to examine all of the data in the table which effectively becomes a full table scan. The beauty of indices is that you only need to scan a subset of the data to find the information you're looking for.
    - withinboredom 4y ago
      You can store columns for each bit in the filter, so a binary OR wasn’t a full table scan, just an index lookup for certain columns.
- deleted 4y ago
  [deleted]

a1369209993 4y ago

> something that could support queries on encrypted data Assuming you're talking about client-specified queries (database-specified are impossible by definition of "encrypted"), the keyword you want is "fully homomorphic encryption". AFAIK, there aren't any fully working systems yet, although they're pretty close and should be available Real Soon Now. The main restriction is that for any given query you have a response of a fixed (and known-to-the-attacker) size, so you can't do open-ended queries like "all records between 2021-01-01 and 2021-12-31". Instead you'd get something like a fixed-size mapreduce/foldMap interface, and queries would look something like "total number of records (modulo UINT_MAX+1) matching predicate x and first N such records according to ordering y", where N, sizeof x, and sizeof y - but not x and y themselves - are known by the database/attacker.

withinboredom 4y ago
This is not necessarily true. It depends on your security model. You can use a bloom filter on each row. When the client does the encryption it encodes properties about the encrypted value into a bloom filter. The filter’s construction can be scrambled according to the user (salted) using regular means (xor). An attacker would need to unsalt the filter and know how to query the filter in order to derive any useful information. Arbitrary querying of all users data is computationally impossible. The client can even do the salting and pass the salt to the server to support server-side querying, thus allowing a user to consent to a server to know information it otherwise wouldn’t know.

MattPalmer1086 4y ago

There are things like cryptdb: https://m-cacm.acm.org/magazines/2012/9/154574-cryptdb-processing-queries-on-an-encrypted-database/fulltext https://m-cacm.acm.org/magazines/2012/9/154574-cryptdb-proce... Update: It's been a while since I've looked into encrypted databases. They do a reasonable job, but they are limited in various ways. Private Information Retrieval is also interesting. https://en.m.wikipedia.org/wiki/Private_information_retrieval https://en.m.wikipedia.org/wiki/Private_information_retrieva...

Comevius 4y ago

I spent a long time trying to build a privacy-preserving database. The challenge is that a persistent attacker (a honest, but curious server hosting your data) can defeat the encryption by observing the access pattern. This happens because issuing the same query twice will access the same encrypted data, and the same amount of encrypted data. Naively one would think that this is of no use, and such patterns can be trivially obfuscated, but any statistical correlation can be fatal, and ensuing that they do not occur is costly. If you would download the entire database for each query that would be private, but also have a linear communication overhead. You could rewrite data to a new location after you read it, which is what ORAM does, and it has at least a logarithmic communication overhead. This is where the buck stops, logarithmic is a theoretical minimum cost even for the weakest computational access pattern privacy guarantees. With differential privacy guarantees a double logarithmic overhead is possible, but it is not clear when such guarantees are useful. Fully homomorphic encryption would only allow to push the overhead from communication to computation. On the practical side there are symmetric searchable encryption schemes with forward and backward privacy. They are reasonably functional, with reasonable leakage, without any guarantees. They tend to be vulnerable to sophisticated adversaries with knowledge about the queries or the documents. These schemes often have to deal with more than just access pattern privacy, because they not all passive (where the server is only a storage device, the client selects the documents to access). They have to worry about the search tokens presented to the server, which is now running code. Some of these schemes have to deal with a malicious server breaking protocol.