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 ?