True/False if a user is a customer without revealing the actual customer

I have a user A and a third party company B. I want to check if A is a customer of B.

1. B cannot reveal any information about their customer list to me.
2. If A is a customer of B, I do not want B to know which customer they are. They should only know True/False answer to wether they are a customer.

What sort of problem is this? I thought this might be a private set intersection problem but the definition seems to violate my second condition. Is this instead a Zero Knowledge Proof problem?

"Private set intersection (PSI) allows two parties to compute the intersection of their sets without revealing any information about items that are not in the intersection."

• It would seem that what you really want is the cardinality of the private set intersection. You want to know is the intersection empty or non-empty. There are protocols out there for that. – mikeazo Sep 17 '18 at 19:30
• @mikeazo thanks for the help. I found this paper ics.uci.edu/~gts/paps/psi-ca.pdf would that be a good place to start? – Toby Sep 18 '18 at 15:09
• @mikeazo actually a bit of further reading seems like Kissner and Song might be a better starting point. people.eecs.berkeley.edu/~dawnsong/papers/set-int-full.pdf – Toby Sep 18 '18 at 16:05
• I assume that you also don't want to reveal the identity of A to B if they're not a customer. Because otherwise you could just ask B "hey, is A a customer of yours?" and have them reply yes/no. (Also, in practice, I'd be concerned about the possibility that you might just obtain a huge list of all potential customers you think B might have and query B for all of them. Such a list might not actually be as long or as hard to generate as you might think. Rate limits could help here.) – Ilmari Karonen Jan 9 '19 at 15:47

A 1-out-of-n Oblivious Transfer protocol would fit as a solution to your problem.

Oblivious Transfer can be viewed as an improved Private information retrieval protocol, because it allows that only exactly 1 item is retrieved from the database, without sharing any additional info about the database. In addition the "sharer" of the database ($$B$$) doesn't learn about which item ($$A$$) was retrieved.

If $$A$$ is not a customer of $$B$$ then $$B$$ should only return information in a way to make it clear to you that $$A$$ indeed is not a customer and not any information more should be disclosed by $$B$$.

Tung Chou and Claudio Orlandi have designed a relatively easy to understand 1-out-of-n OT-protocol, appropriately named The Simplest Protocol for Oblivious Transfer. The math used for this protocol is almost the same that is also used for Diffie-Hellman key exchange.

If you really want a computationally efficient protocol, then the OT-protocol designed by Moni Naor and Benny Pinkas (Computationally Secure Oblivious Transfer) is more appropriate.