> Not sure what the state the art is in searchable encryption for db indexes, but just trying to do stuff that requires a scan becomes untenable due to having to read and decrypt on the client to find it or aggregate it.
There are a lot of different approaches, but the one CipherSweet uses is actually simple.
First, take the HMAC() of the plaintext (or of some pre-determined transformation of the plaintext), with a static key.
Now, throw away most of it, except a few bits. Store those.
Later, when you want to query your database, perform the same operation on your query.
One of two things will happen:
1. Despite most of the bits being discarded, you will find your plaintext.
2. With overwhelming probability, you will also find some false positives. This will be significantly less than a full table scan (O(log N) vs O(N)). Your library needs to filter those out.
This simple abstraction gives you k-anonymity. The only difficulty is, you need to know how many bits to keep. This is not trivial and requires knowing the shape of your data.
https://ciphersweet.paragonie.com/security#blind-index-infor...
I proposed the same technique to AWS, who adopted it under the name Beacons for the AWS Database Encryption SDK.
https://docs.aws.amazon.com/database-encryption-sdk/latest/d...
There are a lot of different approaches, but the one CipherSweet uses is actually simple.
First, take the HMAC() of the plaintext (or of some pre-determined transformation of the plaintext), with a static key.
Now, throw away most of it, except a few bits. Store those.
Later, when you want to query your database, perform the same operation on your query.
One of two things will happen:
1. Despite most of the bits being discarded, you will find your plaintext.
2. With overwhelming probability, you will also find some false positives. This will be significantly less than a full table scan (O(log N) vs O(N)). Your library needs to filter those out.
This simple abstraction gives you k-anonymity. The only difficulty is, you need to know how many bits to keep. This is not trivial and requires knowing the shape of your data.
https://ciphersweet.paragonie.com/security#blind-index-infor...
I proposed the same technique to AWS, who adopted it under the name Beacons for the AWS Database Encryption SDK.
https://docs.aws.amazon.com/database-encryption-sdk/latest/d...