10

Yes. If you encrypt the documents with this purpose in mind (you have to use a special kind of encryption algorithm), then yes, it is possible to do this, for certain kinds of search queries. There is a rich research literature on this topic. The buzzword is "search on encrypted data". I'll point you to a few sample papers in this space. Do a literature ...


6

This is somewhat a paradox. It seems that if the server cannot know when equality is reached, how can it return only those documents. Surprisingly, it can be done, under the assumption that an upper bound is given on the number of documents (and at the cost of that upper bound). Assume first that only one document matches, and this is known. Denote by ${\...


5

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 ...


4

It is mainly to make the search operation more efficient. In searchable encryption, mostly invert index is used. It is a data structure that stores mapping from words to documents or set of documents i.e. directs you from word to document, e.g. something like: word 1: {doc1, doc2, doc3} word 2: {doc1, doc3} word 2: {doc1} The earliest ...


4

If you only use the group in a black-box way (meaning, if you wish to rely on the discrete logarithm problem on an arbitrary group), we do not know of any encryption scheme (searchable or not) whose IND-CPA security reduces to the discrete logarithm problem. What we can do from the discrete logarithm problem directly is quite limited. In particular: you can ...


4

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 ...


4

I think the keyword equality can be done with FHE, but, as you pointed out, the server will not know the result of the test since it will be encrypted. Considering this, the answer to your question "Does this mean server does not know whether the string matches the document?" should be yes, it does. The server does not know whether a match occurs or not. ...


3

The condition $\tau(\mathbf{D}_{0}, w_{0,1},\ldots,w_{0,q})=\tau(\mathbf{D}_{1}, w_{1,1},\ldots,w_{1,q})$ rules out the possibility that $\mathcal{A}$ issues the keywords as I pointed in the question, since the output of $\tau$ includes the search pattern matrix defined in page 9. This has the effect of weakening the definition to allow search pattern ...


3

Searchable encryption is a form of encryption where you can search for ciphertexts whose decryption satisfying some condition without decrypting those ciphertexts and looking at the decryption. The end result is typically a collection of ciphertexts. Sometimes a secret key is needed to create a "search token" for a given query. Searchable encryption for ...


3

$\mathcal{M}$ is the domain of the inverse trapdoor permutation $\pi^{-1}$. For example, if $\pi^{-1}(m)= m^d \bmod N$ implemented using RSA, then $\mathcal{M}=Z^*_N$. The domain/range of $\pi$ and $\pi^{-1}$ are all $\mathcal{M}=Z^*_N$. Generate a random big integer in $Z^*_N$ (roughly from range 1 to $N$) should be fine (there is a negligible probability ...


1

Answering my own question. I believe it is possible. We can use the scheme by Boneh et al. described here. It uses pairing-based cryptography to be able to create a searchable, asymmetric, tagging scheme. In this scheme, queries are made through a trapdoor of the real key that we want to search, making it impossible for the set holder to retrieve ...


1

If you encrypt the words with the ECB mode then it will reveal information which we call frequency attack. The attacker can see which words are repeating among the rows and try to extract information especially if the attackers have some knowledge of the data contained in the database. We can see this in a small SEARCH column if encrypted with ECB mode; | ...


1

Query with SELECT AES with ECB mode can be used as long as the vouchers codes are unique. ECB mode gives you the same results when the key and plaintext are same. Another solution is continuing to use AES-GCM to save your vouchers codes. To have the equality on the SELECT statement, use a secure hash function e.g. choose from the SHA3 family. With ...


1

Yes, the client needs to figure out which of the results are actually relevant. For obfuscation reasons the server returns irrelevant documents and also cannot know which documents are irrelevant so the client has to make that distinction.


1

Comparision is not possible between Searchable Symmetric Encryption (SSE) and Deterministic Encryption (DE). The reason is given below: DE is an encryption scheme with the property that it always generates the same ciphertext for the same message. Hence, this is more prone to Guessing Attacks. Examples of DE are Unpadded RSA, AES with ECB mode, and Order ...


1

ORAM can be built on a multi-party scenario, where the data belongs to various parties using Secure Multiparty Computation. Recent research calls this approach ORAM for Secure Computation (SC-ORAM). Given that writing and reading are required, it is my believe this would be the best approach. In the typical SC-ORAM setting, several parties store ...


1

Additional Storage approach A trivial way is with additional storage. by making the $l$ to be complete string instead of few $left$ bits shown in the figure above. so technically $|l|=|n|$ and $|m| = 0$. This way the entire string is covered for search. Now rest of the scheme is same except that the stream cipher bits $S_i$ in the figure above are $\oplus$...


Only top voted, non community-wiki answers of a minimum length are eligible