1

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 both numbers and compare these encrypted messages. In this case, it is still, in theory, possible to compute/to guess the other secret number (even if is very improbable).

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

Honza
  • 11
  • 1
  • This is partly the basis for symmetric cryptography. This may be a better question on http://crypto.stackexchange.com/ but in short, you can use this method and to reduce the chances of someone *reversing the algorithm* you can use large numbers (usually primes). – HashHazard Sep 21 '16 at 13:42
  • 1
    How large are the space of possible secret number? If it is large, you can just hash the numbers and compare the hash. However, if the only possible numbers are 1, 2 and 3 it is not a very good option... – Anders Sep 21 '16 at 14:02
  • @Anders - indeed, since the format is known (ie, number of decimal places, rounding, etc) it could be brute forced. Even SHA512, you have to assume they can do, say, a million a second, meaning that the numbers in question would have to be extraordinarily big - if these are bids, for instance, this method is right out. – crovers Sep 21 '16 at 14:27
  • @Honza This is likely a better question for http://crypto.stackexchange.com/ - but I believe this could be solved with https://en.wikipedia.org/wiki/Yao%27s_Millionaires%27_Problem - more details, including an algorithm here : https://www.cerias.purdue.edu/assets/pdf/bibtex_archive/2003-39.pdf – crovers Sep 21 '16 at 14:31
  • Thank you for your comments. The set of possible numbers is very limited and thus it is possible to try to encrypt/hash all possibilities and check which one is the secret number. I'll ask http://crypto.stackexchange.com - thanks for suggestion! – Honza Sep 23 '16 at 08:13

1 Answers1

1

There is no need to encrypt anything in this use case. Hashing with a non invertible algorithm is enough. In order to avoid to give a constant hash, you could imagine a challenge protocol:

  • each part builds (separately) a random string and sends it to the other
  • each part concatenates the received random string with its own secret, computes a strong hash (sha512 is generally considered as strong enough)
  • each part concatenates the produced random string with it own secret and computes the hash
  • each part sends to the other the hash produced with the other's random string

If the secrets were identical, the hashes should compare equal. If they are not, no part can guess the secret from its peer because only non invertible hashes of one time messages have been exchanged. Even if a man in the middle could intercept the messages, he could neither guess the secret, nor pretend to know it later because of the random part

Serge Ballesta
  • 25,636
  • 4
  • 42
  • 84
  • Smart sollution! Do you know if this has a name? – Anders Sep 21 '16 at 15:45
  • 1
    Honnestly, I do not know. It can be seen as a symetric derivative of [CHAP](https://en.wikipedia.org/wiki/Challenge-Handshake_Authentication_Protocol). – Serge Ballesta Sep 21 '16 at 15:57
  • Thanks for suggestion. Nevertheless, I'm not sure how the random appendix improves the overall security when this suffix is publicly known. It seems to me that this is equivalent to just exchange the hashes. – Honza Sep 23 '16 at 08:17
  • @Honza: The random appendix is never re-used. Suppose you directly exchange the hashes. If someone pretends to know the secret, you will give him a hash of the secret. Ok, as it has not given it to you that time, you will not trust him. But on next attempt he will know the hash and will be able to present it. The random appendix mitigates that risk because on next attempt the hash would be different. – Serge Ballesta Sep 23 '16 at 08:51