How can I increase the complexity of a number and maintain uniqueness

Question

I have an 8-digit number and you have an 8-digit number - I want to see if our numbers are the same without either of us passing the other our actual number. Hashing the numbers is the obvious solution. However, if you send me your hashed number and I do not have it - it is very easy to hash all the permutations of an 8-digit number and see your number.

I am looking for a way to increase the complexity of the 8-digit number while maintaining uniqueness and a universal process (i.e. we need to be able to apply the same process on both ends.) Squaring the number or something like that will not work because there are the same number of unique squares of an 8 digit number as there are unique 8 digit permutations. Salting will not work for the same reason.

Is there anything I can do to the number to make brute-forcing all permutations not viable?

Answer 1

There are only $10^8$ eight digit numbers, even if you allow leading zeros. No deterministic operation can increase the entropy of this. Your example of squaring is a good one. It makes the number larger, but does not increase the number of results. You need more possible codes, either by adding digits or by having more digits as in allowing other characters.

One other approach is to make a very slow checking algorithm. If it takes an hour to check a code (and that is acceptable if somebody has the code), brute forcing would require a considerable investment in computing resources. One could still buy $10^4$ computers, set them running in parallel, and have the answer in a month and a half.

Answer 2

You will likely need to use a scheme with a trusted third party. Let the two parties be A and B, and the trusted third party be X.

1. A sends X its key K1 and gets back some sort of token T1. This token needs to have some small lifetime guarantees etc.
2. B sends X it’s key K2 and gets back another token T2.
3. A and B exchange tokens. Each sends {T1, T2} to X and X responds if they are identical.

Now the token provider X should provide tokens in such a way that the same key K will generate a different token whenever the request is made etc.

Answer 3

In Cryptography, There are two interesting problems;

1. Yao's Millionaires Problem: In which two millionaires want to know who is the reacher without revealing their riches to the other.
2. Socialist Millionaires : In which two millionaires want to know their wealth is equal or not without revealing their riches to the other.

You can think the first one as a secure $>$ and the second one as secure $=$

Therefore, the second one can compare the values without revealing the value.

Note 1: these problems are part of secure multi-party computation.

Note 2: You can also solve this by using SPAKE2. I've given a complete answer in Cryptography