3
$\begingroup$

Ok, I hope this question makes some sense because I am not so sure how to word it any differently… Imagine the following situation:

  • There are 10 defined colors (blue, orange, yellow etc.)
  • There are 2 Persons and each of them has 1 favorite, secrete color
  • The 2 persons don't know each other's favorite color, however, they want to know if they share the same

My question: How can they do a comparison without exposing their own favorite color to the other person (or to anyone else!) in case they do not match?

Or, to explain the problem with other words: Person A should only know the favorite color of Person B if they share the same. Hence, the result of the comparison must only be True or False.

My first thought was: Every person could simply create a hash of their favorite color using the same hash algorithm (MD5, SHA etc.) and then they can compare the hashes. But obviously, that doesn't work, because it’s easy to find out which hash belongs to which color.

Is there a solution for such a use case? Any help would be highly appreciated.

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ I think private set intersection should be what you are looking for. $\endgroup$
    – Maeher
    Apr 30, 2013 at 21:16
  • 2
    $\begingroup$ That's way more complicated that what's needed for his situation. $\hspace{2.2 in}$ See $\:$ en.wikipedia.org/wiki/Socialist_millionaire . $\;\;$ $\endgroup$
    – user991
    Apr 30, 2013 at 21:40
  • $\begingroup$ @RickyDemer, post that as the answer, because it's the answer. $\endgroup$
    – John Deters
    Apr 30, 2013 at 21:45

2 Answers 2

Reset to default
3
$\begingroup$

That sort of thing is known as multi-party computation, and you
should use a Socialist Millionaire Protocol for your particular instance.

Improve this answer
$\endgroup$
0
$\begingroup$

Comparing data sets can also be done using "order preserving Encryption" techniques

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ There is no order in a privacy preserving set intersection protocol. Only equality $\endgroup$
    – curious
    Jun 10, 2013 at 9:36
  • $\begingroup$ so this answer is wrong? $\endgroup$
    – Mike
    Jul 1, 2013 at 0:14

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.