4 ms·
> something that could support queries on encrypted data Assuming you're talking about client-specified queries (database-specified are impossible by definitio
by 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 agoThis 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.