The database provider HIBP has 4 billion stolen passwords, and wishes to offer an API for websites to use during new-user signup (and password change) operations, so they can refuse to allow users to select a password that is known to have already been stolen.
HIBP is not trusted.
Does a way exist for a website to ask HIBP some question, and receive some result, that never allows HIBP to determine the password being inquired about (including against dictionary attacks) assuming that the password is NOT in the database.
Is the above possible, even if the password is in the database? e.g. can I check HIBP for existence of the string "password123", and get a result that I can understand means "yes, that exists", but which leaves HIBP with no way to know what string I queried, nor whether it was found?
This sounds like an interesting homomorphic challenge to me, but I don't know this field in depth.