Well, maybe you were on to something-- your thoughts inspired me to think about this a little more- we just need a unique salt only the user would know.

still, bcrypt's design means it'll take way too many cycles to brute-force-reverse the dataset, so it should be safe to share.

One downside of a record-specific salt is nicknames e.g. john vs johnathan , or misspellings. (false negatives)

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.

This is basically how HIBP's Pwned Password API works:

https://www.troyhunt.com/were-baking-have-i-been-pwned-into-...

https://haveibeenpwned.com/API/v2#PwnedPasswords

https://www.troyhunt.com/introducing-306-million-freely-down...

https://www.troyhunt.com/ive-just-launched-pwned-passwords-v...