7
$\begingroup$

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."

Improve this question
$\endgroup$
4
  • 4
    $\begingroup$ 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. $\endgroup$
    – mikeazo
    Sep 17, 2018 at 19:30
  • $\begingroup$ @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? $\endgroup$
    – Toby
    Sep 18, 2018 at 15:09
  • $\begingroup$ @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 $\endgroup$
    – Toby
    Sep 18, 2018 at 16:05
  • $\begingroup$ 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.) $\endgroup$
    – Ilmari Karonen
    Jan 9, 2019 at 15:47

1 Answer 1

Reset to default
4
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.