Alice's forgetful banking Alice has a bank account number, but has forgotten which bank it is for. There are 4 banks, run by Bob, Carlos, David, and Eve.

She could find out by going to all of the banks and asking if they have the account number. However, if Eve learns Alice's account number, then Eve will go to Alice's actual bank and steal all of Alice's money.

Alice could hash the bank account number, and ask about the hash, but since the account number is only 8 digits, Eve could bruteforce the hash anyway. Then, Eve will go to Alice's bank and steal all of her money.

Alice could use a Zero Knowledge Proving Protocol, but how would the bank know which account number to check against without repeating the ZKPP for every account number? Each of them has thousands of customers.

Context: I'm writing a program to retrieve an encrypted copy of one's keys and friends-list for a project called Tox (http://wiki.tox.im/index.php/Proposal:Friendslist_Server). I'd like to make it automatically detect which server has it.
Private Set Intersection

How about a private set intersection protocol?

The banks input is a set of all of their account numbers, the user's input is their account number (a single member set). The output could be given to the user, or the bank, or both, depending on your needs.

You would need a way to protect against guessing account numbers. For example, I could just keep submitting account numbers to one of the banks until I find a valid account at that bank. Or, the bank could put tons, and tons of accounts in their set that they don't actually own with the hopes that your account number will be in there and they can figure out your account.

Both would be fairly easy to protect against if the account numbers are fairly large (say 256 bits) and randomly generated. The probability of success would be greatly limited. You could further limit the bank from submitting overly large sets as I think the size of the set is probably not kept hidden.

Another possibility

Another possibility would be to develop a multiparty set intersection protocol using multiparty computation. Use the paper I linked to as a basis (it only supports 2 parties). That way all parties participate in the protocol at the same time. An MPC framework such as VIFF will be helpful.

The idea is that all banks would input their account databases, the user would input their account number, and you find which set contains the account number and return to the user the ID of that bank. If 2 banks are found to have that account, someone likely falsifying accounts and return $\bot$.