It's always nice to see when some new field has managed not to experience every single classic blunder firsthand to learn not to do that. So there is something akin to a salt in the data that keeps identical records from being searchable, that's good to know.
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.
By search, I assume you mean how would you do a database search with FHE referred to in the article. A simple example of private information retrieval is as follows:
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.
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.