In the FHE model, the assumption usually is - you have some data, someone else does some encrypted calculations, you get the encrypted answer back, you decrypt the answer and read it. The adversary cannot play 20 questions because they only calculate the encrypted answers, they are not allowed to see what the answers are.
Do you by chance have a simple way to explain how the search works then? Because superficially it seems like you might assume that you're looking for Enc(pk, m') == Enc(pk, m) and apparently that does not work.
Suppose Bob has an array of data he arranges into an mxn matrix, A. This data is not encrypted, but is encoded appropriately. Note that many FHE schemes allow you to compute ciphertext-plaintext operations.
Alice can send him 2 vectors x and y encrypted under her key, where x and y are all zero except for single 1. Bob homomorphically computes Ax = b. Since x is all zeros except for element i, the operation Ax effectively selects the ith column of A. Bob then computes dot(b, y). Since y is all zeros except for a 1 at element j, the dot product effectively selects the jth row of y. Bob sends the dot product back to Alice, which due to FHE is still encrypted under her key.
Alice decrypts the result and has looked up the j,ith element in A without Bob learning Alice's query or which data was involved in processing her search.
The default program on the Sunscreen[1] compiler playground shows this exact algorithm.
Disclaimer: I am an employee of Sunscreen.
With a symmetric cipher, I could figure out the blood type of every employee pretty easily. With an asymmetric cipher, I could figure out everyone who has my blood type, and the blood types of anyone who reveals that information.
If the point is to filter data when you aren’t allowed to know what the data is, then the act of being in the filter or not reveals some of that information. It’s just a game of twenty questions.