Just off the top of my head: you can hash the text with hash-1, and send a query containing a hash id bucket computed with h1%(N/1000), get 1000 responses from the server hashed with h2 function. Then we can search for our h2 inside the 1000 results without the server knowing which one we were looking at. We also can't decode the 1000 responses we got.
One downside of a record-specific salt is nicknames e.g. john vs johnathan , or misspellings. (false negatives)