HOWTO: Full-text search over an encrypted database?

Question

I want to adhere to the best practices and obviously encrypt the data sent to me by user. And I also want to provide the full-text search feature to the user (user can only search their own data, if that is not quite obvious).

Example usecase:
There's a messaging app which is privacy oriented (for the simplicity of the example, we omit the e2e-encryption). This app stores messages in an encrypted form in a PostgreSQL database. I would like to provide a fulltext search feature, thus I need to build an fts-index.

I, however, cannot think of any possible solution. How to achieve it?

EDIT:

I am not asking about messaging app architecture, just a way to use fulltextsearch on encrypted data. And think of some other usecases, where the data to be searched is in orders of terrabytes, so offsetting the fts indexing to the client itself does not seem like a viable solution.

Answer 1

You don't.

The whole point of messaging privacy is that nobody except the sender and intended recipient are able to decrypt the messages. Not the platform provider, not their sysadmin, not some spy listening on network devices.

If the recipient wants to do a full text search, they may do so on their local device, where messages might be stored encrypted but could be decrypted using their private key on the fly. This will cause some performance hit, sometimes that's what you pay for privacy.

You say you omit e2e-encryption for simplicity of the example, but privacy that's not e2e is snake-oil privacy. Don't do that.

If your actual use case isn't messaging between users but users communicating with you, then you're party to the conversation and of course have a right to decrypt. You need to take extra precautions to make sure that you don't accidentally leak information entrusted to you to other users or external entities.

Answer 2

Obviously, you shouldn't have the key to decrypt messages, as pointed out by others. So how do you search on encrypted data?

Well, there is homomorphic encryption. Theoretically it lets you apply any function on the ciphertext itself, which then decrypts to the function applied to the cleartext. I.e. you can send a function to the server, which can evaluate it on the ciphertext without knowing what it is actually doing, then give you the result.

That is the good news. The bad news is in practice that doesn't work so well. Yet. Currently we can do a couple of additions and one or two multiplications at most. Even that is pretty computationally expensive. And there is no search algorithm/index design for it yet, so you'd have to roll your own.

All in all possible, but computationally expensive, and you'd be the first.

Just as a sidenote at Dead Drop (a private communication app) we do use homomorphic encryption (proprietary, not MS or OSS). Last time I checked we were at processing 20 MB/sec on one node I believe. And that is just one multiplication (and a bunch of additions, which are relatively easy), not a complex function.

Answer 3

The nature of (good) encryption is that the cypher text (the encrypted data) bears no resemblance to the plain text (the unencrypted data). That makes it impossible to perform a full text search on cypher text, with the expectation that you will find anything that is useful after decrypting.

Even something a simple as changing a single comma to a period or a lower-case letter to upper case in the plain text will yield a completely different cypher text.

With that out of the way, how do those other products off full-text search capabilities over an encrypted database? Simply by decrypting the entries in the database while performing the search. But, that requires that you have a decryption key for the data.

The big problem in your proposition is not technical. It is the notion that you offer a privacy oriented messaging app and that you have a key to decrypt the (private) communication between users of your app. Those two things are very much at odds with each other.

Answer 4

If you want to make full-text searches possible for a messaging app, it makes only sense for a user to search their own messages, the ones they send plus the ones they received. On the user's local device(s), the messages can be read and processed in decrypted form, hence it should be easy to build the index behind the decryption endpoint, on their local device, as long as the device has enough storage.

The index will allow to find one or more message IDs, and assumed the encryption is per message, it will allow you to retrive the correct message from the server by querying it by its id.

Assumed your users want to share the index over multiple devices, the index can be stored and distributed using the server, too, but only in encrypted form as well. Otherwise an attacker could be able to use the index to break the encryption of the messages.