0

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.

11
  • Your edit makes no sense; the whole point about encrypting the data is to stop a third party (and in this case, you are a third party) bring able to read the message, and if you can't read the message, you can't do a search on it. (There is a very esoteric branch of cryptography called homomorphic encryption which might in theory let you do this, but it would be a major research breakthrough if you managed it; homomorphic encryption is about at the level of being able to add two small integers every second) Dec 21 '21 at 11:30
  • 1
    You are completely wrong with the thing being esoteric, Microsoft and Oracle provide solutions I was able to find out a bit later after posting docs.microsoft.com/en-us/sql/relational-databases/security/… oracle.com/technetwork/database/options/advanced-security/… These, however, are payed (and very expensive with their propriertary algos)
    – miqem
    Dec 21 '21 at 11:49
  • With all due respect, did you read the article you linked to? "TDE doesn't provide encryption across communication channels."; you are out of your depth here - stop digging. Dec 21 '21 at 11:52
  • 1
    @PhilipKendall: That's actually pretty impressive, considering when I last looked into FHE, it could do about 1 bit operation per hour :-D Dec 21 '21 at 11:59
  • 3
    Then there is no point in creating a full text search index on an encrypted central server. Your users simply need a full text search index on their local copy of their own decrypted data. Keep a search index for each user on their local device, behind the decrypted endpoint - problem solved.
    – Doc Brown
    Dec 21 '21 at 20:49
6

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.

2
  • Thank you for your input in a form of "You don't need X", but this is as far from a valueable answer in the set context as it can be.
    – miqem
    Dec 21 '21 at 10:33
  • @miqem: You asked a question with mutually incompatible constraints. It's impossible to provide a satisfactory answer to such questions, as any such answer will either be, "That's impossible" or, "Here's how to do it if we ignore an important part of the question." As written, your question isn't answerable. Consider asking a new question: Instead of stating that you wish to encrypt your database, list what thread models you intend to address. Possibly, but not necessarily, there is a way to address your specific security concerns without sacrificing server-side search.
    – Brian
    Jan 5 at 15:23
5

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.

4

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.

1

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.

2
  • I thank you for trying to provide the answer. I however, have to elaborate - a "messaging app" example is quite ill-fit, it was the first thing I could have thought of to make use of "encryption" and "full-text search". Now, speaking of leveraging the client itself to perform the searches - what if we are talking about data in orders of terrabytes? And the resulting indices for fts, - those would grow way larger than that. I don't think it's possible to offset this task to a client. So, any other suggestions?
    – miqem
    Dec 22 '21 at 7:32
  • 4
    @miqem: that's not the question you wrote, and by just inventing new unreasonable, invented requirements which don't really fit together to your idea of encryption and "each user has access to only their own data", you can invalidate almost any approach. You will be better off to describe a real problem you have, with real requirements and context to validate your wishes.
    – Doc Brown
    Dec 22 '21 at 7:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.