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?
$\begingroup$
$\endgroup$
7
-
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$– mikeazoCommented Apr 25, 2016 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$– pg1989Commented Apr 25, 2016 at 22:17
-
$\begingroup$ mikeazo, you understand my problem exactly. $\endgroup$– Hakan ALTAŞCommented Apr 26, 2016 at 10:50
-
$\begingroup$ pg1989, This paper was very helpful. But, it is not easy to implement algorithm starting from it. $\endgroup$– Hakan ALTAŞCommented Apr 26, 2016 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 ShenCommented Apr 27, 2016 at 13:55
|
Show 2 more comments
2 Answers
$\begingroup$
$\endgroup$
2
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
-
$\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$ Commented Apr 26, 2016 at 11:00
-
$\begingroup$ what is practical for you? Why Chase and Shen is not practical? $\endgroup$– curiousCommented May 4, 2016 at 5:49
$\begingroup$
$\endgroup$
2
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.
-
1$\begingroup$ CryptDB doesn't do this, and its security is not well-understood. CryptDB is not the right tool for this problem. $\endgroup$– pg1989Commented Apr 25, 2016 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$ Commented Apr 26, 2016 at 11:06