7
$\begingroup$

I want to search substrings in encrypted string. To do that I have read “Implement Rabin-Karp Algorithm” and “Substring-Searchable Symmetric Encryption”. After that, I completed the Rabin-Karp implementation. But, those does not answer for my problem. Rabin-Karp requires both main string for searching substrings and substring to be searched. What I want to do is finding patterns in encrypted strings without decrypt it?

$\endgroup$
  • 1
    $\begingroup$ Let me make sure I understand, you want to be able to encrypt a string, send it to some untrusted 3rd party. That 3rd party should be able to find patterns in the encrypted strings without the decryption key? Are these patterns supplied by the user? $\endgroup$ – mikeazo Apr 25 '16 at 11:39
  • $\begingroup$ I don't understand what exactly you want. The second paper you linked by Chase and Shen is pretty much the state of the art in this area, so you might want to just do that. $\endgroup$ – pg1989 Apr 25 '16 at 22:17
  • $\begingroup$ mikeazo, you understand my problem exactly. $\endgroup$ – Hakan ALTAŞ Apr 26 '16 at 10:50
  • $\begingroup$ pg1989, This paper was very helpful. But, it is not easy to implement algorithm starting from it. $\endgroup$ – Hakan ALTAŞ Apr 26 '16 at 10:57
  • $\begingroup$ My layman's question: Could your goal be exactly realizable at all for materials that are encrypted by sufficiently strong algorithms? (Do I understand correctly that you want to have a way to check whether a possible string guessed from context, say "Execute Plan B!", is in the plaintext corresponding to a given ciphertext?) $\endgroup$ – Mok-Kong Shen Apr 27 '16 at 13:55
5
$\begingroup$

There are some works both theoretical and practical that they do solve your problem efficiently and in a secure way. By efficiently i mean the search efficiency is linear on the size of the searched substring. This is achieved by using auxiliary data structures known as suffix tree. Chase and Shen follow this approach, by encrypting the suffix tree with symmetric primitives.

This work does not use any auxiliary data structure for efficiency. It encrypts consecutive n-grams and their positions.

A theoretical work follows another technique. By altering the subset sum problem to be easily solvable they issue subset sum instances to the cloud, and the cloud solves them polynomially and the solutions are the positions in the original string of the substring.

Stronger security guarantees with oblivious ram are presented here

| improve this answer | |
$\endgroup$
  • $\begingroup$ I am looking for practical solutions for this job. But, I have not come across any of them yet. This article and work does not include what i seek. $\endgroup$ – Hakan ALTAŞ Apr 26 '16 at 11:00
  • $\begingroup$ what is practical for you? Why Chase and Shen is not practical? $\endgroup$ – curious May 4 '16 at 5:49
4
$\begingroup$

I am afraid you are a little early: searchable encryption is quite a new field in cryptography, and I am not sure there exists any good implementation yet. However, answers to this question suggest cryptdb.

Also, I do not think the Rabin-Karp Algorithm is easily transposable to searchable encryption. I believe it has many optimisations, which could conflict with the internal workings of the encryption schemes. I'm not saying it is impossible, though.

| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ CryptDB doesn't do this, and its security is not well-understood. CryptDB is not the right tool for this problem. $\endgroup$ – pg1989 Apr 25 '16 at 22:16
  • $\begingroup$ I have read many articles about CryptDB. It does not support substring operations as mentioned here. CryptDB does not support queries on certain sensitive fields that perform string manipulation (e.g., substring and lowercase conversions) or date manipulation (e.g., obtaining the day, month, or year of an encrypted date). However, if these functions were precomputed with the result added as standalone columns (e.g., each of the three parts of a date were encrypted separately), CryptDB would support these queries. $\endgroup$ – Hakan ALTAŞ Apr 26 '16 at 11:06

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.