4

If I use rot13 crypto I still can do text search. For example:

Query:           John
Encrypted Query: WBUA

Database Entries: John Smith => WBUA FZVGU
                  Jon Babe   => WBA ONOR

Result: WBUA matches WBUA FZVGU

Are there more secure crypto methods (for example with a secure key), with that I also can do textsearch?

Thanks

1
  • not yet really, but it's a field of ongoing research.
    – dandavis
    Sep 10, 2016 at 17:40

3 Answers 3

3

No, this is not possible with secure encryption. The reason is really simple.

What you do requires that you are able to create the cypher text ξ(λ) of a small piece of plain text λ and then can find that cypher text everywhere where λ occurs in a bigger piece of plain text Λ.

When people do crypto, they attempt to reach so-called protection goals. One of them usually is that an outside observer cannot figure out whether the same piece of text occurs twice in the same message or even whether 2 messages stem from the same plain text. Therefore, ξ(Λ) is not guaranteed to contain ξ(λ) and finding ξ(λ) in ξ(Λ) doesn't tell you anything because it can show up anywhere.

7
  • Thanks @UTF-8, do you know another insecure encryption method? That protects the data a little bit better than rot13?
    – John Smith
    Sep 10, 2016 at 13:35
  • There are plenty of insecure encryption methods but I suppose you're asking for one which is easily searchable. rot13 is merely one of the so-called Caesar ciphers. You can rotate by any different number ∈ {1, ..., 25} as well. rot13 is the one best known, though. The other Caesar ciphers also share the property of being searchable. If what you're searching for is very short, the Vigenère cipher is searchable as well but you have to try different possible ξ(λ). The Vigenère cipher has been thought to be secure for centuries. You can see how it gets harder when better crypto is used.
    – UTF-8
    Sep 10, 2016 at 14:30
  • @Acapulco by now has posted their answer linking to a Wikipedia article describing that this is a problem for which a solution is hard to find. For simply the purpose of searching through text, it's probably best to just encrypt it and search for the text once you got the plain text. Note that this can usually be done without decrypting everything first. Instead, a part can be decrypted and searched while the rest is still being decrypted. This not only can give you the first results soon but also means that you don't need to write all the plain text data onto a storage medium first.
    – UTF-8
    Sep 10, 2016 at 14:34
  • @JohnSmith To be clear, Vigenere was indeed thought secure for centuries, but it has now been known broken for a century and a half, so it is not actuallly secure. Sep 11, 2016 at 12:09
  • @dave_thompson_085 And when I first heard of it in the first lecture of a university course about security, the professor said in advance that it was thought to be secure for centuries and before he could explain how it worked (the slide was already visible), pretty much every single person in the room broke out in laughter, not believing that people could be dumb enough not to instantly see how easy it is to break the Vigenère cipher.
    – UTF-8
    Sep 11, 2016 at 14:11
3

I believe the technique you are looking for is called Fully homomorphic encryption

Such a system lets you use encrypted inputs to do arbitrary operations on encrypted data while returning an encrypted output.

The current problem is that operations on FHE systems are terribly slow.

1
  • 1
    An other problem with FHE systems is that the fundamental operations they support aren't typically the search operation, so you'd have to implement that using the other operations which means that a simple text search becomes a sequence of a lot of other operations, each of these is terribly slow.
    – Bakuriu
    Sep 14, 2016 at 13:34
3

An alternative could be to use a search index (inverted index).

Index the data before encryption. Then encrypt the index.

You have to decrypt the index before performing the search, but the index could be much smaller than the data. Also, depending on the index technique, only parts of the index may need to be decrypted.

(This approach may not be efficient if the text in the database is frequently updated.)

Sample index (abstraction):

Word    Record#
----    --------
anders  245,354
babe    181
bill    133,354
david   201,245
john    139
jon     181,310
niven   201
smith   133,139,310
2
  • Thanks for your answer! What encryption algorithm should I use? Thanks
    – John Smith
    Sep 13, 2016 at 21:10
  • I don't know. It partly depends on the chosen indexing technique. I suspect one alternative could be to have the index in a small db in an encrypted directory. While the db manager reads and writes disk blocks the cryptfilesystem will encrypt and decrypt the blocks. The db access would be in clear text. That way the encryption keys are kept in a well tested component near the os, and not in your application. (I am not versed to recommend a particular directory level filesystem encryption or a database manager. I guess any would do.) Sep 14, 2016 at 8:06

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .