paradox on fully homomorphic equality checking Imagine, a client encrypts a corpus of data (say documents of text) with the public key of a Fully Homomorphic Encryption scheme (FHE) and outsources the data to an untrusted server.Now the client wants search for a particular word in the corpus of encrypted documents and retrieve the matching documents that contain the word as a result. So the client could encrypt the search word with public key of FHE scheme and send to the server. The server would evaluate a "equality circuit" for blind folded matching using Evaluate method of FHE scheme. Remember the result (in this case it is MATCH or NO MATCH) also is encrypted in FHE schemes and hidden from the untrusted server. 

Now my paradox begins, 
Does this mean server does not know whether the string matches the document ? 


If the server does not know how will it retrieve and send those matching documents alone ?
If the server knows whether the string matches or not in this particular case  will such FHE scheme considered secure at all ? 
Is this situation any better if the FHE scheme is probabilistic or deterministic ? 


On a side note, the above need not be for a word (as in words of a text) equality checking, the same argument could be given for numerical equality checking (arithmetic circuits) as well. Any comments on this paradox ?
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 ${\cal X}=X_1,\ldots,X_n$ the documents, and assume that there exist lists ${\cal L}=L_1,\ldots,L_n$ such that $L_i$ is the list of keywords in $X_i$. (This is just to simplify the explanation.) Then, let $f(a,L_i)=1$ if $a$ is in the list $L_i$, and otherwise $f(a,L_i)=0$. Clearly, $f$ can be computed inside FHE. Then, the server can compute the function $g(a,{\cal X},{\cal L})=\sum_{i=1}^n f(a,L_i) \cdot X_i$ inside FHE and return the result to the client. Since we are guaranteed that only one document matches, we have that $f(a,L_i)$ will equal 0 in all but one place. Thus, if $a\in L_j$, then the result will be $X_j$ only.

In order to extend this to the general case where an upper bound $t$ is given on the number of matches, the following can be done. Define $f_m(a,i,{\cal L})$ to be a function so that $f_m(a,i,{\cal L})=1$ if $L_i$ is the $m$th list $(1\leq m\leq t)$ in ${\cal L}$ containing $a$, and otherwise equals 0. Then, define $g_m(a,{\cal X},{\cal L})=\sum_{i=1}^n f_m(a,L_i) \cdot X_i$. Finally, the server computes and returns to the client the (encrypted) values $g_1(a,{\cal X},{\cal L})$, $g_2(a,{\cal X},{\cal L})$, up to $g_t(a,{\cal X},{\cal L})$.

In this way, the communication is just $t$ ciphertexts, and thus not everything needs to be returned.

Note that if you don't have any upper bound on the number of responses, then you can't do this, and you end up sending everything. In order to solve this, the client can first send an encryption of $a$ to the server, who then computes a function that just returns the number of lists that $a$ appears in. The client can then decrypt and send this to the server who continues as above. This does require interaction, but solves the problem of knowing a reasonable upper bound on the size of the output.