I'm solving a theoretical problem with two entities, each having one secret number. They need to find out whether these number equal without disclosing their number when they differ.

Easy solution is to encrypt/hash both numbers and compare these encrypted messages/hashes. In this case, it is still, in theory, possible to compute/to guess the other secret number (even if is very improbable). For example when there is very limited number of possible secret numbers.

Is there any protocol that is 'totally safe' - meaning that an entity cannot guess the other secret number regardless of its computation power?

  • $\begingroup$ This paper may help, there is an equality test in there: eprint.iacr.org/2015/634.pdf $\endgroup$ – user153465 Sep 23 '16 at 9:10
  • $\begingroup$ usenix.org/system/files/conference/usenixsecurity14/… $\endgroup$ – user153465 Sep 23 '16 at 9:11
  • $\begingroup$ Thanks for these interesting articles! Nevertheless, I'm still not sure whether ideal PSI (how they define it) exists except for the case with trusted third party. Which of the cases is ideal even in the case when entities can factor large numbers or even have access to infinite computation power? $\endgroup$ – Honza Sep 23 '16 at 14:10
  • 2
    $\begingroup$ The problem you're facing is also called the "socialist millionaires' problem". $\endgroup$ – SEJPM Sep 23 '16 at 19:55

Equality of single bits is the XNOR function. There is no unconditionally secure protocol for XNOR in the presence of malicious adversaries. We prove this in:

HK Maji, M Prabhakaran, M Rosulek: Complexity of Multiparty Computation Problems: The Case of 2-Party Symmetric Secure Function Evaluation, TCC 2009.

There is a simple protocol secure against semi-honest adversaries, but keep in mind that if you know your input bit, you know whether your bit is equal to the other guy's bit, then you know the other guy's bit. So the secure protocol is "just tell the other guy your input."

On the other hand, equality of strings 2 bits or longer does not even have a protocol secure against semi-honest adversaries. This follows from an old characterization of Kushilevitz: the function is not "decomposable".

E Kushilevitz: Privacy and Communication Complexity. FOCS 1989

You can get equality test if you assume an ideal oblivious transfer. This is not unreasonable since you can get oblivious transfer from physical assumptions (like noisy channels). The private equality test described in this paper is pretty straight-forward, and unconditionally secure against semi-honest adversaries assuming an ideal oblivious transfer:

B Pinkas, T Schneider, M Zohner: Faster Private Set Intersection Based on OT Extension, Usenix 2014


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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