What math makes it safe to offer a stolen-password check service? 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.
If we think of this as secure multi party computation then we want to calculate a function on two inputs the DB and the password. We want to know if the password exists. We don't want the db holder to learn anything about the password and the password holder to learn anything about the db beyond the answer to the question does the password exist. This is definitely solveable with generic secure multi party computation solutions. You had an extra requirement of the db holder not getting the answer to the question which I suspect may not be possible(it might be).
See: https://en.m.wikipedia.org/wiki/Secure_multi-party_computation