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?


1 Answer 1


Sure they can, it's called the socialist millionaires problem. The most common solution is to use Yao's protocol: Alice sends a garbled circuit of the equality function to Bob, and then Alice use oblivious transfers to send the keys necessary for the evaluation of the circuit to Bob. Another option is to rely on additively homomorphic IND-CPA encryption: Alice sends an encryption $E(a)$ of her input $a$, Bob computes $E(r\cdot (a-b))$ from this ciphertext, using his input $b$ and a uniformly random value (over the plaintext space of the scheme) $r$. Alice decrypts and outputs yes if the result is 0, and no otherwise. As the scheme is IND-CPA, Bob learns nothing on Alice's input (the protocol is therefore computationally private for Alice); because of the random coin $r$, the decrypted value statistically masks $b$ when $a \neq b$ (the protocol is therefore statistically private for Bob).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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