Alice and Bob each secretly chooses an integer between 1 and 10, `a` and `b`. They want to know (with high probability) whether or not `a` equals `b`, without revealing any other information. Can they?



Zero knowledge proof of equality
In typical mathematician fashion, let me explain how to reduce your problem to a harder one ☺, namely homomorphic encryption. (**Edit**: I should have made it clear that the problem of constructing homomorphic encryption schemes, at least to the extent required here, is indeed solved.)


Assume Charlie is an "honest but curious" third party (i.e., Charlie can be trusted to perform computations honestly but should not be allowed to know $a$ or $b$): I hope it is not unreasonable to assume the existence of Charlie. Alice and Bob ask Charlie to set up a [homomorphic encryption](https://en.wikipedia.org/wiki/Homomorphic_encryption) scheme and give them the public key. Alice and Bob each encrypt their integer using this public key, and share the (encrypted) result, but don't give it to Charlie. They then use the homomorphic properties of the scheme to compute the (encrypted) value of the "if $a=b$ then $1$ else $0$" function (as a boolean function, this does not require a large number of bit multiplications, so the homomorphic properties required are not too difficult to obtain). Both can perform the computation. They send the result to Charlie for decryption, and Charlie can return the result. Thus, at the end, Alice, Bob and Charlie each know whether $a=b$ but not what the numbers are except those they themselves chose.


**Edit 2:** as per Pace Nielsen's comment, I should have clarified that this kind of encryption is non-determinististic: there isn't just one cyphertext for each of the values from 1 to 10, there are a huge number, and neither Alice nor Bob can decrypt the other's value by simply trying out all possibilities.


Of course, this leaves a lot of questions unanswered, like whether we can arrange for Charlie not to know whether $a=b$, or do without Charlie altogether (probably something can be done with functional encryption or homomorphic encryption with a secret key that is *split* between Alice and Bob, but there are usually lots of honesty assumptions that might not be obvious). Perhaps more insidiously, I don't know how to make sure that Alice does not select a number outside the allowed range (a number that would essentially return "no" to any comparison with a number honestly chosen by Bob).


